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 /* Allocnos live at current point in the scan. */
72 static sparseset allocnos_live
;
74 /* Set of hard regs (except eliminable ones) currently live. */
75 static HARD_REG_SET hard_regs_live
;
77 /* The loop tree node corresponding to the current basic block. */
78 static ira_loop_tree_node_t curr_bb_node
;
80 /* The number of the last processed call. */
81 static int last_call_num
;
82 /* The number of last call at which given allocno was saved. */
83 static int *allocno_saved_at_call
;
85 /* Record the birth of hard register REGNO, updating hard_regs_live
86 and hard reg conflict information for living allocno. */
88 make_hard_regno_born (int regno
)
92 SET_HARD_REG_BIT (hard_regs_live
, regno
);
93 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
95 ira_allocno_t allocno
= ira_allocnos
[i
];
96 ira_object_t obj
= ALLOCNO_OBJECT (allocno
);
97 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj
), regno
);
98 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
);
102 /* Process the death of hard register REGNO. This updates
105 make_hard_regno_dead (int regno
)
107 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
110 /* Record the birth of allocno A, starting a new live range for
111 it if necessary, and updating hard reg conflict information. We also
112 record it in allocnos_live. */
114 make_allocno_born (ira_allocno_t a
)
116 live_range_t p
= ALLOCNO_LIVE_RANGES (a
);
117 ira_object_t obj
= ALLOCNO_OBJECT (a
);
119 sparseset_set_bit (allocnos_live
, ALLOCNO_NUM (a
));
120 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), hard_regs_live
);
121 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), hard_regs_live
);
124 || (p
->finish
!= curr_point
&& p
->finish
+ 1 != curr_point
))
125 ALLOCNO_LIVE_RANGES (a
)
126 = ira_create_allocno_live_range (a
, curr_point
, -1,
127 ALLOCNO_LIVE_RANGES (a
));
130 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A. */
132 update_allocno_pressure_excess_length (ira_allocno_t a
)
135 enum reg_class cover_class
, cl
;
138 cover_class
= ALLOCNO_COVER_CLASS (a
);
140 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
143 if (high_pressure_start_point
[cl
] < 0)
145 p
= ALLOCNO_LIVE_RANGES (a
);
146 ira_assert (p
!= NULL
);
147 start
= (high_pressure_start_point
[cl
] > p
->start
148 ? high_pressure_start_point
[cl
] : p
->start
);
149 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
153 /* Process the death of allocno A. This finishes the current live
156 make_allocno_dead (ira_allocno_t a
)
160 p
= ALLOCNO_LIVE_RANGES (a
);
161 ira_assert (p
!= NULL
);
162 p
->finish
= curr_point
;
163 update_allocno_pressure_excess_length (a
);
164 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (a
));
167 /* The current register pressures for each cover class for the current
169 static int curr_reg_pressure
[N_REG_CLASSES
];
171 /* Record that register pressure for COVER_CLASS increased by N
172 registers. Update the current register pressure, maximal register
173 pressure for the current BB and the start point of the register
176 inc_register_pressure (enum reg_class cover_class
, int n
)
182 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
185 curr_reg_pressure
[cl
] += n
;
186 if (high_pressure_start_point
[cl
] < 0
187 && (curr_reg_pressure
[cl
] > ira_available_class_regs
[cl
]))
188 high_pressure_start_point
[cl
] = curr_point
;
189 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
190 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
194 /* Record that register pressure for COVER_CLASS has decreased by
195 NREGS registers; update current register pressure, start point of
196 the register pressure excess, and register pressure excess length
197 for living allocnos. */
200 dec_register_pressure (enum reg_class cover_class
, int nregs
)
208 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
211 curr_reg_pressure
[cl
] -= nregs
;
212 ira_assert (curr_reg_pressure
[cl
] >= 0);
213 if (high_pressure_start_point
[cl
] >= 0
214 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
219 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, j
)
220 update_allocno_pressure_excess_length (ira_allocnos
[j
]);
222 (cl
= ira_reg_class_super_classes
[cover_class
][i
])
225 if (high_pressure_start_point
[cl
] >= 0
226 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
227 high_pressure_start_point
[cl
] = -1;
231 /* Mark the pseudo register REGNO as live. Update all information about
232 live ranges and register pressure. */
234 mark_pseudo_regno_live (int regno
)
236 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
243 /* Invalidate because it is referenced. */
244 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
246 if (sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
249 cl
= ALLOCNO_COVER_CLASS (a
);
250 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
251 inc_register_pressure (cl
, nregs
);
252 make_allocno_born (a
);
255 /* Mark the hard register REG as live. Store a 1 in hard_regs_live
256 for this register, record how many consecutive hardware registers
257 it actually needs. */
259 mark_hard_reg_live (rtx reg
)
261 int regno
= REGNO (reg
);
263 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
265 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
269 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
270 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
272 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
273 inc_register_pressure (cover_class
, 1);
274 make_hard_regno_born (regno
);
281 /* Mark the register referenced by use or def REF as live. */
283 mark_ref_live (df_ref ref
)
287 reg
= DF_REF_REG (ref
);
288 if (GET_CODE (reg
) == SUBREG
)
289 reg
= SUBREG_REG (reg
);
290 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
291 mark_pseudo_regno_live (REGNO (reg
));
293 mark_hard_reg_live (reg
);
296 /* Mark the pseudo register REGNO as dead. Update all information about
297 live ranges and register pressure. */
299 mark_pseudo_regno_dead (int regno
)
301 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
308 /* Invalidate because it is referenced. */
309 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
311 if (! sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
314 cl
= ALLOCNO_COVER_CLASS (a
);
315 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
316 dec_register_pressure (cl
, nregs
);
318 make_allocno_dead (a
);
321 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live
324 mark_hard_reg_dead (rtx reg
)
326 int regno
= REGNO (reg
);
328 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
330 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
334 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
336 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
337 dec_register_pressure (cover_class
, 1);
338 make_hard_regno_dead (regno
);
345 /* Mark the register referenced by definition DEF as dead, if the
346 definition is a total one. */
348 mark_ref_dead (df_ref def
)
352 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
353 || DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
356 reg
= DF_REF_REG (def
);
357 if (GET_CODE (reg
) == SUBREG
)
358 reg
= SUBREG_REG (reg
);
359 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
360 mark_pseudo_regno_dead (REGNO (reg
));
362 mark_hard_reg_dead (reg
);
365 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
366 class is intersected with class CL. Advance the current program
367 point before making the conflict if ADVANCE_P. Return TRUE if we
368 will need to advance the current program point. */
370 make_pseudo_conflict (rtx reg
, enum reg_class cl
, rtx dreg
, bool advance_p
)
374 if (GET_CODE (reg
) == SUBREG
)
375 reg
= SUBREG_REG (reg
);
377 if (! REG_P (reg
) || REGNO (reg
) < FIRST_PSEUDO_REGISTER
)
380 a
= ira_curr_regno_allocno_map
[REGNO (reg
)];
381 if (! reg_classes_intersect_p (cl
, ALLOCNO_COVER_CLASS (a
)))
387 mark_pseudo_regno_live (REGNO (reg
));
388 mark_pseudo_regno_live (REGNO (dreg
));
389 mark_pseudo_regno_dead (REGNO (reg
));
390 mark_pseudo_regno_dead (REGNO (dreg
));
395 /* Check and make if necessary conflicts for pseudo DREG of class
396 DEF_CL of the current insn with input operand USE of class USE_CL.
397 Advance the current program point before making the conflict if
398 ADVANCE_P. Return TRUE if we will need to advance the current
401 check_and_make_def_use_conflict (rtx dreg
, enum reg_class def_cl
,
402 int use
, enum reg_class use_cl
,
405 if (! reg_classes_intersect_p (def_cl
, use_cl
))
408 advance_p
= make_pseudo_conflict (recog_data
.operand
[use
],
409 use_cl
, dreg
, advance_p
);
410 /* Reload may end up swapping commutative operands, so you
411 have to take both orderings into account. The
412 constraints for the two operands can be completely
413 different. (Indeed, if the constraints for the two
414 operands are the same for all alternatives, there's no
415 point marking them as commutative.) */
416 if (use
< recog_data
.n_operands
- 1
417 && recog_data
.constraints
[use
][0] == '%')
419 = make_pseudo_conflict (recog_data
.operand
[use
+ 1],
420 use_cl
, dreg
, advance_p
);
422 && recog_data
.constraints
[use
- 1][0] == '%')
424 = make_pseudo_conflict (recog_data
.operand
[use
- 1],
425 use_cl
, dreg
, advance_p
);
429 /* Check and make if necessary conflicts for definition DEF of class
430 DEF_CL of the current insn with input operands. Process only
431 constraints of alternative ALT. */
433 check_and_make_def_conflict (int alt
, int def
, enum reg_class def_cl
)
437 enum reg_class use_cl
, acl
;
439 rtx dreg
= recog_data
.operand
[def
];
441 if (def_cl
== NO_REGS
)
444 if (GET_CODE (dreg
) == SUBREG
)
445 dreg
= SUBREG_REG (dreg
);
447 if (! REG_P (dreg
) || REGNO (dreg
) < FIRST_PSEUDO_REGISTER
)
450 a
= ira_curr_regno_allocno_map
[REGNO (dreg
)];
451 acl
= ALLOCNO_COVER_CLASS (a
);
452 if (! reg_classes_intersect_p (acl
, def_cl
))
457 for (use
= 0; use
< recog_data
.n_operands
; use
++)
461 if (use
== def
|| recog_data
.operand_type
[use
] == OP_OUT
)
464 if (recog_op_alt
[use
][alt
].anything_ok
)
467 use_cl
= recog_op_alt
[use
][alt
].cl
;
469 /* If there's any alternative that allows USE to match DEF, do not
470 record a conflict. If that causes us to create an invalid
471 instruction due to the earlyclobber, reload must fix it up. */
472 for (alt1
= 0; alt1
< recog_data
.n_alternatives
; alt1
++)
473 if (recog_op_alt
[use
][alt1
].matches
== def
474 || (use
< recog_data
.n_operands
- 1
475 && recog_data
.constraints
[use
][0] == '%'
476 && recog_op_alt
[use
+ 1][alt1
].matches
== def
)
478 && recog_data
.constraints
[use
- 1][0] == '%'
479 && recog_op_alt
[use
- 1][alt1
].matches
== def
))
482 if (alt1
< recog_data
.n_alternatives
)
485 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
488 if ((use_match
= recog_op_alt
[use
][alt
].matches
) >= 0)
490 if (use_match
== def
)
493 if (recog_op_alt
[use_match
][alt
].anything_ok
)
496 use_cl
= recog_op_alt
[use_match
][alt
].cl
;
497 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
503 /* Make conflicts of early clobber pseudo registers of the current
504 insn with its inputs. Avoid introducing unnecessary conflicts by
505 checking classes of the constraints and pseudos because otherwise
506 significant code degradation is possible for some targets. */
508 make_early_clobber_and_input_conflicts (void)
512 enum reg_class def_cl
;
514 for (alt
= 0; alt
< recog_data
.n_alternatives
; alt
++)
515 for (def
= 0; def
< recog_data
.n_operands
; def
++)
518 if (recog_op_alt
[def
][alt
].earlyclobber
)
520 if (recog_op_alt
[def
][alt
].anything_ok
)
523 def_cl
= recog_op_alt
[def
][alt
].cl
;
524 check_and_make_def_conflict (alt
, def
, def_cl
);
526 if ((def_match
= recog_op_alt
[def
][alt
].matches
) >= 0
527 && (recog_op_alt
[def_match
][alt
].earlyclobber
528 || recog_op_alt
[def
][alt
].earlyclobber
))
530 if (recog_op_alt
[def_match
][alt
].anything_ok
)
533 def_cl
= recog_op_alt
[def_match
][alt
].cl
;
534 check_and_make_def_conflict (alt
, def
, def_cl
);
539 /* Mark early clobber hard registers of the current INSN as live (if
540 LIVE_P) or dead. Return true if there are such registers. */
542 mark_hard_reg_early_clobbers (rtx insn
, bool live_p
)
547 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
548 if (DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MUST_CLOBBER
))
550 rtx dreg
= DF_REF_REG (*def_rec
);
552 if (GET_CODE (dreg
) == SUBREG
)
553 dreg
= SUBREG_REG (dreg
);
554 if (! REG_P (dreg
) || REGNO (dreg
) >= FIRST_PSEUDO_REGISTER
)
557 /* Hard register clobbers are believed to be early clobber
558 because there is no way to say that non-operand hard
559 register clobbers are not early ones. */
561 mark_ref_live (*def_rec
);
563 mark_ref_dead (*def_rec
);
570 /* Checks that CONSTRAINTS permits to use only one hard register. If
571 it is so, the function returns the class of the hard register.
572 Otherwise it returns NO_REGS. */
573 static enum reg_class
574 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
577 enum reg_class cl
, next_cl
;
581 for (ignore_p
= false;
583 constraints
+= CONSTRAINT_LEN (c
, constraints
))
603 || (equiv_const
!= NULL_RTX
&& CONSTANT_P (equiv_const
)))
609 || (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE (op
) == VOIDmode
)
610 || (equiv_const
!= NULL_RTX
611 && (CONST_INT_P (equiv_const
)
612 || (GET_CODE (equiv_const
) == CONST_DOUBLE
613 && GET_MODE (equiv_const
) == VOIDmode
))))
618 if ((CONSTANT_P (op
) && !CONST_INT_P (op
)
619 && (GET_CODE (op
) != CONST_DOUBLE
|| GET_MODE (op
) != VOIDmode
))
620 || (equiv_const
!= NULL_RTX
621 && CONSTANT_P (equiv_const
)
622 && !CONST_INT_P (equiv_const
)
623 && (GET_CODE (equiv_const
) != CONST_DOUBLE
624 || GET_MODE (equiv_const
) != VOIDmode
)))
636 if ((CONST_INT_P (op
)
637 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, constraints
))
638 || (equiv_const
!= NULL_RTX
639 && CONST_INT_P (equiv_const
)
640 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const
),
647 if (GET_CODE (op
) == CONST_DOUBLE
648 || (GET_CODE (op
) == CONST_VECTOR
649 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
)
650 || (equiv_const
!= NULL_RTX
651 && (GET_CODE (equiv_const
) == CONST_DOUBLE
652 || (GET_CODE (equiv_const
) == CONST_VECTOR
653 && (GET_MODE_CLASS (GET_MODE (equiv_const
))
654 == MODE_VECTOR_FLOAT
)))))
660 if ((GET_CODE (op
) == CONST_DOUBLE
661 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, constraints
))
662 || (equiv_const
!= NULL_RTX
663 && GET_CODE (equiv_const
) == CONST_DOUBLE
664 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const
,
667 /* ??? what about memory */
669 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
670 case 'h': case 'j': case 'k': case 'l':
671 case 'q': case 't': case 'u':
672 case 'v': case 'w': case 'x': case 'y': case 'z':
673 case 'A': case 'B': case 'C': case 'D':
674 case 'Q': case 'R': case 'S': case 'T': case 'U':
675 case 'W': case 'Y': case 'Z':
678 : REG_CLASS_FROM_CONSTRAINT (c
, constraints
));
679 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
680 || (ira_available_class_regs
[next_cl
]
681 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
686 case '0': case '1': case '2': case '3': case '4':
687 case '5': case '6': case '7': case '8': case '9':
689 = single_reg_class (recog_data
.constraints
[c
- '0'],
690 recog_data
.operand
[c
- '0'], NULL_RTX
);
691 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
692 || next_cl
== NO_REGS
693 || (ira_available_class_regs
[next_cl
]
694 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
705 /* The function checks that operand OP_NUM of the current insn can use
706 only one hard register. If it is so, the function returns the
707 class of the hard register. Otherwise it returns NO_REGS. */
708 static enum reg_class
709 single_reg_operand_class (int op_num
)
711 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
713 return single_reg_class (recog_data
.constraints
[op_num
],
714 recog_data
.operand
[op_num
], NULL_RTX
);
717 /* The function sets up hard register set *SET to hard registers which
718 might be used by insn reloads because the constraints are too
721 ira_implicitly_set_insn_hard_regs (HARD_REG_SET
*set
)
727 enum machine_mode mode
;
729 CLEAR_HARD_REG_SET (*set
);
730 for (i
= 0; i
< recog_data
.n_operands
; i
++)
732 op
= recog_data
.operand
[i
];
734 if (GET_CODE (op
) == SUBREG
)
735 op
= SUBREG_REG (op
);
737 if (GET_CODE (op
) == SCRATCH
738 || (REG_P (op
) && (regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
))
740 const char *p
= recog_data
.constraints
[i
];
742 mode
= (GET_CODE (op
) == SCRATCH
743 ? GET_MODE (op
) : PSEUDO_REGNO_MODE (regno
));
745 for (ignore_p
= false; (c
= *p
); p
+= CONSTRAINT_LEN (c
, p
))
754 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
755 case 'h': case 'j': case 'k': case 'l':
756 case 'q': case 't': case 'u':
757 case 'v': case 'w': case 'x': case 'y': case 'z':
758 case 'A': case 'B': case 'C': case 'D':
759 case 'Q': case 'R': case 'S': case 'T': case 'U':
760 case 'W': case 'Y': case 'Z':
763 : REG_CLASS_FROM_CONSTRAINT (c
, p
));
765 /* There is no register pressure problem if all of the
766 regs in this class are fixed. */
767 && ira_available_class_regs
[cl
] != 0
768 && (ira_available_class_regs
[cl
]
769 <= ira_reg_class_nregs
[cl
][mode
]))
770 IOR_HARD_REG_SET (*set
, reg_class_contents
[cl
]);
776 /* Processes input operands, if IN_P, or output operands otherwise of
777 the current insn with FREQ to find allocno which can use only one
778 hard register and makes other currently living allocnos conflicting
779 with the hard register. */
781 process_single_reg_class_operands (bool in_p
, int freq
)
787 ira_allocno_t operand_a
, a
;
789 for (i
= 0; i
< recog_data
.n_operands
; i
++)
791 operand
= recog_data
.operand
[i
];
792 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
793 && recog_data
.operand_type
[i
] != OP_INOUT
)
795 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
796 && recog_data
.operand_type
[i
] != OP_INOUT
)
798 cl
= single_reg_operand_class (i
);
804 if (GET_CODE (operand
) == SUBREG
)
805 operand
= SUBREG_REG (operand
);
808 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
810 enum machine_mode mode
;
811 enum reg_class cover_class
;
813 operand_a
= ira_curr_regno_allocno_map
[regno
];
814 mode
= ALLOCNO_MODE (operand_a
);
815 cover_class
= ALLOCNO_COVER_CLASS (operand_a
);
816 if (ira_class_subset_p
[cl
][cover_class
]
817 && ira_class_hard_regs_num
[cl
] != 0
818 && (ira_class_hard_reg_index
[cover_class
]
819 [ira_class_hard_regs
[cl
][0]]) >= 0
820 && reg_class_size
[cl
] <= (unsigned) CLASS_MAX_NREGS (cl
, mode
))
826 ? ira_get_register_move_cost (mode
, cover_class
, cl
)
827 : ira_get_register_move_cost (mode
, cl
, cover_class
)));
828 ira_allocate_and_set_costs
829 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
), cover_class
, 0);
830 size
= ira_reg_class_nregs
[cover_class
][mode
];
831 for (i
= 0; i
< size
; i
++)
832 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
833 [ira_class_hard_reg_index
834 [cover_class
][ira_class_hard_regs
[cl
][i
]]]
839 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
841 a
= ira_allocnos
[px
];
844 ira_object_t obj
= ALLOCNO_OBJECT (a
);
846 /* We could increase costs of A instead of making it
847 conflicting with the hard register. But it works worse
848 because it will be spilled in reload in anyway. */
849 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
850 reg_class_contents
[cl
]);
851 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
852 reg_class_contents
[cl
]);
858 /* Return true when one of the predecessor edges of BB is marked with
859 EDGE_ABNORMAL_CALL or EDGE_EH. */
861 bb_has_abnormal_call_pred (basic_block bb
)
866 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
868 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
874 /* Process insns of the basic block given by its LOOP_TREE_NODE to
875 update allocno live ranges, allocno hard register conflicts,
876 intersected calls, and register pressure info for allocnos for the
877 basic block for and regions containing the basic block. */
879 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
890 bb
= loop_tree_node
->bb
;
893 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
895 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
896 high_pressure_start_point
[ira_reg_class_cover
[i
]] = -1;
898 curr_bb_node
= loop_tree_node
;
899 reg_live_out
= DF_LR_OUT (bb
);
900 sparseset_clear (allocnos_live
);
901 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
902 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
903 AND_COMPL_HARD_REG_SET (hard_regs_live
, ira_no_alloc_regs
);
904 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
905 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
907 enum reg_class cover_class
, cl
;
909 cover_class
= ira_class_translate
[REGNO_REG_CLASS (i
)];
911 (cl
= ira_reg_class_super_classes
[cover_class
][j
])
915 curr_reg_pressure
[cl
]++;
916 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
917 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
918 ira_assert (curr_reg_pressure
[cl
]
919 <= ira_available_class_regs
[cl
]);
922 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
923 mark_pseudo_regno_live (j
);
925 freq
= REG_FREQ_FROM_BB (bb
);
929 /* Invalidate all allocno_saved_at_call entries. */
932 /* Scan the code of this basic block, noting which allocnos and
933 hard regs are born or die.
935 Note that this loop treats uninitialized values as live until
936 the beginning of the block. For example, if an instruction
937 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
938 set, FOO will remain live until the beginning of the block.
939 Likewise if FOO is not set at all. This is unnecessarily
940 pessimistic, but it probably doesn't matter much in practice. */
941 FOR_BB_INSNS_REVERSE (bb
, insn
)
943 df_ref
*def_rec
, *use_rec
;
946 if (!NONDEBUG_INSN_P (insn
))
949 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
950 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
951 INSN_UID (insn
), loop_tree_node
->parent
->loop
->num
,
954 /* Mark each defined value as live. We need to do this for
955 unused values because they still conflict with quantities
956 that are live at the time of the definition.
958 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
959 references represent the effect of the called function
960 on a call-clobbered register. Marking the register as
961 live would stop us from allocating it to a call-crossing
963 call_p
= CALL_P (insn
);
964 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
965 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
966 mark_ref_live (*def_rec
);
968 /* If INSN has multiple outputs, then any value used in one
969 of the outputs conflicts with the other outputs. Model this
970 by making the used value live during the output phase.
972 It is unsafe to use !single_set here since it will ignore
973 an unused output. Just because an output is unused does
974 not mean the compiler can assume the side effect will not
975 occur. Consider if ALLOCNO appears in the address of an
976 output and we reload the output. If we allocate ALLOCNO
977 to the same hard register as an unused output we could
978 set the hard register before the output reload insn. */
979 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
980 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
985 reg
= DF_REF_REG (*use_rec
);
986 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
990 set
= XVECEXP (PATTERN (insn
), 0, i
);
991 if (GET_CODE (set
) == SET
992 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
994 /* After the previous loop, this is a no-op if
995 REG is contained within SET_DEST (SET). */
996 mark_ref_live (*use_rec
);
1002 extract_insn (insn
);
1003 preprocess_constraints ();
1004 process_single_reg_class_operands (false, freq
);
1006 /* See which defined values die here. */
1007 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1008 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1009 mark_ref_dead (*def_rec
);
1014 /* The current set of live allocnos are live across the call. */
1015 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
1017 ira_allocno_t a
= ira_allocnos
[i
];
1019 if (allocno_saved_at_call
[i
] != last_call_num
)
1020 /* Here we are mimicking caller-save.c behaviour
1021 which does not save hard register at a call if
1022 it was saved on previous call in the same basic
1023 block and the hard register was not mentioned
1024 between the two calls. */
1025 ALLOCNO_CALL_FREQ (a
) += freq
;
1026 /* Mark it as saved at the next call. */
1027 allocno_saved_at_call
[i
] = last_call_num
+ 1;
1028 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
1029 /* Don't allocate allocnos that cross setjmps or any
1030 call, if this function receives a nonlocal
1032 if (cfun
->has_nonlocal_label
1033 || find_reg_note (insn
, REG_SETJMP
,
1034 NULL_RTX
) != NULL_RTX
)
1036 ira_object_t obj
= ALLOCNO_OBJECT (a
);
1037 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
));
1038 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1040 if (can_throw_internal (insn
))
1042 ira_object_t obj
= ALLOCNO_OBJECT (a
);
1043 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
1045 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
1051 make_early_clobber_and_input_conflicts ();
1055 /* Mark each used value as live. */
1056 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1057 mark_ref_live (*use_rec
);
1059 process_single_reg_class_operands (true, freq
);
1061 set_p
= mark_hard_reg_early_clobbers (insn
, true);
1065 mark_hard_reg_early_clobbers (insn
, false);
1067 /* Mark each hard reg as live again. For example, a
1068 hard register can be in clobber and in an insn
1070 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1072 rtx ureg
= DF_REF_REG (*use_rec
);
1074 if (GET_CODE (ureg
) == SUBREG
)
1075 ureg
= SUBREG_REG (ureg
);
1076 if (! REG_P (ureg
) || REGNO (ureg
) >= FIRST_PSEUDO_REGISTER
)
1079 mark_ref_live (*use_rec
);
1086 #ifdef EH_RETURN_DATA_REGNO
1087 if (bb_has_eh_pred (bb
))
1090 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1091 if (regno
== INVALID_REGNUM
)
1093 make_hard_regno_born (regno
);
1097 /* Allocnos can't go in stack regs at the start of a basic block
1098 that is reached by an abnormal edge. Likewise for call
1099 clobbered regs, because caller-save, fixup_abnormal_edges and
1100 possibly the table driven EH machinery are not quite ready to
1101 handle such allocnos live across such edges. */
1102 if (bb_has_abnormal_pred (bb
))
1105 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
1107 ALLOCNO_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
1108 ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
1110 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1111 make_hard_regno_born (px
);
1113 /* No need to record conflicts for call clobbered regs if we
1114 have nonlocal labels around, as we don't ever try to
1115 allocate such regs in this case. */
1116 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
1117 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
1118 if (call_used_regs
[px
])
1119 make_hard_regno_born (px
);
1122 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
1123 make_allocno_dead (ira_allocnos
[i
]);
1128 /* Propagate register pressure to upper loop tree nodes: */
1129 if (loop_tree_node
!= ira_loop_tree_root
)
1130 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1132 enum reg_class cover_class
;
1134 cover_class
= ira_reg_class_cover
[i
];
1135 if (loop_tree_node
->reg_pressure
[cover_class
]
1136 > loop_tree_node
->parent
->reg_pressure
[cover_class
])
1137 loop_tree_node
->parent
->reg_pressure
[cover_class
]
1138 = loop_tree_node
->reg_pressure
[cover_class
];
1142 /* Create and set up IRA_START_POINT_RANGES and
1143 IRA_FINISH_POINT_RANGES. */
1145 create_start_finish_chains (void)
1148 ira_allocno_iterator ai
;
1151 ira_start_point_ranges
1152 = (live_range_t
*) ira_allocate (ira_max_point
1153 * sizeof (live_range_t
));
1154 memset (ira_start_point_ranges
, 0,
1155 ira_max_point
* sizeof (live_range_t
));
1156 ira_finish_point_ranges
1157 = (live_range_t
*) ira_allocate (ira_max_point
1158 * sizeof (live_range_t
));
1159 memset (ira_finish_point_ranges
, 0,
1160 ira_max_point
* sizeof (live_range_t
));
1161 FOR_EACH_ALLOCNO (a
, ai
)
1163 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1165 r
->start_next
= ira_start_point_ranges
[r
->start
];
1166 ira_start_point_ranges
[r
->start
] = r
;
1167 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
1168 ira_finish_point_ranges
[r
->finish
] = r
;
1173 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1174 new live ranges and program points were added as a result if new
1177 ira_rebuild_start_finish_chains (void)
1179 ira_free (ira_finish_point_ranges
);
1180 ira_free (ira_start_point_ranges
);
1181 create_start_finish_chains ();
1184 /* Compress allocno live ranges by removing program points where
1187 remove_some_program_points_and_update_live_ranges (void)
1193 ira_allocno_iterator ai
;
1195 bitmap born_or_died
;
1198 born_or_died
= ira_allocate_bitmap ();
1199 FOR_EACH_ALLOCNO (a
, ai
)
1201 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1203 ira_assert (r
->start
<= r
->finish
);
1204 bitmap_set_bit (born_or_died
, r
->start
);
1205 bitmap_set_bit (born_or_died
, r
->finish
);
1208 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1210 EXECUTE_IF_SET_IN_BITMAP(born_or_died
, 0, i
, bi
)
1214 ira_free_bitmap (born_or_died
);
1215 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1216 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1217 ira_max_point
, n
, 100 * n
/ ira_max_point
);
1219 FOR_EACH_ALLOCNO (a
, ai
)
1221 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1223 r
->start
= map
[r
->start
];
1224 r
->finish
= map
[r
->finish
];
1230 /* Print live ranges R to file F. */
1232 ira_print_live_range_list (FILE *f
, live_range_t r
)
1234 for (; r
!= NULL
; r
= r
->next
)
1235 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1239 /* Print live ranges R to stderr. */
1241 ira_debug_live_range_list (live_range_t r
)
1243 ira_print_live_range_list (stderr
, r
);
1246 /* Print live ranges of allocno A to file F. */
1248 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
1250 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1251 ira_print_live_range_list (f
, ALLOCNO_LIVE_RANGES (a
));
1254 /* Print live ranges of allocno A to stderr. */
1256 ira_debug_allocno_live_ranges (ira_allocno_t a
)
1258 print_allocno_live_ranges (stderr
, a
);
1261 /* Print live ranges of all allocnos to file F. */
1263 print_live_ranges (FILE *f
)
1266 ira_allocno_iterator ai
;
1268 FOR_EACH_ALLOCNO (a
, ai
)
1269 print_allocno_live_ranges (f
, a
);
1272 /* Print live ranges of all allocnos to stderr. */
1274 ira_debug_live_ranges (void)
1276 print_live_ranges (stderr
);
1279 /* The main entry function creates live ranges, set up
1280 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1281 calculate register pressure info. */
1283 ira_create_allocno_live_ranges (void)
1285 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
1288 allocno_saved_at_call
1289 = (int *) ira_allocate (ira_allocnos_num
* sizeof (int));
1290 memset (allocno_saved_at_call
, 0, ira_allocnos_num
* sizeof (int));
1291 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
1292 process_bb_node_lives
);
1293 ira_max_point
= curr_point
;
1294 create_start_finish_chains ();
1295 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1296 print_live_ranges (ira_dump_file
);
1298 ira_free (allocno_saved_at_call
);
1299 sparseset_free (allocnos_live
);
1302 /* Compress allocno live ranges. */
1304 ira_compress_allocno_live_ranges (void)
1306 remove_some_program_points_and_update_live_ranges ();
1307 ira_rebuild_start_finish_chains ();
1308 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1310 fprintf (ira_dump_file
, "Ranges after the compression:\n");
1311 print_live_ranges (ira_dump_file
);
1315 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1317 ira_finish_allocno_live_ranges (void)
1319 ira_free (ira_finish_point_ranges
);
1320 ira_free (ira_start_point_ranges
);