1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
31 #include "insn-config.h"
35 #include "sparseset.h"
37 /* The code in this file is similar to one in global but the code
38 works on the allocno basis and creates live ranges instead of
39 pseudo-register conflicts. */
41 /* Program points are enumerated by numbers from range
42 0..IRA_MAX_POINT-1. There are approximately two times more program
43 points than insns. Program points are places in the program where
44 liveness info can be changed. In most general case (there are more
45 complicated cases too) some program points correspond to places
46 where input operand dies and other ones correspond to places where
47 output operands are born. */
50 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
51 live ranges with given start/finish point. */
52 live_range_t
*ira_start_point_ranges
, *ira_finish_point_ranges
;
54 /* Number of the current program point. */
55 static int curr_point
;
57 /* Point where register pressure excess started or -1 if there is no
58 register pressure excess. Excess pressure for a register class at
59 some point means that there are more allocnos of given register
60 class living at the point than number of hard-registers of the
61 class available for the allocation. It is defined only for
63 static int high_pressure_start_point
[N_REG_CLASSES
];
65 /* Objects live at current point in the scan. */
66 static sparseset objects_live
;
68 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
70 static sparseset allocnos_processed
;
72 /* Set of hard regs (except eliminable ones) currently live. */
73 static HARD_REG_SET hard_regs_live
;
75 /* The loop tree node corresponding to the current basic block. */
76 static ira_loop_tree_node_t curr_bb_node
;
78 /* The number of the last processed call. */
79 static int last_call_num
;
80 /* The number of last call at which given allocno was saved. */
81 static int *allocno_saved_at_call
;
83 /* The value returned by ira_setup_alts for the current instruction;
84 i.e. the set of alternatives that we should consider to be likely
85 candidates during reloading. */
86 static alternative_mask preferred_alternatives
;
88 /* If non-NULL, the source operand of a register to register copy for which
89 we should not add a conflict with the copy's destination operand. */
90 static rtx ignore_reg_for_conflicts
;
92 /* Record hard register REGNO as now being live. */
94 make_hard_regno_live (int regno
)
96 SET_HARD_REG_BIT (hard_regs_live
, regno
);
99 /* Process the definition of hard register REGNO. This updates
100 hard_regs_live and hard reg conflict information for living allocnos. */
102 make_hard_regno_dead (int regno
)
105 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
107 ira_object_t obj
= ira_object_id_map
[i
];
109 if (ignore_reg_for_conflicts
!= NULL_RTX
110 && REGNO (ignore_reg_for_conflicts
)
111 == (unsigned int) ALLOCNO_REGNO (OBJECT_ALLOCNO (obj
)))
114 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj
), regno
);
115 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
);
117 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
120 /* Record object OBJ as now being live. Set a bit for it in objects_live,
121 and start a new live range for it if necessary. */
123 make_object_live (ira_object_t obj
)
125 sparseset_set_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
127 live_range_t lr
= OBJECT_LIVE_RANGES (obj
);
129 || (lr
->finish
!= curr_point
&& lr
->finish
+ 1 != curr_point
))
130 ira_add_live_range_to_object (obj
, curr_point
, -1);
133 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
134 associated with object OBJ. */
136 update_allocno_pressure_excess_length (ira_object_t obj
)
138 ira_allocno_t a
= OBJECT_ALLOCNO (obj
);
140 enum reg_class aclass
, pclass
, cl
;
143 aclass
= ALLOCNO_CLASS (a
);
144 pclass
= ira_pressure_class_translate
[aclass
];
146 (cl
= ira_reg_class_super_classes
[pclass
][i
]) != LIM_REG_CLASSES
;
149 if (! ira_reg_pressure_class_p
[cl
])
151 if (high_pressure_start_point
[cl
] < 0)
153 p
= OBJECT_LIVE_RANGES (obj
);
154 ira_assert (p
!= NULL
);
155 start
= (high_pressure_start_point
[cl
] > p
->start
156 ? high_pressure_start_point
[cl
] : p
->start
);
157 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
161 /* Process the definition of object OBJ, which is associated with allocno A.
162 This finishes the current live range for it. */
164 make_object_dead (ira_object_t obj
)
168 int ignore_regno
= -1;
169 int ignore_total_regno
= -1;
172 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
174 /* Check whether any part of IGNORE_REG_FOR_CONFLICTS already conflicts
176 if (ignore_reg_for_conflicts
!= NULL_RTX
177 && REGNO (ignore_reg_for_conflicts
) < FIRST_PSEUDO_REGISTER
)
179 end_regno
= END_REGNO (ignore_reg_for_conflicts
);
180 ignore_regno
= ignore_total_regno
= REGNO (ignore_reg_for_conflicts
);
182 for (regno
= ignore_regno
; regno
< end_regno
; regno
++)
184 if (TEST_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj
), regno
))
185 ignore_regno
= end_regno
;
186 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
187 ignore_total_regno
= end_regno
;
191 OBJECT_CONFLICT_HARD_REGS (obj
) |= hard_regs_live
;
192 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= hard_regs_live
;
194 /* If IGNORE_REG_FOR_CONFLICTS did not already conflict with OBJ, make
195 sure it still doesn't. */
196 for (regno
= ignore_regno
; regno
< end_regno
; regno
++)
197 CLEAR_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj
), regno
);
198 for (regno
= ignore_total_regno
; regno
< end_regno
; regno
++)
199 CLEAR_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
);
201 lr
= OBJECT_LIVE_RANGES (obj
);
202 ira_assert (lr
!= NULL
);
203 lr
->finish
= curr_point
;
204 update_allocno_pressure_excess_length (obj
);
207 /* The current register pressures for each pressure class for the current
209 static int curr_reg_pressure
[N_REG_CLASSES
];
211 /* Record that register pressure for PCLASS increased by N registers.
212 Update the current register pressure, maximal register pressure for
213 the current BB and the start point of the register pressure
216 inc_register_pressure (enum reg_class pclass
, int n
)
222 (cl
= ira_reg_class_super_classes
[pclass
][i
]) != LIM_REG_CLASSES
;
225 if (! ira_reg_pressure_class_p
[cl
])
227 curr_reg_pressure
[cl
] += n
;
228 if (high_pressure_start_point
[cl
] < 0
229 && (curr_reg_pressure
[cl
] > ira_class_hard_regs_num
[cl
]))
230 high_pressure_start_point
[cl
] = curr_point
;
231 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
232 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
236 /* Record that register pressure for PCLASS has decreased by NREGS
237 registers; update current register pressure, start point of the
238 register pressure excess, and register pressure excess length for
242 dec_register_pressure (enum reg_class pclass
, int nregs
)
250 (cl
= ira_reg_class_super_classes
[pclass
][i
]) != LIM_REG_CLASSES
;
253 if (! ira_reg_pressure_class_p
[cl
])
255 curr_reg_pressure
[cl
] -= nregs
;
256 ira_assert (curr_reg_pressure
[cl
] >= 0);
257 if (high_pressure_start_point
[cl
] >= 0
258 && curr_reg_pressure
[cl
] <= ira_class_hard_regs_num
[cl
])
263 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, j
)
264 update_allocno_pressure_excess_length (ira_object_id_map
[j
]);
266 (cl
= ira_reg_class_super_classes
[pclass
][i
]) != LIM_REG_CLASSES
;
269 if (! ira_reg_pressure_class_p
[cl
])
271 if (high_pressure_start_point
[cl
] >= 0
272 && curr_reg_pressure
[cl
] <= ira_class_hard_regs_num
[cl
])
273 high_pressure_start_point
[cl
] = -1;
278 /* Determine from the objects_live bitmap whether REGNO is currently live,
279 and occupies only one object. Return false if we have no information. */
281 pseudo_regno_single_word_and_live_p (int regno
)
283 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
288 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
291 obj
= ALLOCNO_OBJECT (a
, 0);
293 return sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
));
296 /* Mark the pseudo register REGNO as live. Update all information about
297 live ranges and register pressure. */
299 mark_pseudo_regno_live (int regno
)
301 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
302 enum reg_class pclass
;
308 /* Invalidate because it is referenced. */
309 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
311 n
= ALLOCNO_NUM_OBJECTS (a
);
312 pclass
= ira_pressure_class_translate
[ALLOCNO_CLASS (a
)];
313 nregs
= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
316 /* We track every subobject separately. */
317 gcc_assert (nregs
== n
);
321 for (i
= 0; i
< n
; i
++)
323 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
325 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
328 inc_register_pressure (pclass
, nregs
);
329 make_object_live (obj
);
333 /* Like mark_pseudo_regno_live, but try to only mark one subword of
334 the pseudo as live. SUBWORD indicates which; a value of 0
335 indicates the low part. */
337 mark_pseudo_regno_subword_live (int regno
, int subword
)
339 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
341 enum reg_class pclass
;
347 /* Invalidate because it is referenced. */
348 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
350 n
= ALLOCNO_NUM_OBJECTS (a
);
353 mark_pseudo_regno_live (regno
);
357 pclass
= ira_pressure_class_translate
[ALLOCNO_CLASS (a
)];
359 (n
== ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
360 obj
= ALLOCNO_OBJECT (a
, subword
);
362 if (sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
365 inc_register_pressure (pclass
, 1);
366 make_object_live (obj
);
369 /* Mark the register REG as live. Store a 1 in hard_regs_live for
370 this register, record how many consecutive hardware registers it
373 mark_hard_reg_live (rtx reg
)
375 int regno
= REGNO (reg
);
377 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
379 int last
= END_REGNO (reg
);
380 enum reg_class aclass
, pclass
;
384 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
385 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
387 aclass
= ira_hard_regno_allocno_class
[regno
];
388 pclass
= ira_pressure_class_translate
[aclass
];
389 inc_register_pressure (pclass
, 1);
390 make_hard_regno_live (regno
);
397 /* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's
398 register number; ORIG_REG is the access in the insn, which may be a
401 mark_pseudo_reg_live (rtx orig_reg
, unsigned regno
)
403 if (read_modify_subreg_p (orig_reg
))
405 mark_pseudo_regno_subword_live (regno
,
406 subreg_lowpart_p (orig_reg
) ? 0 : 1);
409 mark_pseudo_regno_live (regno
);
412 /* Mark the register referenced by use or def REF as live. */
414 mark_ref_live (df_ref ref
)
416 rtx reg
= DF_REF_REG (ref
);
419 if (GET_CODE (reg
) == SUBREG
)
420 reg
= SUBREG_REG (reg
);
422 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
423 mark_pseudo_reg_live (orig_reg
, REGNO (reg
));
425 mark_hard_reg_live (reg
);
428 /* Mark the pseudo register REGNO as dead. Update all information about
429 live ranges and register pressure. */
431 mark_pseudo_regno_dead (int regno
)
433 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
440 /* Invalidate because it is referenced. */
441 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
443 n
= ALLOCNO_NUM_OBJECTS (a
);
444 cl
= ira_pressure_class_translate
[ALLOCNO_CLASS (a
)];
445 nregs
= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
448 /* We track every subobject separately. */
449 gcc_assert (nregs
== n
);
452 for (i
= 0; i
< n
; i
++)
454 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
455 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
458 dec_register_pressure (cl
, nregs
);
459 make_object_dead (obj
);
463 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
464 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
466 mark_pseudo_regno_subword_dead (int regno
, int subword
)
468 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
476 /* Invalidate because it is referenced. */
477 allocno_saved_at_call
[ALLOCNO_NUM (a
)] = 0;
479 n
= ALLOCNO_NUM_OBJECTS (a
);
481 /* The allocno as a whole doesn't die in this case. */
484 cl
= ira_pressure_class_translate
[ALLOCNO_CLASS (a
)];
486 (n
== ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
488 obj
= ALLOCNO_OBJECT (a
, subword
);
489 if (!sparseset_bit_p (objects_live
, OBJECT_CONFLICT_ID (obj
)))
492 dec_register_pressure (cl
, 1);
493 make_object_dead (obj
);
496 /* Process the definition of hard register REG. This updates hard_regs_live
497 and hard reg conflict information for living allocnos. */
499 mark_hard_reg_dead (rtx reg
)
501 int regno
= REGNO (reg
);
503 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
505 int last
= END_REGNO (reg
);
506 enum reg_class aclass
, pclass
;
510 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
512 aclass
= ira_hard_regno_allocno_class
[regno
];
513 pclass
= ira_pressure_class_translate
[aclass
];
514 dec_register_pressure (pclass
, 1);
515 make_hard_regno_dead (regno
);
522 /* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's
523 register number; ORIG_REG is the access in the insn, which may be a
526 mark_pseudo_reg_dead (rtx orig_reg
, unsigned regno
)
528 if (read_modify_subreg_p (orig_reg
))
530 mark_pseudo_regno_subword_dead (regno
,
531 subreg_lowpart_p (orig_reg
) ? 0 : 1);
534 mark_pseudo_regno_dead (regno
);
537 /* Mark the register referenced by definition DEF as dead, if the
538 definition is a total one. */
540 mark_ref_dead (df_ref def
)
542 rtx reg
= DF_REF_REG (def
);
545 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
548 if (GET_CODE (reg
) == SUBREG
)
549 reg
= SUBREG_REG (reg
);
551 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
552 && (GET_CODE (orig_reg
) != SUBREG
553 || REGNO (reg
) < FIRST_PSEUDO_REGISTER
554 || !read_modify_subreg_p (orig_reg
)))
557 if (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
558 mark_pseudo_reg_dead (orig_reg
, REGNO (reg
));
560 mark_hard_reg_dead (reg
);
563 /* If REG is a pseudo or a subreg of it, and the class of its allocno
564 intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the
565 rtx actually accessed, it may be identical to DREG or a subreg of it.
566 Advance the current program point before making the conflict if
567 ADVANCE_P. Return TRUE if we will need to advance the current
570 make_pseudo_conflict (rtx reg
, enum reg_class cl
, rtx dreg
, rtx orig_dreg
,
576 if (GET_CODE (reg
) == SUBREG
)
577 reg
= SUBREG_REG (reg
);
579 if (! REG_P (reg
) || REGNO (reg
) < FIRST_PSEUDO_REGISTER
)
582 a
= ira_curr_regno_allocno_map
[REGNO (reg
)];
583 if (! reg_classes_intersect_p (cl
, ALLOCNO_CLASS (a
)))
589 mark_pseudo_reg_live (orig_reg
, REGNO (reg
));
590 mark_pseudo_reg_live (orig_dreg
, REGNO (dreg
));
591 mark_pseudo_reg_dead (orig_reg
, REGNO (reg
));
592 mark_pseudo_reg_dead (orig_dreg
, REGNO (dreg
));
597 /* Check and make if necessary conflicts for pseudo DREG of class
598 DEF_CL of the current insn with input operand USE of class USE_CL.
599 ORIG_DREG is the rtx actually accessed, it may be identical to
600 DREG or a subreg of it. Advance the current program point before
601 making the conflict if ADVANCE_P. Return TRUE if we will need to
602 advance the current program point. */
604 check_and_make_def_use_conflict (rtx dreg
, rtx orig_dreg
,
605 enum reg_class def_cl
, int use
,
606 enum reg_class use_cl
, bool advance_p
)
608 if (! reg_classes_intersect_p (def_cl
, use_cl
))
611 advance_p
= make_pseudo_conflict (recog_data
.operand
[use
],
612 use_cl
, dreg
, orig_dreg
, advance_p
);
614 /* Reload may end up swapping commutative operands, so you
615 have to take both orderings into account. The
616 constraints for the two operands can be completely
617 different. (Indeed, if the constraints for the two
618 operands are the same for all alternatives, there's no
619 point marking them as commutative.) */
620 if (use
< recog_data
.n_operands
- 1
621 && recog_data
.constraints
[use
][0] == '%')
623 = make_pseudo_conflict (recog_data
.operand
[use
+ 1],
624 use_cl
, dreg
, orig_dreg
, advance_p
);
626 && recog_data
.constraints
[use
- 1][0] == '%')
628 = make_pseudo_conflict (recog_data
.operand
[use
- 1],
629 use_cl
, dreg
, orig_dreg
, advance_p
);
633 /* Check and make if necessary conflicts for definition DEF of class
634 DEF_CL of the current insn with input operands. Process only
635 constraints of alternative ALT. */
637 check_and_make_def_conflict (int alt
, int def
, enum reg_class def_cl
)
641 enum reg_class use_cl
, acl
;
643 rtx dreg
= recog_data
.operand
[def
];
644 rtx orig_dreg
= dreg
;
646 if (def_cl
== NO_REGS
)
649 if (GET_CODE (dreg
) == SUBREG
)
650 dreg
= SUBREG_REG (dreg
);
652 if (! REG_P (dreg
) || REGNO (dreg
) < FIRST_PSEUDO_REGISTER
)
655 a
= ira_curr_regno_allocno_map
[REGNO (dreg
)];
656 acl
= ALLOCNO_CLASS (a
);
657 if (! reg_classes_intersect_p (acl
, def_cl
))
662 int n_operands
= recog_data
.n_operands
;
663 const operand_alternative
*op_alt
= &recog_op_alt
[alt
* n_operands
];
664 for (use
= 0; use
< n_operands
; use
++)
668 if (use
== def
|| recog_data
.operand_type
[use
] == OP_OUT
)
671 if (op_alt
[use
].anything_ok
)
674 use_cl
= op_alt
[use
].cl
;
676 /* If there's any alternative that allows USE to match DEF, do not
677 record a conflict. If that causes us to create an invalid
678 instruction due to the earlyclobber, reload must fix it up. */
679 for (alt1
= 0; alt1
< recog_data
.n_alternatives
; alt1
++)
681 if (!TEST_BIT (preferred_alternatives
, alt1
))
683 const operand_alternative
*op_alt1
684 = &recog_op_alt
[alt1
* n_operands
];
685 if (op_alt1
[use
].matches
== def
686 || (use
< n_operands
- 1
687 && recog_data
.constraints
[use
][0] == '%'
688 && op_alt1
[use
+ 1].matches
== def
)
690 && recog_data
.constraints
[use
- 1][0] == '%'
691 && op_alt1
[use
- 1].matches
== def
))
695 if (alt1
< recog_data
.n_alternatives
)
698 advance_p
= check_and_make_def_use_conflict (dreg
, orig_dreg
, def_cl
,
699 use
, use_cl
, advance_p
);
701 if ((use_match
= op_alt
[use
].matches
) >= 0)
703 if (use_match
== def
)
706 if (op_alt
[use_match
].anything_ok
)
709 use_cl
= op_alt
[use_match
].cl
;
710 advance_p
= check_and_make_def_use_conflict (dreg
, orig_dreg
, def_cl
,
711 use
, use_cl
, advance_p
);
716 /* Make conflicts of early clobber pseudo registers of the current
717 insn with its inputs. Avoid introducing unnecessary conflicts by
718 checking classes of the constraints and pseudos because otherwise
719 significant code degradation is possible for some targets. */
721 make_early_clobber_and_input_conflicts (void)
725 enum reg_class def_cl
;
727 int n_alternatives
= recog_data
.n_alternatives
;
728 int n_operands
= recog_data
.n_operands
;
729 const operand_alternative
*op_alt
= recog_op_alt
;
730 for (alt
= 0; alt
< n_alternatives
; alt
++, op_alt
+= n_operands
)
731 if (TEST_BIT (preferred_alternatives
, alt
))
732 for (def
= 0; def
< n_operands
; def
++)
735 if (op_alt
[def
].earlyclobber
)
737 if (op_alt
[def
].anything_ok
)
740 def_cl
= op_alt
[def
].cl
;
741 check_and_make_def_conflict (alt
, def
, def_cl
);
743 if ((def_match
= op_alt
[def
].matches
) >= 0
744 && (op_alt
[def_match
].earlyclobber
745 || op_alt
[def
].earlyclobber
))
747 if (op_alt
[def_match
].anything_ok
)
750 def_cl
= op_alt
[def_match
].cl
;
751 check_and_make_def_conflict (alt
, def
, def_cl
);
756 /* Mark early clobber hard registers of the current INSN as live (if
757 LIVE_P) or dead. Return true if there are such registers. */
759 mark_hard_reg_early_clobbers (rtx_insn
*insn
, bool live_p
)
764 FOR_EACH_INSN_DEF (def
, insn
)
765 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
))
767 rtx dreg
= DF_REF_REG (def
);
769 if (GET_CODE (dreg
) == SUBREG
)
770 dreg
= SUBREG_REG (dreg
);
771 if (! REG_P (dreg
) || REGNO (dreg
) >= FIRST_PSEUDO_REGISTER
)
774 /* Hard register clobbers are believed to be early clobber
775 because there is no way to say that non-operand hard
776 register clobbers are not early ones. */
787 /* Checks that CONSTRAINTS permits to use only one hard register. If
788 it is so, the function returns the class of the hard register.
789 Otherwise it returns NO_REGS. */
790 static enum reg_class
791 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
794 enum reg_class cl
, next_cl
;
795 enum constraint_num cn
;
798 alternative_mask preferred
= preferred_alternatives
;
799 for (; (c
= *constraints
); constraints
+= CONSTRAINT_LEN (c
, constraints
))
801 preferred
&= ~ALTERNATIVE_BIT (0);
804 else if (preferred
& 1)
811 /* ??? Is this the best way to handle memory constraints? */
812 cn
= lookup_constraint (constraints
);
813 if (insn_extra_memory_constraint (cn
)
814 || insn_extra_special_memory_constraint (cn
)
815 || insn_extra_address_constraint (cn
))
817 if (constraint_satisfied_p (op
, cn
)
818 || (equiv_const
!= NULL_RTX
819 && CONSTANT_P (equiv_const
)
820 && constraint_satisfied_p (equiv_const
, cn
)))
822 next_cl
= reg_class_for_constraint (cn
);
823 if (next_cl
== NO_REGS
)
826 ? ira_class_singleton
[next_cl
][GET_MODE (op
)] < 0
827 : (ira_class_singleton
[cl
][GET_MODE (op
)]
828 != ira_class_singleton
[next_cl
][GET_MODE (op
)]))
833 case '0': case '1': case '2': case '3': case '4':
834 case '5': case '6': case '7': case '8': case '9':
836 = single_reg_class (recog_data
.constraints
[c
- '0'],
837 recog_data
.operand
[c
- '0'], NULL_RTX
);
839 ? ira_class_singleton
[next_cl
][GET_MODE (op
)] < 0
840 : (ira_class_singleton
[cl
][GET_MODE (op
)]
841 != ira_class_singleton
[next_cl
][GET_MODE (op
)]))
849 /* The function checks that operand OP_NUM of the current insn can use
850 only one hard register. If it is so, the function returns the
851 class of the hard register. Otherwise it returns NO_REGS. */
852 static enum reg_class
853 single_reg_operand_class (int op_num
)
855 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
857 return single_reg_class (recog_data
.constraints
[op_num
],
858 recog_data
.operand
[op_num
], NULL_RTX
);
861 /* The function sets up hard register set *SET to hard registers which
862 might be used by insn reloads because the constraints are too
865 ira_implicitly_set_insn_hard_regs (HARD_REG_SET
*set
,
866 alternative_mask preferred
)
873 CLEAR_HARD_REG_SET (*set
);
874 for (i
= 0; i
< recog_data
.n_operands
; i
++)
876 op
= recog_data
.operand
[i
];
878 if (GET_CODE (op
) == SUBREG
)
879 op
= SUBREG_REG (op
);
881 if (GET_CODE (op
) == SCRATCH
882 || (REG_P (op
) && (regno
= REGNO (op
)) >= FIRST_PSEUDO_REGISTER
))
884 const char *p
= recog_data
.constraints
[i
];
886 mode
= (GET_CODE (op
) == SCRATCH
887 ? GET_MODE (op
) : PSEUDO_REGNO_MODE (regno
));
889 for (; (c
= *p
); p
+= CONSTRAINT_LEN (c
, p
))
891 preferred
&= ~ALTERNATIVE_BIT (0);
894 else if (preferred
& 1)
896 cl
= reg_class_for_constraint (lookup_constraint (p
));
899 /* There is no register pressure problem if all of the
900 regs in this class are fixed. */
901 int regno
= ira_class_singleton
[cl
][mode
];
903 add_to_hard_reg_set (set
, mode
, regno
);
909 /* Processes input operands, if IN_P, or output operands otherwise of
910 the current insn with FREQ to find allocno which can use only one
911 hard register and makes other currently living allocnos conflicting
912 with the hard register. */
914 process_single_reg_class_operands (bool in_p
, int freq
)
920 ira_allocno_t operand_a
, a
;
922 for (i
= 0; i
< recog_data
.n_operands
; i
++)
924 operand
= recog_data
.operand
[i
];
925 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
926 && recog_data
.operand_type
[i
] != OP_INOUT
)
928 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
929 && recog_data
.operand_type
[i
] != OP_INOUT
)
931 cl
= single_reg_operand_class (i
);
937 if (GET_CODE (operand
) == SUBREG
)
938 operand
= SUBREG_REG (operand
);
941 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
943 enum reg_class aclass
;
945 operand_a
= ira_curr_regno_allocno_map
[regno
];
946 aclass
= ALLOCNO_CLASS (operand_a
);
947 if (ira_class_subset_p
[cl
][aclass
])
949 /* View the desired allocation of OPERAND as:
955 (subreg:YMODE (reg:XMODE XREGNO) OFFSET). */
956 machine_mode ymode
, xmode
;
960 xmode
= recog_data
.operand_mode
[i
];
961 xregno
= ira_class_singleton
[cl
][xmode
];
962 gcc_assert (xregno
>= 0);
963 ymode
= ALLOCNO_MODE (operand_a
);
964 offset
= subreg_lowpart_offset (ymode
, xmode
);
965 yregno
= simplify_subreg_regno (xregno
, xmode
, offset
, ymode
);
967 && ira_class_hard_reg_index
[aclass
][yregno
] >= 0)
971 ira_allocate_and_set_costs
972 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
),
974 ira_init_register_move_cost_if_necessary (xmode
);
976 ? ira_register_move_cost
[xmode
][aclass
][cl
]
977 : ira_register_move_cost
[xmode
][cl
][aclass
]);
978 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
979 [ira_class_hard_reg_index
[aclass
][yregno
]] -= cost
;
984 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
986 ira_object_t obj
= ira_object_id_map
[px
];
987 a
= OBJECT_ALLOCNO (obj
);
990 /* We could increase costs of A instead of making it
991 conflicting with the hard register. But it works worse
992 because it will be spilled in reload in anyway. */
993 OBJECT_CONFLICT_HARD_REGS (obj
) |= reg_class_contents
[cl
];
994 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= reg_class_contents
[cl
];
1000 /* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if
1001 we find a SET rtx that we can use to deduce that a register can be cheaply
1002 caller-saved. Return such a register, or NULL_RTX if none is found. */
1004 find_call_crossed_cheap_reg (rtx_insn
*insn
)
1006 rtx cheap_reg
= NULL_RTX
;
1007 rtx exp
= CALL_INSN_FUNCTION_USAGE (insn
);
1011 rtx x
= XEXP (exp
, 0);
1012 if (GET_CODE (x
) == SET
)
1017 exp
= XEXP (exp
, 1);
1021 basic_block bb
= BLOCK_FOR_INSN (insn
);
1022 rtx reg
= SET_SRC (exp
);
1023 rtx_insn
*prev
= PREV_INSN (insn
);
1024 while (prev
&& !(INSN_P (prev
)
1025 && BLOCK_FOR_INSN (prev
) != bb
))
1027 if (NONDEBUG_INSN_P (prev
))
1029 rtx set
= single_set (prev
);
1031 if (set
&& rtx_equal_p (SET_DEST (set
), reg
))
1033 rtx src
= SET_SRC (set
);
1034 if (!REG_P (src
) || HARD_REGISTER_P (src
)
1035 || !pseudo_regno_single_word_and_live_p (REGNO (src
)))
1037 if (!modified_between_p (src
, prev
, insn
))
1041 if (set
&& rtx_equal_p (SET_SRC (set
), reg
))
1043 rtx dest
= SET_DEST (set
);
1044 if (!REG_P (dest
) || HARD_REGISTER_P (dest
)
1045 || !pseudo_regno_single_word_and_live_p (REGNO (dest
)))
1047 if (!modified_between_p (dest
, prev
, insn
))
1052 if (reg_set_p (reg
, prev
))
1055 prev
= PREV_INSN (prev
);
1061 /* Determine whether INSN is a register to register copy of the type where
1062 we do not need to make the source and destiniation registers conflict.
1063 If this is a copy instruction, then return the source reg. Otherwise,
1066 non_conflicting_reg_copy_p (rtx_insn
*insn
)
1068 /* Reload has issues with overlapping pseudos being assigned to the
1069 same hard register, so don't allow it. See PR87600 for details. */
1070 if (!targetm
.lra_p ())
1073 rtx set
= single_set (insn
);
1075 /* Disallow anything other than a simple register to register copy
1076 that has no side effects. */
1078 || !REG_P (SET_DEST (set
))
1079 || !REG_P (SET_SRC (set
))
1080 || side_effects_p (set
))
1083 int dst_regno
= REGNO (SET_DEST (set
));
1084 int src_regno
= REGNO (SET_SRC (set
));
1085 machine_mode mode
= GET_MODE (SET_DEST (set
));
1087 /* By definition, a register does not conflict with itself, therefore we
1088 do not have to handle it specially. Returning NULL_RTX now, helps
1089 simplify the callers of this function. */
1090 if (dst_regno
== src_regno
)
1093 /* Computing conflicts for register pairs is difficult to get right, so
1094 for now, disallow it. */
1095 if ((HARD_REGISTER_NUM_P (dst_regno
)
1096 && hard_regno_nregs (dst_regno
, mode
) != 1)
1097 || (HARD_REGISTER_NUM_P (src_regno
)
1098 && hard_regno_nregs (src_regno
, mode
) != 1))
1101 return SET_SRC (set
);
1104 /* Process insns of the basic block given by its LOOP_TREE_NODE to
1105 update allocno live ranges, allocno hard register conflicts,
1106 intersected calls, and register pressure info for allocnos for the
1107 basic block for and regions containing the basic block. */
1109 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
1116 bitmap reg_live_out
;
1120 bb
= loop_tree_node
->bb
;
1123 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1125 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1126 high_pressure_start_point
[ira_pressure_classes
[i
]] = -1;
1128 curr_bb_node
= loop_tree_node
;
1129 reg_live_out
= df_get_live_out (bb
);
1130 sparseset_clear (objects_live
);
1131 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
1132 hard_regs_live
&= ~(eliminable_regset
| ira_no_alloc_regs
);
1133 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1134 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
1136 enum reg_class aclass
, pclass
, cl
;
1138 aclass
= ira_allocno_class_translate
[REGNO_REG_CLASS (i
)];
1139 pclass
= ira_pressure_class_translate
[aclass
];
1141 (cl
= ira_reg_class_super_classes
[pclass
][j
])
1145 if (! ira_reg_pressure_class_p
[cl
])
1147 curr_reg_pressure
[cl
]++;
1148 if (curr_bb_node
->reg_pressure
[cl
] < curr_reg_pressure
[cl
])
1149 curr_bb_node
->reg_pressure
[cl
] = curr_reg_pressure
[cl
];
1150 ira_assert (curr_reg_pressure
[cl
]
1151 <= ira_class_hard_regs_num
[cl
]);
1154 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
1155 mark_pseudo_regno_live (j
);
1157 freq
= REG_FREQ_FROM_BB (bb
);
1161 /* Invalidate all allocno_saved_at_call entries. */
1164 /* Scan the code of this basic block, noting which allocnos and
1165 hard regs are born or die.
1167 Note that this loop treats uninitialized values as live until
1168 the beginning of the block. For example, if an instruction
1169 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1170 set, FOO will remain live until the beginning of the block.
1171 Likewise if FOO is not set at all. This is unnecessarily
1172 pessimistic, but it probably doesn't matter much in practice. */
1173 FOR_BB_INSNS_REVERSE (bb
, insn
)
1179 if (!NONDEBUG_INSN_P (insn
))
1182 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1183 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
1184 INSN_UID (insn
), loop_tree_node
->parent
->loop_num
,
1187 call_p
= CALL_P (insn
);
1188 ignore_reg_for_conflicts
= non_conflicting_reg_copy_p (insn
);
1190 /* Mark each defined value as live. We need to do this for
1191 unused values because they still conflict with quantities
1192 that are live at the time of the definition.
1194 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1195 references represent the effect of the called function
1196 on a call-clobbered register. Marking the register as
1197 live would stop us from allocating it to a call-crossing
1199 FOR_EACH_INSN_DEF (def
, insn
)
1200 if (!call_p
|| !DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1201 mark_ref_live (def
);
1203 /* If INSN has multiple outputs, then any value used in one
1204 of the outputs conflicts with the other outputs. Model this
1205 by making the used value live during the output phase.
1207 It is unsafe to use !single_set here since it will ignore
1208 an unused output. Just because an output is unused does
1209 not mean the compiler can assume the side effect will not
1210 occur. Consider if ALLOCNO appears in the address of an
1211 output and we reload the output. If we allocate ALLOCNO
1212 to the same hard register as an unused output we could
1213 set the hard register before the output reload insn. */
1214 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
1215 FOR_EACH_INSN_USE (use
, insn
)
1220 reg
= DF_REF_REG (use
);
1221 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
1225 set
= XVECEXP (PATTERN (insn
), 0, i
);
1226 if (GET_CODE (set
) == SET
1227 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
1229 /* After the previous loop, this is a no-op if
1230 REG is contained within SET_DEST (SET). */
1231 mark_ref_live (use
);
1237 preferred_alternatives
= ira_setup_alts (insn
);
1238 process_single_reg_class_operands (false, freq
);
1242 /* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from
1243 there, try to find a pseudo that is live across the call but
1244 can be cheaply reconstructed from the return value. */
1245 rtx cheap_reg
= find_call_crossed_cheap_reg (insn
);
1246 if (cheap_reg
!= NULL_RTX
)
1247 add_reg_note (insn
, REG_RETURNED
, cheap_reg
);
1250 sparseset_clear (allocnos_processed
);
1251 /* The current set of live allocnos are live across the call. */
1252 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1254 ira_object_t obj
= ira_object_id_map
[i
];
1255 a
= OBJECT_ALLOCNO (obj
);
1256 int num
= ALLOCNO_NUM (a
);
1257 HARD_REG_SET this_call_used_reg_set
;
1259 get_call_reg_set_usage (insn
, &this_call_used_reg_set
,
1260 call_used_or_fixed_regs
);
1262 /* Don't allocate allocnos that cross setjmps or any
1263 call, if this function receives a nonlocal
1265 if (cfun
->has_nonlocal_label
1266 || (!targetm
.setjmp_preserves_nonvolatile_regs_p ()
1267 && (find_reg_note (insn
, REG_SETJMP
, NULL_RTX
)
1270 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
));
1271 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1273 if (can_throw_internal (insn
))
1275 OBJECT_CONFLICT_HARD_REGS (obj
)
1276 |= this_call_used_reg_set
;
1277 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
)
1278 |= this_call_used_reg_set
;
1281 if (sparseset_bit_p (allocnos_processed
, num
))
1283 sparseset_set_bit (allocnos_processed
, num
);
1285 if (allocno_saved_at_call
[num
] != last_call_num
)
1286 /* Here we are mimicking caller-save.c behavior
1287 which does not save hard register at a call if
1288 it was saved on previous call in the same basic
1289 block and the hard register was not mentioned
1290 between the two calls. */
1291 ALLOCNO_CALL_FREQ (a
) += freq
;
1292 /* Mark it as saved at the next call. */
1293 allocno_saved_at_call
[num
] = last_call_num
+ 1;
1294 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
1295 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
)
1296 |= this_call_used_reg_set
;
1297 if (cheap_reg
!= NULL_RTX
1298 && ALLOCNO_REGNO (a
) == (int) REGNO (cheap_reg
))
1299 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
)++;
1303 /* See which defined values die here. Note that we include
1304 the call insn in the lifetimes of these values, so we don't
1305 mistakenly consider, for e.g. an addressing mode with a
1306 side-effect like a post-increment fetching the address,
1307 that the use happens before the call, and the def to happen
1308 after the call: we believe both to happen before the actual
1309 call. (We don't handle return-values here.) */
1310 FOR_EACH_INSN_DEF (def
, insn
)
1311 if (!call_p
|| !DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
1312 mark_ref_dead (def
);
1314 make_early_clobber_and_input_conflicts ();
1318 /* Mark each used value as live. */
1319 FOR_EACH_INSN_USE (use
, insn
)
1320 mark_ref_live (use
);
1322 process_single_reg_class_operands (true, freq
);
1324 set_p
= mark_hard_reg_early_clobbers (insn
, true);
1328 mark_hard_reg_early_clobbers (insn
, false);
1330 /* Mark each hard reg as live again. For example, a
1331 hard register can be in clobber and in an insn
1333 FOR_EACH_INSN_USE (use
, insn
)
1335 rtx ureg
= DF_REF_REG (use
);
1337 if (GET_CODE (ureg
) == SUBREG
)
1338 ureg
= SUBREG_REG (ureg
);
1339 if (! REG_P (ureg
) || REGNO (ureg
) >= FIRST_PSEUDO_REGISTER
)
1342 mark_ref_live (use
);
1348 ignore_reg_for_conflicts
= NULL_RTX
;
1350 if (bb_has_eh_pred (bb
))
1353 unsigned int regno
= EH_RETURN_DATA_REGNO (j
);
1354 if (regno
== INVALID_REGNUM
)
1356 make_hard_regno_live (regno
);
1359 /* Allocnos can't go in stack regs at the start of a basic block
1360 that is reached by an abnormal edge. Likewise for call
1361 clobbered regs, because caller-save, fixup_abnormal_edges and
1362 possibly the table driven EH machinery are not quite ready to
1363 handle such allocnos live across such edges. */
1364 if (bb_has_abnormal_pred (bb
))
1367 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, px
)
1369 ira_allocno_t a
= OBJECT_ALLOCNO (ira_object_id_map
[px
]);
1371 ALLOCNO_NO_STACK_REG_P (a
) = true;
1372 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = true;
1374 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
1375 make_hard_regno_live (px
);
1377 /* No need to record conflicts for call clobbered regs if we
1378 have nonlocal labels around, as we don't ever try to
1379 allocate such regs in this case. */
1380 if (!cfun
->has_nonlocal_label
1381 && has_abnormal_call_or_eh_pred_edge_p (bb
))
1382 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
1383 if (call_used_regs
[px
]
1384 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1385 /* We should create a conflict of PIC pseudo with
1386 PIC hard reg as PIC hard reg can have a wrong
1387 value after jump described by the abnormal edge.
1388 In this case we cannot allocate PIC hard reg to
1389 PIC pseudo as PIC pseudo will also have a wrong
1390 value. This code is not critical as LRA can fix
1391 it but it is better to have the right allocation
1393 || (px
== REAL_PIC_OFFSET_TABLE_REGNUM
1394 && pic_offset_table_rtx
!= NULL_RTX
1395 && REGNO (pic_offset_table_rtx
) >= FIRST_PSEUDO_REGISTER
)
1398 make_hard_regno_live (px
);
1401 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, i
)
1402 make_object_dead (ira_object_id_map
[i
]);
1407 /* Propagate register pressure to upper loop tree nodes. */
1408 if (loop_tree_node
!= ira_loop_tree_root
)
1409 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1411 enum reg_class pclass
;
1413 pclass
= ira_pressure_classes
[i
];
1414 if (loop_tree_node
->reg_pressure
[pclass
]
1415 > loop_tree_node
->parent
->reg_pressure
[pclass
])
1416 loop_tree_node
->parent
->reg_pressure
[pclass
]
1417 = loop_tree_node
->reg_pressure
[pclass
];
1421 /* Create and set up IRA_START_POINT_RANGES and
1422 IRA_FINISH_POINT_RANGES. */
1424 create_start_finish_chains (void)
1427 ira_object_iterator oi
;
1430 ira_start_point_ranges
1431 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1432 memset (ira_start_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1433 ira_finish_point_ranges
1434 = (live_range_t
*) ira_allocate (ira_max_point
* sizeof (live_range_t
));
1435 memset (ira_finish_point_ranges
, 0, ira_max_point
* sizeof (live_range_t
));
1436 FOR_EACH_OBJECT (obj
, oi
)
1437 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1439 r
->start_next
= ira_start_point_ranges
[r
->start
];
1440 ira_start_point_ranges
[r
->start
] = r
;
1441 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
1442 ira_finish_point_ranges
[r
->finish
] = r
;
1446 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1447 new live ranges and program points were added as a result if new
1450 ira_rebuild_start_finish_chains (void)
1452 ira_free (ira_finish_point_ranges
);
1453 ira_free (ira_start_point_ranges
);
1454 create_start_finish_chains ();
1457 /* Compress allocno live ranges by removing program points where
1460 remove_some_program_points_and_update_live_ranges (void)
1466 ira_object_iterator oi
;
1467 live_range_t r
, prev_r
, next_r
;
1468 sbitmap_iterator sbi
;
1469 bool born_p
, dead_p
, prev_born_p
, prev_dead_p
;
1471 auto_sbitmap
born (ira_max_point
);
1472 auto_sbitmap
dead (ira_max_point
);
1473 bitmap_clear (born
);
1474 bitmap_clear (dead
);
1475 FOR_EACH_OBJECT (obj
, oi
)
1476 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
1478 ira_assert (r
->start
<= r
->finish
);
1479 bitmap_set_bit (born
, r
->start
);
1480 bitmap_set_bit (dead
, r
->finish
);
1483 auto_sbitmap
born_or_dead (ira_max_point
);
1484 bitmap_ior (born_or_dead
, born
, dead
);
1485 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1487 prev_born_p
= prev_dead_p
= false;
1488 EXECUTE_IF_SET_IN_BITMAP (born_or_dead
, 0, i
, sbi
)
1490 born_p
= bitmap_bit_p (born
, i
);
1491 dead_p
= bitmap_bit_p (dead
, i
);
1492 if ((prev_born_p
&& ! prev_dead_p
&& born_p
&& ! dead_p
)
1493 || (prev_dead_p
&& ! prev_born_p
&& dead_p
&& ! born_p
))
1497 prev_born_p
= born_p
;
1498 prev_dead_p
= dead_p
;
1502 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1503 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
1504 ira_max_point
, n
, 100 * n
/ ira_max_point
);
1507 FOR_EACH_OBJECT (obj
, oi
)
1508 for (r
= OBJECT_LIVE_RANGES (obj
), prev_r
= NULL
; r
!= NULL
; r
= next_r
)
1511 r
->start
= map
[r
->start
];
1512 r
->finish
= map
[r
->finish
];
1513 if (prev_r
== NULL
|| prev_r
->start
> r
->finish
+ 1)
1518 prev_r
->start
= r
->start
;
1519 prev_r
->next
= next_r
;
1520 ira_finish_live_range (r
);
1526 /* Print live ranges R to file F. */
1528 ira_print_live_range_list (FILE *f
, live_range_t r
)
1530 for (; r
!= NULL
; r
= r
->next
)
1531 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
1536 debug (live_range
&ref
)
1538 ira_print_live_range_list (stderr
, &ref
);
1542 debug (live_range
*ptr
)
1547 fprintf (stderr
, "<nil>\n");
1550 /* Print live ranges R to stderr. */
1552 ira_debug_live_range_list (live_range_t r
)
1554 ira_print_live_range_list (stderr
, r
);
1557 /* Print live ranges of object OBJ to file F. */
1559 print_object_live_ranges (FILE *f
, ira_object_t obj
)
1561 ira_print_live_range_list (f
, OBJECT_LIVE_RANGES (obj
));
1564 /* Print live ranges of allocno A to file F. */
1566 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
1568 int n
= ALLOCNO_NUM_OBJECTS (a
);
1571 for (i
= 0; i
< n
; i
++)
1573 fprintf (f
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1575 fprintf (f
, " [%d]", i
);
1577 print_object_live_ranges (f
, ALLOCNO_OBJECT (a
, i
));
1581 /* Print live ranges of allocno A to stderr. */
1583 ira_debug_allocno_live_ranges (ira_allocno_t a
)
1585 print_allocno_live_ranges (stderr
, a
);
1588 /* Print live ranges of all allocnos to file F. */
1590 print_live_ranges (FILE *f
)
1593 ira_allocno_iterator ai
;
1595 FOR_EACH_ALLOCNO (a
, ai
)
1596 print_allocno_live_ranges (f
, a
);
1599 /* Print live ranges of all allocnos to stderr. */
1601 ira_debug_live_ranges (void)
1603 print_live_ranges (stderr
);
1606 /* The main entry function creates live ranges, set up
1607 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1608 calculate register pressure info. */
1610 ira_create_allocno_live_ranges (void)
1612 objects_live
= sparseset_alloc (ira_objects_num
);
1613 allocnos_processed
= sparseset_alloc (ira_allocnos_num
);
1616 allocno_saved_at_call
1617 = (int *) ira_allocate (ira_allocnos_num
* sizeof (int));
1618 memset (allocno_saved_at_call
, 0, ira_allocnos_num
* sizeof (int));
1619 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
1620 process_bb_node_lives
);
1621 ira_max_point
= curr_point
;
1622 create_start_finish_chains ();
1623 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1624 print_live_ranges (ira_dump_file
);
1626 ira_free (allocno_saved_at_call
);
1627 sparseset_free (objects_live
);
1628 sparseset_free (allocnos_processed
);
1631 /* Compress allocno live ranges. */
1633 ira_compress_allocno_live_ranges (void)
1635 remove_some_program_points_and_update_live_ranges ();
1636 ira_rebuild_start_finish_chains ();
1637 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1639 fprintf (ira_dump_file
, "Ranges after the compression:\n");
1640 print_live_ranges (ira_dump_file
);
1644 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1646 ira_finish_allocno_live_ranges (void)
1648 ira_free (ira_finish_point_ranges
);
1649 ira_free (ira_start_point_ranges
);