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"
36 #include "diagnostic-core.h"
40 #include "sparseset.h"
43 /* The code in this file is similar to one in global but the code
44 works on the allocno basis and creates live ranges instead of
45 pseudo-register conflicts. */
47 /* Program points are enumerated by numbers from range
48 0..IRA_MAX_POINT-1. There are approximately two times more program
49 points than insns. Program points are places in the program where
50 liveness info can be changed. In most general case (there are more
51 complicated cases too) some program points correspond to places
52 where input operand dies and other ones correspond to places where
53 output operands are born. */
56 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
57 live ranges with given start/finish point. */
58 live_range_t
*ira_start_point_ranges
, *ira_finish_point_ranges
;
60 /* Number of the current program point. */
61 static int curr_point
;
63 /* Point where register pressure excess started or -1 if there is no
64 register pressure excess. Excess pressure for a register class at
65 some point means that there are more allocnos of given register
66 class living at the point than number of hard-registers of the
67 class available for the allocation. It is defined only for cover
69 static int high_pressure_start_point
[N_REG_CLASSES
];
71 /* Objects live at current point in the scan. */
72 static sparseset objects_live
;
74 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
76 static sparseset allocnos_processed
;
78 /* Set of hard regs (except eliminable ones) currently live. */
79 static HARD_REG_SET hard_regs_live
;
81 /* The loop tree node corresponding to the current basic block. */
82 static ira_loop_tree_node_t curr_bb_node
;
84 /* The number of the last processed call. */
85 static int last_call_num
;
86 /* The number of last call at which given allocno was saved. */
87 static int *allocno_saved_at_call
;
89 /* Record the birth of hard register REGNO, updating hard_regs_live and
90 hard reg conflict information for living allocnos. */
92 make_hard_regno_born (int regno
)
96 SET_HARD_REG_BIT (hard_regs_live
, regno
);
97 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
99 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
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
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
);
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. */
133 update_allocno_pressure_excess_length (ira_object_t obj
)
135 ira_allocno_t a
= OBJECT_ALLOCNO (obj
);
137 enum reg_class cover_class
, cl
;
140 cover_class
= ALLOCNO_COVER_CLASS (a
);
142 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
145 if (high_pressure_start_point
[cl
] < 0)
147 p
= OBJECT_LIVE_RANGES (obj
);
148 ira_assert (p
!= NULL
);
149 start
= (high_pressure_start_point
[cl
] > p
->start
150 ? high_pressure_start_point
[cl
] : p
->start
);
151 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
155 /* Process the death of object OBJ, which is associated with allocno
156 A. This finishes the current live range for it. */
158 make_object_dead (ira_object_t obj
)
162 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
163 lr
= OBJECT_LIVE_RANGES (obj
);
164 ira_assert (lr
!= NULL
);
165 lr
->finish
= curr_point
;
166 update_allocno_pressure_excess_length (obj
);
169 /* The current register pressures for each cover class for the current
171 static int curr_reg_pressure
[N_REG_CLASSES
];
173 /* Record that register pressure for COVER_CLASS increased by N
174 registers. Update the current register pressure, maximal register
175 pressure for the current BB and the start point of the register
178 inc_register_pressure (enum reg_class cover_class
, int n
)
184 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
187 curr_reg_pressure
[cl
] += n
;
188 if (high_pressure_start_point
[cl
] < 0
189 && (curr_reg_pressure
[cl
] > ira_available_class_regs
[cl
]))
190 high_pressure_start_point
[cl
] = curr_point
;
191 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
192 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
196 /* Record that register pressure for COVER_CLASS has decreased by
197 NREGS registers; update current register pressure, start point of
198 the register pressure excess, and register pressure excess length
199 for living allocnos. */
202 dec_register_pressure (enum reg_class cover_class
, int nregs
)
210 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
213 curr_reg_pressure
[cl
] -= nregs
;
214 ira_assert (curr_reg_pressure
[cl
] >= 0);
215 if (high_pressure_start_point
[cl
] >= 0
216 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
221 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, j
)
222 update_allocno_pressure_excess_length (ira_object_id_map
[j
]);
224 (cl
= ira_reg_class_super_classes
[cover_class
][i
])
227 if (high_pressure_start_point
[cl
] >= 0
228 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
229 high_pressure_start_point
[cl
] = -1;
233 /* Mark the pseudo register REGNO as live. Update all information about
234 live ranges and register pressure. */
236 mark_pseudo_regno_live (int regno
)
238 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
245 /* Invalidate because it is referenced. */
246 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
248 n
= ALLOCNO_NUM_OBJECTS (a
);
249 cl
= ALLOCNO_COVER_CLASS (a
);
250 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
253 /* We track every subobject separately. */
254 gcc_assert (nregs
== n
);
258 for (i
= 0; i
< n
; i
++)
260 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
261 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
264 inc_register_pressure (cl
, nregs
);
265 make_object_born (obj
);
269 /* Like mark_pseudo_regno_live, but try to only mark one subword of
270 the pseudo as live. SUBWORD indicates which; a value of 0
271 indicates the low part. */
273 mark_pseudo_regno_subword_live (int regno
, int subword
)
275 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
283 /* Invalidate because it is referenced. */
284 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
286 n
= ALLOCNO_NUM_OBJECTS (a
);
289 mark_pseudo_regno_live (regno
);
293 cl
= ALLOCNO_COVER_CLASS (a
);
294 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
295 gcc_assert (nregs
== n
);
296 obj
= ALLOCNO_OBJECT (a
, subword
);
298 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
301 inc_register_pressure (cl
, nregs
);
302 make_object_born (obj
);
305 /* Mark the register REG as live. Store a 1 in hard_regs_live for
306 this register, record how many consecutive hardware registers it
309 mark_hard_reg_live (rtx reg
)
311 int regno
= REGNO (reg
);
313 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
315 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
319 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
320 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
322 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
323 inc_register_pressure (cover_class
, 1);
324 make_hard_regno_born (regno
);
331 /* Mark the register referenced by use or def REF as live. */
333 mark_ref_live (df_ref ref
)
335 rtx reg
= DF_REF_REG (ref
);
338 if (GET_CODE (reg
) == SUBREG
)
339 reg
= SUBREG_REG (reg
);
341 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
343 if (df_read_modify_subreg_p (orig_reg
))
345 mark_pseudo_regno_subword_live (REGNO (reg
),
346 subreg_lowpart_p (orig_reg
) ? 0 : 1);
349 mark_pseudo_regno_live (REGNO (reg
));
352 mark_hard_reg_live (reg
);
355 /* Mark the pseudo register REGNO as dead. Update all information about
356 live ranges and register pressure. */
358 mark_pseudo_regno_dead (int regno
)
360 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
367 /* Invalidate because it is referenced. */
368 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
370 n
= ALLOCNO_NUM_OBJECTS (a
);
371 cl
= ALLOCNO_COVER_CLASS (a
);
372 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
375 /* We track every subobject separately. */
376 gcc_assert (nregs
== n
);
379 for (i
= 0; i
< n
; i
++)
381 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
382 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
385 dec_register_pressure (cl
, nregs
);
386 make_object_dead (obj
);
390 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
391 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
393 mark_pseudo_regno_subword_dead (int regno
, int subword
)
395 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
403 /* Invalidate because it is referenced. */
404 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
406 n
= ALLOCNO_NUM_OBJECTS (a
);
408 /* The allocno as a whole doesn't die in this case. */
411 cl
= ALLOCNO_COVER_CLASS (a
);
412 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
413 gcc_assert (nregs
== n
);
415 obj
= ALLOCNO_OBJECT (a
, subword
);
416 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
419 dec_register_pressure (cl
, 1);
420 make_object_dead (obj
);
423 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the
426 mark_hard_reg_dead (rtx reg
)
428 int regno
= REGNO (reg
);
430 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
432 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
436 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
438 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
439 dec_register_pressure (cover_class
, 1);
440 make_hard_regno_dead (regno
);
447 /* Mark the register referenced by definition DEF as dead, if the
448 definition is a total one. */
450 mark_ref_dead (df_ref def
)
452 rtx reg
= DF_REF_REG (def
);
455 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
458 if (GET_CODE (reg
) == SUBREG
)
459 reg
= SUBREG_REG (reg
);
461 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
462 && (GET_CODE (orig_reg
) != SUBREG
463 || REGNO (reg
) < FIRST_PSEUDO_REGISTER
464 || !df_read_modify_subreg_p (orig_reg
)))
467 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
469 if (df_read_modify_subreg_p (orig_reg
))
471 mark_pseudo_regno_subword_dead (REGNO (reg
),
472 subreg_lowpart_p (orig_reg
) ? 0 : 1);
475 mark_pseudo_regno_dead (REGNO (reg
));
478 mark_hard_reg_dead (reg
);
481 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
482 class is intersected with class CL. Advance the current program
483 point before making the conflict if ADVANCE_P. Return TRUE if we
484 will need to advance the current program point. */
486 make_pseudo_conflict (rtx reg
, enum reg_class cl
, rtx dreg
, bool advance_p
)
490 if (GET_CODE (reg
) == SUBREG
)
491 reg
= SUBREG_REG (reg
);
493 if (! REG_P (reg
) || REGNO (reg
) < FIRST_PSEUDO_REGISTER
)
496 a
= ira_curr_regno_allocno_map
[REGNO (reg
)];
497 if (! reg_classes_intersect_p (cl
, ALLOCNO_COVER_CLASS (a
)))
503 mark_pseudo_regno_live (REGNO (reg
));
504 mark_pseudo_regno_live (REGNO (dreg
));
505 mark_pseudo_regno_dead (REGNO (reg
));
506 mark_pseudo_regno_dead (REGNO (dreg
));
511 /* Check and make if necessary conflicts for pseudo DREG of class
512 DEF_CL of the current insn with input operand USE of class USE_CL.
513 Advance the current program point before making the conflict if
514 ADVANCE_P. Return TRUE if we will need to advance the current
517 check_and_make_def_use_conflict (rtx dreg
, enum reg_class def_cl
,
518 int use
, enum reg_class use_cl
,
521 if (! reg_classes_intersect_p (def_cl
, use_cl
))
524 advance_p
= make_pseudo_conflict (recog_data
.operand
[use
],
525 use_cl
, dreg
, advance_p
);
526 /* Reload may end up swapping commutative operands, so you
527 have to take both orderings into account. The
528 constraints for the two operands can be completely
529 different. (Indeed, if the constraints for the two
530 operands are the same for all alternatives, there's no
531 point marking them as commutative.) */
532 if (use
< recog_data
.n_operands
- 1
533 && recog_data
.constraints
[use
][0] == '%')
535 = make_pseudo_conflict (recog_data
.operand
[use
+ 1],
536 use_cl
, dreg
, advance_p
);
538 && recog_data
.constraints
[use
- 1][0] == '%')
540 = make_pseudo_conflict (recog_data
.operand
[use
- 1],
541 use_cl
, dreg
, advance_p
);
545 /* Check and make if necessary conflicts for definition DEF of class
546 DEF_CL of the current insn with input operands. Process only
547 constraints of alternative ALT. */
549 check_and_make_def_conflict (int alt
, int def
, enum reg_class def_cl
)
553 enum reg_class use_cl
, acl
;
555 rtx dreg
= recog_data
.operand
[def
];
557 if (def_cl
== NO_REGS
)
560 if (GET_CODE (dreg
) == SUBREG
)
561 dreg
= SUBREG_REG (dreg
);
563 if (! REG_P (dreg
) || REGNO (dreg
) < FIRST_PSEUDO_REGISTER
)
566 a
= ira_curr_regno_allocno_map
[REGNO (dreg
)];
567 acl
= ALLOCNO_COVER_CLASS (a
);
568 if (! reg_classes_intersect_p (acl
, def_cl
))
573 for (use
= 0; use
< recog_data
.n_operands
; use
++)
577 if (use
== def
|| recog_data
.operand_type
[use
] == OP_OUT
)
580 if (recog_op_alt
[use
][alt
].anything_ok
)
583 use_cl
= recog_op_alt
[use
][alt
].cl
;
585 /* If there's any alternative that allows USE to match DEF, do not
586 record a conflict. If that causes us to create an invalid
587 instruction due to the earlyclobber, reload must fix it up. */
588 for (alt1
= 0; alt1
< recog_data
.n_alternatives
; alt1
++)
589 if (recog_op_alt
[use
][alt1
].matches
== def
590 || (use
< recog_data
.n_operands
- 1
591 && recog_data
.constraints
[use
][0] == '%'
592 && recog_op_alt
[use
+ 1][alt1
].matches
== def
)
594 && recog_data
.constraints
[use
- 1][0] == '%'
595 && recog_op_alt
[use
- 1][alt1
].matches
== def
))
598 if (alt1
< recog_data
.n_alternatives
)
601 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
604 if ((use_match
= recog_op_alt
[use
][alt
].matches
) >= 0)
606 if (use_match
== def
)
609 if (recog_op_alt
[use_match
][alt
].anything_ok
)
612 use_cl
= recog_op_alt
[use_match
][alt
].cl
;
613 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
619 /* Make conflicts of early clobber pseudo registers of the current
620 insn with its inputs. Avoid introducing unnecessary conflicts by
621 checking classes of the constraints and pseudos because otherwise
622 significant code degradation is possible for some targets. */
624 make_early_clobber_and_input_conflicts (void)
628 enum reg_class def_cl
;
630 for (alt
= 0; alt
< recog_data
.n_alternatives
; alt
++)
631 for (def
= 0; def
< recog_data
.n_operands
; def
++)
634 if (recog_op_alt
[def
][alt
].earlyclobber
)
636 if (recog_op_alt
[def
][alt
].anything_ok
)
639 def_cl
= recog_op_alt
[def
][alt
].cl
;
640 check_and_make_def_conflict (alt
, def
, def_cl
);
642 if ((def_match
= recog_op_alt
[def
][alt
].matches
) >= 0
643 && (recog_op_alt
[def_match
][alt
].earlyclobber
644 || recog_op_alt
[def
][alt
].earlyclobber
))
646 if (recog_op_alt
[def_match
][alt
].anything_ok
)
649 def_cl
= recog_op_alt
[def_match
][alt
].cl
;
650 check_and_make_def_conflict (alt
, def
, def_cl
);
655 /* Mark early clobber hard registers of the current INSN as live (if
656 LIVE_P) or dead. Return true if there are such registers. */
658 mark_hard_reg_early_clobbers (rtx insn
, bool live_p
)
663 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
664 if (DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MUST_CLOBBER
))
666 rtx dreg
= DF_REF_REG (*def_rec
);
668 if (GET_CODE (dreg
) == SUBREG
)
669 dreg
= SUBREG_REG (dreg
);
670 if (! REG_P (dreg
) || REGNO (dreg
) >= FIRST_PSEUDO_REGISTER
)
673 /* Hard register clobbers are believed to be early clobber
674 because there is no way to say that non-operand hard
675 register clobbers are not early ones. */
677 mark_ref_live (*def_rec
);
679 mark_ref_dead (*def_rec
);
686 /* Checks that CONSTRAINTS permits to use only one hard register. If
687 it is so, the function returns the class of the hard register.
688 Otherwise it returns NO_REGS. */
689 static enum reg_class
690 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
693 enum reg_class cl
, next_cl
;
697 for (ignore_p
= false;
699 constraints
+= CONSTRAINT_LEN (c
, constraints
))
719 || (equiv_const
!= NULL_RTX
&& CONSTANT_P (equiv_const
)))
725 || (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE (op
) == VOIDmode
)
726 || (equiv_const
!= NULL_RTX
727 && (CONST_INT_P (equiv_const
)
728 || (GET_CODE (equiv_const
) == CONST_DOUBLE
729 && GET_MODE (equiv_const
) == VOIDmode
))))
734 if ((CONSTANT_P (op
) && !CONST_INT_P (op
)
735 && (GET_CODE (op
) != CONST_DOUBLE
|| GET_MODE (op
) != VOIDmode
))
736 || (equiv_const
!= NULL_RTX
737 && CONSTANT_P (equiv_const
)
738 && !CONST_INT_P (equiv_const
)
739 && (GET_CODE (equiv_const
) != CONST_DOUBLE
740 || GET_MODE (equiv_const
) != VOIDmode
)))
752 if ((CONST_INT_P (op
)
753 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, constraints
))
754 || (equiv_const
!= NULL_RTX
755 && CONST_INT_P (equiv_const
)
756 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const
),
763 if (GET_CODE (op
) == CONST_DOUBLE
764 || (GET_CODE (op
) == CONST_VECTOR
765 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
)
766 || (equiv_const
!= NULL_RTX
767 && (GET_CODE (equiv_const
) == CONST_DOUBLE
768 || (GET_CODE (equiv_const
) == CONST_VECTOR
769 && (GET_MODE_CLASS (GET_MODE (equiv_const
))
770 == MODE_VECTOR_FLOAT
)))))
776 if ((GET_CODE (op
) == CONST_DOUBLE
777 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, constraints
))
778 || (equiv_const
!= NULL_RTX
779 && GET_CODE (equiv_const
) == CONST_DOUBLE
780 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const
,
783 /* ??? what about memory */
785 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
786 case 'h': case 'j': case 'k': case 'l':
787 case 'q': case 't': case 'u':
788 case 'v': case 'w': case 'x': case 'y': case 'z':
789 case 'A': case 'B': case 'C': case 'D':
790 case 'Q': case 'R': case 'S': case 'T': case 'U':
791 case 'W': case 'Y': case 'Z':
794 : REG_CLASS_FROM_CONSTRAINT (c
, constraints
));
795 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
796 || (ira_available_class_regs
[next_cl
]
797 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
802 case '0': case '1': case '2': case '3': case '4':
803 case '5': case '6': case '7': case '8': case '9':
805 = single_reg_class (recog_data
.constraints
[c
- '0'],
806 recog_data
.operand
[c
- '0'], NULL_RTX
);
807 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
808 || next_cl
== NO_REGS
809 || (ira_available_class_regs
[next_cl
]
810 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
821 /* The function checks that operand OP_NUM of the current insn can use
822 only one hard register. If it is so, the function returns the
823 class of the hard register. Otherwise it returns NO_REGS. */
824 static enum reg_class
825 single_reg_operand_class (int op_num
)
827 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
829 return single_reg_class (recog_data
.constraints
[op_num
],
830 recog_data
.operand
[op_num
], NULL_RTX
);
833 /* The function sets up hard register set *SET to hard registers which
834 might be used by insn reloads because the constraints are too
837 ira_implicitly_set_insn_hard_regs (HARD_REG_SET
*set
)
843 enum machine_mode mode
;
845 CLEAR_HARD_REG_SET (*set
);
846 for (i
= 0; i
< recog_data
.n_operands
; i
++)
848 op
= recog_data
.operand
[i
];
850 if (GET_CODE (op
) == SUBREG
)
851 op
= SUBREG_REG (op
);
853 if (GET_CODE (op
) == SCRATCH
854 || (REG_P (op
) && (regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
))
856 const char *p
= recog_data
.constraints
[i
];
858 mode
= (GET_CODE (op
) == SCRATCH
859 ? GET_MODE (op
) : PSEUDO_REGNO_MODE (regno
));
861 for (ignore_p
= false; (c
= *p
); p
+= CONSTRAINT_LEN (c
, p
))
870 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
871 case 'h': case 'j': case 'k': case 'l':
872 case 'q': case 't': case 'u':
873 case 'v': case 'w': case 'x': case 'y': case 'z':
874 case 'A': case 'B': case 'C': case 'D':
875 case 'Q': case 'R': case 'S': case 'T': case 'U':
876 case 'W': case 'Y': case 'Z':
879 : REG_CLASS_FROM_CONSTRAINT (c
, p
));
881 /* There is no register pressure problem if all of the
882 regs in this class are fixed. */
883 && ira_available_class_regs
[cl
] != 0
884 && (ira_available_class_regs
[cl
]
885 <= ira_reg_class_nregs
[cl
][mode
]))
886 IOR_HARD_REG_SET (*set
, reg_class_contents
[cl
]);
892 /* Processes input operands, if IN_P, or output operands otherwise of
893 the current insn with FREQ to find allocno which can use only one
894 hard register and makes other currently living allocnos conflicting
895 with the hard register. */
897 process_single_reg_class_operands (bool in_p
, int freq
)
903 ira_allocno_t operand_a
, a
;
905 for (i
= 0; i
< recog_data
.n_operands
; i
++)
907 operand
= recog_data
.operand
[i
];
908 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
909 && recog_data
.operand_type
[i
] != OP_INOUT
)
911 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
912 && recog_data
.operand_type
[i
] != OP_INOUT
)
914 cl
= single_reg_operand_class (i
);
920 if (GET_CODE (operand
) == SUBREG
)
921 operand
= SUBREG_REG (operand
);
924 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
926 enum machine_mode mode
;
927 enum reg_class cover_class
;
929 operand_a
= ira_curr_regno_allocno_map
[regno
];
930 mode
= ALLOCNO_MODE (operand_a
);
931 cover_class
= ALLOCNO_COVER_CLASS (operand_a
);
932 if (ira_class_subset_p
[cl
][cover_class
]
933 && ira_class_hard_regs_num
[cl
] != 0
934 && (ira_class_hard_reg_index
[cover_class
]
935 [ira_class_hard_regs
[cl
][0]]) >= 0
936 && reg_class_size
[cl
] <= (unsigned) CLASS_MAX_NREGS (cl
, mode
))
942 ? ira_get_register_move_cost (mode
, cover_class
, cl
)
943 : ira_get_register_move_cost (mode
, cl
, cover_class
)));
944 ira_allocate_and_set_costs
945 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
), cover_class
, 0);
946 size
= ira_reg_class_nregs
[cover_class
][mode
];
947 for (i
= 0; i
< size
; i
++)
948 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
949 [ira_class_hard_reg_index
950 [cover_class
][ira_class_hard_regs
[cl
][i
]]]
955 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
957 ira_object_t obj
= ira_object_id_map
[px
];
958 a
= OBJECT_ALLOCNO (obj
);
961 /* We could increase costs of A instead of making it
962 conflicting with the hard register. But it works worse
963 because it will be spilled in reload in anyway. */
964 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
965 reg_class_contents
[cl
]);
966 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
967 reg_class_contents
[cl
]);
973 /* Return true when one of the predecessor edges of BB is marked with
974 EDGE_ABNORMAL_CALL or EDGE_EH. */
976 bb_has_abnormal_call_pred (basic_block bb
)
981 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
983 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
989 /* Process insns of the basic block given by its LOOP_TREE_NODE to
990 update allocno live ranges, allocno hard register conflicts,
991 intersected calls, and register pressure info for allocnos for the
992 basic block for and regions containing the basic block. */
994 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
1001 bitmap reg_live_out
;
1005 bb
= loop_tree_node
->bb
;
1008 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1010 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
1011 high_pressure_start_point
[ira_reg_class_cover
[i
]] = -1;
1013 curr_bb_node
= loop_tree_node
;
1014 reg_live_out
= DF_LR_OUT (bb
);
1015 sparseset_clear (objects_live
);
1016 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
1017 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
1018 AND_COMPL_HARD_REG_SET (hard_regs_live
, ira_no_alloc_regs
);
1019 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1020 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
1022 enum reg_class cover_class
, cl
;
1024 cover_class
= ira_class_translate
[REGNO_REG_CLASS (i
)];
1026 (cl
= ira_reg_class_super_classes
[cover_class
][j
])
1030 curr_reg_pressure
[cl
]++;
1031 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
1032 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
1033 ira_assert (curr_reg_pressure
[cl
]
1034 <= ira_available_class_regs
[cl
]);
1037 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
1038 mark_pseudo_regno_live (j
);
1040 freq
= REG_FREQ_FROM_BB (bb
);
1044 /* Invalidate all allocno_saved_at_call entries. */
1047 /* Scan the code of this basic block, noting which allocnos and
1048 hard regs are born or die.
1050 Note that this loop treats uninitialized values as live until
1051 the beginning of the block. For example, if an instruction
1052 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1053 set, FOO will remain live until the beginning of the block.
1054 Likewise if FOO is not set at all. This is unnecessarily
1055 pessimistic, but it probably doesn't matter much in practice. */
1056 FOR_BB_INSNS_REVERSE (bb
, insn
)
1058 df_ref
*def_rec
, *use_rec
;
1061 if (!NONDEBUG_INSN_P (insn
))
1064 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1065 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
1066 INSN_UID (insn
), loop_tree_node
->parent
->loop
->num
,
1069 /* Mark each defined value as live. We need to do this for
1070 unused values because they still conflict with quantities
1071 that are live at the time of the definition.
1073 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1074 references represent the effect of the called function
1075 on a call-clobbered register. Marking the register as
1076 live would stop us from allocating it to a call-crossing
1078 call_p
= CALL_P (insn
);
1079 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1080 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1081 mark_ref_live (*def_rec
);
1083 /* If INSN has multiple outputs, then any value used in one
1084 of the outputs conflicts with the other outputs. Model this
1085 by making the used value live during the output phase.
1087 It is unsafe to use !single_set here since it will ignore
1088 an unused output. Just because an output is unused does
1089 not mean the compiler can assume the side effect will not
1090 occur. Consider if ALLOCNO appears in the address of an
1091 output and we reload the output. If we allocate ALLOCNO
1092 to the same hard register as an unused output we could
1093 set the hard register before the output reload insn. */
1094 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
1095 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1100 reg
= DF_REF_REG (*use_rec
);
1101 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
1105 set
= XVECEXP (PATTERN (insn
), 0, i
);
1106 if (GET_CODE (set
) == SET
1107 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
1109 /* After the previous loop, this is a no-op if
1110 REG is contained within SET_DEST (SET). */
1111 mark_ref_live (*use_rec
);
1117 extract_insn (insn
);
1118 preprocess_constraints ();
1119 process_single_reg_class_operands (false, freq
);
1121 /* See which defined values die here. */
1122 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1123 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1124 mark_ref_dead (*def_rec
);
1129 sparseset_clear (allocnos_processed
);
1130 /* The current set of live allocnos are live across the call. */
1131 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1133 ira_object_t obj
= ira_object_id_map
[i
];
1134 ira_allocno_t a
= OBJECT_ALLOCNO (obj
);
1135 int num
= ALLOCNO_NUM (a
);
1137 /* Don't allocate allocnos that cross setjmps or any
1138 call, if this function receives a nonlocal
1140 if (cfun
->has_nonlocal_label
1141 || find_reg_note (insn
, REG_SETJMP
,
1142 NULL_RTX
) != NULL_RTX
)
1144 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
));
1145 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1147 if (can_throw_internal (insn
))
1149 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
1151 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
1155 if (sparseset_bit_p (allocnos_processed
, num
))
1157 sparseset_set_bit (allocnos_processed
, num
);
1159 if (allocno_saved_at_call
[num
] != last_call_num
)
1160 /* Here we are mimicking caller-save.c behaviour
1161 which does not save hard register at a call if
1162 it was saved on previous call in the same basic
1163 block and the hard register was not mentioned
1164 between the two calls. */
1165 ALLOCNO_CALL_FREQ (a
) += freq
;
1166 /* Mark it as saved at the next call. */
1167 allocno_saved_at_call
[num
] = last_call_num
+ 1;
1168 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
1172 make_early_clobber_and_input_conflicts ();
1176 /* Mark each used value as live. */
1177 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1178 mark_ref_live (*use_rec
);
1180 process_single_reg_class_operands (true, freq
);
1182 set_p
= mark_hard_reg_early_clobbers (insn
, true);
1186 mark_hard_reg_early_clobbers (insn
, false);
1188 /* Mark each hard reg as live again. For example, a
1189 hard register can be in clobber and in an insn
1191 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1193 rtx ureg
= DF_REF_REG (*use_rec
);
1195 if (GET_CODE (ureg
) == SUBREG
)
1196 ureg
= SUBREG_REG (ureg
);
1197 if (! REG_P (ureg
) || REGNO (ureg
) >= FIRST_PSEUDO_REGISTER
)
1200 mark_ref_live (*use_rec
);
1207 #ifdef EH_RETURN_DATA_REGNO
1208 if (bb_has_eh_pred (bb
))
1211 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1212 if (regno
== INVALID_REGNUM
)
1214 make_hard_regno_born (regno
);
1218 /* Allocnos can't go in stack regs at the start of a basic block
1219 that is reached by an abnormal edge. Likewise for call
1220 clobbered regs, because caller-save, fixup_abnormal_edges and
1221 possibly the table driven EH machinery are not quite ready to
1222 handle such allocnos live across such edges. */
1223 if (bb_has_abnormal_pred (bb
))
1226 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
1228 ira_allocno_t a
= OBJECT_ALLOCNO (ira_object_id_map
[px
]);
1229 ALLOCNO_NO_STACK_REG_P (a
) = true;
1230 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = true;
1232 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1233 make_hard_regno_born (px
);
1235 /* No need to record conflicts for call clobbered regs if we
1236 have nonlocal labels around, as we don't ever try to
1237 allocate such regs in this case. */
1238 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
1239 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
1240 if (call_used_regs
[px
])
1241 make_hard_regno_born (px
);
1244 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1245 make_object_dead (ira_object_id_map
[i
]);
1250 /* Propagate register pressure to upper loop tree nodes: */
1251 if (loop_tree_node
!= ira_loop_tree_root
)
1252 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1254 enum reg_class cover_class
;
1256 cover_class
= ira_reg_class_cover
[i
];
1257 if (loop_tree_node
->reg_pressure
[cover_class
]
1258 > loop_tree_node
->parent
->reg_pressure
[cover_class
])
1259 loop_tree_node
->parent
->reg_pressure
[cover_class
]
1260 = loop_tree_node
->reg_pressure
[cover_class
];
1264 /* Create and set up IRA_START_POINT_RANGES and
1265 IRA_FINISH_POINT_RANGES. */
1267 create_start_finish_chains (void)
1270 ira_object_iterator oi
;
1273 ira_start_point_ranges
1274 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1275 memset (ira_start_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1276 ira_finish_point_ranges
1277 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1278 memset (ira_finish_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1279 FOR_EACH_OBJECT (obj
, oi
)
1280 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1282 r
->start_next
= ira_start_point_ranges
[r
->start
];
1283 ira_start_point_ranges
[r
->start
] = r
;
1284 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
1285 ira_finish_point_ranges
[r
->finish
] = r
;
1289 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1290 new live ranges and program points were added as a result if new
1293 ira_rebuild_start_finish_chains (void)
1295 ira_free (ira_finish_point_ranges
);
1296 ira_free (ira_start_point_ranges
);
1297 create_start_finish_chains ();
1300 /* Compress allocno live ranges by removing program points where
1303 remove_some_program_points_and_update_live_ranges (void)
1309 ira_object_iterator oi
;
1311 bitmap born_or_died
;
1314 born_or_died
= ira_allocate_bitmap ();
1315 FOR_EACH_OBJECT (obj
, oi
)
1316 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1318 ira_assert (r
->start
<= r
->finish
);
1319 bitmap_set_bit (born_or_died
, r
->start
);
1320 bitmap_set_bit (born_or_died
, r
->finish
);
1323 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1325 EXECUTE_IF_SET_IN_BITMAP(born_or_died
, 0, i
, bi
)
1329 ira_free_bitmap (born_or_died
);
1330 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1331 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1332 ira_max_point
, n
, 100 * n
/ ira_max_point
);
1335 FOR_EACH_OBJECT (obj
, oi
)
1336 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1338 r
->start
= map
[r
->start
];
1339 r
->finish
= map
[r
->finish
];
1345 /* Print live ranges R to file F. */
1347 ira_print_live_range_list (FILE *f
, live_range_t r
)
1349 for (; r
!= NULL
; r
= r
->next
)
1350 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1354 /* Print live ranges R to stderr. */
1356 ira_debug_live_range_list (live_range_t r
)
1358 ira_print_live_range_list (stderr
, r
);
1361 /* Print live ranges of object OBJ to file F. */
1363 print_object_live_ranges (FILE *f
, ira_object_t obj
)
1365 ira_print_live_range_list (f
, OBJECT_LIVE_RANGES (obj
));
1368 /* Print live ranges of allocno A to file F. */
1370 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
1372 int n
= ALLOCNO_NUM_OBJECTS (a
);
1374 for (i
= 0; i
< n
; i
++)
1376 fprintf (f
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1378 fprintf (f
, " [%d]", i
);
1380 print_object_live_ranges (f
, ALLOCNO_OBJECT (a
, i
));
1384 /* Print live ranges of allocno A to stderr. */
1386 ira_debug_allocno_live_ranges (ira_allocno_t a
)
1388 print_allocno_live_ranges (stderr
, a
);
1391 /* Print live ranges of all allocnos to file F. */
1393 print_live_ranges (FILE *f
)
1396 ira_allocno_iterator ai
;
1398 FOR_EACH_ALLOCNO (a
, ai
)
1399 print_allocno_live_ranges (f
, a
);
1402 /* Print live ranges of all allocnos to stderr. */
1404 ira_debug_live_ranges (void)
1406 print_live_ranges (stderr
);
1409 /* The main entry function creates live ranges, set up
1410 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1411 calculate register pressure info. */
1413 ira_create_allocno_live_ranges (void)
1415 objects_live
= sparseset_alloc (ira_objects_num
);
1416 allocnos_processed
= sparseset_alloc (ira_allocnos_num
);
1419 allocno_saved_at_call
1420 = (int *) ira_allocate (ira_allocnos_num
* sizeof (int));
1421 memset (allocno_saved_at_call
, 0, ira_allocnos_num
* sizeof (int));
1422 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
1423 process_bb_node_lives
);
1424 ira_max_point
= curr_point
;
1425 create_start_finish_chains ();
1426 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1427 print_live_ranges (ira_dump_file
);
1429 ira_free (allocno_saved_at_call
);
1430 sparseset_free (objects_live
);
1431 sparseset_free (allocnos_processed
);
1434 /* Compress allocno live ranges. */
1436 ira_compress_allocno_live_ranges (void)
1438 remove_some_program_points_and_update_live_ranges ();
1439 ira_rebuild_start_finish_chains ();
1440 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1442 fprintf (ira_dump_file
, "Ranges after the compression:\n");
1443 print_live_ranges (ira_dump_file
);
1447 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1449 ira_finish_allocno_live_ranges (void)
1451 ira_free (ira_finish_point_ranges
);
1452 ira_free (ira_start_point_ranges
);