2014-10-24 Christophe Lyon <christophe.lyon@linaro.org>
[official-gcc.git] / gcc / ira-lives.c
blob1c9f8841dfeb474f2372f3b54a7a5cd14efaab9d
1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006-2014 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
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "regs.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "target.h"
29 #include "flags.h"
30 #include "except.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "diagnostic-core.h"
36 #include "params.h"
37 #include "df.h"
38 #include "sbitmap.h"
39 #include "sparseset.h"
40 #include "ira-int.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. */
53 int ira_max_point;
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
67 pressure classes. */
68 static int high_pressure_start_point[N_REG_CLASSES];
70 /* Objects live at current point in the scan. */
71 static sparseset objects_live;
73 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
74 multiple times. */
75 static sparseset allocnos_processed;
77 /* Set of hard regs (except eliminable ones) currently live. */
78 static HARD_REG_SET hard_regs_live;
80 /* The loop tree node corresponding to the current basic block. */
81 static ira_loop_tree_node_t curr_bb_node;
83 /* The number of the last processed call. */
84 static int last_call_num;
85 /* The number of last call at which given allocno was saved. */
86 static int *allocno_saved_at_call;
88 /* The value of get_preferred_alternatives for the current instruction,
89 supplemental to recog_data. */
90 static alternative_mask preferred_alternatives;
92 /* Record the birth of hard register REGNO, updating hard_regs_live and
93 hard reg conflict information for living allocnos. */
94 static void
95 make_hard_regno_born (int regno)
97 unsigned int i;
99 SET_HARD_REG_BIT (hard_regs_live, regno);
100 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
102 ira_object_t obj = ira_object_id_map[i];
104 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
105 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno);
109 /* Process the death of hard register REGNO. This updates
110 hard_regs_live. */
111 static void
112 make_hard_regno_dead (int regno)
114 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
117 /* Record the birth of object OBJ. Set a bit for it in objects_live,
118 start a new live range for it if necessary and update hard register
119 conflicts. */
120 static void
121 make_object_born (ira_object_t obj)
123 live_range_t lr = OBJECT_LIVE_RANGES (obj);
125 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
126 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), hard_regs_live);
127 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), hard_regs_live);
129 if (lr == NULL
130 || (lr->finish != curr_point && lr->finish + 1 != curr_point))
131 ira_add_live_range_to_object (obj, curr_point, -1);
134 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
135 associated with object OBJ. */
136 static void
137 update_allocno_pressure_excess_length (ira_object_t obj)
139 ira_allocno_t a = OBJECT_ALLOCNO (obj);
140 int start, i;
141 enum reg_class aclass, pclass, cl;
142 live_range_t p;
144 aclass = ALLOCNO_CLASS (a);
145 pclass = ira_pressure_class_translate[aclass];
146 for (i = 0;
147 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
148 i++)
150 if (! ira_reg_pressure_class_p[cl])
151 continue;
152 if (high_pressure_start_point[cl] < 0)
153 continue;
154 p = OBJECT_LIVE_RANGES (obj);
155 ira_assert (p != NULL);
156 start = (high_pressure_start_point[cl] > p->start
157 ? high_pressure_start_point[cl] : p->start);
158 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
162 /* Process the death of object OBJ, which is associated with allocno
163 A. This finishes the current live range for it. */
164 static void
165 make_object_dead (ira_object_t obj)
167 live_range_t lr;
169 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (obj));
170 lr = OBJECT_LIVE_RANGES (obj);
171 ira_assert (lr != NULL);
172 lr->finish = curr_point;
173 update_allocno_pressure_excess_length (obj);
176 /* The current register pressures for each pressure class for the current
177 basic block. */
178 static int curr_reg_pressure[N_REG_CLASSES];
180 /* Record that register pressure for PCLASS increased by N registers.
181 Update the current register pressure, maximal register pressure for
182 the current BB and the start point of the register pressure
183 excess. */
184 static void
185 inc_register_pressure (enum reg_class pclass, int n)
187 int i;
188 enum reg_class cl;
190 for (i = 0;
191 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
192 i++)
194 if (! ira_reg_pressure_class_p[cl])
195 continue;
196 curr_reg_pressure[cl] += n;
197 if (high_pressure_start_point[cl] < 0
198 && (curr_reg_pressure[cl] > ira_class_hard_regs_num[cl]))
199 high_pressure_start_point[cl] = curr_point;
200 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
201 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
205 /* Record that register pressure for PCLASS has decreased by NREGS
206 registers; update current register pressure, start point of the
207 register pressure excess, and register pressure excess length for
208 living allocnos. */
210 static void
211 dec_register_pressure (enum reg_class pclass, int nregs)
213 int i;
214 unsigned int j;
215 enum reg_class cl;
216 bool set_p = false;
218 for (i = 0;
219 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
220 i++)
222 if (! ira_reg_pressure_class_p[cl])
223 continue;
224 curr_reg_pressure[cl] -= nregs;
225 ira_assert (curr_reg_pressure[cl] >= 0);
226 if (high_pressure_start_point[cl] >= 0
227 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
228 set_p = true;
230 if (set_p)
232 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
233 update_allocno_pressure_excess_length (ira_object_id_map[j]);
234 for (i = 0;
235 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
236 i++)
238 if (! ira_reg_pressure_class_p[cl])
239 continue;
240 if (high_pressure_start_point[cl] >= 0
241 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
242 high_pressure_start_point[cl] = -1;
247 /* Determine from the objects_live bitmap whether REGNO is currently live,
248 and occupies only one object. Return false if we have no information. */
249 static bool
250 pseudo_regno_single_word_and_live_p (int regno)
252 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
253 ira_object_t obj;
255 if (a == NULL)
256 return false;
257 if (ALLOCNO_NUM_OBJECTS (a) > 1)
258 return false;
260 obj = ALLOCNO_OBJECT (a, 0);
262 return sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj));
265 /* Mark the pseudo register REGNO as live. Update all information about
266 live ranges and register pressure. */
267 static void
268 mark_pseudo_regno_live (int regno)
270 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
271 enum reg_class pclass;
272 int i, n, nregs;
274 if (a == NULL)
275 return;
277 /* Invalidate because it is referenced. */
278 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
280 n = ALLOCNO_NUM_OBJECTS (a);
281 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
282 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
283 if (n > 1)
285 /* We track every subobject separately. */
286 gcc_assert (nregs == n);
287 nregs = 1;
290 for (i = 0; i < n; i++)
292 ira_object_t obj = ALLOCNO_OBJECT (a, i);
294 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
295 continue;
297 inc_register_pressure (pclass, nregs);
298 make_object_born (obj);
302 /* Like mark_pseudo_regno_live, but try to only mark one subword of
303 the pseudo as live. SUBWORD indicates which; a value of 0
304 indicates the low part. */
305 static void
306 mark_pseudo_regno_subword_live (int regno, int subword)
308 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
309 int n;
310 enum reg_class pclass;
311 ira_object_t obj;
313 if (a == NULL)
314 return;
316 /* Invalidate because it is referenced. */
317 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
319 n = ALLOCNO_NUM_OBJECTS (a);
320 if (n == 1)
322 mark_pseudo_regno_live (regno);
323 return;
326 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
327 gcc_assert
328 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
329 obj = ALLOCNO_OBJECT (a, subword);
331 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
332 return;
334 inc_register_pressure (pclass, 1);
335 make_object_born (obj);
338 /* Mark the register REG as live. Store a 1 in hard_regs_live for
339 this register, record how many consecutive hardware registers it
340 actually needs. */
341 static void
342 mark_hard_reg_live (rtx reg)
344 int regno = REGNO (reg);
346 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
348 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
349 enum reg_class aclass, pclass;
351 while (regno < last)
353 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
354 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
356 aclass = ira_hard_regno_allocno_class[regno];
357 pclass = ira_pressure_class_translate[aclass];
358 inc_register_pressure (pclass, 1);
359 make_hard_regno_born (regno);
361 regno++;
366 /* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's
367 register number; ORIG_REG is the access in the insn, which may be a
368 subreg. */
369 static void
370 mark_pseudo_reg_live (rtx orig_reg, unsigned regno)
372 if (df_read_modify_subreg_p (orig_reg))
374 mark_pseudo_regno_subword_live (regno,
375 subreg_lowpart_p (orig_reg) ? 0 : 1);
377 else
378 mark_pseudo_regno_live (regno);
381 /* Mark the register referenced by use or def REF as live. */
382 static void
383 mark_ref_live (df_ref ref)
385 rtx reg = DF_REF_REG (ref);
386 rtx orig_reg = reg;
388 if (GET_CODE (reg) == SUBREG)
389 reg = SUBREG_REG (reg);
391 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
392 mark_pseudo_reg_live (orig_reg, REGNO (reg));
393 else
394 mark_hard_reg_live (reg);
397 /* Mark the pseudo register REGNO as dead. Update all information about
398 live ranges and register pressure. */
399 static void
400 mark_pseudo_regno_dead (int regno)
402 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
403 int n, i, nregs;
404 enum reg_class cl;
406 if (a == NULL)
407 return;
409 /* Invalidate because it is referenced. */
410 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
412 n = ALLOCNO_NUM_OBJECTS (a);
413 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
414 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
415 if (n > 1)
417 /* We track every subobject separately. */
418 gcc_assert (nregs == n);
419 nregs = 1;
421 for (i = 0; i < n; i++)
423 ira_object_t obj = ALLOCNO_OBJECT (a, i);
424 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
425 continue;
427 dec_register_pressure (cl, nregs);
428 make_object_dead (obj);
432 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
433 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
434 static void
435 mark_pseudo_regno_subword_dead (int regno, int subword)
437 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
438 int n;
439 enum reg_class cl;
440 ira_object_t obj;
442 if (a == NULL)
443 return;
445 /* Invalidate because it is referenced. */
446 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
448 n = ALLOCNO_NUM_OBJECTS (a);
449 if (n == 1)
450 /* The allocno as a whole doesn't die in this case. */
451 return;
453 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
454 gcc_assert
455 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
457 obj = ALLOCNO_OBJECT (a, subword);
458 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
459 return;
461 dec_register_pressure (cl, 1);
462 make_object_dead (obj);
465 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the
466 register. */
467 static void
468 mark_hard_reg_dead (rtx reg)
470 int regno = REGNO (reg);
472 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
474 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
475 enum reg_class aclass, pclass;
477 while (regno < last)
479 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
481 aclass = ira_hard_regno_allocno_class[regno];
482 pclass = ira_pressure_class_translate[aclass];
483 dec_register_pressure (pclass, 1);
484 make_hard_regno_dead (regno);
486 regno++;
491 /* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's
492 register number; ORIG_REG is the access in the insn, which may be a
493 subreg. */
494 static void
495 mark_pseudo_reg_dead (rtx orig_reg, unsigned regno)
497 if (df_read_modify_subreg_p (orig_reg))
499 mark_pseudo_regno_subword_dead (regno,
500 subreg_lowpart_p (orig_reg) ? 0 : 1);
502 else
503 mark_pseudo_regno_dead (regno);
506 /* Mark the register referenced by definition DEF as dead, if the
507 definition is a total one. */
508 static void
509 mark_ref_dead (df_ref def)
511 rtx reg = DF_REF_REG (def);
512 rtx orig_reg = reg;
514 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
515 return;
517 if (GET_CODE (reg) == SUBREG)
518 reg = SUBREG_REG (reg);
520 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
521 && (GET_CODE (orig_reg) != SUBREG
522 || REGNO (reg) < FIRST_PSEUDO_REGISTER
523 || !df_read_modify_subreg_p (orig_reg)))
524 return;
526 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
527 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
528 else
529 mark_hard_reg_dead (reg);
532 /* If REG is a pseudo or a subreg of it, and the class of its allocno
533 intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the
534 rtx actually accessed, it may be identical to DREG or a subreg of it.
535 Advance the current program point before making the conflict if
536 ADVANCE_P. Return TRUE if we will need to advance the current
537 program point. */
538 static bool
539 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, rtx orig_dreg,
540 bool advance_p)
542 rtx orig_reg = reg;
543 ira_allocno_t a;
545 if (GET_CODE (reg) == SUBREG)
546 reg = SUBREG_REG (reg);
548 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
549 return advance_p;
551 a = ira_curr_regno_allocno_map[REGNO (reg)];
552 if (! reg_classes_intersect_p (cl, ALLOCNO_CLASS (a)))
553 return advance_p;
555 if (advance_p)
556 curr_point++;
558 mark_pseudo_reg_live (orig_reg, REGNO (reg));
559 mark_pseudo_reg_live (orig_dreg, REGNO (dreg));
560 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
561 mark_pseudo_reg_dead (orig_dreg, REGNO (dreg));
563 return false;
566 /* Check and make if necessary conflicts for pseudo DREG of class
567 DEF_CL of the current insn with input operand USE of class USE_CL.
568 ORIG_DREG is the rtx actually accessed, it may be identical to
569 DREG or a subreg of it. Advance the current program point before
570 making the conflict if ADVANCE_P. Return TRUE if we will need to
571 advance the current program point. */
572 static bool
573 check_and_make_def_use_conflict (rtx dreg, rtx orig_dreg,
574 enum reg_class def_cl, int use,
575 enum reg_class use_cl, bool advance_p)
577 if (! reg_classes_intersect_p (def_cl, use_cl))
578 return advance_p;
580 advance_p = make_pseudo_conflict (recog_data.operand[use],
581 use_cl, dreg, orig_dreg, advance_p);
583 /* Reload may end up swapping commutative operands, so you
584 have to take both orderings into account. The
585 constraints for the two operands can be completely
586 different. (Indeed, if the constraints for the two
587 operands are the same for all alternatives, there's no
588 point marking them as commutative.) */
589 if (use < recog_data.n_operands - 1
590 && recog_data.constraints[use][0] == '%')
591 advance_p
592 = make_pseudo_conflict (recog_data.operand[use + 1],
593 use_cl, dreg, orig_dreg, advance_p);
594 if (use >= 1
595 && recog_data.constraints[use - 1][0] == '%')
596 advance_p
597 = make_pseudo_conflict (recog_data.operand[use - 1],
598 use_cl, dreg, orig_dreg, advance_p);
599 return advance_p;
602 /* Check and make if necessary conflicts for definition DEF of class
603 DEF_CL of the current insn with input operands. Process only
604 constraints of alternative ALT. */
605 static void
606 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
608 int use, use_match;
609 ira_allocno_t a;
610 enum reg_class use_cl, acl;
611 bool advance_p;
612 rtx dreg = recog_data.operand[def];
613 rtx orig_dreg = dreg;
615 if (def_cl == NO_REGS)
616 return;
618 if (GET_CODE (dreg) == SUBREG)
619 dreg = SUBREG_REG (dreg);
621 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
622 return;
624 a = ira_curr_regno_allocno_map[REGNO (dreg)];
625 acl = ALLOCNO_CLASS (a);
626 if (! reg_classes_intersect_p (acl, def_cl))
627 return;
629 advance_p = true;
631 int n_operands = recog_data.n_operands;
632 const operand_alternative *op_alt = &recog_op_alt[alt * n_operands];
633 for (use = 0; use < n_operands; use++)
635 int alt1;
637 if (use == def || recog_data.operand_type[use] == OP_OUT)
638 continue;
640 if (op_alt[use].anything_ok)
641 use_cl = ALL_REGS;
642 else
643 use_cl = op_alt[use].cl;
645 /* If there's any alternative that allows USE to match DEF, do not
646 record a conflict. If that causes us to create an invalid
647 instruction due to the earlyclobber, reload must fix it up. */
648 for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
650 if (!TEST_BIT (preferred_alternatives, alt1))
651 continue;
652 const operand_alternative *op_alt1
653 = &recog_op_alt[alt1 * n_operands];
654 if (op_alt1[use].matches == def
655 || (use < n_operands - 1
656 && recog_data.constraints[use][0] == '%'
657 && op_alt1[use + 1].matches == def)
658 || (use >= 1
659 && recog_data.constraints[use - 1][0] == '%'
660 && op_alt1[use - 1].matches == def))
661 break;
664 if (alt1 < recog_data.n_alternatives)
665 continue;
667 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
668 use, use_cl, advance_p);
670 if ((use_match = op_alt[use].matches) >= 0)
672 if (use_match == def)
673 continue;
675 if (op_alt[use_match].anything_ok)
676 use_cl = ALL_REGS;
677 else
678 use_cl = op_alt[use_match].cl;
679 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
680 use, use_cl, advance_p);
685 /* Make conflicts of early clobber pseudo registers of the current
686 insn with its inputs. Avoid introducing unnecessary conflicts by
687 checking classes of the constraints and pseudos because otherwise
688 significant code degradation is possible for some targets. */
689 static void
690 make_early_clobber_and_input_conflicts (void)
692 int alt;
693 int def, def_match;
694 enum reg_class def_cl;
696 int n_alternatives = recog_data.n_alternatives;
697 int n_operands = recog_data.n_operands;
698 const operand_alternative *op_alt = recog_op_alt;
699 for (alt = 0; alt < n_alternatives; alt++, op_alt += n_operands)
700 if (TEST_BIT (preferred_alternatives, alt))
701 for (def = 0; def < n_operands; def++)
703 def_cl = NO_REGS;
704 if (op_alt[def].earlyclobber)
706 if (op_alt[def].anything_ok)
707 def_cl = ALL_REGS;
708 else
709 def_cl = op_alt[def].cl;
710 check_and_make_def_conflict (alt, def, def_cl);
712 if ((def_match = op_alt[def].matches) >= 0
713 && (op_alt[def_match].earlyclobber
714 || op_alt[def].earlyclobber))
716 if (op_alt[def_match].anything_ok)
717 def_cl = ALL_REGS;
718 else
719 def_cl = op_alt[def_match].cl;
720 check_and_make_def_conflict (alt, def, def_cl);
725 /* Mark early clobber hard registers of the current INSN as live (if
726 LIVE_P) or dead. Return true if there are such registers. */
727 static bool
728 mark_hard_reg_early_clobbers (rtx_insn *insn, bool live_p)
730 df_ref def;
731 bool set_p = false;
733 FOR_EACH_INSN_DEF (def, insn)
734 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
736 rtx dreg = DF_REF_REG (def);
738 if (GET_CODE (dreg) == SUBREG)
739 dreg = SUBREG_REG (dreg);
740 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
741 continue;
743 /* Hard register clobbers are believed to be early clobber
744 because there is no way to say that non-operand hard
745 register clobbers are not early ones. */
746 if (live_p)
747 mark_ref_live (def);
748 else
749 mark_ref_dead (def);
750 set_p = true;
753 return set_p;
756 /* Checks that CONSTRAINTS permits to use only one hard register. If
757 it is so, the function returns the class of the hard register.
758 Otherwise it returns NO_REGS. */
759 static enum reg_class
760 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
762 int c;
763 enum reg_class cl, next_cl;
764 enum constraint_num cn;
766 cl = NO_REGS;
767 alternative_mask preferred = preferred_alternatives;
768 for (; (c = *constraints); constraints += CONSTRAINT_LEN (c, constraints))
769 if (c == '#')
770 preferred &= ~ALTERNATIVE_BIT (0);
771 else if (c == ',')
772 preferred >>= 1;
773 else if (preferred & 1)
774 switch (c)
776 case 'g':
777 return NO_REGS;
779 default:
780 /* ??? Is this the best way to handle memory constraints? */
781 cn = lookup_constraint (constraints);
782 if (insn_extra_memory_constraint (cn)
783 || insn_extra_address_constraint (cn))
784 return NO_REGS;
785 if (constraint_satisfied_p (op, cn)
786 || (equiv_const != NULL_RTX
787 && CONSTANT_P (equiv_const)
788 && constraint_satisfied_p (equiv_const, cn)))
789 return NO_REGS;
790 next_cl = reg_class_for_constraint (cn);
791 if (next_cl == NO_REGS)
792 break;
793 if (cl == NO_REGS
794 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0
795 : (ira_class_singleton[cl][GET_MODE (op)]
796 != ira_class_singleton[next_cl][GET_MODE (op)]))
797 return NO_REGS;
798 cl = next_cl;
799 break;
801 case '0': case '1': case '2': case '3': case '4':
802 case '5': case '6': case '7': case '8': case '9':
803 next_cl
804 = single_reg_class (recog_data.constraints[c - '0'],
805 recog_data.operand[c - '0'], NULL_RTX);
806 if (cl == NO_REGS
807 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0
808 : (ira_class_singleton[cl][GET_MODE (op)]
809 != ira_class_singleton[next_cl][GET_MODE (op)]))
810 return NO_REGS;
811 cl = next_cl;
812 break;
814 return cl;
817 /* The function checks that operand OP_NUM of the current insn can use
818 only one hard register. If it is so, the function returns the
819 class of the hard register. Otherwise it returns NO_REGS. */
820 static enum reg_class
821 single_reg_operand_class (int op_num)
823 if (op_num < 0 || recog_data.n_alternatives == 0)
824 return NO_REGS;
825 return single_reg_class (recog_data.constraints[op_num],
826 recog_data.operand[op_num], NULL_RTX);
829 /* The function sets up hard register set *SET to hard registers which
830 might be used by insn reloads because the constraints are too
831 strict. */
832 void
833 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
835 int i, c, regno = 0;
836 enum reg_class cl;
837 rtx op;
838 enum machine_mode mode;
840 CLEAR_HARD_REG_SET (*set);
841 for (i = 0; i < recog_data.n_operands; i++)
843 op = recog_data.operand[i];
845 if (GET_CODE (op) == SUBREG)
846 op = SUBREG_REG (op);
848 if (GET_CODE (op) == SCRATCH
849 || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
851 const char *p = recog_data.constraints[i];
853 mode = (GET_CODE (op) == SCRATCH
854 ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
855 cl = NO_REGS;
856 alternative_mask preferred = preferred_alternatives;
857 for (; (c = *p); p += CONSTRAINT_LEN (c, p))
858 if (c == '#')
859 preferred &= ~ALTERNATIVE_BIT (0);
860 else if (c == ',')
861 preferred >>= 1;
862 else if (preferred & 1)
864 cl = reg_class_for_constraint (lookup_constraint (p));
865 if (cl != NO_REGS)
867 /* There is no register pressure problem if all of the
868 regs in this class are fixed. */
869 int regno = ira_class_singleton[cl][mode];
870 if (regno >= 0)
871 add_to_hard_reg_set (set, mode, regno);
877 /* Processes input operands, if IN_P, or output operands otherwise of
878 the current insn with FREQ to find allocno which can use only one
879 hard register and makes other currently living allocnos conflicting
880 with the hard register. */
881 static void
882 process_single_reg_class_operands (bool in_p, int freq)
884 int i, regno;
885 unsigned int px;
886 enum reg_class cl;
887 rtx operand;
888 ira_allocno_t operand_a, a;
890 for (i = 0; i < recog_data.n_operands; i++)
892 operand = recog_data.operand[i];
893 if (in_p && recog_data.operand_type[i] != OP_IN
894 && recog_data.operand_type[i] != OP_INOUT)
895 continue;
896 if (! in_p && recog_data.operand_type[i] != OP_OUT
897 && recog_data.operand_type[i] != OP_INOUT)
898 continue;
899 cl = single_reg_operand_class (i);
900 if (cl == NO_REGS)
901 continue;
903 operand_a = NULL;
905 if (GET_CODE (operand) == SUBREG)
906 operand = SUBREG_REG (operand);
908 if (REG_P (operand)
909 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
911 enum reg_class aclass;
913 operand_a = ira_curr_regno_allocno_map[regno];
914 aclass = ALLOCNO_CLASS (operand_a);
915 if (ira_class_subset_p[cl][aclass])
917 /* View the desired allocation of OPERAND as:
919 (REG:YMODE YREGNO),
921 a simplification of:
923 (subreg:YMODE (reg:XMODE XREGNO) OFFSET). */
924 enum machine_mode ymode, xmode;
925 int xregno, yregno;
926 HOST_WIDE_INT offset;
928 xmode = recog_data.operand_mode[i];
929 xregno = ira_class_singleton[cl][xmode];
930 gcc_assert (xregno >= 0);
931 ymode = ALLOCNO_MODE (operand_a);
932 offset = subreg_lowpart_offset (ymode, xmode);
933 yregno = simplify_subreg_regno (xregno, xmode, offset, ymode);
934 if (yregno >= 0
935 && ira_class_hard_reg_index[aclass][yregno] >= 0)
937 int cost;
939 ira_allocate_and_set_costs
940 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a),
941 aclass, 0);
942 ira_init_register_move_cost_if_necessary (xmode);
943 cost = freq * (in_p
944 ? ira_register_move_cost[xmode][aclass][cl]
945 : ira_register_move_cost[xmode][cl][aclass]);
946 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
947 [ira_class_hard_reg_index[aclass][yregno]] -= cost;
952 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
954 ira_object_t obj = ira_object_id_map[px];
955 a = OBJECT_ALLOCNO (obj);
956 if (a != operand_a)
958 /* We could increase costs of A instead of making it
959 conflicting with the hard register. But it works worse
960 because it will be spilled in reload in anyway. */
961 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
962 reg_class_contents[cl]);
963 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
964 reg_class_contents[cl]);
970 /* Return true when one of the predecessor edges of BB is marked with
971 EDGE_ABNORMAL_CALL or EDGE_EH. */
972 static bool
973 bb_has_abnormal_call_pred (basic_block bb)
975 edge e;
976 edge_iterator ei;
978 FOR_EACH_EDGE (e, ei, bb->preds)
980 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
981 return true;
983 return false;
986 /* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if
987 we find a SET rtx that we can use to deduce that a register can be cheaply
988 caller-saved. Return such a register, or NULL_RTX if none is found. */
989 static rtx
990 find_call_crossed_cheap_reg (rtx_insn *insn)
992 rtx cheap_reg = NULL_RTX;
993 rtx exp = CALL_INSN_FUNCTION_USAGE (insn);
995 while (exp != NULL)
997 rtx x = XEXP (exp, 0);
998 if (GET_CODE (x) == SET)
1000 exp = x;
1001 break;
1003 exp = XEXP (exp, 1);
1005 if (exp != NULL)
1007 basic_block bb = BLOCK_FOR_INSN (insn);
1008 rtx reg = SET_SRC (exp);
1009 rtx_insn *prev = PREV_INSN (insn);
1010 while (prev && !(INSN_P (prev)
1011 && BLOCK_FOR_INSN (prev) != bb))
1013 if (NONDEBUG_INSN_P (prev))
1015 rtx set = single_set (prev);
1017 if (set && rtx_equal_p (SET_DEST (set), reg))
1019 rtx src = SET_SRC (set);
1020 if (!REG_P (src) || HARD_REGISTER_P (src)
1021 || !pseudo_regno_single_word_and_live_p (REGNO (src)))
1022 break;
1023 if (!modified_between_p (src, prev, insn))
1024 cheap_reg = src;
1025 break;
1027 if (set && rtx_equal_p (SET_SRC (set), reg))
1029 rtx dest = SET_DEST (set);
1030 if (!REG_P (dest) || HARD_REGISTER_P (dest)
1031 || !pseudo_regno_single_word_and_live_p (REGNO (dest)))
1032 break;
1033 if (!modified_between_p (dest, prev, insn))
1034 cheap_reg = dest;
1035 break;
1038 if (reg_overlap_mentioned_p (reg, PATTERN (prev)))
1039 break;
1041 prev = PREV_INSN (prev);
1044 return cheap_reg;
1047 /* Process insns of the basic block given by its LOOP_TREE_NODE to
1048 update allocno live ranges, allocno hard register conflicts,
1049 intersected calls, and register pressure info for allocnos for the
1050 basic block for and regions containing the basic block. */
1051 static void
1052 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
1054 int i, freq;
1055 unsigned int j;
1056 basic_block bb;
1057 rtx_insn *insn;
1058 bitmap_iterator bi;
1059 bitmap reg_live_out;
1060 unsigned int px;
1061 bool set_p;
1063 bb = loop_tree_node->bb;
1064 if (bb != NULL)
1066 for (i = 0; i < ira_pressure_classes_num; i++)
1068 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1069 high_pressure_start_point[ira_pressure_classes[i]] = -1;
1071 curr_bb_node = loop_tree_node;
1072 reg_live_out = df_get_live_out (bb);
1073 sparseset_clear (objects_live);
1074 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
1075 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
1076 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
1077 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1078 if (TEST_HARD_REG_BIT (hard_regs_live, i))
1080 enum reg_class aclass, pclass, cl;
1082 aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)];
1083 pclass = ira_pressure_class_translate[aclass];
1084 for (j = 0;
1085 (cl = ira_reg_class_super_classes[pclass][j])
1086 != LIM_REG_CLASSES;
1087 j++)
1089 if (! ira_reg_pressure_class_p[cl])
1090 continue;
1091 curr_reg_pressure[cl]++;
1092 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
1093 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
1094 ira_assert (curr_reg_pressure[cl]
1095 <= ira_class_hard_regs_num[cl]);
1098 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
1099 mark_pseudo_regno_live (j);
1101 freq = REG_FREQ_FROM_BB (bb);
1102 if (freq == 0)
1103 freq = 1;
1105 /* Invalidate all allocno_saved_at_call entries. */
1106 last_call_num++;
1108 /* Scan the code of this basic block, noting which allocnos and
1109 hard regs are born or die.
1111 Note that this loop treats uninitialized values as live until
1112 the beginning of the block. For example, if an instruction
1113 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1114 set, FOO will remain live until the beginning of the block.
1115 Likewise if FOO is not set at all. This is unnecessarily
1116 pessimistic, but it probably doesn't matter much in practice. */
1117 FOR_BB_INSNS_REVERSE (bb, insn)
1119 df_ref def, use;
1120 bool call_p;
1122 if (!NONDEBUG_INSN_P (insn))
1123 continue;
1125 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1126 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n",
1127 INSN_UID (insn), loop_tree_node->parent->loop_num,
1128 curr_point);
1130 /* Mark each defined value as live. We need to do this for
1131 unused values because they still conflict with quantities
1132 that are live at the time of the definition.
1134 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1135 references represent the effect of the called function
1136 on a call-clobbered register. Marking the register as
1137 live would stop us from allocating it to a call-crossing
1138 allocno. */
1139 call_p = CALL_P (insn);
1140 FOR_EACH_INSN_DEF (def, insn)
1141 if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1142 mark_ref_live (def);
1144 /* If INSN has multiple outputs, then any value used in one
1145 of the outputs conflicts with the other outputs. Model this
1146 by making the used value live during the output phase.
1148 It is unsafe to use !single_set here since it will ignore
1149 an unused output. Just because an output is unused does
1150 not mean the compiler can assume the side effect will not
1151 occur. Consider if ALLOCNO appears in the address of an
1152 output and we reload the output. If we allocate ALLOCNO
1153 to the same hard register as an unused output we could
1154 set the hard register before the output reload insn. */
1155 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1156 FOR_EACH_INSN_USE (use, insn)
1158 int i;
1159 rtx reg;
1161 reg = DF_REF_REG (use);
1162 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1164 rtx set;
1166 set = XVECEXP (PATTERN (insn), 0, i);
1167 if (GET_CODE (set) == SET
1168 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1170 /* After the previous loop, this is a no-op if
1171 REG is contained within SET_DEST (SET). */
1172 mark_ref_live (use);
1173 break;
1178 extract_insn (insn);
1179 preferred_alternatives = get_preferred_alternatives (insn);
1180 preprocess_constraints (insn);
1181 process_single_reg_class_operands (false, freq);
1183 /* See which defined values die here. */
1184 FOR_EACH_INSN_DEF (def, insn)
1185 if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1186 mark_ref_dead (def);
1188 if (call_p)
1190 /* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from
1191 there, try to find a pseudo that is live across the call but
1192 can be cheaply reconstructed from the return value. */
1193 rtx cheap_reg = find_call_crossed_cheap_reg (insn);
1194 if (cheap_reg != NULL_RTX)
1195 add_reg_note (insn, REG_RETURNED, cheap_reg);
1197 last_call_num++;
1198 sparseset_clear (allocnos_processed);
1199 /* The current set of live allocnos are live across the call. */
1200 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1202 ira_object_t obj = ira_object_id_map[i];
1203 ira_allocno_t a = OBJECT_ALLOCNO (obj);
1204 int num = ALLOCNO_NUM (a);
1205 HARD_REG_SET this_call_used_reg_set;
1207 get_call_reg_set_usage (insn, &this_call_used_reg_set,
1208 call_used_reg_set);
1210 /* Don't allocate allocnos that cross setjmps or any
1211 call, if this function receives a nonlocal
1212 goto. */
1213 if (cfun->has_nonlocal_label
1214 || find_reg_note (insn, REG_SETJMP,
1215 NULL_RTX) != NULL_RTX)
1217 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj));
1218 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1220 if (can_throw_internal (insn))
1222 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
1223 this_call_used_reg_set);
1224 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1225 this_call_used_reg_set);
1228 if (sparseset_bit_p (allocnos_processed, num))
1229 continue;
1230 sparseset_set_bit (allocnos_processed, num);
1232 if (allocno_saved_at_call[num] != last_call_num)
1233 /* Here we are mimicking caller-save.c behavior
1234 which does not save hard register at a call if
1235 it was saved on previous call in the same basic
1236 block and the hard register was not mentioned
1237 between the two calls. */
1238 ALLOCNO_CALL_FREQ (a) += freq;
1239 /* Mark it as saved at the next call. */
1240 allocno_saved_at_call[num] = last_call_num + 1;
1241 ALLOCNO_CALLS_CROSSED_NUM (a)++;
1242 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a),
1243 this_call_used_reg_set);
1244 if (cheap_reg != NULL_RTX
1245 && ALLOCNO_REGNO (a) == (int) REGNO (cheap_reg))
1246 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)++;
1250 make_early_clobber_and_input_conflicts ();
1252 curr_point++;
1254 /* Mark each used value as live. */
1255 FOR_EACH_INSN_USE (use, insn)
1256 mark_ref_live (use);
1258 process_single_reg_class_operands (true, freq);
1260 set_p = mark_hard_reg_early_clobbers (insn, true);
1262 if (set_p)
1264 mark_hard_reg_early_clobbers (insn, false);
1266 /* Mark each hard reg as live again. For example, a
1267 hard register can be in clobber and in an insn
1268 input. */
1269 FOR_EACH_INSN_USE (use, insn)
1271 rtx ureg = DF_REF_REG (use);
1273 if (GET_CODE (ureg) == SUBREG)
1274 ureg = SUBREG_REG (ureg);
1275 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1276 continue;
1278 mark_ref_live (use);
1282 curr_point++;
1285 #ifdef EH_RETURN_DATA_REGNO
1286 if (bb_has_eh_pred (bb))
1287 for (j = 0; ; ++j)
1289 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1290 if (regno == INVALID_REGNUM)
1291 break;
1292 make_hard_regno_born (regno);
1294 #endif
1296 /* Allocnos can't go in stack regs at the start of a basic block
1297 that is reached by an abnormal edge. Likewise for call
1298 clobbered regs, because caller-save, fixup_abnormal_edges and
1299 possibly the table driven EH machinery are not quite ready to
1300 handle such allocnos live across such edges. */
1301 if (bb_has_abnormal_pred (bb))
1303 #ifdef STACK_REGS
1304 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1306 ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]);
1308 ALLOCNO_NO_STACK_REG_P (a) = true;
1309 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1311 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1312 make_hard_regno_born (px);
1313 #endif
1314 /* No need to record conflicts for call clobbered regs if we
1315 have nonlocal labels around, as we don't ever try to
1316 allocate such regs in this case. */
1317 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1318 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1319 if (call_used_regs[px])
1320 make_hard_regno_born (px);
1323 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1324 make_object_dead (ira_object_id_map[i]);
1326 curr_point++;
1329 /* Propagate register pressure to upper loop tree nodes. */
1330 if (loop_tree_node != ira_loop_tree_root)
1331 for (i = 0; i < ira_pressure_classes_num; i++)
1333 enum reg_class pclass;
1335 pclass = ira_pressure_classes[i];
1336 if (loop_tree_node->reg_pressure[pclass]
1337 > loop_tree_node->parent->reg_pressure[pclass])
1338 loop_tree_node->parent->reg_pressure[pclass]
1339 = loop_tree_node->reg_pressure[pclass];
1343 /* Create and set up IRA_START_POINT_RANGES and
1344 IRA_FINISH_POINT_RANGES. */
1345 static void
1346 create_start_finish_chains (void)
1348 ira_object_t obj;
1349 ira_object_iterator oi;
1350 live_range_t r;
1352 ira_start_point_ranges
1353 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1354 memset (ira_start_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1355 ira_finish_point_ranges
1356 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1357 memset (ira_finish_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1358 FOR_EACH_OBJECT (obj, oi)
1359 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1361 r->start_next = ira_start_point_ranges[r->start];
1362 ira_start_point_ranges[r->start] = r;
1363 r->finish_next = ira_finish_point_ranges[r->finish];
1364 ira_finish_point_ranges[r->finish] = r;
1368 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1369 new live ranges and program points were added as a result if new
1370 insn generation. */
1371 void
1372 ira_rebuild_start_finish_chains (void)
1374 ira_free (ira_finish_point_ranges);
1375 ira_free (ira_start_point_ranges);
1376 create_start_finish_chains ();
1379 /* Compress allocno live ranges by removing program points where
1380 nothing happens. */
1381 static void
1382 remove_some_program_points_and_update_live_ranges (void)
1384 unsigned i;
1385 int n;
1386 int *map;
1387 ira_object_t obj;
1388 ira_object_iterator oi;
1389 live_range_t r, prev_r, next_r;
1390 sbitmap born_or_dead, born, dead;
1391 sbitmap_iterator sbi;
1392 bool born_p, dead_p, prev_born_p, prev_dead_p;
1394 born = sbitmap_alloc (ira_max_point);
1395 dead = sbitmap_alloc (ira_max_point);
1396 bitmap_clear (born);
1397 bitmap_clear (dead);
1398 FOR_EACH_OBJECT (obj, oi)
1399 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1401 ira_assert (r->start <= r->finish);
1402 bitmap_set_bit (born, r->start);
1403 bitmap_set_bit (dead, r->finish);
1406 born_or_dead = sbitmap_alloc (ira_max_point);
1407 bitmap_ior (born_or_dead, born, dead);
1408 map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1409 n = -1;
1410 prev_born_p = prev_dead_p = false;
1411 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1413 born_p = bitmap_bit_p (born, i);
1414 dead_p = bitmap_bit_p (dead, i);
1415 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1416 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1417 map[i] = n;
1418 else
1419 map[i] = ++n;
1420 prev_born_p = born_p;
1421 prev_dead_p = dead_p;
1423 sbitmap_free (born_or_dead);
1424 sbitmap_free (born);
1425 sbitmap_free (dead);
1426 n++;
1427 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1428 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1429 ira_max_point, n, 100 * n / ira_max_point);
1430 ira_max_point = n;
1432 FOR_EACH_OBJECT (obj, oi)
1433 for (r = OBJECT_LIVE_RANGES (obj), prev_r = NULL; r != NULL; r = next_r)
1435 next_r = r->next;
1436 r->start = map[r->start];
1437 r->finish = map[r->finish];
1438 if (prev_r == NULL || prev_r->start > r->finish + 1)
1440 prev_r = r;
1441 continue;
1443 prev_r->start = r->start;
1444 prev_r->next = next_r;
1445 ira_finish_live_range (r);
1448 ira_free (map);
1451 /* Print live ranges R to file F. */
1452 void
1453 ira_print_live_range_list (FILE *f, live_range_t r)
1455 for (; r != NULL; r = r->next)
1456 fprintf (f, " [%d..%d]", r->start, r->finish);
1457 fprintf (f, "\n");
1460 DEBUG_FUNCTION void
1461 debug (live_range &ref)
1463 ira_print_live_range_list (stderr, &ref);
1466 DEBUG_FUNCTION void
1467 debug (live_range *ptr)
1469 if (ptr)
1470 debug (*ptr);
1471 else
1472 fprintf (stderr, "<nil>\n");
1475 /* Print live ranges R to stderr. */
1476 void
1477 ira_debug_live_range_list (live_range_t r)
1479 ira_print_live_range_list (stderr, r);
1482 /* Print live ranges of object OBJ to file F. */
1483 static void
1484 print_object_live_ranges (FILE *f, ira_object_t obj)
1486 ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj));
1489 /* Print live ranges of allocno A to file F. */
1490 static void
1491 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1493 int n = ALLOCNO_NUM_OBJECTS (a);
1494 int i;
1496 for (i = 0; i < n; i++)
1498 fprintf (f, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1499 if (n > 1)
1500 fprintf (f, " [%d]", i);
1501 fprintf (f, "):");
1502 print_object_live_ranges (f, ALLOCNO_OBJECT (a, i));
1506 /* Print live ranges of allocno A to stderr. */
1507 void
1508 ira_debug_allocno_live_ranges (ira_allocno_t a)
1510 print_allocno_live_ranges (stderr, a);
1513 /* Print live ranges of all allocnos to file F. */
1514 static void
1515 print_live_ranges (FILE *f)
1517 ira_allocno_t a;
1518 ira_allocno_iterator ai;
1520 FOR_EACH_ALLOCNO (a, ai)
1521 print_allocno_live_ranges (f, a);
1524 /* Print live ranges of all allocnos to stderr. */
1525 void
1526 ira_debug_live_ranges (void)
1528 print_live_ranges (stderr);
1531 /* The main entry function creates live ranges, set up
1532 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1533 calculate register pressure info. */
1534 void
1535 ira_create_allocno_live_ranges (void)
1537 objects_live = sparseset_alloc (ira_objects_num);
1538 allocnos_processed = sparseset_alloc (ira_allocnos_num);
1539 curr_point = 0;
1540 last_call_num = 0;
1541 allocno_saved_at_call
1542 = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1543 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1544 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1545 process_bb_node_lives);
1546 ira_max_point = curr_point;
1547 create_start_finish_chains ();
1548 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1549 print_live_ranges (ira_dump_file);
1550 /* Clean up. */
1551 ira_free (allocno_saved_at_call);
1552 sparseset_free (objects_live);
1553 sparseset_free (allocnos_processed);
1556 /* Compress allocno live ranges. */
1557 void
1558 ira_compress_allocno_live_ranges (void)
1560 remove_some_program_points_and_update_live_ranges ();
1561 ira_rebuild_start_finish_chains ();
1562 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1564 fprintf (ira_dump_file, "Ranges after the compression:\n");
1565 print_live_ranges (ira_dump_file);
1569 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1570 void
1571 ira_finish_allocno_live_ranges (void)
1573 ira_free (ira_finish_point_ranges);
1574 ira_free (ira_start_point_ranges);