1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "insn-config.h"
39 #include "sparseset.h"
42 /* The code in this file is similar to one in global but the code
43 works on the allocno basis and creates live ranges instead of
44 pseudo-register conflicts. */
46 /* Program points are enumerated by numbers from range
47 0..IRA_MAX_POINT-1. There are approximately two times more program
48 points than insns. Program points are places in the program where
49 liveness info can be changed. In most general case (there are more
50 complicated cases too) some program points correspond to places
51 where input operand dies and other ones correspond to places where
52 output operands are born. */
55 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
56 live ranges with given start/finish point. */
57 live_range_t
*ira_start_point_ranges
, *ira_finish_point_ranges
;
59 /* Number of the current program point. */
60 static int curr_point
;
62 /* Point where register pressure excess started or -1 if there is no
63 register pressure excess. Excess pressure for a register class at
64 some point means that there are more allocnos of given register
65 class living at the point than number of hard-registers of the
66 class available for the allocation. It is defined only for cover
68 static int high_pressure_start_point
[N_REG_CLASSES
];
70 /* Allocnos live at current point in the scan. */
71 static sparseset allocnos_live
;
73 /* Set of hard regs (except eliminable ones) currently live. */
74 static HARD_REG_SET hard_regs_live
;
76 /* The loop tree node corresponding to the current basic block. */
77 static ira_loop_tree_node_t curr_bb_node
;
79 /* The number of the last processed call. */
80 static int last_call_num
;
81 /* The number of last call at which given allocno was saved. */
82 static int *allocno_saved_at_call
;
84 /* Record the birth of hard register REGNO, updating hard_regs_live
85 and hard reg conflict information for living allocno. */
87 make_hard_regno_born (int regno
)
91 SET_HARD_REG_BIT (hard_regs_live
, regno
);
92 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
94 SET_HARD_REG_BIT (ALLOCNO_CONFLICT_HARD_REGS (ira_allocnos
[i
]),
96 SET_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (ira_allocnos
[i
]),
101 /* Process the death of hard register REGNO. This updates
104 make_hard_regno_dead (int regno
)
106 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
109 /* Record the birth of allocno A, starting a new live range for
110 it if necessary, and updating hard reg conflict information. We also
111 record it in allocnos_live. */
113 make_allocno_born (ira_allocno_t a
)
115 live_range_t p
= ALLOCNO_LIVE_RANGES (a
);
117 sparseset_set_bit (allocnos_live
, ALLOCNO_NUM (a
));
118 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
), hard_regs_live
);
119 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), hard_regs_live
);
122 || (p
->finish
!= curr_point
&& p
->finish
+ 1 != curr_point
))
123 ALLOCNO_LIVE_RANGES (a
)
124 = ira_create_allocno_live_range (a
, curr_point
, -1,
125 ALLOCNO_LIVE_RANGES (a
));
128 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A. */
130 update_allocno_pressure_excess_length (ira_allocno_t a
)
133 enum reg_class cover_class
, cl
;
136 cover_class
= ALLOCNO_COVER_CLASS (a
);
138 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
141 if (high_pressure_start_point
[cl
] < 0)
143 p
= ALLOCNO_LIVE_RANGES (a
);
144 ira_assert (p
!= NULL
);
145 start
= (high_pressure_start_point
[cl
] > p
->start
146 ? high_pressure_start_point
[cl
] : p
->start
);
147 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
151 /* Process the death of allocno A. This finishes the current live
154 make_allocno_dead (ira_allocno_t a
)
158 p
= ALLOCNO_LIVE_RANGES (a
);
159 ira_assert (p
!= NULL
);
160 p
->finish
= curr_point
;
161 update_allocno_pressure_excess_length (a
);
162 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (a
));
165 /* The current register pressures for each cover class for the current
167 static int curr_reg_pressure
[N_REG_CLASSES
];
169 /* Record that register pressure for COVER_CLASS increased by N
170 registers. Update the current register pressure, maximal register
171 pressure for the current BB and the start point of the register
174 inc_register_pressure (enum reg_class cover_class
, int n
)
180 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
183 curr_reg_pressure
[cl
] += n
;
184 if (high_pressure_start_point
[cl
] < 0
185 && (curr_reg_pressure
[cl
] > ira_available_class_regs
[cl
]))
186 high_pressure_start_point
[cl
] = curr_point
;
187 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
188 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
192 /* Record that register pressure for COVER_CLASS has decreased by
193 NREGS registers; update current register pressure, start point of
194 the register pressure excess, and register pressure excess length
195 for living allocnos. */
198 dec_register_pressure (enum reg_class cover_class
, int nregs
)
206 (cl
= ira_reg_class_super_classes
[cover_class
][i
]) != LIM_REG_CLASSES
;
209 curr_reg_pressure
[cl
] -= nregs
;
210 ira_assert (curr_reg_pressure
[cl
] >= 0);
211 if (high_pressure_start_point
[cl
] >= 0
212 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
217 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, j
)
218 update_allocno_pressure_excess_length (ira_allocnos
[j
]);
220 (cl
= ira_reg_class_super_classes
[cover_class
][i
])
223 if (high_pressure_start_point
[cl
] >= 0
224 && curr_reg_pressure
[cl
] <= ira_available_class_regs
[cl
])
225 high_pressure_start_point
[cl
] = -1;
229 /* Mark the pseudo register REGNO as live. Update all information about
230 live ranges and register pressure. */
232 mark_pseudo_regno_live (int regno
)
234 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
241 /* Invalidate because it is referenced. */
242 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
244 if (sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
247 cl
= ALLOCNO_COVER_CLASS (a
);
248 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
249 inc_register_pressure (cl
, nregs
);
250 make_allocno_born (a
);
253 /* Mark the hard register REG as live. Store a 1 in hard_regs_live
254 for this register, record how many consecutive hardware registers
255 it actually needs. */
257 mark_hard_reg_live (rtx reg
)
259 int regno
= REGNO (reg
);
261 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
263 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
267 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
268 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
270 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
271 inc_register_pressure (cover_class
, 1);
272 make_hard_regno_born (regno
);
279 /* Mark the register referenced by use or def REF as live. */
281 mark_ref_live (df_ref ref
)
285 reg
= DF_REF_REG (ref
);
286 if (GET_CODE (reg
) == SUBREG
)
287 reg
= SUBREG_REG (reg
);
288 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
289 mark_pseudo_regno_live (REGNO (reg
));
291 mark_hard_reg_live (reg
);
294 /* Mark the pseudo register REGNO as dead. Update all information about
295 live ranges and register pressure. */
297 mark_pseudo_regno_dead (int regno
)
299 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
306 /* Invalidate because it is referenced. */
307 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
309 if (! sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
312 cl
= ALLOCNO_COVER_CLASS (a
);
313 nregs
= ira_reg_class_nregs
[cl
][ALLOCNO_MODE (a
)];
314 dec_register_pressure (cl
, nregs
);
316 make_allocno_dead (a
);
319 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live
322 mark_hard_reg_dead (rtx reg
)
324 int regno
= REGNO (reg
);
326 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
328 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
332 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
334 enum reg_class cover_class
= ira_hard_regno_cover_class
[regno
];
335 dec_register_pressure (cover_class
, 1);
336 make_hard_regno_dead (regno
);
343 /* Mark the register referenced by definition DEF as dead, if the
344 definition is a total one. */
346 mark_ref_dead (df_ref def
)
350 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
351 || DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
354 reg
= DF_REF_REG (def
);
355 if (GET_CODE (reg
) == SUBREG
)
356 reg
= SUBREG_REG (reg
);
357 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
358 mark_pseudo_regno_dead (REGNO (reg
));
360 mark_hard_reg_dead (reg
);
363 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
364 class is intersected with class CL. Advance the current program
365 point before making the conflict if ADVANCE_P. Return TRUE if we
366 will need to advance the current program point. */
368 make_pseudo_conflict (rtx reg
, enum reg_class cl
, rtx dreg
, bool advance_p
)
372 if (GET_CODE (reg
) == SUBREG
)
373 reg
= SUBREG_REG (reg
);
375 if (! REG_P (reg
) || REGNO (reg
) < FIRST_PSEUDO_REGISTER
)
378 a
= ira_curr_regno_allocno_map
[REGNO (reg
)];
379 if (! reg_classes_intersect_p (cl
, ALLOCNO_COVER_CLASS (a
)))
385 mark_pseudo_regno_live (REGNO (reg
));
386 mark_pseudo_regno_live (REGNO (dreg
));
387 mark_pseudo_regno_dead (REGNO (reg
));
388 mark_pseudo_regno_dead (REGNO (dreg
));
393 /* Check and make if necessary conflicts for pseudo DREG of class
394 DEF_CL of the current insn with input operand USE of class USE_CL.
395 Advance the current program point before making the conflict if
396 ADVANCE_P. Return TRUE if we will need to advance the current
399 check_and_make_def_use_conflict (rtx dreg
, enum reg_class def_cl
,
400 int use
, enum reg_class use_cl
,
403 if (! reg_classes_intersect_p (def_cl
, use_cl
))
406 advance_p
= make_pseudo_conflict (recog_data
.operand
[use
],
407 use_cl
, dreg
, advance_p
);
408 /* Reload may end up swapping commutative operands, so you
409 have to take both orderings into account. The
410 constraints for the two operands can be completely
411 different. (Indeed, if the constraints for the two
412 operands are the same for all alternatives, there's no
413 point marking them as commutative.) */
414 if (use
< recog_data
.n_operands
- 1
415 && recog_data
.constraints
[use
][0] == '%')
417 = make_pseudo_conflict (recog_data
.operand
[use
+ 1],
418 use_cl
, dreg
, advance_p
);
420 && recog_data
.constraints
[use
- 1][0] == '%')
422 = make_pseudo_conflict (recog_data
.operand
[use
- 1],
423 use_cl
, dreg
, advance_p
);
427 /* Check and make if necessary conflicts for definition DEF of class
428 DEF_CL of the current insn with input operands. Process only
429 constraints of alternative ALT. */
431 check_and_make_def_conflict (int alt
, int def
, enum reg_class def_cl
)
435 enum reg_class use_cl
, acl
;
437 rtx dreg
= recog_data
.operand
[def
];
439 if (def_cl
== NO_REGS
)
442 if (GET_CODE (dreg
) == SUBREG
)
443 dreg
= SUBREG_REG (dreg
);
445 if (! REG_P (dreg
) || REGNO (dreg
) < FIRST_PSEUDO_REGISTER
)
448 a
= ira_curr_regno_allocno_map
[REGNO (dreg
)];
449 acl
= ALLOCNO_COVER_CLASS (a
);
450 if (! reg_classes_intersect_p (acl
, def_cl
))
455 for (use
= 0; use
< recog_data
.n_operands
; use
++)
459 if (use
== def
|| recog_data
.operand_type
[use
] == OP_OUT
)
462 if (recog_op_alt
[use
][alt
].anything_ok
)
465 use_cl
= recog_op_alt
[use
][alt
].cl
;
467 /* If there's any alternative that allows USE to match DEF, do not
468 record a conflict. If that causes us to create an invalid
469 instruction due to the earlyclobber, reload must fix it up. */
470 for (alt1
= 0; alt1
< recog_data
.n_alternatives
; alt1
++)
471 if (recog_op_alt
[use
][alt1
].matches
== def
472 || (use
< recog_data
.n_operands
- 1
473 && recog_data
.constraints
[use
][0] == '%'
474 && recog_op_alt
[use
+ 1][alt1
].matches
== def
)
476 && recog_data
.constraints
[use
- 1][0] == '%'
477 && recog_op_alt
[use
- 1][alt1
].matches
== def
))
480 if (alt1
< recog_data
.n_alternatives
)
483 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
486 if ((use_match
= recog_op_alt
[use
][alt
].matches
) >= 0)
488 if (use_match
== def
)
491 if (recog_op_alt
[use_match
][alt
].anything_ok
)
494 use_cl
= recog_op_alt
[use_match
][alt
].cl
;
495 advance_p
= check_and_make_def_use_conflict (dreg
, def_cl
, use
,
501 /* Make conflicts of early clobber pseudo registers of the current
502 insn with its inputs. Avoid introducing unnecessary conflicts by
503 checking classes of the constraints and pseudos because otherwise
504 significant code degradation is possible for some targets. */
506 make_early_clobber_and_input_conflicts (void)
510 enum reg_class def_cl
;
512 for (alt
= 0; alt
< recog_data
.n_alternatives
; alt
++)
513 for (def
= 0; def
< recog_data
.n_operands
; def
++)
516 if (recog_op_alt
[def
][alt
].earlyclobber
)
518 if (recog_op_alt
[def
][alt
].anything_ok
)
521 def_cl
= recog_op_alt
[def
][alt
].cl
;
522 check_and_make_def_conflict (alt
, def
, def_cl
);
524 if ((def_match
= recog_op_alt
[def
][alt
].matches
) >= 0
525 && (recog_op_alt
[def_match
][alt
].earlyclobber
526 || recog_op_alt
[def
][alt
].earlyclobber
))
528 if (recog_op_alt
[def_match
][alt
].anything_ok
)
531 def_cl
= recog_op_alt
[def_match
][alt
].cl
;
532 check_and_make_def_conflict (alt
, def
, def_cl
);
537 /* Mark early clobber hard registers of the current INSN as live (if
538 LIVE_P) or dead. Return true if there are such registers. */
540 mark_hard_reg_early_clobbers (rtx insn
, bool live_p
)
545 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
546 if (DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MUST_CLOBBER
))
548 rtx dreg
= DF_REF_REG (*def_rec
);
550 if (GET_CODE (dreg
) == SUBREG
)
551 dreg
= SUBREG_REG (dreg
);
552 if (! REG_P (dreg
) || REGNO (dreg
) >= FIRST_PSEUDO_REGISTER
)
555 /* Hard register clobbers are believed to be early clobber
556 because there is no way to say that non-operand hard
557 register clobbers are not early ones. */
559 mark_ref_live (*def_rec
);
561 mark_ref_dead (*def_rec
);
568 /* Checks that CONSTRAINTS permits to use only one hard register. If
569 it is so, the function returns the class of the hard register.
570 Otherwise it returns NO_REGS. */
571 static enum reg_class
572 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
575 enum reg_class cl
, next_cl
;
579 for (ignore_p
= false;
581 constraints
+= CONSTRAINT_LEN (c
, constraints
))
601 || (equiv_const
!= NULL_RTX
&& CONSTANT_P (equiv_const
)))
607 || (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE (op
) == VOIDmode
)
608 || (equiv_const
!= NULL_RTX
609 && (CONST_INT_P (equiv_const
)
610 || (GET_CODE (equiv_const
) == CONST_DOUBLE
611 && GET_MODE (equiv_const
) == VOIDmode
))))
616 if ((CONSTANT_P (op
) && !CONST_INT_P (op
)
617 && (GET_CODE (op
) != CONST_DOUBLE
|| GET_MODE (op
) != VOIDmode
))
618 || (equiv_const
!= NULL_RTX
619 && CONSTANT_P (equiv_const
)
620 && !CONST_INT_P (equiv_const
)
621 && (GET_CODE (equiv_const
) != CONST_DOUBLE
622 || GET_MODE (equiv_const
) != VOIDmode
)))
634 if ((CONST_INT_P (op
)
635 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, constraints
))
636 || (equiv_const
!= NULL_RTX
637 && CONST_INT_P (equiv_const
)
638 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const
),
645 if (GET_CODE (op
) == CONST_DOUBLE
646 || (GET_CODE (op
) == CONST_VECTOR
647 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
)
648 || (equiv_const
!= NULL_RTX
649 && (GET_CODE (equiv_const
) == CONST_DOUBLE
650 || (GET_CODE (equiv_const
) == CONST_VECTOR
651 && (GET_MODE_CLASS (GET_MODE (equiv_const
))
652 == MODE_VECTOR_FLOAT
)))))
658 if ((GET_CODE (op
) == CONST_DOUBLE
659 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, constraints
))
660 || (equiv_const
!= NULL_RTX
661 && GET_CODE (equiv_const
) == CONST_DOUBLE
662 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const
,
665 /* ??? what about memory */
667 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
668 case 'h': case 'j': case 'k': case 'l':
669 case 'q': case 't': case 'u':
670 case 'v': case 'w': case 'x': case 'y': case 'z':
671 case 'A': case 'B': case 'C': case 'D':
672 case 'Q': case 'R': case 'S': case 'T': case 'U':
673 case 'W': case 'Y': case 'Z':
676 : REG_CLASS_FROM_CONSTRAINT (c
, constraints
));
677 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
678 || (ira_available_class_regs
[next_cl
]
679 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
684 case '0': case '1': case '2': case '3': case '4':
685 case '5': case '6': case '7': case '8': case '9':
687 = single_reg_class (recog_data
.constraints
[c
- '0'],
688 recog_data
.operand
[c
- '0'], NULL_RTX
);
689 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
690 || next_cl
== NO_REGS
691 || (ira_available_class_regs
[next_cl
]
692 > ira_reg_class_nregs
[next_cl
][GET_MODE (op
)]))
703 /* The function checks that operand OP_NUM of the current insn can use
704 only one hard register. If it is so, the function returns the
705 class of the hard register. Otherwise it returns NO_REGS. */
706 static enum reg_class
707 single_reg_operand_class (int op_num
)
709 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
711 return single_reg_class (recog_data
.constraints
[op_num
],
712 recog_data
.operand
[op_num
], NULL_RTX
);
715 /* The function sets up hard register set *SET to hard registers which
716 might be used by insn reloads because the constraints are too
719 ira_implicitly_set_insn_hard_regs (HARD_REG_SET
*set
)
725 enum machine_mode mode
;
727 CLEAR_HARD_REG_SET (*set
);
728 for (i
= 0; i
< recog_data
.n_operands
; i
++)
730 op
= recog_data
.operand
[i
];
732 if (GET_CODE (op
) == SUBREG
)
733 op
= SUBREG_REG (op
);
735 if (GET_CODE (op
) == SCRATCH
736 || (REG_P (op
) && (regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
))
738 const char *p
= recog_data
.constraints
[i
];
740 mode
= (GET_CODE (op
) == SCRATCH
741 ? GET_MODE (op
) : PSEUDO_REGNO_MODE (regno
));
743 for (ignore_p
= false; (c
= *p
); p
+= CONSTRAINT_LEN (c
, p
))
752 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
753 case 'h': case 'j': case 'k': case 'l':
754 case 'q': case 't': case 'u':
755 case 'v': case 'w': case 'x': case 'y': case 'z':
756 case 'A': case 'B': case 'C': case 'D':
757 case 'Q': case 'R': case 'S': case 'T': case 'U':
758 case 'W': case 'Y': case 'Z':
761 : REG_CLASS_FROM_CONSTRAINT (c
, p
));
763 /* There is no register pressure problem if all of the
764 regs in this class are fixed. */
765 && ira_available_class_regs
[cl
] != 0
766 && (ira_available_class_regs
[cl
]
767 <= ira_reg_class_nregs
[cl
][mode
]))
768 IOR_HARD_REG_SET (*set
, reg_class_contents
[cl
]);
774 /* Processes input operands, if IN_P, or output operands otherwise of
775 the current insn with FREQ to find allocno which can use only one
776 hard register and makes other currently living allocnos conflicting
777 with the hard register. */
779 process_single_reg_class_operands (bool in_p
, int freq
)
785 ira_allocno_t operand_a
, a
;
787 for (i
= 0; i
< recog_data
.n_operands
; i
++)
789 operand
= recog_data
.operand
[i
];
790 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
791 && recog_data
.operand_type
[i
] != OP_INOUT
)
793 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
794 && recog_data
.operand_type
[i
] != OP_INOUT
)
796 cl
= single_reg_operand_class (i
);
802 if (GET_CODE (operand
) == SUBREG
)
803 operand
= SUBREG_REG (operand
);
806 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
808 enum machine_mode mode
;
809 enum reg_class cover_class
;
811 operand_a
= ira_curr_regno_allocno_map
[regno
];
812 mode
= ALLOCNO_MODE (operand_a
);
813 cover_class
= ALLOCNO_COVER_CLASS (operand_a
);
814 if (ira_class_subset_p
[cl
][cover_class
]
815 && ira_class_hard_regs_num
[cl
] != 0
816 && (ira_class_hard_reg_index
[cover_class
]
817 [ira_class_hard_regs
[cl
][0]]) >= 0
818 && reg_class_size
[cl
] <= (unsigned) CLASS_MAX_NREGS (cl
, mode
))
824 ? ira_get_register_move_cost (mode
, cover_class
, cl
)
825 : ira_get_register_move_cost (mode
, cl
, cover_class
)));
826 ira_allocate_and_set_costs
827 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
), cover_class
, 0);
828 size
= ira_reg_class_nregs
[cover_class
][mode
];
829 for (i
= 0; i
< size
; i
++)
830 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
831 [ira_class_hard_reg_index
832 [cover_class
][ira_class_hard_regs
[cl
][i
]]]
837 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
839 a
= ira_allocnos
[px
];
842 /* We could increase costs of A instead of making it
843 conflicting with the hard register. But it works worse
844 because it will be spilled in reload in anyway. */
845 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
846 reg_class_contents
[cl
]);
847 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
848 reg_class_contents
[cl
]);
854 /* Return true when one of the predecessor edges of BB is marked with
855 EDGE_ABNORMAL_CALL or EDGE_EH. */
857 bb_has_abnormal_call_pred (basic_block bb
)
862 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
864 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
870 /* Process insns of the basic block given by its LOOP_TREE_NODE to
871 update allocno live ranges, allocno hard register conflicts,
872 intersected calls, and register pressure info for allocnos for the
873 basic block for and regions containing the basic block. */
875 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
886 bb
= loop_tree_node
->bb
;
889 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
891 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
892 high_pressure_start_point
[ira_reg_class_cover
[i
]] = -1;
894 curr_bb_node
= loop_tree_node
;
895 reg_live_out
= DF_LR_OUT (bb
);
896 sparseset_clear (allocnos_live
);
897 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
898 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
899 AND_COMPL_HARD_REG_SET (hard_regs_live
, ira_no_alloc_regs
);
900 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
901 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
903 enum reg_class cover_class
, cl
;
905 cover_class
= ira_class_translate
[REGNO_REG_CLASS (i
)];
907 (cl
= ira_reg_class_super_classes
[cover_class
][j
])
911 curr_reg_pressure
[cl
]++;
912 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
913 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
914 ira_assert (curr_reg_pressure
[cl
]
915 <= ira_available_class_regs
[cl
]);
918 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
919 mark_pseudo_regno_live (j
);
921 freq
= REG_FREQ_FROM_BB (bb
);
925 /* Invalidate all allocno_saved_at_call entries. */
928 /* Scan the code of this basic block, noting which allocnos and
929 hard regs are born or die.
931 Note that this loop treats uninitialized values as live until
932 the beginning of the block. For example, if an instruction
933 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
934 set, FOO will remain live until the beginning of the block.
935 Likewise if FOO is not set at all. This is unnecessarily
936 pessimistic, but it probably doesn't matter much in practice. */
937 FOR_BB_INSNS_REVERSE (bb
, insn
)
939 df_ref
*def_rec
, *use_rec
;
942 if (!NONDEBUG_INSN_P (insn
))
945 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
946 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
947 INSN_UID (insn
), loop_tree_node
->parent
->loop
->num
,
950 /* Mark each defined value as live. We need to do this for
951 unused values because they still conflict with quantities
952 that are live at the time of the definition.
954 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
955 references represent the effect of the called function
956 on a call-clobbered register. Marking the register as
957 live would stop us from allocating it to a call-crossing
959 call_p
= CALL_P (insn
);
960 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
961 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
962 mark_ref_live (*def_rec
);
964 /* If INSN has multiple outputs, then any value used in one
965 of the outputs conflicts with the other outputs. Model this
966 by making the used value live during the output phase.
968 It is unsafe to use !single_set here since it will ignore
969 an unused output. Just because an output is unused does
970 not mean the compiler can assume the side effect will not
971 occur. Consider if ALLOCNO appears in the address of an
972 output and we reload the output. If we allocate ALLOCNO
973 to the same hard register as an unused output we could
974 set the hard register before the output reload insn. */
975 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
976 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
981 reg
= DF_REF_REG (*use_rec
);
982 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
986 set
= XVECEXP (PATTERN (insn
), 0, i
);
987 if (GET_CODE (set
) == SET
988 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
990 /* After the previous loop, this is a no-op if
991 REG is contained within SET_DEST (SET). */
992 mark_ref_live (*use_rec
);
999 preprocess_constraints ();
1000 process_single_reg_class_operands (false, freq
);
1002 /* See which defined values die here. */
1003 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1004 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
1005 mark_ref_dead (*def_rec
);
1010 /* The current set of live allocnos are live across the call. */
1011 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
1013 ira_allocno_t a
= ira_allocnos
[i
];
1015 if (allocno_saved_at_call
[i
] != last_call_num
)
1016 /* Here we are mimicking caller-save.c behaviour
1017 which does not save hard register at a call if
1018 it was saved on previous call in the same basic
1019 block and the hard register was not mentioned
1020 between the two calls. */
1021 ALLOCNO_CALL_FREQ (a
) += freq
;
1022 /* Mark it as saved at the next call. */
1023 allocno_saved_at_call
[i
] = last_call_num
+ 1;
1024 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
1025 /* Don't allocate allocnos that cross setjmps or any
1026 call, if this function receives a nonlocal
1028 if (cfun
->has_nonlocal_label
1029 || find_reg_note (insn
, REG_SETJMP
,
1030 NULL_RTX
) != NULL_RTX
)
1032 SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
));
1033 SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1035 if (can_throw_internal (insn
))
1037 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
1039 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
1045 make_early_clobber_and_input_conflicts ();
1049 /* Mark each used value as live. */
1050 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1051 mark_ref_live (*use_rec
);
1053 process_single_reg_class_operands (true, freq
);
1055 set_p
= mark_hard_reg_early_clobbers (insn
, true);
1059 mark_hard_reg_early_clobbers (insn
, false);
1061 /* Mark each hard reg as live again. For example, a
1062 hard register can be in clobber and in an insn
1064 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
1066 rtx ureg
= DF_REF_REG (*use_rec
);
1068 if (GET_CODE (ureg
) == SUBREG
)
1069 ureg
= SUBREG_REG (ureg
);
1070 if (! REG_P (ureg
) || REGNO (ureg
) >= FIRST_PSEUDO_REGISTER
)
1073 mark_ref_live (*use_rec
);
1080 #ifdef EH_RETURN_DATA_REGNO
1081 if (bb_has_eh_pred (bb
))
1084 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1085 if (regno
== INVALID_REGNUM
)
1087 make_hard_regno_born (regno
);
1091 /* Allocnos can't go in stack regs at the start of a basic block
1092 that is reached by an abnormal edge. Likewise for call
1093 clobbered regs, because caller-save, fixup_abnormal_edges and
1094 possibly the table driven EH machinery are not quite ready to
1095 handle such allocnos live across such edges. */
1096 if (bb_has_abnormal_pred (bb
))
1099 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
1101 ALLOCNO_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
1102 ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
1104 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1105 make_hard_regno_born (px
);
1107 /* No need to record conflicts for call clobbered regs if we
1108 have nonlocal labels around, as we don't ever try to
1109 allocate such regs in this case. */
1110 if (!cfun
->has_nonlocal_label
&& bb_has_abnormal_call_pred (bb
))
1111 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
1112 if (call_used_regs
[px
])
1113 make_hard_regno_born (px
);
1116 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
1117 make_allocno_dead (ira_allocnos
[i
]);
1122 /* Propagate register pressure to upper loop tree nodes: */
1123 if (loop_tree_node
!= ira_loop_tree_root
)
1124 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1126 enum reg_class cover_class
;
1128 cover_class
= ira_reg_class_cover
[i
];
1129 if (loop_tree_node
->reg_pressure
[cover_class
]
1130 > loop_tree_node
->parent
->reg_pressure
[cover_class
])
1131 loop_tree_node
->parent
->reg_pressure
[cover_class
]
1132 = loop_tree_node
->reg_pressure
[cover_class
];
1136 /* Create and set up IRA_START_POINT_RANGES and
1137 IRA_FINISH_POINT_RANGES. */
1139 create_start_finish_chains (void)
1142 ira_allocno_iterator ai
;
1145 ira_start_point_ranges
1146 = (live_range_t
*) ira_allocate (ira_max_point
1147 * sizeof (live_range_t
));
1148 memset (ira_start_point_ranges
, 0,
1149 ira_max_point
* sizeof (live_range_t
));
1150 ira_finish_point_ranges
1151 = (live_range_t
*) ira_allocate (ira_max_point
1152 * sizeof (live_range_t
));
1153 memset (ira_finish_point_ranges
, 0,
1154 ira_max_point
* sizeof (live_range_t
));
1155 FOR_EACH_ALLOCNO (a
, ai
)
1157 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1159 r
->start_next
= ira_start_point_ranges
[r
->start
];
1160 ira_start_point_ranges
[r
->start
] = r
;
1161 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
1162 ira_finish_point_ranges
[r
->finish
] = r
;
1167 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1168 new live ranges and program points were added as a result if new
1171 ira_rebuild_start_finish_chains (void)
1173 ira_free (ira_finish_point_ranges
);
1174 ira_free (ira_start_point_ranges
);
1175 create_start_finish_chains ();
1178 /* Compress allocno live ranges by removing program points where
1181 remove_some_program_points_and_update_live_ranges (void)
1187 ira_allocno_iterator ai
;
1189 bitmap born_or_died
;
1192 born_or_died
= ira_allocate_bitmap ();
1193 FOR_EACH_ALLOCNO (a
, ai
)
1195 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1197 ira_assert (r
->start
<= r
->finish
);
1198 bitmap_set_bit (born_or_died
, r
->start
);
1199 bitmap_set_bit (born_or_died
, r
->finish
);
1202 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1204 EXECUTE_IF_SET_IN_BITMAP(born_or_died
, 0, i
, bi
)
1208 ira_free_bitmap (born_or_died
);
1209 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1210 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1211 ira_max_point
, n
, 100 * n
/ ira_max_point
);
1213 FOR_EACH_ALLOCNO (a
, ai
)
1215 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1217 r
->start
= map
[r
->start
];
1218 r
->finish
= map
[r
->finish
];
1224 /* Print live ranges R to file F. */
1226 ira_print_live_range_list (FILE *f
, live_range_t r
)
1228 for (; r
!= NULL
; r
= r
->next
)
1229 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1233 /* Print live ranges R to stderr. */
1235 ira_debug_live_range_list (live_range_t r
)
1237 ira_print_live_range_list (stderr
, r
);
1240 /* Print live ranges of allocno A to file F. */
1242 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
1244 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1245 ira_print_live_range_list (f
, ALLOCNO_LIVE_RANGES (a
));
1248 /* Print live ranges of allocno A to stderr. */
1250 ira_debug_allocno_live_ranges (ira_allocno_t a
)
1252 print_allocno_live_ranges (stderr
, a
);
1255 /* Print live ranges of all allocnos to file F. */
1257 print_live_ranges (FILE *f
)
1260 ira_allocno_iterator ai
;
1262 FOR_EACH_ALLOCNO (a
, ai
)
1263 print_allocno_live_ranges (f
, a
);
1266 /* Print live ranges of all allocnos to stderr. */
1268 ira_debug_live_ranges (void)
1270 print_live_ranges (stderr
);
1273 /* The main entry function creates live ranges, set up
1274 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1275 calculate register pressure info. */
1277 ira_create_allocno_live_ranges (void)
1279 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
1282 allocno_saved_at_call
1283 = (int *) ira_allocate (ira_allocnos_num
* sizeof (int));
1284 memset (allocno_saved_at_call
, 0, ira_allocnos_num
* sizeof (int));
1285 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
1286 process_bb_node_lives
);
1287 ira_max_point
= curr_point
;
1288 create_start_finish_chains ();
1289 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1290 print_live_ranges (ira_dump_file
);
1292 ira_free (allocno_saved_at_call
);
1293 sparseset_free (allocnos_live
);
1296 /* Compress allocno live ranges. */
1298 ira_compress_allocno_live_ranges (void)
1300 remove_some_program_points_and_update_live_ranges ();
1301 ira_rebuild_start_finish_chains ();
1302 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1304 fprintf (ira_dump_file
, "Ranges after the compression:\n");
1305 print_live_ranges (ira_dump_file
);
1309 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1311 ira_finish_allocno_live_ranges (void)
1313 ira_free (ira_finish_point_ranges
);
1314 ira_free (ira_start_point_ranges
);