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"
41 #include "sparseset.h"
44 /* The code in this file is similar to one in global but the code
45 works on the allocno basis and creates live ranges instead of
46 pseudo-register conflicts. */
48 /* Program points are enumerated by numbers from range
49 0..IRA_MAX_POINT-1. There are approximately two times more program
50 points than insns. Program points are places in the program where
51 liveness info can be changed. In most general case (there are more
52 complicated cases too) some program points correspond to places
53 where input operand dies and other ones correspond to places where
54 output operands are born. */
57 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
58 live ranges with given start/finish point. */
59 live_range_t
*ira_start_point_ranges
, *ira_finish_point_ranges
;
61 /* Number of the current program point. */
62 static int curr_point
;
64 /* Point where register pressure excess started or -1 if there is no
65 register pressure excess. Excess pressure for a register class at
66 some point means that there are more allocnos of given register
67 class living at the point than number of hard-registers of the
68 class available for the allocation. It is defined only for cover
70 static int high_pressure_start_point
[N_REG_CLASSES
];
72 /* Objects live at current point in the scan. */
73 static sparseset objects_live
;
75 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
77 static sparseset allocnos_processed
;
79 /* Set of hard regs (except eliminable ones) currently live. */
80 static HARD_REG_SET hard_regs_live
;
82 /* The loop tree node corresponding to the current basic block. */
83 static ira_loop_tree_node_t curr_bb_node
;
85 /* The number of the last processed call. */
86 static int last_call_num
;
87 /* The number of last call at which given allocno was saved. */
88 static int *allocno_saved_at_call
;
90 /* Record the birth of hard register REGNO, updating hard_regs_live and
91 hard reg conflict information for living allocnos. */
93 make_hard_regno_born (int regno
)
97 SET_HARD_REG_BIT (hard_regs_live
, regno
);
98 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
100 ira_object_t obj
= ira_object_id_map
[i
];
101 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj
), regno
);
102 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
);
106 /* Process the death of hard register REGNO. This updates
109 make_hard_regno_dead (int regno
)
111 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
114 /* Record the birth of object OBJ. Set a bit for it in objects_live,
115 start a new live range for it if necessary and update hard register
118 make_object_born (ira_object_t obj
)
120 live_range_t lr
= OBJECT_LIVE_RANGES (obj
);
122 sparseset_set_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
123 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), hard_regs_live
);
124 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), hard_regs_live
);
127 || (lr
->finish
!= curr_point
&& lr
->finish
+ 1 != curr_point
))
128 ira_add_live_range_to_object (obj
, curr_point
, -1);
131 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
132 associated with object OBJ. */
134 update_allocno_pressure_excess_length (ira_object_t obj
)
136 ira_allocno_t a
= OBJECT_ALLOCNO (obj
);
138 enum reg_class cover_class
, cl
;
141 cover_class
= ALLOCNO_COVER_CLASS (a
);
143 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
146 if (high_pressure_start_point
[cl
] < 0)
148 p
= OBJECT_LIVE_RANGES (obj
);
149 ira_assert (p
!= NULL
);
150 start
= (high_pressure_start_point
[cl
] > p
->start
151 ? high_pressure_start_point
[cl
] : p
->start
);
152 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
156 /* Process the death of object OBJ, which is associated with allocno
157 A. This finishes the current live range for it. */
159 make_object_dead (ira_object_t obj
)
163 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
164 lr
= OBJECT_LIVE_RANGES (obj
);
165 ira_assert (lr
!= NULL
);
166 lr
->finish
= curr_point
;
167 update_allocno_pressure_excess_length (obj
);
170 /* The current register pressures for each cover class for the current
172 static int curr_reg_pressure
[N_REG_CLASSES
];
174 /* Record that register pressure for COVER_CLASS increased by N
175 registers. Update the current register pressure, maximal register
176 pressure for the current BB and the start point of the register
179 inc_register_pressure (enum reg_class cover_class
, int n
)
185 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
188 curr_reg_pressure
[cl
] += n
;
189 if (high_pressure_start_point
[cl
] < 0
190 && (curr_reg_pressure
[cl
] > ira_available_class_regs
[cl
]))
191 high_pressure_start_point
[cl
] = curr_point
;
192 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
193 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
197 /* Record that register pressure for COVER_CLASS has decreased by
198 NREGS registers; update current register pressure, start point of
199 the register pressure excess, and register pressure excess length
200 for living allocnos. */
203 dec_register_pressure (enum reg_class cover_class
, int nregs
)
211 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
214 curr_reg_pressure
[cl
] -= nregs
;
215 ira_assert (curr_reg_pressure
[cl
] >= 0);
216 if (high_pressure_start_point
[cl
] >= 0
217 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
222 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, j
)
223 update_allocno_pressure_excess_length (ira_object_id_map
[j
]);
225 (cl
= ira_reg_class_super_classes
[cover_class
][i
])
228 if (high_pressure_start_point
[cl
] >= 0
229 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
230 high_pressure_start_point
[cl
] = -1;
234 /* Mark the pseudo register REGNO as live. Update all information about
235 live ranges and register pressure. */
237 mark_pseudo_regno_live (int regno
)
239 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
246 /* Invalidate because it is referenced. */
247 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
249 n
= ALLOCNO_NUM_OBJECTS (a
);
250 cl
= ALLOCNO_COVER_CLASS (a
);
251 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
254 /* We track every subobject separately. */
255 gcc_assert (nregs
== n
);
259 for (i
= 0; i
< n
; i
++)
261 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
262 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
265 inc_register_pressure (cl
, nregs
);
266 make_object_born (obj
);
270 /* Like mark_pseudo_regno_live, but try to only mark one subword of
271 the pseudo as live. SUBWORD indicates which; a value of 0
272 indicates the low part. */
274 mark_pseudo_regno_subword_live (int regno
, int subword
)
276 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
284 /* Invalidate because it is referenced. */
285 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
287 n
= ALLOCNO_NUM_OBJECTS (a
);
290 mark_pseudo_regno_live (regno
);
294 cl
= ALLOCNO_COVER_CLASS (a
);
295 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
296 gcc_assert (nregs
== n
);
297 obj
= ALLOCNO_OBJECT (a
, subword
);
299 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
302 inc_register_pressure (cl
, nregs
);
303 make_object_born (obj
);
306 /* Mark the register REG as live. Store a 1 in hard_regs_live for
307 this register, record how many consecutive hardware registers it
310 mark_hard_reg_live (rtx reg
)
312 int regno
= REGNO (reg
);
314 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
316 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
320 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
321 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
323 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
324 inc_register_pressure (cover_class
, 1);
325 make_hard_regno_born (regno
);
332 /* Mark the register referenced by use or def REF as live. */
334 mark_ref_live (df_ref ref
)
336 rtx reg
= DF_REF_REG (ref
);
339 if (GET_CODE (reg
) == SUBREG
)
340 reg
= SUBREG_REG (reg
);
342 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
344 if (df_read_modify_subreg_p (orig_reg
))
346 mark_pseudo_regno_subword_live (REGNO (reg
),
347 subreg_lowpart_p (orig_reg
) ? 0 : 1);
350 mark_pseudo_regno_live (REGNO (reg
));
353 mark_hard_reg_live (reg
);
356 /* Mark the pseudo register REGNO as dead. Update all information about
357 live ranges and register pressure. */
359 mark_pseudo_regno_dead (int regno
)
361 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
368 /* Invalidate because it is referenced. */
369 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
371 n
= ALLOCNO_NUM_OBJECTS (a
);
372 cl
= ALLOCNO_COVER_CLASS (a
);
373 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
376 /* We track every subobject separately. */
377 gcc_assert (nregs
== n
);
380 for (i
= 0; i
< n
; i
++)
382 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
383 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
386 dec_register_pressure (cl
, nregs
);
387 make_object_dead (obj
);
391 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
392 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
394 mark_pseudo_regno_subword_dead (int regno
, int subword
)
396 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
404 /* Invalidate because it is referenced. */
405 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
407 n
= ALLOCNO_NUM_OBJECTS (a
);
409 /* The allocno as a whole doesn't die in this case. */
412 cl
= ALLOCNO_COVER_CLASS (a
);
413 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
414 gcc_assert (nregs
== n
);
416 obj
= ALLOCNO_OBJECT (a
, subword
);
417 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
420 dec_register_pressure (cl
, 1);
421 make_object_dead (obj
);
424 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the
427 mark_hard_reg_dead (rtx reg
)
429 int regno
= REGNO (reg
);
431 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
433 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
437 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
439 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
440 dec_register_pressure (cover_class
, 1);
441 make_hard_regno_dead (regno
);
448 /* Mark the register referenced by definition DEF as dead, if the
449 definition is a total one. */
451 mark_ref_dead (df_ref def
)
453 rtx reg
= DF_REF_REG (def
);
456 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
459 if (GET_CODE (reg
) == SUBREG
)
460 reg
= SUBREG_REG (reg
);
462 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
463 && (GET_CODE (orig_reg
) != SUBREG
464 || REGNO (reg
) < FIRST_PSEUDO_REGISTER
465 || !df_read_modify_subreg_p (orig_reg
)))
468 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
470 if (df_read_modify_subreg_p (orig_reg
))
472 mark_pseudo_regno_subword_dead (REGNO (reg
),
473 subreg_lowpart_p (orig_reg
) ? 0 : 1);
476 mark_pseudo_regno_dead (REGNO (reg
));
479 mark_hard_reg_dead (reg
);
482 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
483 class is intersected with class CL. Advance the current program
484 point before making the conflict if ADVANCE_P. Return TRUE if we
485 will need to advance the current program point. */
487 make_pseudo_conflict (rtx reg
, enum reg_class cl
, rtx dreg
, bool advance_p
)
491 if (GET_CODE (reg
) == SUBREG
)
492 reg
= SUBREG_REG (reg
);
494 if (! REG_P (reg
) || REGNO (reg
) < FIRST_PSEUDO_REGISTER
)
497 a
= ira_curr_regno_allocno_map
[REGNO (reg
)];
498 if (! reg_classes_intersect_p (cl
, ALLOCNO_COVER_CLASS (a
)))
504 mark_pseudo_regno_live (REGNO (reg
));
505 mark_pseudo_regno_live (REGNO (dreg
));
506 mark_pseudo_regno_dead (REGNO (reg
));
507 mark_pseudo_regno_dead (REGNO (dreg
));
512 /* Check and make if necessary conflicts for pseudo DREG of class
513 DEF_CL of the current insn with input operand USE of class USE_CL.
514 Advance the current program point before making the conflict if
515 ADVANCE_P. Return TRUE if we will need to advance the current
518 check_and_make_def_use_conflict (rtx dreg
, enum reg_class def_cl
,
519 int use
, enum reg_class use_cl
,
522 if (! reg_classes_intersect_p (def_cl
, use_cl
))
525 advance_p
= make_pseudo_conflict (recog_data
.operand
[use
],
526 use_cl
, dreg
, advance_p
);
527 /* Reload may end up swapping commutative operands, so you
528 have to take both orderings into account. The
529 constraints for the two operands can be completely
530 different. (Indeed, if the constraints for the two
531 operands are the same for all alternatives, there's no
532 point marking them as commutative.) */
533 if (use
< recog_data
.n_operands
- 1
534 && recog_data
.constraints
[use
][0] == '%')
536 = make_pseudo_conflict (recog_data
.operand
[use
+ 1],
537 use_cl
, dreg
, advance_p
);
539 && recog_data
.constraints
[use
- 1][0] == '%')
541 = make_pseudo_conflict (recog_data
.operand
[use
- 1],
542 use_cl
, dreg
, advance_p
);
546 /* Check and make if necessary conflicts for definition DEF of class
547 DEF_CL of the current insn with input operands. Process only
548 constraints of alternative ALT. */
550 check_and_make_def_conflict (int alt
, int def
, enum reg_class def_cl
)
554 enum reg_class use_cl
, acl
;
556 rtx dreg
= recog_data
.operand
[def
];
558 if (def_cl
== NO_REGS
)
561 if (GET_CODE (dreg
) == SUBREG
)
562 dreg
= SUBREG_REG (dreg
);
564 if (! REG_P (dreg
) || REGNO (dreg
) < FIRST_PSEUDO_REGISTER
)
567 a
= ira_curr_regno_allocno_map
[REGNO (dreg
)];
568 acl
= ALLOCNO_COVER_CLASS (a
);
569 if (! reg_classes_intersect_p (acl
, def_cl
))
574 for (use
= 0; use
< recog_data
.n_operands
; use
++)
578 if (use
== def
|| recog_data
.operand_type
[use
] == OP_OUT
)
581 if (recog_op_alt
[use
][alt
].anything_ok
)
584 use_cl
= recog_op_alt
[use
][alt
].cl
;
586 /* If there's any alternative that allows USE to match DEF, do not
587 record a conflict. If that causes us to create an invalid
588 instruction due to the earlyclobber, reload must fix it up. */
589 for (alt1
= 0; alt1
< recog_data
.n_alternatives
; alt1
++)
590 if (recog_op_alt
[use
][alt1
].matches
== def
591 || (use
< recog_data
.n_operands
- 1
592 && recog_data
.constraints
[use
][0] == '%'
593 && recog_op_alt
[use
+ 1][alt1
].matches
== def
)
595 && recog_data
.constraints
[use
- 1][0] == '%'
596 && recog_op_alt
[use
- 1][alt1
].matches
== def
))
599 if (alt1
< recog_data
.n_alternatives
)
602 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
605 if ((use_match
= recog_op_alt
[use
][alt
].matches
) >= 0)
607 if (use_match
== def
)
610 if (recog_op_alt
[use_match
][alt
].anything_ok
)
613 use_cl
= recog_op_alt
[use_match
][alt
].cl
;
614 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
620 /* Make conflicts of early clobber pseudo registers of the current
621 insn with its inputs. Avoid introducing unnecessary conflicts by
622 checking classes of the constraints and pseudos because otherwise
623 significant code degradation is possible for some targets. */
625 make_early_clobber_and_input_conflicts (void)
629 enum reg_class def_cl
;
631 for (alt
= 0; alt
< recog_data
.n_alternatives
; alt
++)
632 for (def
= 0; def
< recog_data
.n_operands
; def
++)
635 if (recog_op_alt
[def
][alt
].earlyclobber
)
637 if (recog_op_alt
[def
][alt
].anything_ok
)
640 def_cl
= recog_op_alt
[def
][alt
].cl
;
641 check_and_make_def_conflict (alt
, def
, def_cl
);
643 if ((def_match
= recog_op_alt
[def
][alt
].matches
) >= 0
644 && (recog_op_alt
[def_match
][alt
].earlyclobber
645 || recog_op_alt
[def
][alt
].earlyclobber
))
647 if (recog_op_alt
[def_match
][alt
].anything_ok
)
650 def_cl
= recog_op_alt
[def_match
][alt
].cl
;
651 check_and_make_def_conflict (alt
, def
, def_cl
);
656 /* Mark early clobber hard registers of the current INSN as live (if
657 LIVE_P) or dead. Return true if there are such registers. */
659 mark_hard_reg_early_clobbers (rtx insn
, bool live_p
)
664 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
665 if (DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MUST_CLOBBER
))
667 rtx dreg
= DF_REF_REG (*def_rec
);
669 if (GET_CODE (dreg
) == SUBREG
)
670 dreg
= SUBREG_REG (dreg
);
671 if (! REG_P (dreg
) || REGNO (dreg
) >= FIRST_PSEUDO_REGISTER
)
674 /* Hard register clobbers are believed to be early clobber
675 because there is no way to say that non-operand hard
676 register clobbers are not early ones. */
678 mark_ref_live (*def_rec
);
680 mark_ref_dead (*def_rec
);
687 /* Checks that CONSTRAINTS permits to use only one hard register. If
688 it is so, the function returns the class of the hard register.
689 Otherwise it returns NO_REGS. */
690 static enum reg_class
691 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
694 enum reg_class cl
, next_cl
;
698 for (ignore_p
= false;
700 constraints
+= CONSTRAINT_LEN (c
, constraints
))
720 || (equiv_const
!= NULL_RTX
&& CONSTANT_P (equiv_const
)))
726 || (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE (op
) == VOIDmode
)
727 || (equiv_const
!= NULL_RTX
728 && (CONST_INT_P (equiv_const
)
729 || (GET_CODE (equiv_const
) == CONST_DOUBLE
730 && GET_MODE (equiv_const
) == VOIDmode
))))
735 if ((CONSTANT_P (op
) && !CONST_INT_P (op
)
736 && (GET_CODE (op
) != CONST_DOUBLE
|| GET_MODE (op
) != VOIDmode
))
737 || (equiv_const
!= NULL_RTX
738 && CONSTANT_P (equiv_const
)
739 && !CONST_INT_P (equiv_const
)
740 && (GET_CODE (equiv_const
) != CONST_DOUBLE
741 || GET_MODE (equiv_const
) != VOIDmode
)))
753 if ((CONST_INT_P (op
)
754 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, constraints
))
755 || (equiv_const
!= NULL_RTX
756 && CONST_INT_P (equiv_const
)
757 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const
),
764 if (GET_CODE (op
) == CONST_DOUBLE
765 || (GET_CODE (op
) == CONST_VECTOR
766 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
)
767 || (equiv_const
!= NULL_RTX
768 && (GET_CODE (equiv_const
) == CONST_DOUBLE
769 || (GET_CODE (equiv_const
) == CONST_VECTOR
770 && (GET_MODE_CLASS (GET_MODE (equiv_const
))
771 == MODE_VECTOR_FLOAT
)))))
777 if ((GET_CODE (op
) == CONST_DOUBLE
778 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, constraints
))
779 || (equiv_const
!= NULL_RTX
780 && GET_CODE (equiv_const
) == CONST_DOUBLE
781 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const
,
784 /* ??? what about memory */
786 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
787 case 'h': case 'j': case 'k': case 'l':
788 case 'q': case 't': case 'u':
789 case 'v': case 'w': case 'x': case 'y': case 'z':
790 case 'A': case 'B': case 'C': case 'D':
791 case 'Q': case 'R': case 'S': case 'T': case 'U':
792 case 'W': case 'Y': case 'Z':
795 : REG_CLASS_FROM_CONSTRAINT (c
, constraints
));
796 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
797 || (ira_available_class_regs
[next_cl
]
798 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
803 case '0': case '1': case '2': case '3': case '4':
804 case '5': case '6': case '7': case '8': case '9':
806 = single_reg_class (recog_data
.constraints
[c
- '0'],
807 recog_data
.operand
[c
- '0'], NULL_RTX
);
808 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
809 || next_cl
== NO_REGS
810 || (ira_available_class_regs
[next_cl
]
811 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
822 /* The function checks that operand OP_NUM of the current insn can use
823 only one hard register. If it is so, the function returns the
824 class of the hard register. Otherwise it returns NO_REGS. */
825 static enum reg_class
826 single_reg_operand_class (int op_num
)
828 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
830 return single_reg_class (recog_data
.constraints
[op_num
],
831 recog_data
.operand
[op_num
], NULL_RTX
);
834 /* The function sets up hard register set *SET to hard registers which
835 might be used by insn reloads because the constraints are too
838 ira_implicitly_set_insn_hard_regs (HARD_REG_SET
*set
)
844 enum machine_mode mode
;
846 CLEAR_HARD_REG_SET (*set
);
847 for (i
= 0; i
< recog_data
.n_operands
; i
++)
849 op
= recog_data
.operand
[i
];
851 if (GET_CODE (op
) == SUBREG
)
852 op
= SUBREG_REG (op
);
854 if (GET_CODE (op
) == SCRATCH
855 || (REG_P (op
) && (regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
))
857 const char *p
= recog_data
.constraints
[i
];
859 mode
= (GET_CODE (op
) == SCRATCH
860 ? GET_MODE (op
) : PSEUDO_REGNO_MODE (regno
));
862 for (ignore_p
= false; (c
= *p
); p
+= CONSTRAINT_LEN (c
, p
))
871 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
872 case 'h': case 'j': case 'k': case 'l':
873 case 'q': case 't': case 'u':
874 case 'v': case 'w': case 'x': case 'y': case 'z':
875 case 'A': case 'B': case 'C': case 'D':
876 case 'Q': case 'R': case 'S': case 'T': case 'U':
877 case 'W': case 'Y': case 'Z':
880 : REG_CLASS_FROM_CONSTRAINT (c
, p
));
882 /* There is no register pressure problem if all of the
883 regs in this class are fixed. */
884 && ira_available_class_regs
[cl
] != 0
885 && (ira_available_class_regs
[cl
]
886 <= ira_reg_class_nregs
[cl
][mode
]))
887 IOR_HARD_REG_SET (*set
, reg_class_contents
[cl
]);
893 /* Processes input operands, if IN_P, or output operands otherwise of
894 the current insn with FREQ to find allocno which can use only one
895 hard register and makes other currently living allocnos conflicting
896 with the hard register. */
898 process_single_reg_class_operands (bool in_p
, int freq
)
904 ira_allocno_t operand_a
, a
;
906 for (i
= 0; i
< recog_data
.n_operands
; i
++)
908 operand
= recog_data
.operand
[i
];
909 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
910 && recog_data
.operand_type
[i
] != OP_INOUT
)
912 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
913 && recog_data
.operand_type
[i
] != OP_INOUT
)
915 cl
= single_reg_operand_class (i
);
921 if (GET_CODE (operand
) == SUBREG
)
922 operand
= SUBREG_REG (operand
);
925 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
927 enum machine_mode mode
;
928 enum reg_class cover_class
;
930 operand_a
= ira_curr_regno_allocno_map
[regno
];
931 mode
= ALLOCNO_MODE (operand_a
);
932 cover_class
= ALLOCNO_COVER_CLASS (operand_a
);
933 if (ira_class_subset_p
[cl
][cover_class
]
934 && ira_class_hard_regs_num
[cl
] != 0
935 && (ira_class_hard_reg_index
[cover_class
]
936 [ira_class_hard_regs
[cl
][0]]) >= 0
937 && reg_class_size
[cl
] <= (unsigned) CLASS_MAX_NREGS (cl
, mode
))
943 ? ira_get_register_move_cost (mode
, cover_class
, cl
)
944 : ira_get_register_move_cost (mode
, cl
, cover_class
)));
945 ira_allocate_and_set_costs
946 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
), cover_class
, 0);
947 size
= ira_reg_class_nregs
[cover_class
][mode
];
948 for (i
= 0; i
< size
; i
++)
949 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
950 [ira_class_hard_reg_index
951 [cover_class
][ira_class_hard_regs
[cl
][i
]]]
956 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
958 ira_object_t obj
= ira_object_id_map
[px
];
959 a
= OBJECT_ALLOCNO (obj
);
962 /* We could increase costs of A instead of making it
963 conflicting with the hard register. But it works worse
964 because it will be spilled in reload in anyway. */
965 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
966 reg_class_contents
[cl
]);
967 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
968 reg_class_contents
[cl
]);
974 /* Return true when one of the predecessor edges of BB is marked with
975 EDGE_ABNORMAL_CALL or EDGE_EH. */
977 bb_has_abnormal_call_pred (basic_block bb
)
982 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
984 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
990 /* Process insns of the basic block given by its LOOP_TREE_NODE to
991 update allocno live ranges, allocno hard register conflicts,
992 intersected calls, and register pressure info for allocnos for the
993 basic block for and regions containing the basic block. */
995 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
1002 bitmap reg_live_out
;
1006 bb
= loop_tree_node
->bb
;
1009 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1011 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
1012 high_pressure_start_point
[ira_reg_class_cover
[i
]] = -1;
1014 curr_bb_node
= loop_tree_node
;
1015 reg_live_out
= DF_LR_OUT (bb
);
1016 sparseset_clear (objects_live
);
1017 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
1018 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
1019 AND_COMPL_HARD_REG_SET (hard_regs_live
, ira_no_alloc_regs
);
1020 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1021 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
1023 enum reg_class cover_class
, cl
;
1025 cover_class
= ira_class_translate
[REGNO_REG_CLASS (i
)];
1027 (cl
= ira_reg_class_super_classes
[cover_class
][j
])
1031 curr_reg_pressure
[cl
]++;
1032 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
1033 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
1034 ira_assert (curr_reg_pressure
[cl
]
1035 <= ira_available_class_regs
[cl
]);
1038 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
1039 mark_pseudo_regno_live (j
);
1041 freq
= REG_FREQ_FROM_BB (bb
);
1045 /* Invalidate all allocno_saved_at_call entries. */
1048 /* Scan the code of this basic block, noting which allocnos and
1049 hard regs are born or die.
1051 Note that this loop treats uninitialized values as live until
1052 the beginning of the block. For example, if an instruction
1053 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1054 set, FOO will remain live until the beginning of the block.
1055 Likewise if FOO is not set at all. This is unnecessarily
1056 pessimistic, but it probably doesn't matter much in practice. */
1057 FOR_BB_INSNS_REVERSE (bb
, insn
)
1059 df_ref
*def_rec
, *use_rec
;
1062 if (!NONDEBUG_INSN_P (insn
))
1065 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1066 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
1067 INSN_UID (insn
), loop_tree_node
->parent
->loop
->num
,
1070 /* Mark each defined value as live. We need to do this for
1071 unused values because they still conflict with quantities
1072 that are live at the time of the definition.
1074 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1075 references represent the effect of the called function
1076 on a call-clobbered register. Marking the register as
1077 live would stop us from allocating it to a call-crossing
1079 call_p
= CALL_P (insn
);
1080 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1081 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1082 mark_ref_live (*def_rec
);
1084 /* If INSN has multiple outputs, then any value used in one
1085 of the outputs conflicts with the other outputs. Model this
1086 by making the used value live during the output phase.
1088 It is unsafe to use !single_set here since it will ignore
1089 an unused output. Just because an output is unused does
1090 not mean the compiler can assume the side effect will not
1091 occur. Consider if ALLOCNO appears in the address of an
1092 output and we reload the output. If we allocate ALLOCNO
1093 to the same hard register as an unused output we could
1094 set the hard register before the output reload insn. */
1095 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
1096 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1101 reg
= DF_REF_REG (*use_rec
);
1102 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
1106 set
= XVECEXP (PATTERN (insn
), 0, i
);
1107 if (GET_CODE (set
) == SET
1108 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
1110 /* After the previous loop, this is a no-op if
1111 REG is contained within SET_DEST (SET). */
1112 mark_ref_live (*use_rec
);
1118 extract_insn (insn
);
1119 preprocess_constraints ();
1120 process_single_reg_class_operands (false, freq
);
1122 /* See which defined values die here. */
1123 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1124 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1125 mark_ref_dead (*def_rec
);
1130 sparseset_clear (allocnos_processed
);
1131 /* The current set of live allocnos are live across the call. */
1132 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1134 ira_object_t obj
= ira_object_id_map
[i
];
1135 ira_allocno_t a
= OBJECT_ALLOCNO (obj
);
1136 int num
= ALLOCNO_NUM (a
);
1138 /* Don't allocate allocnos that cross setjmps or any
1139 call, if this function receives a nonlocal
1141 if (cfun
->has_nonlocal_label
1142 || find_reg_note (insn
, REG_SETJMP
,
1143 NULL_RTX
) != NULL_RTX
)
1145 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
));
1146 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1148 if (can_throw_internal (insn
))
1150 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
1152 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
1156 if (sparseset_bit_p (allocnos_processed
, num
))
1158 sparseset_set_bit (allocnos_processed
, num
);
1160 if (allocno_saved_at_call
[num
] != last_call_num
)
1161 /* Here we are mimicking caller-save.c behaviour
1162 which does not save hard register at a call if
1163 it was saved on previous call in the same basic
1164 block and the hard register was not mentioned
1165 between the two calls. */
1166 ALLOCNO_CALL_FREQ (a
) += freq
;
1167 /* Mark it as saved at the next call. */
1168 allocno_saved_at_call
[num
] = last_call_num
+ 1;
1169 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
1173 make_early_clobber_and_input_conflicts ();
1177 /* Mark each used value as live. */
1178 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1179 mark_ref_live (*use_rec
);
1181 process_single_reg_class_operands (true, freq
);
1183 set_p
= mark_hard_reg_early_clobbers (insn
, true);
1187 mark_hard_reg_early_clobbers (insn
, false);
1189 /* Mark each hard reg as live again. For example, a
1190 hard register can be in clobber and in an insn
1192 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1194 rtx ureg
= DF_REF_REG (*use_rec
);
1196 if (GET_CODE (ureg
) == SUBREG
)
1197 ureg
= SUBREG_REG (ureg
);
1198 if (! REG_P (ureg
) || REGNO (ureg
) >= FIRST_PSEUDO_REGISTER
)
1201 mark_ref_live (*use_rec
);
1208 #ifdef EH_RETURN_DATA_REGNO
1209 if (bb_has_eh_pred (bb
))
1212 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1213 if (regno
== INVALID_REGNUM
)
1215 make_hard_regno_born (regno
);
1219 /* Allocnos can't go in stack regs at the start of a basic block
1220 that is reached by an abnormal edge. Likewise for call
1221 clobbered regs, because caller-save, fixup_abnormal_edges and
1222 possibly the table driven EH machinery are not quite ready to
1223 handle such allocnos live across such edges. */
1224 if (bb_has_abnormal_pred (bb
))
1227 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
1229 ira_allocno_t a
= OBJECT_ALLOCNO (ira_object_id_map
[px
]);
1230 ALLOCNO_NO_STACK_REG_P (a
) = true;
1231 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = true;
1233 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1234 make_hard_regno_born (px
);
1236 /* No need to record conflicts for call clobbered regs if we
1237 have nonlocal labels around, as we don't ever try to
1238 allocate such regs in this case. */
1239 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
1240 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
1241 if (call_used_regs
[px
])
1242 make_hard_regno_born (px
);
1245 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1246 make_object_dead (ira_object_id_map
[i
]);
1251 /* Propagate register pressure to upper loop tree nodes: */
1252 if (loop_tree_node
!= ira_loop_tree_root
)
1253 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1255 enum reg_class cover_class
;
1257 cover_class
= ira_reg_class_cover
[i
];
1258 if (loop_tree_node
->reg_pressure
[cover_class
]
1259 > loop_tree_node
->parent
->reg_pressure
[cover_class
])
1260 loop_tree_node
->parent
->reg_pressure
[cover_class
]
1261 = loop_tree_node
->reg_pressure
[cover_class
];
1265 /* Create and set up IRA_START_POINT_RANGES and
1266 IRA_FINISH_POINT_RANGES. */
1268 create_start_finish_chains (void)
1271 ira_object_iterator oi
;
1274 ira_start_point_ranges
1275 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1276 memset (ira_start_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1277 ira_finish_point_ranges
1278 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1279 memset (ira_finish_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1280 FOR_EACH_OBJECT (obj
, oi
)
1281 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1283 r
->start_next
= ira_start_point_ranges
[r
->start
];
1284 ira_start_point_ranges
[r
->start
] = r
;
1285 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
1286 ira_finish_point_ranges
[r
->finish
] = r
;
1290 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1291 new live ranges and program points were added as a result if new
1294 ira_rebuild_start_finish_chains (void)
1296 ira_free (ira_finish_point_ranges
);
1297 ira_free (ira_start_point_ranges
);
1298 create_start_finish_chains ();
1301 /* Compress allocno live ranges by removing program points where
1304 remove_some_program_points_and_update_live_ranges (void)
1310 ira_object_iterator oi
;
1312 sbitmap born_or_dead
, born
, dead
;
1313 sbitmap_iterator sbi
;
1314 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1316 born
= sbitmap_alloc (ira_max_point
);
1317 dead
= sbitmap_alloc (ira_max_point
);
1318 sbitmap_zero (born
);
1319 sbitmap_zero (dead
);
1320 FOR_EACH_OBJECT (obj
, oi
)
1321 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1323 ira_assert (r
->start
<= r
->finish
);
1324 SET_BIT (born
, r
->start
);
1325 SET_BIT (dead
, r
->finish
);
1328 born_or_dead
= sbitmap_alloc (ira_max_point
);
1329 sbitmap_a_or_b (born_or_dead
, born
, dead
);
1330 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1332 prev_born_p
= prev_dead_p
= false;
1333 EXECUTE_IF_SET_IN_SBITMAP (born_or_dead
, 0, i
, sbi
)
1335 born_p
= TEST_BIT (born
, i
);
1336 dead_p
= TEST_BIT (dead
, i
);
1337 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1338 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1342 prev_born_p
= born_p
;
1343 prev_dead_p
= dead_p
;
1345 sbitmap_free (born_or_dead
);
1346 sbitmap_free (born
);
1347 sbitmap_free (dead
);
1349 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1350 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1351 ira_max_point
, n
, 100 * n
/ ira_max_point
);
1354 FOR_EACH_OBJECT (obj
, oi
)
1355 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1357 r
->start
= map
[r
->start
];
1358 r
->finish
= map
[r
->finish
];
1364 /* Print live ranges R to file F. */
1366 ira_print_live_range_list (FILE *f
, live_range_t r
)
1368 for (; r
!= NULL
; r
= r
->next
)
1369 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1373 /* Print live ranges R to stderr. */
1375 ira_debug_live_range_list (live_range_t r
)
1377 ira_print_live_range_list (stderr
, r
);
1380 /* Print live ranges of object OBJ to file F. */
1382 print_object_live_ranges (FILE *f
, ira_object_t obj
)
1384 ira_print_live_range_list (f
, OBJECT_LIVE_RANGES (obj
));
1387 /* Print live ranges of allocno A to file F. */
1389 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
1391 int n
= ALLOCNO_NUM_OBJECTS (a
);
1393 for (i
= 0; i
< n
; i
++)
1395 fprintf (f
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1397 fprintf (f
, " [%d]", i
);
1399 print_object_live_ranges (f
, ALLOCNO_OBJECT (a
, i
));
1403 /* Print live ranges of allocno A to stderr. */
1405 ira_debug_allocno_live_ranges (ira_allocno_t a
)
1407 print_allocno_live_ranges (stderr
, a
);
1410 /* Print live ranges of all allocnos to file F. */
1412 print_live_ranges (FILE *f
)
1415 ira_allocno_iterator ai
;
1417 FOR_EACH_ALLOCNO (a
, ai
)
1418 print_allocno_live_ranges (f
, a
);
1421 /* Print live ranges of all allocnos to stderr. */
1423 ira_debug_live_ranges (void)
1425 print_live_ranges (stderr
);
1428 /* The main entry function creates live ranges, set up
1429 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1430 calculate register pressure info. */
1432 ira_create_allocno_live_ranges (void)
1434 objects_live
= sparseset_alloc (ira_objects_num
);
1435 allocnos_processed
= sparseset_alloc (ira_allocnos_num
);
1438 allocno_saved_at_call
1439 = (int *) ira_allocate (ira_allocnos_num
* sizeof (int));
1440 memset (allocno_saved_at_call
, 0, ira_allocnos_num
* sizeof (int));
1441 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
1442 process_bb_node_lives
);
1443 ira_max_point
= curr_point
;
1444 create_start_finish_chains ();
1445 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1446 print_live_ranges (ira_dump_file
);
1448 ira_free (allocno_saved_at_call
);
1449 sparseset_free (objects_live
);
1450 sparseset_free (allocnos_processed
);
1453 /* Compress allocno live ranges. */
1455 ira_compress_allocno_live_ranges (void)
1457 remove_some_program_points_and_update_live_ranges ();
1458 ira_rebuild_start_finish_chains ();
1459 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1461 fprintf (ira_dump_file
, "Ranges after the compression:\n");
1462 print_live_ranges (ira_dump_file
);
1466 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1468 ira_finish_allocno_live_ranges (void)
1470 ira_free (ira_finish_point_ranges
);
1471 ira_free (ira_start_point_ranges
);