1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006, 2007, 2008
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"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
38 #include "sparseset.h"
41 /* The code in this file is similar to one in global but the code
42 works on the allocno basis and creates live ranges instead of
43 pseudo-register conflicts. */
45 /* Program points are enumerated by numbers from range
46 0..IRA_MAX_POINT-1. There are approximately two times more program
47 points than insns. Program points are places in the program where
48 liveness info can be changed. In most general case (there are more
49 complicated cases too) some program points correspond to places
50 where input operand dies and other ones correspond to places where
51 output operands are born. */
54 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
55 live ranges with given start/finish point. */
56 allocno_live_range_t
*ira_start_point_ranges
, *ira_finish_point_ranges
;
58 /* Number of the current program point. */
59 static int curr_point
;
61 /* Point where register pressure excess started or -1 if there is no
62 register pressure excess. Excess pressure for a register class at
63 some point means that there are more allocnos of given register
64 class living at the point than number of hard-registers of the
65 class available for the allocation. It is defined only for cover
67 static int high_pressure_start_point
[N_REG_CLASSES
];
69 /* Allocnos live at current point in the scan. */
70 static sparseset allocnos_live
;
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 function processing birth of register REGNO. It updates living
79 hard regs and conflict hard regs for living allocnos or starts a
80 new live range for the allocno corresponding to REGNO if it is
83 make_regno_born (int regno
)
87 allocno_live_range_t p
;
89 if (regno
< FIRST_PSEUDO_REGISTER
)
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 a
= ira_curr_regno_allocno_map
[regno
];
104 if ((p
= ALLOCNO_LIVE_RANGES (a
)) == NULL
105 || (p
->finish
!= curr_point
&& p
->finish
+ 1 != curr_point
))
106 ALLOCNO_LIVE_RANGES (a
)
107 = ira_create_allocno_live_range (a
, curr_point
, -1,
108 ALLOCNO_LIVE_RANGES (a
));
111 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A. */
113 update_allocno_pressure_excess_length (ira_allocno_t a
)
116 enum reg_class cover_class
;
117 allocno_live_range_t p
;
119 cover_class
= ALLOCNO_COVER_CLASS (a
);
120 if (high_pressure_start_point
[cover_class
] < 0)
122 p
= ALLOCNO_LIVE_RANGES (a
);
123 ira_assert (p
!= NULL
);
124 start
= (high_pressure_start_point
[cover_class
] > p
->start
125 ? high_pressure_start_point
[cover_class
] : p
->start
);
126 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) += curr_point
- start
+ 1;
129 /* Process the death of register REGNO. This updates hard_regs_live
130 or finishes the current live range for the allocno corresponding to
133 make_regno_dead (int regno
)
136 allocno_live_range_t p
;
138 if (regno
< FIRST_PSEUDO_REGISTER
)
140 CLEAR_HARD_REG_BIT (hard_regs_live
, regno
);
143 a
= ira_curr_regno_allocno_map
[regno
];
146 p
= ALLOCNO_LIVE_RANGES (a
);
147 ira_assert (p
!= NULL
);
148 p
->finish
= curr_point
;
149 update_allocno_pressure_excess_length (a
);
152 /* The current register pressures for each cover class for the current
154 static int curr_reg_pressure
[N_REG_CLASSES
];
156 /* Mark allocno A as currently living and update current register
157 pressure, maximal register pressure for the current BB, start point
158 of the register pressure excess, and conflicting hard registers of
161 set_allocno_live (ira_allocno_t a
)
164 enum reg_class cover_class
;
166 if (sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
168 sparseset_set_bit (allocnos_live
, ALLOCNO_NUM (a
));
169 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
), hard_regs_live
);
170 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), hard_regs_live
);
171 cover_class
= ALLOCNO_COVER_CLASS (a
);
172 nregs
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (a
)];
173 curr_reg_pressure
[cover_class
] += nregs
;
174 if (high_pressure_start_point
[cover_class
] < 0
175 && (curr_reg_pressure
[cover_class
]
176 > ira_available_class_regs
[cover_class
]))
177 high_pressure_start_point
[cover_class
] = curr_point
;
178 if (curr_bb_node
->reg_pressure
[cover_class
]
179 < curr_reg_pressure
[cover_class
])
180 curr_bb_node
->reg_pressure
[cover_class
] = curr_reg_pressure
[cover_class
];
183 /* Mark allocno A as currently not living and update current register
184 pressure, start point of the register pressure excess, and register
185 pressure excess length for living allocnos. */
187 clear_allocno_live (ira_allocno_t a
)
190 enum reg_class cover_class
;
192 if (sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
194 cover_class
= ALLOCNO_COVER_CLASS (a
);
195 curr_reg_pressure
[cover_class
]
196 -= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (a
)];
197 ira_assert (curr_reg_pressure
[cover_class
] >= 0);
198 if (high_pressure_start_point
[cover_class
] >= 0
199 && (curr_reg_pressure
[cover_class
]
200 <= ira_available_class_regs
[cover_class
]))
202 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
204 update_allocno_pressure_excess_length (ira_allocnos
[i
]);
206 high_pressure_start_point
[cover_class
] = -1;
209 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (a
));
212 /* Mark the register referenced by use or def REF as live
213 Store a 1 in hard_regs_live or allocnos_live for this register or
214 the corresponding allocno, record how many consecutive hardware
215 registers it actually needs. */
218 mark_ref_live (struct df_ref
*ref
)
223 reg
= DF_REF_REG (ref
);
224 if (GET_CODE (reg
) == SUBREG
)
225 reg
= SUBREG_REG (reg
);
226 gcc_assert (REG_P (reg
));
229 if (regno
>= FIRST_PSEUDO_REGISTER
)
231 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
235 if (sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
237 set_allocno_live (a
);
239 make_regno_born (regno
);
241 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
243 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
244 enum reg_class cover_class
;
248 if (! TEST_HARD_REG_BIT (hard_regs_live
, regno
)
249 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
251 cover_class
= ira_class_translate
[REGNO_REG_CLASS (regno
)];
252 if (cover_class
!= NO_REGS
)
254 curr_reg_pressure
[cover_class
]++;
255 if (high_pressure_start_point
[cover_class
] < 0
256 && (curr_reg_pressure
[cover_class
]
257 > ira_available_class_regs
[cover_class
]))
258 high_pressure_start_point
[cover_class
] = curr_point
;
260 make_regno_born (regno
);
261 if (cover_class
!= NO_REGS
262 && (curr_bb_node
->reg_pressure
[cover_class
]
263 < curr_reg_pressure
[cover_class
]))
264 curr_bb_node
->reg_pressure
[cover_class
]
265 = curr_reg_pressure
[cover_class
];
272 /* Return true if the definition described by DEF conflicts with the
273 instruction's inputs. */
275 def_conflicts_with_inputs_p (struct df_ref
*def
)
277 /* Conservatively assume that the condition is true for all clobbers. */
278 return DF_REF_FLAGS_IS_SET (def
, DF_REF_MUST_CLOBBER
);
281 /* Mark the register referenced by definition DEF as dead, if the
282 definition is a total one. Store a 0 in hard_regs_live or
283 allocnos_live for the register. */
285 mark_ref_dead (struct df_ref
*def
)
291 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
)
292 || DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
))
295 reg
= DF_REF_REG (def
);
296 if (GET_CODE (reg
) == SUBREG
)
297 reg
= SUBREG_REG (reg
);
298 gcc_assert (REG_P (reg
));
301 if (regno
>= FIRST_PSEUDO_REGISTER
)
303 ira_allocno_t a
= ira_curr_regno_allocno_map
[regno
];
307 if (! sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)))
309 clear_allocno_live (a
);
311 make_regno_dead (regno
);
313 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
315 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
316 enum reg_class cover_class
;
320 if (TEST_HARD_REG_BIT (hard_regs_live
, regno
))
322 cover_class
= ira_class_translate
[REGNO_REG_CLASS (regno
)];
323 if (cover_class
!= NO_REGS
)
325 curr_reg_pressure
[cover_class
]--;
326 if (high_pressure_start_point
[cover_class
] >= 0
327 && (curr_reg_pressure
[cover_class
]
328 <= ira_available_class_regs
[cover_class
]))
330 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
332 update_allocno_pressure_excess_length
335 high_pressure_start_point
[cover_class
] = -1;
337 ira_assert (curr_reg_pressure
[cover_class
] >= 0);
339 make_regno_dead (regno
);
346 /* Checks that CONSTRAINTS permits to use only one hard register. If
347 it is so, the function returns the class of the hard register.
348 Otherwise it returns NO_REGS. */
349 static enum reg_class
350 single_reg_class (const char *constraints
, rtx op
, rtx equiv_const
)
353 enum reg_class cl
, next_cl
;
357 for (ignore_p
= false;
359 constraints
+= CONSTRAINT_LEN (c
, constraints
))
379 || (equiv_const
!= NULL_RTX
&& CONSTANT_P (equiv_const
)))
384 if (GET_CODE (op
) == CONST_INT
385 || (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE (op
) == VOIDmode
)
386 || (equiv_const
!= NULL_RTX
387 && (GET_CODE (equiv_const
) == CONST_INT
388 || (GET_CODE (equiv_const
) == CONST_DOUBLE
389 && GET_MODE (equiv_const
) == VOIDmode
))))
394 if ((CONSTANT_P (op
) && GET_CODE (op
) != CONST_INT
395 && (GET_CODE (op
) != CONST_DOUBLE
|| GET_MODE (op
) != VOIDmode
))
396 || (equiv_const
!= NULL_RTX
397 && CONSTANT_P (equiv_const
)
398 && GET_CODE (equiv_const
) != CONST_INT
399 && (GET_CODE (equiv_const
) != CONST_DOUBLE
400 || GET_MODE (equiv_const
) != VOIDmode
)))
412 if ((GET_CODE (op
) == CONST_INT
413 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, constraints
))
414 || (equiv_const
!= NULL_RTX
415 && GET_CODE (equiv_const
) == CONST_INT
416 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const
),
423 if (GET_CODE (op
) == CONST_DOUBLE
424 || (GET_CODE (op
) == CONST_VECTOR
425 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
)
426 || (equiv_const
!= NULL_RTX
427 && (GET_CODE (equiv_const
) == CONST_DOUBLE
428 || (GET_CODE (equiv_const
) == CONST_VECTOR
429 && (GET_MODE_CLASS (GET_MODE (equiv_const
))
430 == MODE_VECTOR_FLOAT
)))))
436 if ((GET_CODE (op
) == CONST_DOUBLE
437 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, constraints
))
438 || (equiv_const
!= NULL_RTX
439 && GET_CODE (equiv_const
) == CONST_DOUBLE
440 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const
,
443 /* ??? what about memory */
445 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
446 case 'h': case 'j': case 'k': case 'l':
447 case 'q': case 't': case 'u':
448 case 'v': case 'w': case 'x': case 'y': case 'z':
449 case 'A': case 'B': case 'C': case 'D':
450 case 'Q': case 'R': case 'S': case 'T': case 'U':
451 case 'W': case 'Y': case 'Z':
454 : REG_CLASS_FROM_CONSTRAINT (c
, constraints
));
455 if ((cl
!= NO_REGS
&& next_cl
!= cl
)
456 || ira_available_class_regs
[next_cl
] > 1)
461 case '0': case '1': case '2': case '3': case '4':
462 case '5': case '6': case '7': case '8': case '9':
464 = single_reg_class (recog_data
.constraints
[c
- '0'],
465 recog_data
.operand
[c
- '0'], NULL_RTX
);
466 if ((cl
!= NO_REGS
&& next_cl
!= cl
) || next_cl
== NO_REGS
467 || ira_available_class_regs
[next_cl
] > 1)
478 /* The function checks that operand OP_NUM of the current insn can use
479 only one hard register. If it is so, the function returns the
480 class of the hard register. Otherwise it returns NO_REGS. */
481 static enum reg_class
482 single_reg_operand_class (int op_num
)
484 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
486 return single_reg_class (recog_data
.constraints
[op_num
],
487 recog_data
.operand
[op_num
], NULL_RTX
);
490 /* Processes input operands, if IN_P, or output operands otherwise of
491 the current insn with FREQ to find allocno which can use only one
492 hard register and makes other currently living allocnos conflicting
493 with the hard register. */
495 process_single_reg_class_operands (bool in_p
, int freq
)
499 enum reg_class cl
, cover_class
;
501 ira_allocno_t operand_a
, a
;
503 for (i
= 0; i
< recog_data
.n_operands
; i
++)
505 operand
= recog_data
.operand
[i
];
506 if (in_p
&& recog_data
.operand_type
[i
] != OP_IN
507 && recog_data
.operand_type
[i
] != OP_INOUT
)
509 if (! in_p
&& recog_data
.operand_type
[i
] != OP_OUT
510 && recog_data
.operand_type
[i
] != OP_INOUT
)
512 cl
= single_reg_operand_class (i
);
518 if (GET_CODE (operand
) == SUBREG
)
519 operand
= SUBREG_REG (operand
);
522 && (regno
= REGNO (operand
)) >= FIRST_PSEUDO_REGISTER
)
524 enum machine_mode mode
;
525 enum reg_class cover_class
;
527 operand_a
= ira_curr_regno_allocno_map
[regno
];
528 mode
= ALLOCNO_MODE (operand_a
);
529 cover_class
= ALLOCNO_COVER_CLASS (operand_a
);
530 if (ira_class_subset_p
[cl
][cover_class
]
531 && ira_class_hard_regs_num
[cl
] != 0
532 && (ira_class_hard_reg_index
[cover_class
]
533 [ira_class_hard_regs
[cl
][0]]) >= 0
534 && reg_class_size
[cl
] <= (unsigned) CLASS_MAX_NREGS (cl
, mode
))
538 ? ira_register_move_cost
[mode
][cover_class
][cl
]
539 : ira_register_move_cost
[mode
][cl
][cover_class
]);
540 ira_allocate_and_set_costs
541 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
), cover_class
, 0);
542 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a
)
543 [ira_class_hard_reg_index
544 [cover_class
][ira_class_hard_regs
[cl
][0]]]
549 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
551 a
= ira_allocnos
[px
];
552 cover_class
= ALLOCNO_COVER_CLASS (a
);
555 /* We could increase costs of A instead of making it
556 conflicting with the hard register. But it works worse
557 because it will be spilled in reload in anyway. */
558 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
559 reg_class_contents
[cl
]);
560 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
561 reg_class_contents
[cl
]);
567 /* Process insns of the basic block given by its LOOP_TREE_NODE to
568 update allocno live ranges, allocno hard register conflicts,
569 intersected calls, and register pressure info for allocnos for the
570 basic block for and regions containing the basic block. */
572 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node
)
584 bb
= loop_tree_node
->bb
;
587 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
589 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
590 high_pressure_start_point
[ira_reg_class_cover
[i
]] = -1;
592 curr_bb_node
= loop_tree_node
;
593 reg_live_out
= DF_LR_OUT (bb
);
594 sparseset_clear (allocnos_live
);
595 REG_SET_TO_HARD_REG_SET (hard_regs_live
, reg_live_out
);
596 AND_COMPL_HARD_REG_SET (hard_regs_live
, eliminable_regset
);
597 AND_COMPL_HARD_REG_SET (hard_regs_live
, ira_no_alloc_regs
);
598 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
599 if (TEST_HARD_REG_BIT (hard_regs_live
, i
))
601 enum reg_class cover_class
;
603 cover_class
= REGNO_REG_CLASS (i
);
604 if (cover_class
== NO_REGS
)
606 cover_class
= ira_class_translate
[cover_class
];
607 curr_reg_pressure
[cover_class
]++;
608 if (curr_bb_node
->reg_pressure
[cover_class
]
609 < curr_reg_pressure
[cover_class
])
610 curr_bb_node
->reg_pressure
[cover_class
]
611 = curr_reg_pressure
[cover_class
];
612 ira_assert (curr_reg_pressure
[cover_class
]
613 <= ira_available_class_regs
[cover_class
]);
615 EXECUTE_IF_SET_IN_BITMAP (reg_live_out
, FIRST_PSEUDO_REGISTER
, j
, bi
)
617 ira_allocno_t a
= ira_curr_regno_allocno_map
[j
];
621 ira_assert (! sparseset_bit_p (allocnos_live
, ALLOCNO_NUM (a
)));
622 set_allocno_live (a
);
626 freq
= REG_FREQ_FROM_BB (bb
);
630 /* Scan the code of this basic block, noting which allocnos and
631 hard regs are born or die.
633 Note that this loop treats uninitialized values as live until
634 the beginning of the block. For example, if an instruction
635 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
636 set, FOO will remain live until the beginning of the block.
637 Likewise if FOO is not set at all. This is unnecessarily
638 pessimistic, but it probably doesn't matter much in practice. */
639 FOR_BB_INSNS_REVERSE (bb
, insn
)
641 struct df_ref
**def_rec
, **use_rec
;
647 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
648 fprintf (ira_dump_file
, " Insn %u(l%d): point = %d\n",
649 INSN_UID (insn
), loop_tree_node
->parent
->loop
->num
,
652 /* Mark each defined value as live. We need to do this for
653 unused values because they still conflict with quantities
654 that are live at the time of the definition.
656 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
657 references represent the effect of the called function
658 on a call-clobbered register. Marking the register as
659 live would stop us from allocating it to a call-crossing
661 call_p
= CALL_P (insn
);
662 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
663 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
664 mark_ref_live (*def_rec
);
666 /* If INSN has multiple outputs, then any value used in one
667 of the outputs conflicts with the other outputs. Model this
668 by making the used value live during the output phase.
670 It is unsafe to use !single_set here since it will ignore
671 an unused output. Just because an output is unused does
672 not mean the compiler can assume the side effect will not
673 occur. Consider if ALLOCNO appears in the address of an
674 output and we reload the output. If we allocate ALLOCNO
675 to the same hard register as an unused output we could
676 set the hard register before the output reload insn. */
677 if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& multiple_sets (insn
))
678 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
683 reg
= DF_REF_REG (*use_rec
);
684 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
688 set
= XVECEXP (PATTERN (insn
), 0, i
);
689 if (GET_CODE (set
) == SET
690 && reg_overlap_mentioned_p (reg
, SET_DEST (set
)))
692 /* After the previous loop, this is a no-op if
693 REG is contained within SET_DEST (SET). */
694 mark_ref_live (*use_rec
);
701 process_single_reg_class_operands (false, freq
);
703 /* See which defined values die here. */
704 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
705 if (!call_p
|| !DF_REF_FLAGS_IS_SET (*def_rec
, DF_REF_MAY_CLOBBER
))
706 mark_ref_dead (*def_rec
);
710 /* The current set of live allocnos are live across the call. */
711 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
713 ira_allocno_t a
= ira_allocnos
[i
];
715 ALLOCNO_CALL_FREQ (a
) += freq
;
716 ALLOCNO_CALLS_CROSSED_NUM (a
)++;
717 /* Don't allocate allocnos that cross setjmps or any
718 call, if this function receives a nonlocal
720 if (cfun
->has_nonlocal_label
721 || find_reg_note (insn
, REG_SETJMP
,
722 NULL_RTX
) != NULL_RTX
)
724 SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
));
725 SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
732 /* Mark each used value as live. */
733 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
734 mark_ref_live (*use_rec
);
736 /* If any defined values conflict with the inputs, mark those
737 defined values as live. */
738 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
739 if (def_conflicts_with_inputs_p (*def_rec
))
740 mark_ref_live (*def_rec
);
742 process_single_reg_class_operands (true, freq
);
744 /* See which of the defined values we marked as live are dead
745 before the instruction. */
746 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
747 if (def_conflicts_with_inputs_p (*def_rec
))
748 mark_ref_dead (*def_rec
);
753 /* Allocnos can't go in stack regs at the start of a basic block
754 that is reached by an abnormal edge. Likewise for call
755 clobbered regs, because caller-save, fixup_abnormal_edges and
756 possibly the table driven EH machinery are not quite ready to
757 handle such allocnos live across such edges. */
758 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
759 if (e
->flags
& EDGE_ABNORMAL
)
765 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, px
)
767 ALLOCNO_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
768 ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos
[px
]) = true;
770 for (px
= FIRST_STACK_REG
; px
<= LAST_STACK_REG
; px
++)
771 make_regno_born (px
);
773 /* No need to record conflicts for call clobbered regs if we
774 have nonlocal labels around, as we don't ever try to
775 allocate such regs in this case. */
776 if (!cfun
->has_nonlocal_label
)
777 for (px
= 0; px
< FIRST_PSEUDO_REGISTER
; px
++)
778 if (call_used_regs
[px
])
779 make_regno_born (px
);
782 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, i
)
784 make_regno_dead (ALLOCNO_REGNO (ira_allocnos
[i
]));
790 /* Propagate register pressure to upper loop tree nodes: */
791 if (loop_tree_node
!= ira_loop_tree_root
)
792 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
794 enum reg_class cover_class
;
796 cover_class
= ira_reg_class_cover
[i
];
797 if (loop_tree_node
->reg_pressure
[cover_class
]
798 > loop_tree_node
->parent
->reg_pressure
[cover_class
])
799 loop_tree_node
->parent
->reg_pressure
[cover_class
]
800 = loop_tree_node
->reg_pressure
[cover_class
];
804 /* Create and set up IRA_START_POINT_RANGES and
805 IRA_FINISH_POINT_RANGES. */
807 create_start_finish_chains (void)
810 ira_allocno_iterator ai
;
811 allocno_live_range_t r
;
813 ira_start_point_ranges
814 = (allocno_live_range_t
*) ira_allocate (ira_max_point
815 * sizeof (allocno_live_range_t
));
816 memset (ira_start_point_ranges
, 0,
817 ira_max_point
* sizeof (allocno_live_range_t
));
818 ira_finish_point_ranges
819 = (allocno_live_range_t
*) ira_allocate (ira_max_point
820 * sizeof (allocno_live_range_t
));
821 memset (ira_finish_point_ranges
, 0,
822 ira_max_point
* sizeof (allocno_live_range_t
));
823 FOR_EACH_ALLOCNO (a
, ai
)
825 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
827 r
->start_next
= ira_start_point_ranges
[r
->start
];
828 ira_start_point_ranges
[r
->start
] = r
;
829 r
->finish_next
= ira_finish_point_ranges
[r
->finish
];
830 ira_finish_point_ranges
[r
->finish
] = r
;
835 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
836 new live ranges and program points were added as a result if new
839 ira_rebuild_start_finish_chains (void)
841 ira_free (ira_finish_point_ranges
);
842 ira_free (ira_start_point_ranges
);
843 create_start_finish_chains ();
846 /* Compress allocno live ranges by removing program points where
849 remove_some_program_points_and_update_live_ranges (void)
855 ira_allocno_iterator ai
;
856 allocno_live_range_t r
;
860 born_or_died
= ira_allocate_bitmap ();
861 FOR_EACH_ALLOCNO (a
, ai
)
863 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
865 ira_assert (r
->start
<= r
->finish
);
866 bitmap_set_bit (born_or_died
, r
->start
);
867 bitmap_set_bit (born_or_died
, r
->finish
);
870 map
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
872 EXECUTE_IF_SET_IN_BITMAP(born_or_died
, 0, i
, bi
)
876 ira_free_bitmap (born_or_died
);
877 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
878 fprintf (ira_dump_file
, "Compressing live ranges: from %d to %d - %d%%\n",
879 ira_max_point
, n
, 100 * n
/ ira_max_point
);
881 FOR_EACH_ALLOCNO (a
, ai
)
883 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
885 r
->start
= map
[r
->start
];
886 r
->finish
= map
[r
->finish
];
892 /* Print live ranges R to file F. */
894 ira_print_live_range_list (FILE *f
, allocno_live_range_t r
)
896 for (; r
!= NULL
; r
= r
->next
)
897 fprintf (f
, " [%d..%d]", r
->start
, r
->finish
);
901 /* Print live ranges R to stderr. */
903 ira_debug_live_range_list (allocno_live_range_t r
)
905 ira_print_live_range_list (stderr
, r
);
908 /* Print live ranges of allocno A to file F. */
910 print_allocno_live_ranges (FILE *f
, ira_allocno_t a
)
912 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
913 ira_print_live_range_list (f
, ALLOCNO_LIVE_RANGES (a
));
916 /* Print live ranges of allocno A to stderr. */
918 ira_debug_allocno_live_ranges (ira_allocno_t a
)
920 print_allocno_live_ranges (stderr
, a
);
923 /* Print live ranges of all allocnos to file F. */
925 print_live_ranges (FILE *f
)
928 ira_allocno_iterator ai
;
930 FOR_EACH_ALLOCNO (a
, ai
)
931 print_allocno_live_ranges (f
, a
);
934 /* Print live ranges of all allocnos to stderr. */
936 ira_debug_live_ranges (void)
938 print_live_ranges (stderr
);
941 /* The main entry function creates live ranges, set up
942 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
943 calculate register pressure info. */
945 ira_create_allocno_live_ranges (void)
947 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
949 ira_traverse_loop_tree (true, ira_loop_tree_root
, NULL
,
950 process_bb_node_lives
);
951 ira_max_point
= curr_point
;
952 create_start_finish_chains ();
953 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
954 print_live_ranges (ira_dump_file
);
956 sparseset_free (allocnos_live
);
959 /* Compress allocno live ranges. */
961 ira_compress_allocno_live_ranges (void)
963 remove_some_program_points_and_update_live_ranges ();
964 ira_rebuild_start_finish_chains ();
965 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
967 fprintf (ira_dump_file
, "Ranges after the compression:\n");
968 print_live_ranges (ira_dump_file
);
972 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
974 ira_finish_allocno_live_ranges (void)
976 ira_free (ira_finish_point_ranges
);
977 ira_free (ira_start_point_ranges
);