1 /* Definitions for computing resource usage of specific insns.
2 Copyright (C) 1999-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
27 #include "hard-reg-set.h"
34 #include "insn-attr.h"
38 /* This structure is used to record liveness information at the targets or
39 fallthrough insns of branches. We will most likely need the information
40 at targets again, so save them in a hash table rather than recomputing them
45 int uid
; /* INSN_UID of target. */
46 struct target_info
*next
; /* Next info for same hash bucket. */
47 HARD_REG_SET live_regs
; /* Registers live at target. */
48 int block
; /* Basic block number containing target. */
49 int bb_tick
; /* Generation count of basic block info. */
52 #define TARGET_HASH_PRIME 257
54 /* Indicates what resources are required at the beginning of the epilogue. */
55 static struct resources start_of_epilogue_needs
;
57 /* Indicates what resources are required at function end. */
58 static struct resources end_of_function_needs
;
60 /* Define the hash table itself. */
61 static struct target_info
**target_hash_table
= NULL
;
63 /* For each basic block, we maintain a generation number of its basic
64 block info, which is updated each time we move an insn from the
65 target of a jump. This is the generation number indexed by block
70 /* Marks registers possibly live at the current place being scanned by
71 mark_target_live_regs. Also used by update_live_status. */
73 static HARD_REG_SET current_live_regs
;
75 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
76 Also only used by the next two functions. */
78 static HARD_REG_SET pending_dead_regs
;
80 static void update_live_status (rtx
, const_rtx
, void *);
81 static int find_basic_block (rtx
, int);
82 static rtx
next_insn_no_annul (rtx
);
83 static rtx
find_dead_or_set_registers (rtx
, struct resources
*,
84 rtx
*, int, struct resources
,
87 /* Utility function called from mark_target_live_regs via note_stores.
88 It deadens any CLOBBERed registers and livens any SET registers. */
91 update_live_status (rtx dest
, const_rtx x
, void *data ATTRIBUTE_UNUSED
)
93 int first_regno
, last_regno
;
97 && (GET_CODE (dest
) != SUBREG
|| !REG_P (SUBREG_REG (dest
))))
100 if (GET_CODE (dest
) == SUBREG
)
102 first_regno
= subreg_regno (dest
);
103 last_regno
= first_regno
+ subreg_nregs (dest
);
108 first_regno
= REGNO (dest
);
109 last_regno
= END_HARD_REGNO (dest
);
112 if (GET_CODE (x
) == CLOBBER
)
113 for (i
= first_regno
; i
< last_regno
; i
++)
114 CLEAR_HARD_REG_BIT (current_live_regs
, i
);
116 for (i
= first_regno
; i
< last_regno
; i
++)
118 SET_HARD_REG_BIT (current_live_regs
, i
);
119 CLEAR_HARD_REG_BIT (pending_dead_regs
, i
);
123 /* Find the number of the basic block with correct live register
124 information that starts closest to INSN. Return -1 if we couldn't
125 find such a basic block or the beginning is more than
126 SEARCH_LIMIT instructions before INSN. Use SEARCH_LIMIT = -1 for
129 The delay slot filling code destroys the control-flow graph so,
130 instead of finding the basic block containing INSN, we search
131 backwards toward a BARRIER where the live register information is
135 find_basic_block (rtx insn
, int search_limit
)
137 /* Scan backwards to the previous BARRIER. Then see if we can find a
138 label that starts a basic block. Return the basic block number. */
139 for (insn
= prev_nonnote_insn (insn
);
140 insn
&& !BARRIER_P (insn
) && search_limit
!= 0;
141 insn
= prev_nonnote_insn (insn
), --search_limit
)
144 /* The closest BARRIER is too far away. */
145 if (search_limit
== 0)
148 /* The start of the function. */
150 return ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->index
;
152 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
153 anything other than a CODE_LABEL or note, we can't find this code. */
154 for (insn
= next_nonnote_insn (insn
);
155 insn
&& LABEL_P (insn
);
156 insn
= next_nonnote_insn (insn
))
157 if (BLOCK_FOR_INSN (insn
))
158 return BLOCK_FOR_INSN (insn
)->index
;
163 /* Similar to next_insn, but ignores insns in the delay slots of
164 an annulled branch. */
167 next_insn_no_annul (rtx insn
)
171 /* If INSN is an annulled branch, skip any insns from the target
174 && INSN_ANNULLED_BRANCH_P (insn
)
175 && NEXT_INSN (PREV_INSN (insn
)) != insn
)
177 rtx_insn
*next
= NEXT_INSN (insn
);
179 while ((NONJUMP_INSN_P (next
) || JUMP_P (next
) || CALL_P (next
))
180 && INSN_FROM_TARGET_P (next
))
183 next
= NEXT_INSN (insn
);
187 insn
= NEXT_INSN (insn
);
188 if (insn
&& NONJUMP_INSN_P (insn
)
189 && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
190 insn
= XVECEXP (PATTERN (insn
), 0, 0);
196 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
197 which resources are referenced by the insn. If INCLUDE_DELAYED_EFFECTS
198 is TRUE, resources used by the called routine will be included for
202 mark_referenced_resources (rtx x
, struct resources
*res
,
203 bool include_delayed_effects
)
205 enum rtx_code code
= GET_CODE (x
);
208 const char *format_ptr
;
210 /* Handle leaf items for which we set resource flags. Also, special-case
211 CALL, SET and CLOBBER operators. */
222 if (!REG_P (SUBREG_REG (x
)))
223 mark_referenced_resources (SUBREG_REG (x
), res
, false);
226 unsigned int regno
= subreg_regno (x
);
227 unsigned int last_regno
= regno
+ subreg_nregs (x
);
229 gcc_assert (last_regno
<= FIRST_PSEUDO_REGISTER
);
230 for (r
= regno
; r
< last_regno
; r
++)
231 SET_HARD_REG_BIT (res
->regs
, r
);
236 gcc_assert (HARD_REGISTER_P (x
));
237 add_to_hard_reg_set (&res
->regs
, GET_MODE (x
), REGNO (x
));
241 /* If this memory shouldn't change, it really isn't referencing
243 if (! MEM_READONLY_P (x
))
245 res
->volatil
|= MEM_VOLATILE_P (x
);
247 /* Mark registers used to access memory. */
248 mark_referenced_resources (XEXP (x
, 0), res
, false);
255 case UNSPEC_VOLATILE
:
258 /* Traditional asm's are always volatile. */
263 res
->volatil
|= MEM_VOLATILE_P (x
);
265 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
266 We can not just fall through here since then we would be confused
267 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
268 traditional asms unlike their normal usage. */
270 for (i
= 0; i
< ASM_OPERANDS_INPUT_LENGTH (x
); i
++)
271 mark_referenced_resources (ASM_OPERANDS_INPUT (x
, i
), res
, false);
275 /* The first operand will be a (MEM (xxx)) but doesn't really reference
276 memory. The second operand may be referenced, though. */
277 mark_referenced_resources (XEXP (XEXP (x
, 0), 0), res
, false);
278 mark_referenced_resources (XEXP (x
, 1), res
, false);
282 /* Usually, the first operand of SET is set, not referenced. But
283 registers used to access memory are referenced. SET_DEST is
284 also referenced if it is a ZERO_EXTRACT. */
286 mark_referenced_resources (SET_SRC (x
), res
, false);
289 if (GET_CODE (x
) == ZERO_EXTRACT
290 || GET_CODE (x
) == STRICT_LOW_PART
)
291 mark_referenced_resources (x
, res
, false);
292 else if (GET_CODE (x
) == SUBREG
)
295 mark_referenced_resources (XEXP (x
, 0), res
, false);
302 if (include_delayed_effects
)
304 /* A CALL references memory, the frame pointer if it exists, the
305 stack pointer, any global registers and any registers given in
306 USE insns immediately in front of the CALL.
308 However, we may have moved some of the parameter loading insns
309 into the delay slot of this CALL. If so, the USE's for them
310 don't count and should be skipped. */
311 rtx_insn
*insn
= PREV_INSN (x
);
312 rtx_sequence
*sequence
= 0;
316 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
317 if (NEXT_INSN (insn
) != x
)
319 sequence
= as_a
<rtx_sequence
*> (PATTERN (NEXT_INSN (insn
)));
320 seq_size
= sequence
->len ();
321 gcc_assert (GET_CODE (sequence
) == SEQUENCE
);
325 SET_HARD_REG_BIT (res
->regs
, STACK_POINTER_REGNUM
);
326 if (frame_pointer_needed
)
328 SET_HARD_REG_BIT (res
->regs
, FRAME_POINTER_REGNUM
);
329 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
330 SET_HARD_REG_BIT (res
->regs
, HARD_FRAME_POINTER_REGNUM
);
334 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
336 SET_HARD_REG_BIT (res
->regs
, i
);
338 /* Check for a REG_SETJMP. If it exists, then we must
339 assume that this call can need any register.
341 This is done to be more conservative about how we handle setjmp.
342 We assume that they both use and set all registers. Using all
343 registers ensures that a register will not be considered dead
344 just because it crosses a setjmp call. A register should be
345 considered dead only if the setjmp call returns nonzero. */
346 if (find_reg_note (x
, REG_SETJMP
, NULL
))
347 SET_HARD_REG_SET (res
->regs
);
352 for (link
= CALL_INSN_FUNCTION_USAGE (x
);
354 link
= XEXP (link
, 1))
355 if (GET_CODE (XEXP (link
, 0)) == USE
)
357 for (i
= 1; i
< seq_size
; i
++)
359 rtx slot_pat
= PATTERN (sequence
->element (i
));
360 if (GET_CODE (slot_pat
) == SET
361 && rtx_equal_p (SET_DEST (slot_pat
),
362 XEXP (XEXP (link
, 0), 0)))
366 mark_referenced_resources (XEXP (XEXP (link
, 0), 0),
372 /* ... fall through to other INSN processing ... */
377 if (GET_CODE (PATTERN (x
)) == COND_EXEC
)
378 /* In addition to the usual references, also consider all outputs
379 as referenced, to compensate for mark_set_resources treating
380 them as killed. This is similar to ZERO_EXTRACT / STRICT_LOW_PART
381 handling, execpt that we got a partial incidence instead of a partial
383 mark_set_resources (x
, res
, 0,
384 include_delayed_effects
385 ? MARK_SRC_DEST_CALL
: MARK_SRC_DEST
);
387 #ifdef INSN_REFERENCES_ARE_DELAYED
388 if (! include_delayed_effects
389 && INSN_REFERENCES_ARE_DELAYED (x
))
393 /* No special processing, just speed up. */
394 mark_referenced_resources (PATTERN (x
), res
, include_delayed_effects
);
401 /* Process each sub-expression and flag what it needs. */
402 format_ptr
= GET_RTX_FORMAT (code
);
403 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
404 switch (*format_ptr
++)
407 mark_referenced_resources (XEXP (x
, i
), res
, include_delayed_effects
);
411 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
412 mark_referenced_resources (XVECEXP (x
, i
, j
), res
,
413 include_delayed_effects
);
418 /* A subroutine of mark_target_live_regs. Search forward from TARGET
419 looking for registers that are set before they are used. These are dead.
420 Stop after passing a few conditional jumps, and/or a small
421 number of unconditional branches. */
424 find_dead_or_set_registers (rtx target
, struct resources
*res
,
425 rtx
*jump_target
, int jump_count
,
426 struct resources set
, struct resources needed
)
428 HARD_REG_SET scratch
;
433 for (insn
= target
; insn
; insn
= next
)
435 rtx this_jump_insn
= insn
;
437 next
= NEXT_INSN (insn
);
439 /* If this instruction can throw an exception, then we don't
440 know where we might end up next. That means that we have to
441 assume that whatever we have already marked as live really is
443 if (can_throw_internal (insn
))
446 switch (GET_CODE (insn
))
449 /* After a label, any pending dead registers that weren't yet
450 used can be made dead. */
451 AND_COMPL_HARD_REG_SET (pending_dead_regs
, needed
.regs
);
452 AND_COMPL_HARD_REG_SET (res
->regs
, pending_dead_regs
);
453 CLEAR_HARD_REG_SET (pending_dead_regs
);
462 if (GET_CODE (PATTERN (insn
)) == USE
)
464 /* If INSN is a USE made by update_block, we care about the
465 underlying insn. Any registers set by the underlying insn
466 are live since the insn is being done somewhere else. */
467 if (INSN_P (XEXP (PATTERN (insn
), 0)))
468 mark_set_resources (XEXP (PATTERN (insn
), 0), res
, 0,
471 /* All other USE insns are to be ignored. */
474 else if (GET_CODE (PATTERN (insn
)) == CLOBBER
)
476 else if (rtx_sequence
*seq
=
477 dyn_cast
<rtx_sequence
*> (PATTERN (insn
)))
479 /* An unconditional jump can be used to fill the delay slot
480 of a call, so search for a JUMP_INSN in any position. */
481 for (i
= 0; i
< seq
->len (); i
++)
483 this_jump_insn
= seq
->element (i
);
484 if (JUMP_P (this_jump_insn
))
493 if (JUMP_P (this_jump_insn
))
495 if (jump_count
++ < 10)
497 if (any_uncondjump_p (this_jump_insn
)
498 || ANY_RETURN_P (PATTERN (this_jump_insn
)))
500 next
= JUMP_LABEL (this_jump_insn
);
501 if (ANY_RETURN_P (next
))
507 *jump_target
= JUMP_LABEL (this_jump_insn
);
510 else if (any_condjump_p (this_jump_insn
))
512 struct resources target_set
, target_res
;
513 struct resources fallthrough_res
;
515 /* We can handle conditional branches here by following
516 both paths, and then IOR the results of the two paths
517 together, which will give us registers that are dead
518 on both paths. Since this is expensive, we give it
519 a much higher cost than unconditional branches. The
520 cost was chosen so that we will follow at most 1
521 conditional branch. */
524 if (jump_count
>= 10)
527 mark_referenced_resources (insn
, &needed
, true);
529 /* For an annulled branch, mark_set_resources ignores slots
530 filled by instructions from the target. This is correct
531 if the branch is not taken. Since we are following both
532 paths from the branch, we must also compute correct info
533 if the branch is taken. We do this by inverting all of
534 the INSN_FROM_TARGET_P bits, calling mark_set_resources,
535 and then inverting the INSN_FROM_TARGET_P bits again. */
537 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
538 && INSN_ANNULLED_BRANCH_P (this_jump_insn
))
540 rtx_sequence
*seq
= as_a
<rtx_sequence
*> (PATTERN (insn
));
541 for (i
= 1; i
< seq
->len (); i
++)
542 INSN_FROM_TARGET_P (seq
->element (i
))
543 = ! INSN_FROM_TARGET_P (seq
->element (i
));
546 mark_set_resources (insn
, &target_set
, 0,
549 for (i
= 1; i
< seq
->len (); i
++)
550 INSN_FROM_TARGET_P (seq
->element (i
))
551 = ! INSN_FROM_TARGET_P (seq
->element (i
));
553 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
557 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
562 COPY_HARD_REG_SET (scratch
, target_set
.regs
);
563 AND_COMPL_HARD_REG_SET (scratch
, needed
.regs
);
564 AND_COMPL_HARD_REG_SET (target_res
.regs
, scratch
);
566 fallthrough_res
= *res
;
567 COPY_HARD_REG_SET (scratch
, set
.regs
);
568 AND_COMPL_HARD_REG_SET (scratch
, needed
.regs
);
569 AND_COMPL_HARD_REG_SET (fallthrough_res
.regs
, scratch
);
571 if (!ANY_RETURN_P (JUMP_LABEL (this_jump_insn
)))
572 find_dead_or_set_registers (JUMP_LABEL (this_jump_insn
),
573 &target_res
, 0, jump_count
,
575 find_dead_or_set_registers (next
,
576 &fallthrough_res
, 0, jump_count
,
578 IOR_HARD_REG_SET (fallthrough_res
.regs
, target_res
.regs
);
579 AND_HARD_REG_SET (res
->regs
, fallthrough_res
.regs
);
587 /* Don't try this optimization if we expired our jump count
588 above, since that would mean there may be an infinite loop
589 in the function being compiled. */
595 mark_referenced_resources (insn
, &needed
, true);
596 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
598 COPY_HARD_REG_SET (scratch
, set
.regs
);
599 AND_COMPL_HARD_REG_SET (scratch
, needed
.regs
);
600 AND_COMPL_HARD_REG_SET (res
->regs
, scratch
);
606 /* Given X, a part of an insn, and a pointer to a `struct resource',
607 RES, indicate which resources are modified by the insn. If
608 MARK_TYPE is MARK_SRC_DEST_CALL, also mark resources potentially
609 set by the called routine.
611 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
612 objects are being referenced instead of set.
614 We never mark the insn as modifying the condition code unless it explicitly
615 SETs CC0 even though this is not totally correct. The reason for this is
616 that we require a SET of CC0 to immediately precede the reference to CC0.
617 So if some other insn sets CC0 as a side-effect, we know it cannot affect
618 our computation and thus may be placed in a delay slot. */
621 mark_set_resources (rtx x
, struct resources
*res
, int in_dest
,
622 enum mark_resource_type mark_type
)
627 const char *format_ptr
;
644 /* These don't set any resources. */
653 /* Called routine modifies the condition code, memory, any registers
654 that aren't saved across calls, global registers and anything
655 explicitly CLOBBERed immediately after the CALL_INSN. */
657 if (mark_type
== MARK_SRC_DEST_CALL
)
662 res
->cc
= res
->memory
= 1;
664 get_call_reg_set_usage (x
, ®s
, regs_invalidated_by_call
);
665 IOR_HARD_REG_SET (res
->regs
, regs
);
667 for (link
= CALL_INSN_FUNCTION_USAGE (x
);
668 link
; link
= XEXP (link
, 1))
669 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
670 mark_set_resources (SET_DEST (XEXP (link
, 0)), res
, 1,
673 /* Check for a REG_SETJMP. If it exists, then we must
674 assume that this call can clobber any register. */
675 if (find_reg_note (x
, REG_SETJMP
, NULL
))
676 SET_HARD_REG_SET (res
->regs
);
679 /* ... and also what its RTL says it modifies, if anything. */
684 /* An insn consisting of just a CLOBBER (or USE) is just for flow
685 and doesn't actually do anything, so we ignore it. */
687 #ifdef INSN_SETS_ARE_DELAYED
688 if (mark_type
!= MARK_SRC_DEST_CALL
689 && INSN_SETS_ARE_DELAYED (x
))
694 if (GET_CODE (x
) != USE
&& GET_CODE (x
) != CLOBBER
)
699 /* If the source of a SET is a CALL, this is actually done by
700 the called routine. So only include it if we are to include the
701 effects of the calling routine. */
703 mark_set_resources (SET_DEST (x
), res
,
704 (mark_type
== MARK_SRC_DEST_CALL
705 || GET_CODE (SET_SRC (x
)) != CALL
),
708 mark_set_resources (SET_SRC (x
), res
, 0, MARK_SRC_DEST
);
712 mark_set_resources (XEXP (x
, 0), res
, 1, MARK_SRC_DEST
);
717 rtx_sequence
*seq
= as_a
<rtx_sequence
*> (x
);
718 rtx control
= seq
->element (0);
719 bool annul_p
= JUMP_P (control
) && INSN_ANNULLED_BRANCH_P (control
);
721 mark_set_resources (control
, res
, 0, mark_type
);
722 for (i
= seq
->len () - 1; i
>= 0; --i
)
724 rtx elt
= seq
->element (i
);
725 if (!annul_p
&& INSN_FROM_TARGET_P (elt
))
726 mark_set_resources (elt
, res
, 0, mark_type
);
735 mark_set_resources (XEXP (x
, 0), res
, 1, MARK_SRC_DEST
);
740 mark_set_resources (XEXP (x
, 0), res
, 1, MARK_SRC_DEST
);
741 mark_set_resources (XEXP (XEXP (x
, 1), 0), res
, 0, MARK_SRC_DEST
);
742 mark_set_resources (XEXP (XEXP (x
, 1), 1), res
, 0, MARK_SRC_DEST
);
747 mark_set_resources (XEXP (x
, 0), res
, in_dest
, MARK_SRC_DEST
);
748 mark_set_resources (XEXP (x
, 1), res
, 0, MARK_SRC_DEST
);
749 mark_set_resources (XEXP (x
, 2), res
, 0, MARK_SRC_DEST
);
756 res
->volatil
|= MEM_VOLATILE_P (x
);
759 mark_set_resources (XEXP (x
, 0), res
, 0, MARK_SRC_DEST
);
765 if (!REG_P (SUBREG_REG (x
)))
766 mark_set_resources (SUBREG_REG (x
), res
, in_dest
, mark_type
);
769 unsigned int regno
= subreg_regno (x
);
770 unsigned int last_regno
= regno
+ subreg_nregs (x
);
772 gcc_assert (last_regno
<= FIRST_PSEUDO_REGISTER
);
773 for (r
= regno
; r
< last_regno
; r
++)
774 SET_HARD_REG_BIT (res
->regs
, r
);
782 gcc_assert (HARD_REGISTER_P (x
));
783 add_to_hard_reg_set (&res
->regs
, GET_MODE (x
), REGNO (x
));
787 case UNSPEC_VOLATILE
:
789 /* Traditional asm's are always volatile. */
798 res
->volatil
|= MEM_VOLATILE_P (x
);
800 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
801 We can not just fall through here since then we would be confused
802 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
803 traditional asms unlike their normal usage. */
805 for (i
= 0; i
< ASM_OPERANDS_INPUT_LENGTH (x
); i
++)
806 mark_set_resources (ASM_OPERANDS_INPUT (x
, i
), res
, in_dest
,
814 /* Process each sub-expression and flag what it needs. */
815 format_ptr
= GET_RTX_FORMAT (code
);
816 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
817 switch (*format_ptr
++)
820 mark_set_resources (XEXP (x
, i
), res
, in_dest
, mark_type
);
824 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
825 mark_set_resources (XVECEXP (x
, i
, j
), res
, in_dest
, mark_type
);
830 /* Return TRUE if INSN is a return, possibly with a filled delay slot. */
833 return_insn_p (const_rtx insn
)
835 if (JUMP_P (insn
) && ANY_RETURN_P (PATTERN (insn
)))
838 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
839 return return_insn_p (XVECEXP (PATTERN (insn
), 0, 0));
844 /* Set the resources that are live at TARGET.
846 If TARGET is zero, we refer to the end of the current function and can
847 return our precomputed value.
849 Otherwise, we try to find out what is live by consulting the basic block
850 information. This is tricky, because we must consider the actions of
851 reload and jump optimization, which occur after the basic block information
854 Accordingly, we proceed as follows::
856 We find the previous BARRIER and look at all immediately following labels
857 (with no intervening active insns) to see if any of them start a basic
858 block. If we hit the start of the function first, we use block 0.
860 Once we have found a basic block and a corresponding first insn, we can
861 accurately compute the live status (by starting at a label following a
862 BARRIER, we are immune to actions taken by reload and jump.) Then we
863 scan all insns between that point and our target. For each CLOBBER (or
864 for call-clobbered regs when we pass a CALL_INSN), mark the appropriate
865 registers are dead. For a SET, mark them as live.
867 We have to be careful when using REG_DEAD notes because they are not
868 updated by such things as find_equiv_reg. So keep track of registers
869 marked as dead that haven't been assigned to, and mark them dead at the
870 next CODE_LABEL since reload and jump won't propagate values across labels.
872 If we cannot find the start of a basic block (should be a very rare
873 case, if it can happen at all), mark everything as potentially live.
875 Next, scan forward from TARGET looking for things set or clobbered
876 before they are used. These are not live.
878 Because we can be called many times on the same target, save our results
879 in a hash table indexed by INSN_UID. This is only done if the function
880 init_resource_info () was invoked before we are called. */
883 mark_target_live_regs (rtx insns
, rtx target
, struct resources
*res
)
887 struct target_info
*tinfo
= NULL
;
891 HARD_REG_SET scratch
;
892 struct resources set
, needed
;
894 /* Handle end of function. */
895 if (target
== 0 || ANY_RETURN_P (target
))
897 *res
= end_of_function_needs
;
901 /* Handle return insn. */
902 else if (return_insn_p (target
))
904 *res
= end_of_function_needs
;
905 mark_referenced_resources (target
, res
, false);
909 /* We have to assume memory is needed, but the CC isn't. */
914 /* See if we have computed this value already. */
915 if (target_hash_table
!= NULL
)
917 for (tinfo
= target_hash_table
[INSN_UID (target
) % TARGET_HASH_PRIME
];
918 tinfo
; tinfo
= tinfo
->next
)
919 if (tinfo
->uid
== INSN_UID (target
))
922 /* Start by getting the basic block number. If we have saved
923 information, we can get it from there unless the insn at the
924 start of the basic block has been deleted. */
925 if (tinfo
&& tinfo
->block
!= -1
926 && ! INSN_DELETED_P (BB_HEAD (BASIC_BLOCK_FOR_FN (cfun
,
932 b
= find_basic_block (target
, MAX_DELAY_SLOT_LIVE_SEARCH
);
934 if (target_hash_table
!= NULL
)
938 /* If the information is up-to-date, use it. Otherwise, we will
940 if (b
== tinfo
->block
&& b
!= -1 && tinfo
->bb_tick
== bb_ticks
[b
])
942 COPY_HARD_REG_SET (res
->regs
, tinfo
->live_regs
);
948 /* Allocate a place to put our results and chain it into the
950 tinfo
= XNEW (struct target_info
);
951 tinfo
->uid
= INSN_UID (target
);
954 = target_hash_table
[INSN_UID (target
) % TARGET_HASH_PRIME
];
955 target_hash_table
[INSN_UID (target
) % TARGET_HASH_PRIME
] = tinfo
;
959 CLEAR_HARD_REG_SET (pending_dead_regs
);
961 /* If we found a basic block, get the live registers from it and update
962 them with anything set or killed between its start and the insn before
963 TARGET; this custom life analysis is really about registers so we need
964 to use the LR problem. Otherwise, we must assume everything is live. */
967 regset regs_live
= DF_LR_IN (BASIC_BLOCK_FOR_FN (cfun
, b
));
968 rtx start_insn
, stop_insn
;
970 /* Compute hard regs live at start of block. */
971 REG_SET_TO_HARD_REG_SET (current_live_regs
, regs_live
);
973 /* Get starting and ending insn, handling the case where each might
975 start_insn
= (b
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
->index
?
976 insns
: BB_HEAD (BASIC_BLOCK_FOR_FN (cfun
, b
)));
979 if (NONJUMP_INSN_P (start_insn
)
980 && GET_CODE (PATTERN (start_insn
)) == SEQUENCE
)
981 start_insn
= XVECEXP (PATTERN (start_insn
), 0, 0);
983 if (NONJUMP_INSN_P (stop_insn
)
984 && GET_CODE (PATTERN (stop_insn
)) == SEQUENCE
)
985 stop_insn
= next_insn (PREV_INSN (stop_insn
));
987 for (insn
= start_insn
; insn
!= stop_insn
;
988 insn
= next_insn_no_annul (insn
))
991 rtx real_insn
= insn
;
992 enum rtx_code code
= GET_CODE (insn
);
994 if (DEBUG_INSN_P (insn
))
997 /* If this insn is from the target of a branch, it isn't going to
998 be used in the sequel. If it is used in both cases, this
999 test will not be true. */
1000 if ((code
== INSN
|| code
== JUMP_INSN
|| code
== CALL_INSN
)
1001 && INSN_FROM_TARGET_P (insn
))
1004 /* If this insn is a USE made by update_block, we care about the
1007 && GET_CODE (PATTERN (insn
)) == USE
1008 && INSN_P (XEXP (PATTERN (insn
), 0)))
1009 real_insn
= XEXP (PATTERN (insn
), 0);
1011 if (CALL_P (real_insn
))
1013 /* Values in call-clobbered registers survive a COND_EXEC CALL
1014 if that is not executed; this matters for resoure use because
1015 they may be used by a complementarily (or more strictly)
1016 predicated instruction, or if the CALL is NORETURN. */
1017 if (GET_CODE (PATTERN (real_insn
)) != COND_EXEC
)
1019 HARD_REG_SET regs_invalidated_by_this_call
;
1020 get_call_reg_set_usage (real_insn
,
1021 ®s_invalidated_by_this_call
,
1022 regs_invalidated_by_call
);
1023 /* CALL clobbers all call-used regs that aren't fixed except
1024 sp, ap, and fp. Do this before setting the result of the
1026 AND_COMPL_HARD_REG_SET (current_live_regs
,
1027 regs_invalidated_by_this_call
);
1030 /* A CALL_INSN sets any global register live, since it may
1031 have been modified by the call. */
1032 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1034 SET_HARD_REG_BIT (current_live_regs
, i
);
1037 /* Mark anything killed in an insn to be deadened at the next
1038 label. Ignore USE insns; the only REG_DEAD notes will be for
1039 parameters. But they might be early. A CALL_INSN will usually
1040 clobber registers used for parameters. It isn't worth bothering
1041 with the unlikely case when it won't. */
1042 if ((NONJUMP_INSN_P (real_insn
)
1043 && GET_CODE (PATTERN (real_insn
)) != USE
1044 && GET_CODE (PATTERN (real_insn
)) != CLOBBER
)
1045 || JUMP_P (real_insn
)
1046 || CALL_P (real_insn
))
1048 for (link
= REG_NOTES (real_insn
); link
; link
= XEXP (link
, 1))
1049 if (REG_NOTE_KIND (link
) == REG_DEAD
1050 && REG_P (XEXP (link
, 0))
1051 && REGNO (XEXP (link
, 0)) < FIRST_PSEUDO_REGISTER
)
1052 add_to_hard_reg_set (&pending_dead_regs
,
1053 GET_MODE (XEXP (link
, 0)),
1054 REGNO (XEXP (link
, 0)));
1056 note_stores (PATTERN (real_insn
), update_live_status
, NULL
);
1058 /* If any registers were unused after this insn, kill them.
1059 These notes will always be accurate. */
1060 for (link
= REG_NOTES (real_insn
); link
; link
= XEXP (link
, 1))
1061 if (REG_NOTE_KIND (link
) == REG_UNUSED
1062 && REG_P (XEXP (link
, 0))
1063 && REGNO (XEXP (link
, 0)) < FIRST_PSEUDO_REGISTER
)
1064 remove_from_hard_reg_set (¤t_live_regs
,
1065 GET_MODE (XEXP (link
, 0)),
1066 REGNO (XEXP (link
, 0)));
1069 else if (LABEL_P (real_insn
))
1073 /* A label clobbers the pending dead registers since neither
1074 reload nor jump will propagate a value across a label. */
1075 AND_COMPL_HARD_REG_SET (current_live_regs
, pending_dead_regs
);
1076 CLEAR_HARD_REG_SET (pending_dead_regs
);
1078 /* We must conservatively assume that all registers that used
1079 to be live here still are. The fallthrough edge may have
1080 left a live register uninitialized. */
1081 bb
= BLOCK_FOR_INSN (real_insn
);
1084 HARD_REG_SET extra_live
;
1086 REG_SET_TO_HARD_REG_SET (extra_live
, DF_LR_IN (bb
));
1087 IOR_HARD_REG_SET (current_live_regs
, extra_live
);
1091 /* The beginning of the epilogue corresponds to the end of the
1092 RTL chain when there are no epilogue insns. Certain resources
1093 are implicitly required at that point. */
1094 else if (NOTE_P (real_insn
)
1095 && NOTE_KIND (real_insn
) == NOTE_INSN_EPILOGUE_BEG
)
1096 IOR_HARD_REG_SET (current_live_regs
, start_of_epilogue_needs
.regs
);
1099 COPY_HARD_REG_SET (res
->regs
, current_live_regs
);
1103 tinfo
->bb_tick
= bb_ticks
[b
];
1107 /* We didn't find the start of a basic block. Assume everything
1108 in use. This should happen only extremely rarely. */
1109 SET_HARD_REG_SET (res
->regs
);
1111 CLEAR_RESOURCE (&set
);
1112 CLEAR_RESOURCE (&needed
);
1114 jump_insn
= find_dead_or_set_registers (target
, res
, &jump_target
, 0,
1117 /* If we hit an unconditional branch, we have another way of finding out
1118 what is live: we can see what is live at the branch target and include
1119 anything used but not set before the branch. We add the live
1120 resources found using the test below to those found until now. */
1124 struct resources new_resources
;
1125 rtx stop_insn
= next_active_insn (jump_insn
);
1127 if (!ANY_RETURN_P (jump_target
))
1128 jump_target
= next_active_insn (jump_target
);
1129 mark_target_live_regs (insns
, jump_target
, &new_resources
);
1130 CLEAR_RESOURCE (&set
);
1131 CLEAR_RESOURCE (&needed
);
1133 /* Include JUMP_INSN in the needed registers. */
1134 for (insn
= target
; insn
!= stop_insn
; insn
= next_active_insn (insn
))
1136 mark_referenced_resources (insn
, &needed
, true);
1138 COPY_HARD_REG_SET (scratch
, needed
.regs
);
1139 AND_COMPL_HARD_REG_SET (scratch
, set
.regs
);
1140 IOR_HARD_REG_SET (new_resources
.regs
, scratch
);
1142 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1145 IOR_HARD_REG_SET (res
->regs
, new_resources
.regs
);
1150 COPY_HARD_REG_SET (tinfo
->live_regs
, res
->regs
);
1154 /* Initialize the resources required by mark_target_live_regs ().
1155 This should be invoked before the first call to mark_target_live_regs. */
1158 init_resource_info (rtx epilogue_insn
)
1163 /* Indicate what resources are required to be valid at the end of the current
1164 function. The condition code never is and memory always is.
1165 The stack pointer is needed unless EXIT_IGNORE_STACK is true
1166 and there is an epilogue that restores the original stack pointer
1167 from the frame pointer. Registers used to return the function value
1168 are needed. Registers holding global variables are needed. */
1170 end_of_function_needs
.cc
= 0;
1171 end_of_function_needs
.memory
= 1;
1172 CLEAR_HARD_REG_SET (end_of_function_needs
.regs
);
1174 if (frame_pointer_needed
)
1176 SET_HARD_REG_BIT (end_of_function_needs
.regs
, FRAME_POINTER_REGNUM
);
1177 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1178 SET_HARD_REG_BIT (end_of_function_needs
.regs
, HARD_FRAME_POINTER_REGNUM
);
1181 if (!(frame_pointer_needed
1182 && EXIT_IGNORE_STACK
1184 && !crtl
->sp_is_unchanging
))
1185 SET_HARD_REG_BIT (end_of_function_needs
.regs
, STACK_POINTER_REGNUM
);
1187 if (crtl
->return_rtx
!= 0)
1188 mark_referenced_resources (crtl
->return_rtx
,
1189 &end_of_function_needs
, true);
1191 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1193 #ifdef EPILOGUE_USES
1194 || EPILOGUE_USES (i
)
1197 SET_HARD_REG_BIT (end_of_function_needs
.regs
, i
);
1199 /* The registers required to be live at the end of the function are
1200 represented in the flow information as being dead just prior to
1201 reaching the end of the function. For example, the return of a value
1202 might be represented by a USE of the return register immediately
1203 followed by an unconditional jump to the return label where the
1204 return label is the end of the RTL chain. The end of the RTL chain
1205 is then taken to mean that the return register is live.
1207 This sequence is no longer maintained when epilogue instructions are
1208 added to the RTL chain. To reconstruct the original meaning, the
1209 start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
1210 point where these registers become live (start_of_epilogue_needs).
1211 If epilogue instructions are present, the registers set by those
1212 instructions won't have been processed by flow. Thus, those
1213 registers are additionally required at the end of the RTL chain
1214 (end_of_function_needs). */
1216 start_of_epilogue_needs
= end_of_function_needs
;
1218 while ((epilogue_insn
= next_nonnote_insn (epilogue_insn
)))
1220 mark_set_resources (epilogue_insn
, &end_of_function_needs
, 0,
1221 MARK_SRC_DEST_CALL
);
1222 if (return_insn_p (epilogue_insn
))
1226 /* Allocate and initialize the tables used by mark_target_live_regs. */
1227 target_hash_table
= XCNEWVEC (struct target_info
*, TARGET_HASH_PRIME
);
1228 bb_ticks
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
1230 /* Set the BLOCK_FOR_INSN of each label that starts a basic block. */
1231 FOR_EACH_BB_FN (bb
, cfun
)
1232 if (LABEL_P (BB_HEAD (bb
)))
1233 BLOCK_FOR_INSN (BB_HEAD (bb
)) = bb
;
1236 /* Free up the resources allocated to mark_target_live_regs (). This
1237 should be invoked after the last call to mark_target_live_regs (). */
1240 free_resource_info (void)
1244 if (target_hash_table
!= NULL
)
1248 for (i
= 0; i
< TARGET_HASH_PRIME
; ++i
)
1250 struct target_info
*ti
= target_hash_table
[i
];
1254 struct target_info
*next
= ti
->next
;
1260 free (target_hash_table
);
1261 target_hash_table
= NULL
;
1264 if (bb_ticks
!= NULL
)
1270 FOR_EACH_BB_FN (bb
, cfun
)
1271 if (LABEL_P (BB_HEAD (bb
)))
1272 BLOCK_FOR_INSN (BB_HEAD (bb
)) = NULL
;
1275 /* Clear any hashed information that we have stored for INSN. */
1278 clear_hashed_info_for_insn (rtx insn
)
1280 struct target_info
*tinfo
;
1282 if (target_hash_table
!= NULL
)
1284 for (tinfo
= target_hash_table
[INSN_UID (insn
) % TARGET_HASH_PRIME
];
1285 tinfo
; tinfo
= tinfo
->next
)
1286 if (tinfo
->uid
== INSN_UID (insn
))
1294 /* Increment the tick count for the basic block that contains INSN. */
1297 incr_ticks_for_insn (rtx insn
)
1299 int b
= find_basic_block (insn
, MAX_DELAY_SLOT_LIVE_SEARCH
);
1305 /* Add TRIAL to the set of resources used at the end of the current
1308 mark_end_of_function_resources (rtx trial
, bool include_delayed_effects
)
1310 mark_referenced_resources (trial
, &end_of_function_needs
,
1311 include_delayed_effects
);