1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
27 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
42 #include "sched-int.h"
48 static regset_head reg_pending_sets_head
;
49 static regset_head reg_pending_clobbers_head
;
50 static regset_head reg_pending_uses_head
;
52 static regset reg_pending_sets
;
53 static regset reg_pending_clobbers
;
54 static regset reg_pending_uses
;
56 /* The following enumeration values tell us what dependencies we
57 should use to implement the barrier. We use true-dependencies for
58 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
59 enum reg_pending_barrier_mode
66 static enum reg_pending_barrier_mode reg_pending_barrier
;
68 /* To speed up the test for duplicate dependency links we keep a
69 record of dependencies created by add_dependence when the average
70 number of instructions in a basic block is very large.
72 Studies have shown that there is typically around 5 instructions between
73 branches for typical C code. So we can make a guess that the average
74 basic block is approximately 5 instructions long; we will choose 100X
75 the average size as a very large basic block.
77 Each insn has associated bitmaps for its dependencies. Each bitmap
78 has enough entries to represent a dependency on any other insn in
79 the insn chain. All bitmap for true dependencies cache is
80 allocated then the rest two ones are also allocated. */
81 static bitmap_head
*true_dependency_cache
;
82 static bitmap_head
*anti_dependency_cache
;
83 static bitmap_head
*output_dependency_cache
;
86 /* To speed up checking consistency of formed forward insn
87 dependencies we use the following cache. Another possible solution
88 could be switching off checking duplication of insns in forward
90 #ifdef ENABLE_CHECKING
91 static bitmap_head
*forward_dependency_cache
;
94 static int deps_may_trap_p (rtx
);
95 static void add_dependence_list (rtx
, rtx
, enum reg_note
);
96 static void add_dependence_list_and_free (rtx
, rtx
*, enum reg_note
);
97 static void set_sched_group_p (rtx
);
99 static void flush_pending_lists (struct deps
*, rtx
, int, int);
100 static void sched_analyze_1 (struct deps
*, rtx
, rtx
);
101 static void sched_analyze_2 (struct deps
*, rtx
, rtx
);
102 static void sched_analyze_insn (struct deps
*, rtx
, rtx
, rtx
);
104 static rtx
get_condition (rtx
);
105 static int conditions_mutex_p (rtx
, rtx
);
107 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
110 deps_may_trap_p (rtx mem
)
112 rtx addr
= XEXP (mem
, 0);
114 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
116 rtx t
= get_reg_known_value (REGNO (addr
));
120 return rtx_addr_can_trap_p (addr
);
123 /* Return the INSN_LIST containing INSN in LIST, or NULL
124 if LIST does not contain INSN. */
127 find_insn_list (rtx insn
, rtx list
)
131 if (XEXP (list
, 0) == insn
)
133 list
= XEXP (list
, 1);
138 /* Find the condition under which INSN is executed. */
141 get_condition (rtx insn
)
143 rtx pat
= PATTERN (insn
);
149 if (GET_CODE (pat
) == COND_EXEC
)
150 return COND_EXEC_TEST (pat
);
152 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
155 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
156 if (XEXP (cond
, 2) == pc_rtx
)
158 else if (XEXP (cond
, 1) == pc_rtx
)
160 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
162 if (revcode
== UNKNOWN
)
164 return gen_rtx_fmt_ee (revcode
, GET_MODE (cond
), XEXP (cond
, 0),
171 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
174 conditions_mutex_p (rtx cond1
, rtx cond2
)
176 if (COMPARISON_P (cond1
)
177 && COMPARISON_P (cond2
)
178 && GET_CODE (cond1
) == reversed_comparison_code (cond2
, NULL
)
179 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
180 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
185 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
186 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
187 type of dependence that this link represents. The function returns
188 nonzero if a new entry has been added to insn's LOG_LINK. */
191 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
197 /* Don't depend an insn on itself. */
201 /* We can get a dependency on deleted insns due to optimizations in
202 the register allocation and reloading or due to splitting. Any
203 such dependency is useless and can be ignored. */
207 /* flow.c doesn't handle conditional lifetimes entirely correctly;
208 calls mess up the conditional lifetimes. */
209 /* ??? add_dependence is the wrong place to be eliding dependencies,
210 as that forgets that the condition expressions themselves may
212 if (!CALL_P (insn
) && !CALL_P (elem
))
214 cond1
= get_condition (insn
);
215 cond2
= get_condition (elem
);
217 && conditions_mutex_p (cond1
, cond2
)
218 /* Make sure first instruction doesn't affect condition of second
219 instruction if switched. */
220 && !modified_in_p (cond1
, elem
)
221 /* Make sure second instruction doesn't affect condition of first
222 instruction if switched. */
223 && !modified_in_p (cond2
, insn
))
228 #ifdef INSN_SCHEDULING
229 /* ??? No good way to tell from here whether we're doing interblock
230 scheduling. Possibly add another callback. */
232 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
233 No need for interblock dependences with calls, since
234 calls are not moved between blocks. Note: the edge where
235 elem is a CALL is still required. */
237 && (INSN_BB (elem
) != INSN_BB (insn
)))
241 /* If we already have a dependency for ELEM, then we do not need to
242 do anything. Avoiding the list walk below can cut compile times
243 dramatically for some code. */
244 if (true_dependency_cache
!= NULL
)
246 enum reg_note present_dep_type
= 0;
248 if (anti_dependency_cache
== NULL
|| output_dependency_cache
== NULL
)
250 if (bitmap_bit_p (&true_dependency_cache
[INSN_LUID (insn
)],
252 /* Do nothing (present_set_type is already 0). */
254 else if (bitmap_bit_p (&anti_dependency_cache
[INSN_LUID (insn
)],
256 present_dep_type
= REG_DEP_ANTI
;
257 else if (bitmap_bit_p (&output_dependency_cache
[INSN_LUID (insn
)],
259 present_dep_type
= REG_DEP_OUTPUT
;
262 if (present_p
&& (int) dep_type
>= (int) present_dep_type
)
267 /* Check that we don't already have this dependence. */
269 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
270 if (XEXP (link
, 0) == elem
)
272 #ifdef INSN_SCHEDULING
273 /* Clear corresponding cache entry because type of the link
275 if (true_dependency_cache
!= NULL
)
277 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
278 bitmap_clear_bit (&anti_dependency_cache
[INSN_LUID (insn
)],
280 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
281 && output_dependency_cache
)
282 bitmap_clear_bit (&output_dependency_cache
[INSN_LUID (insn
)],
289 /* If this is a more restrictive type of dependence than the existing
290 one, then change the existing dependence to this type. */
291 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
292 PUT_REG_NOTE_KIND (link
, dep_type
);
294 #ifdef INSN_SCHEDULING
295 /* If we are adding a dependency to INSN's LOG_LINKs, then
296 note that in the bitmap caches of dependency information. */
297 if (true_dependency_cache
!= NULL
)
299 if ((int) REG_NOTE_KIND (link
) == 0)
300 bitmap_set_bit (&true_dependency_cache
[INSN_LUID (insn
)],
302 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
303 bitmap_set_bit (&anti_dependency_cache
[INSN_LUID (insn
)],
305 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
306 bitmap_set_bit (&output_dependency_cache
[INSN_LUID (insn
)],
312 /* Might want to check one level of transitivity to save conses. */
314 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
315 LOG_LINKS (insn
) = link
;
317 /* Insn dependency, not data dependency. */
318 PUT_REG_NOTE_KIND (link
, dep_type
);
320 #ifdef INSN_SCHEDULING
321 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
322 in the bitmap caches of dependency information. */
323 if (true_dependency_cache
!= NULL
)
325 if ((int) dep_type
== 0)
326 bitmap_set_bit (&true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
327 else if (dep_type
== REG_DEP_ANTI
)
328 bitmap_set_bit (&anti_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
329 else if (dep_type
== REG_DEP_OUTPUT
)
330 bitmap_set_bit (&output_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
336 /* A convenience wrapper to operate on an entire list. */
339 add_dependence_list (rtx insn
, rtx list
, enum reg_note dep_type
)
341 for (; list
; list
= XEXP (list
, 1))
342 add_dependence (insn
, XEXP (list
, 0), dep_type
);
345 /* Similar, but free *LISTP at the same time. */
348 add_dependence_list_and_free (rtx insn
, rtx
*listp
, enum reg_note dep_type
)
351 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
353 next
= XEXP (list
, 1);
354 add_dependence (insn
, XEXP (list
, 0), dep_type
);
355 free_INSN_LIST_node (list
);
359 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
360 goes along with that. */
363 set_sched_group_p (rtx insn
)
367 SCHED_GROUP_P (insn
) = 1;
369 prev
= prev_nonnote_insn (insn
);
370 add_dependence (insn
, prev
, REG_DEP_ANTI
);
373 /* Process an insn's memory dependencies. There are four kinds of
376 (0) read dependence: read follows read
377 (1) true dependence: read follows write
378 (2) anti dependence: write follows read
379 (3) output dependence: write follows write
381 We are careful to build only dependencies which actually exist, and
382 use transitivity to avoid building too many links. */
384 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
385 The MEM is a memory reference contained within INSN, which we are saving
386 so that we can do memory aliasing on it. */
389 add_insn_mem_dependence (struct deps
*deps
, rtx
*insn_list
, rtx
*mem_list
,
394 link
= alloc_INSN_LIST (insn
, *insn_list
);
397 if (current_sched_info
->use_cselib
)
399 mem
= shallow_copy_rtx (mem
);
400 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
402 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
405 deps
->pending_lists_length
++;
408 /* Make a dependency between every memory reference on the pending lists
409 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
410 dependencies for a read operation, similarly with FOR_WRITE. */
413 flush_pending_lists (struct deps
*deps
, rtx insn
, int for_read
,
418 add_dependence_list_and_free (insn
, &deps
->pending_read_insns
,
420 free_EXPR_LIST_list (&deps
->pending_read_mems
);
423 add_dependence_list_and_free (insn
, &deps
->pending_write_insns
,
424 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
425 free_EXPR_LIST_list (&deps
->pending_write_mems
);
426 deps
->pending_lists_length
= 0;
428 add_dependence_list_and_free (insn
, &deps
->last_pending_memory_flush
,
429 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
430 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
431 deps
->pending_flush_length
= 1;
434 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
435 rtx, X, creating all dependencies generated by the write to the
436 destination of X, and reads of everything mentioned. */
439 sched_analyze_1 (struct deps
*deps
, rtx x
, rtx insn
)
442 rtx dest
= XEXP (x
, 0);
443 enum rtx_code code
= GET_CODE (x
);
448 if (GET_CODE (dest
) == PARALLEL
)
452 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
453 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
454 sched_analyze_1 (deps
,
455 gen_rtx_CLOBBER (VOIDmode
,
456 XEXP (XVECEXP (dest
, 0, i
), 0)),
459 if (GET_CODE (x
) == SET
)
460 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
464 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
465 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
467 if (GET_CODE (dest
) == STRICT_LOW_PART
468 || GET_CODE (dest
) == ZERO_EXTRACT
469 || GET_CODE (dest
) == SIGN_EXTRACT
470 || read_modify_subreg_p (dest
))
472 /* These both read and modify the result. We must handle
473 them as writes to get proper dependencies for following
474 instructions. We must handle them as reads to get proper
475 dependencies from this to previous instructions.
476 Thus we need to call sched_analyze_2. */
478 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
480 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
482 /* The second and third arguments are values read by this insn. */
483 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
484 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
486 dest
= XEXP (dest
, 0);
491 regno
= REGNO (dest
);
493 /* A hard reg in a wide mode may really be multiple registers.
494 If so, mark all of them just like the first. */
495 if (regno
< FIRST_PSEUDO_REGISTER
)
497 int i
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
501 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
506 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
509 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
510 it does not reload. Ignore these as they have served their
512 else if (regno
>= deps
->max_reg
)
514 if (GET_CODE (PATTERN (insn
)) != USE
515 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
521 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
523 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
525 /* Pseudos that are REG_EQUIV to something may be replaced
526 by that during reloading. We need only add dependencies for
527 the address in the REG_EQUIV note. */
528 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
530 rtx t
= get_reg_known_value (regno
);
532 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
535 /* Don't let it cross a call after scheduling if it doesn't
536 already cross one. */
537 if (REG_N_CALLS_CROSSED (regno
) == 0)
538 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_ANTI
);
541 else if (MEM_P (dest
))
543 /* Writing memory. */
546 if (current_sched_info
->use_cselib
)
548 t
= shallow_copy_rtx (dest
);
549 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
550 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
554 if (deps
->pending_lists_length
> MAX_PENDING_LIST_LENGTH
)
556 /* Flush all pending reads and writes to prevent the pending lists
557 from getting any larger. Insn scheduling runs too slowly when
558 these lists get long. When compiling GCC with itself,
559 this flush occurs 8 times for sparc, and 10 times for m88k using
560 the default value of 32. */
561 flush_pending_lists (deps
, insn
, false, true);
565 rtx pending
, pending_mem
;
567 pending
= deps
->pending_read_insns
;
568 pending_mem
= deps
->pending_read_mems
;
571 if (anti_dependence (XEXP (pending_mem
, 0), t
))
572 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
574 pending
= XEXP (pending
, 1);
575 pending_mem
= XEXP (pending_mem
, 1);
578 pending
= deps
->pending_write_insns
;
579 pending_mem
= deps
->pending_write_mems
;
582 if (output_dependence (XEXP (pending_mem
, 0), t
))
583 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
585 pending
= XEXP (pending
, 1);
586 pending_mem
= XEXP (pending_mem
, 1);
589 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
592 add_insn_mem_dependence (deps
, &deps
->pending_write_insns
,
593 &deps
->pending_write_mems
, insn
, dest
);
595 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
599 if (GET_CODE (x
) == SET
)
600 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
603 /* Analyze the uses of memory and registers in rtx X in INSN. */
606 sched_analyze_2 (struct deps
*deps
, rtx x
, rtx insn
)
626 /* Ignore constants. Note that we must handle CONST_DOUBLE here
627 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
628 this does not mean that this insn is using cc0. */
633 /* User of CC0 depends on immediately preceding insn. */
634 set_sched_group_p (insn
);
635 /* Don't move CC0 setter to another block (it can set up the
636 same flag for previous CC0 users which is safe). */
637 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
643 int regno
= REGNO (x
);
644 if (regno
< FIRST_PSEUDO_REGISTER
)
646 int i
= hard_regno_nregs
[regno
][GET_MODE (x
)];
648 SET_REGNO_REG_SET (reg_pending_uses
, regno
+ i
);
650 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
651 it does not reload. Ignore these as they have served their
653 else if (regno
>= deps
->max_reg
)
655 if (GET_CODE (PATTERN (insn
)) != USE
656 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
661 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
663 /* Pseudos that are REG_EQUIV to something may be replaced
664 by that during reloading. We need only add dependencies for
665 the address in the REG_EQUIV note. */
666 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
668 rtx t
= get_reg_known_value (regno
);
670 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
673 /* If the register does not already cross any calls, then add this
674 insn to the sched_before_next_call list so that it will still
675 not cross calls after scheduling. */
676 if (REG_N_CALLS_CROSSED (regno
) == 0)
677 deps
->sched_before_next_call
678 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
685 /* Reading memory. */
687 rtx pending
, pending_mem
;
690 if (current_sched_info
->use_cselib
)
692 t
= shallow_copy_rtx (t
);
693 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
694 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
697 pending
= deps
->pending_read_insns
;
698 pending_mem
= deps
->pending_read_mems
;
701 if (read_dependence (XEXP (pending_mem
, 0), t
))
702 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
704 pending
= XEXP (pending
, 1);
705 pending_mem
= XEXP (pending_mem
, 1);
708 pending
= deps
->pending_write_insns
;
709 pending_mem
= deps
->pending_write_mems
;
712 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
714 add_dependence (insn
, XEXP (pending
, 0), 0);
716 pending
= XEXP (pending
, 1);
717 pending_mem
= XEXP (pending_mem
, 1);
720 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
721 if (!JUMP_P (XEXP (u
, 0))
722 || deps_may_trap_p (x
))
723 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
725 /* Always add these dependencies to pending_reads, since
726 this insn may be followed by a write. */
727 add_insn_mem_dependence (deps
, &deps
->pending_read_insns
,
728 &deps
->pending_read_mems
, insn
, x
);
730 /* Take advantage of tail recursion here. */
731 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
735 /* Force pending stores to memory in case a trap handler needs them. */
737 flush_pending_lists (deps
, insn
, true, false);
742 case UNSPEC_VOLATILE
:
744 /* Traditional and volatile asm instructions must be considered to use
745 and clobber all hard registers, all pseudo-registers and all of
746 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
748 Consider for instance a volatile asm that changes the fpu rounding
749 mode. An insn should not be moved across this even if it only uses
750 pseudo-regs because it might give an incorrectly rounded result. */
751 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
752 reg_pending_barrier
= TRUE_BARRIER
;
754 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
755 We can not just fall through here since then we would be confused
756 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
757 traditional asms unlike their normal usage. */
759 if (code
== ASM_OPERANDS
)
761 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
762 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
772 /* These both read and modify the result. We must handle them as writes
773 to get proper dependencies for following instructions. We must handle
774 them as reads to get proper dependencies from this to previous
775 instructions. Thus we need to pass them to both sched_analyze_1
776 and sched_analyze_2. We must call sched_analyze_2 first in order
777 to get the proper antecedent for the read. */
778 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
779 sched_analyze_1 (deps
, x
, insn
);
784 /* op0 = op0 + op1 */
785 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
786 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
787 sched_analyze_1 (deps
, x
, insn
);
794 /* Other cases: walk the insn. */
795 fmt
= GET_RTX_FORMAT (code
);
796 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
799 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
800 else if (fmt
[i
] == 'E')
801 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
802 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
806 /* Analyze an INSN with pattern X to find all dependencies. */
809 sched_analyze_insn (struct deps
*deps
, rtx x
, rtx insn
, rtx loop_notes
)
811 RTX_CODE code
= GET_CODE (x
);
815 if (code
== COND_EXEC
)
817 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
819 /* ??? Should be recording conditions so we reduce the number of
820 false dependencies. */
821 x
= COND_EXEC_CODE (x
);
824 if (code
== SET
|| code
== CLOBBER
)
826 sched_analyze_1 (deps
, x
, insn
);
828 /* Bare clobber insns are used for letting life analysis, reg-stack
829 and others know that a value is dead. Depend on the last call
830 instruction so that reg-stack won't get confused. */
832 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_OUTPUT
);
834 else if (code
== PARALLEL
)
837 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
839 rtx sub
= XVECEXP (x
, 0, i
);
840 code
= GET_CODE (sub
);
842 if (code
== COND_EXEC
)
844 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
845 sub
= COND_EXEC_CODE (sub
);
846 code
= GET_CODE (sub
);
848 if (code
== SET
|| code
== CLOBBER
)
849 sched_analyze_1 (deps
, sub
, insn
);
851 sched_analyze_2 (deps
, sub
, insn
);
855 sched_analyze_2 (deps
, x
, insn
);
857 /* Mark registers CLOBBERED or used by called function. */
860 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
862 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
863 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
865 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
867 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
868 reg_pending_barrier
= MOVE_BARRIER
;
874 next
= next_nonnote_insn (insn
);
875 if (next
&& BARRIER_P (next
))
876 reg_pending_barrier
= TRUE_BARRIER
;
879 rtx pending
, pending_mem
;
880 regset_head tmp_uses
, tmp_sets
;
881 INIT_REG_SET (&tmp_uses
);
882 INIT_REG_SET (&tmp_sets
);
884 (*current_sched_info
->compute_jump_reg_dependencies
)
885 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
886 /* Make latency of jump equal to 0 by using anti-dependence. */
887 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
,
889 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
890 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_ANTI
);
891 add_dependence_list (insn
, reg_last
->clobbers
, REG_DEP_ANTI
);
892 reg_last
->uses_length
++;
893 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
895 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
897 CLEAR_REG_SET (&tmp_uses
);
898 CLEAR_REG_SET (&tmp_sets
);
900 /* All memory writes and volatile reads must happen before the
901 jump. Non-volatile reads must happen before the jump iff
902 the result is needed by the above register used mask. */
904 pending
= deps
->pending_write_insns
;
905 pending_mem
= deps
->pending_write_mems
;
908 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
909 pending
= XEXP (pending
, 1);
910 pending_mem
= XEXP (pending_mem
, 1);
913 pending
= deps
->pending_read_insns
;
914 pending_mem
= deps
->pending_read_mems
;
917 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0)))
918 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
919 pending
= XEXP (pending
, 1);
920 pending_mem
= XEXP (pending_mem
, 1);
923 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
928 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
929 block, then we must be sure that no instructions are scheduled across it.
930 Otherwise, the reg_n_refs info (which depends on loop_depth) would
936 /* Update loop_notes with any notes from this insn. Also determine
937 if any of the notes on the list correspond to instruction scheduling
938 barriers (loop, eh & setjmp notes, but not range notes). */
940 while (XEXP (link
, 1))
942 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
943 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
944 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
945 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
)
946 reg_pending_barrier
= MOVE_BARRIER
;
948 link
= XEXP (link
, 1);
950 XEXP (link
, 1) = REG_NOTES (insn
);
951 REG_NOTES (insn
) = loop_notes
;
954 /* If this instruction can throw an exception, then moving it changes
955 where block boundaries fall. This is mighty confusing elsewhere.
956 Therefore, prevent such an instruction from being moved. */
957 if (can_throw_internal (insn
))
958 reg_pending_barrier
= MOVE_BARRIER
;
960 /* Add dependencies if a scheduling barrier was found. */
961 if (reg_pending_barrier
)
963 /* In the case of barrier the most added dependencies are not
964 real, so we use anti-dependence here. */
965 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
967 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
969 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
970 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
972 (insn
, reg_last
->sets
,
973 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
975 (insn
, reg_last
->clobbers
,
976 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
981 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
983 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
984 add_dependence_list_and_free (insn
, ®_last
->uses
,
986 add_dependence_list_and_free
987 (insn
, ®_last
->sets
,
988 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
989 add_dependence_list_and_free
990 (insn
, ®_last
->clobbers
,
991 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
992 reg_last
->uses_length
= 0;
993 reg_last
->clobbers_length
= 0;
997 for (i
= 0; i
< deps
->max_reg
; i
++)
999 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1000 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1001 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1004 flush_pending_lists (deps
, insn
, true, true);
1005 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
1006 reg_pending_barrier
= NOT_A_BARRIER
;
1010 /* If the current insn is conditional, we can't free any
1012 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
1014 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1016 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1017 add_dependence_list (insn
, reg_last
->sets
, 0);
1018 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1019 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1020 reg_last
->uses_length
++;
1022 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1024 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1025 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1026 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1027 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1028 reg_last
->clobbers_length
++;
1030 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1032 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1033 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1034 add_dependence_list (insn
, reg_last
->clobbers
, REG_DEP_OUTPUT
);
1035 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1036 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1037 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
1042 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1044 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1045 add_dependence_list (insn
, reg_last
->sets
, 0);
1046 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1047 reg_last
->uses_length
++;
1048 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1050 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1052 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1053 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
1054 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
1056 add_dependence_list_and_free (insn
, ®_last
->sets
,
1058 add_dependence_list_and_free (insn
, ®_last
->uses
,
1060 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1062 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1063 reg_last
->clobbers_length
= 0;
1064 reg_last
->uses_length
= 0;
1068 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1069 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1071 reg_last
->clobbers_length
++;
1072 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1074 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1076 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1077 add_dependence_list_and_free (insn
, ®_last
->sets
,
1079 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1081 add_dependence_list_and_free (insn
, ®_last
->uses
,
1083 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1084 reg_last
->uses_length
= 0;
1085 reg_last
->clobbers_length
= 0;
1086 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
1090 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
1091 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
1092 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
1094 CLEAR_REG_SET (reg_pending_uses
);
1095 CLEAR_REG_SET (reg_pending_clobbers
);
1096 CLEAR_REG_SET (reg_pending_sets
);
1098 /* If we are currently in a libcall scheduling group, then mark the
1099 current insn as being in a scheduling group and that it can not
1100 be moved into a different basic block. */
1102 if (deps
->libcall_block_tail_insn
)
1104 set_sched_group_p (insn
);
1105 CANT_MOVE (insn
) = 1;
1108 /* If a post-call group is still open, see if it should remain so.
1109 This insn must be a simple move of a hard reg to a pseudo or
1112 We must avoid moving these insns for correctness on
1113 SMALL_REGISTER_CLASS machines, and for special registers like
1114 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1115 hard regs for all targets. */
1117 if (deps
->in_post_call_group_p
)
1119 rtx tmp
, set
= single_set (insn
);
1120 int src_regno
, dest_regno
;
1123 goto end_call_group
;
1125 tmp
= SET_DEST (set
);
1126 if (GET_CODE (tmp
) == SUBREG
)
1127 tmp
= SUBREG_REG (tmp
);
1129 dest_regno
= REGNO (tmp
);
1131 goto end_call_group
;
1133 tmp
= SET_SRC (set
);
1134 if (GET_CODE (tmp
) == SUBREG
)
1135 tmp
= SUBREG_REG (tmp
);
1136 if ((GET_CODE (tmp
) == PLUS
1137 || GET_CODE (tmp
) == MINUS
)
1138 && REG_P (XEXP (tmp
, 0))
1139 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
1140 && dest_regno
== STACK_POINTER_REGNUM
)
1141 src_regno
= STACK_POINTER_REGNUM
;
1142 else if (REG_P (tmp
))
1143 src_regno
= REGNO (tmp
);
1145 goto end_call_group
;
1147 if (src_regno
< FIRST_PSEUDO_REGISTER
1148 || dest_regno
< FIRST_PSEUDO_REGISTER
)
1150 /* If we are inside a post-call group right at the start of the
1151 scheduling region, we must not add a dependency. */
1152 if (deps
->in_post_call_group_p
== post_call_initial
)
1154 SCHED_GROUP_P (insn
) = 1;
1155 deps
->in_post_call_group_p
= post_call
;
1158 set_sched_group_p (insn
);
1159 CANT_MOVE (insn
) = 1;
1164 deps
->in_post_call_group_p
= not_post_call
;
1169 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1170 for every dependency. */
1173 sched_analyze (struct deps
*deps
, rtx head
, rtx tail
)
1178 if (current_sched_info
->use_cselib
)
1181 /* Before reload, if the previous block ended in a call, show that
1182 we are inside a post-call group, so as to keep the lifetimes of
1183 hard registers correct. */
1184 if (! reload_completed
&& !LABEL_P (head
))
1186 insn
= prev_nonnote_insn (head
);
1187 if (insn
&& CALL_P (insn
))
1188 deps
->in_post_call_group_p
= post_call_initial
;
1190 for (insn
= head
;; insn
= NEXT_INSN (insn
))
1192 rtx link
, end_seq
, r0
, set
;
1194 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
1196 /* Clear out the stale LOG_LINKS from flow. */
1197 free_INSN_LIST_list (&LOG_LINKS (insn
));
1199 /* Make each JUMP_INSN a scheduling barrier for memory
1203 /* Keep the list a reasonable size. */
1204 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
1205 flush_pending_lists (deps
, insn
, true, true);
1207 deps
->last_pending_memory_flush
1208 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
1210 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1213 else if (CALL_P (insn
))
1217 CANT_MOVE (insn
) = 1;
1219 /* Clear out the stale LOG_LINKS from flow. */
1220 free_INSN_LIST_list (&LOG_LINKS (insn
));
1222 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
1224 /* This is setjmp. Assume that all registers, not just
1225 hard registers, may be clobbered by this call. */
1226 reg_pending_barrier
= MOVE_BARRIER
;
1230 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1231 /* A call may read and modify global register variables. */
1234 SET_REGNO_REG_SET (reg_pending_sets
, i
);
1235 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1237 /* Other call-clobbered hard regs may be clobbered.
1238 Since we only have a choice between 'might be clobbered'
1239 and 'definitely not clobbered', we must include all
1240 partly call-clobbered registers here. */
1241 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
1242 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1243 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
1244 /* We don't know what set of fixed registers might be used
1245 by the function, but it is certain that the stack pointer
1246 is among them, but be conservative. */
1247 else if (fixed_regs
[i
])
1248 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1249 /* The frame pointer is normally not used by the function
1250 itself, but by the debugger. */
1251 /* ??? MIPS o32 is an exception. It uses the frame pointer
1252 in the macro expansion of jal but does not represent this
1253 fact in the call_insn rtl. */
1254 else if (i
== FRAME_POINTER_REGNUM
1255 || (i
== HARD_FRAME_POINTER_REGNUM
1256 && (! reload_completed
|| frame_pointer_needed
)))
1257 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1260 /* For each insn which shouldn't cross a call, add a dependence
1261 between that insn and this call insn. */
1262 add_dependence_list_and_free (insn
, &deps
->sched_before_next_call
,
1265 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1268 /* In the absence of interprocedural alias analysis, we must flush
1269 all pending reads and writes, and start new dependencies starting
1270 from here. But only flush writes for constant calls (which may
1271 be passed a pointer to something we haven't written yet). */
1272 flush_pending_lists (deps
, insn
, true, !CONST_OR_PURE_CALL_P (insn
));
1274 /* Remember the last function call for limiting lifetimes. */
1275 free_INSN_LIST_list (&deps
->last_function_call
);
1276 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
1278 /* Before reload, begin a post-call group, so as to keep the
1279 lifetimes of hard registers correct. */
1280 if (! reload_completed
)
1281 deps
->in_post_call_group_p
= post_call
;
1284 /* See comments on reemit_notes as to why we do this.
1285 ??? Actually, the reemit_notes just say what is done, not why. */
1288 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
1289 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
1290 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1291 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
))
1295 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1296 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
1297 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
1299 rtx_region
= const0_rtx
;
1301 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1304 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1305 GEN_INT (NOTE_LINE_NUMBER (insn
)),
1307 CONST_OR_PURE_CALL_P (loop_notes
) = CONST_OR_PURE_CALL_P (insn
);
1310 if (current_sched_info
->use_cselib
)
1311 cselib_process_insn (insn
);
1313 /* Now that we have completed handling INSN, check and see if it is
1314 a CLOBBER beginning a libcall block. If it is, record the
1315 end of the libcall sequence.
1317 We want to schedule libcall blocks as a unit before reload. While
1318 this restricts scheduling, it preserves the meaning of a libcall
1321 As a side effect, we may get better code due to decreased register
1322 pressure as well as less chance of a foreign insn appearing in
1324 if (!reload_completed
1325 /* Note we may have nested libcall sequences. We only care about
1326 the outermost libcall sequence. */
1327 && deps
->libcall_block_tail_insn
== 0
1328 /* The sequence must start with a clobber of a register. */
1329 && NONJUMP_INSN_P (insn
)
1330 && GET_CODE (PATTERN (insn
)) == CLOBBER
1331 && (r0
= XEXP (PATTERN (insn
), 0), REG_P (r0
))
1332 && REG_P (XEXP (PATTERN (insn
), 0))
1333 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1334 && (link
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)) != 0
1335 && (end_seq
= XEXP (link
, 0)) != 0
1336 /* The insn referenced by the REG_LIBCALL note must be a
1337 simple nop copy with the same destination as the register
1338 mentioned in the clobber. */
1339 && (set
= single_set (end_seq
)) != 0
1340 && SET_DEST (set
) == r0
&& SET_SRC (set
) == r0
1341 /* And finally the insn referenced by the REG_LIBCALL must
1342 also contain a REG_EQUAL note and a REG_RETVAL note. */
1343 && find_reg_note (end_seq
, REG_EQUAL
, NULL_RTX
) != 0
1344 && find_reg_note (end_seq
, REG_RETVAL
, NULL_RTX
) != 0)
1345 deps
->libcall_block_tail_insn
= XEXP (link
, 0);
1347 /* If we have reached the end of a libcall block, then close the
1349 if (deps
->libcall_block_tail_insn
== insn
)
1350 deps
->libcall_block_tail_insn
= 0;
1354 if (current_sched_info
->use_cselib
)
1363 /* The following function adds forward dependence (FROM, TO) with
1364 given DEP_TYPE. The forward dependence should be not exist before. */
1367 add_forward_dependence (rtx from
, rtx to
, enum reg_note dep_type
)
1371 #ifdef ENABLE_CHECKING
1372 /* If add_dependence is working properly there should never
1373 be notes, deleted insns or duplicates in the backward
1374 links. Thus we need not check for them here.
1376 However, if we have enabled checking we might as well go
1377 ahead and verify that add_dependence worked properly. */
1379 || INSN_DELETED_P (from
)
1380 || (forward_dependency_cache
!= NULL
1381 && bitmap_bit_p (&forward_dependency_cache
[INSN_LUID (from
)],
1383 || (forward_dependency_cache
== NULL
1384 && find_insn_list (to
, INSN_DEPEND (from
))))
1386 if (forward_dependency_cache
!= NULL
)
1387 bitmap_bit_p (&forward_dependency_cache
[INSN_LUID (from
)],
1391 new_link
= alloc_INSN_LIST (to
, INSN_DEPEND (from
));
1393 PUT_REG_NOTE_KIND (new_link
, dep_type
);
1395 INSN_DEPEND (from
) = new_link
;
1396 INSN_DEP_COUNT (to
) += 1;
1399 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1400 dependences from LOG_LINKS to build forward dependences in
1404 compute_forward_dependences (rtx head
, rtx tail
)
1409 next_tail
= NEXT_INSN (tail
);
1410 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1412 if (! INSN_P (insn
))
1415 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
1416 add_forward_dependence (XEXP (link
, 0), insn
, REG_NOTE_KIND (link
));
1420 /* Initialize variables for region data dependence analysis.
1421 n_bbs is the number of region blocks. */
1424 init_deps (struct deps
*deps
)
1426 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
1428 deps
->max_reg
= max_reg
;
1429 deps
->reg_last
= xcalloc (max_reg
, sizeof (struct deps_reg
));
1430 INIT_REG_SET (&deps
->reg_last_in_use
);
1431 INIT_REG_SET (&deps
->reg_conditional_sets
);
1433 deps
->pending_read_insns
= 0;
1434 deps
->pending_read_mems
= 0;
1435 deps
->pending_write_insns
= 0;
1436 deps
->pending_write_mems
= 0;
1437 deps
->pending_lists_length
= 0;
1438 deps
->pending_flush_length
= 0;
1439 deps
->last_pending_memory_flush
= 0;
1440 deps
->last_function_call
= 0;
1441 deps
->sched_before_next_call
= 0;
1442 deps
->in_post_call_group_p
= not_post_call
;
1443 deps
->libcall_block_tail_insn
= 0;
1446 /* Free insn lists found in DEPS. */
1449 free_deps (struct deps
*deps
)
1453 free_INSN_LIST_list (&deps
->pending_read_insns
);
1454 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1455 free_INSN_LIST_list (&deps
->pending_write_insns
);
1456 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1457 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1459 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1460 times. For a testcase with 42000 regs and 8000 small basic blocks,
1461 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1462 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1464 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1466 free_INSN_LIST_list (®_last
->uses
);
1468 free_INSN_LIST_list (®_last
->sets
);
1469 if (reg_last
->clobbers
)
1470 free_INSN_LIST_list (®_last
->clobbers
);
1472 CLEAR_REG_SET (&deps
->reg_last_in_use
);
1473 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
1475 free (deps
->reg_last
);
1478 /* If it is profitable to use them, initialize caches for tracking
1479 dependency information. LUID is the number of insns to be scheduled,
1480 it is used in the estimate of profitability. */
1483 init_dependency_caches (int luid
)
1485 /* ?!? We could save some memory by computing a per-region luid mapping
1486 which could reduce both the number of vectors in the cache and the size
1487 of each vector. Instead we just avoid the cache entirely unless the
1488 average number of instructions in a basic block is very high. See
1489 the comment before the declaration of true_dependency_cache for
1490 what we consider "very high". */
1491 if (luid
/ n_basic_blocks
> 100 * 5)
1494 true_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1495 anti_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1496 output_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1497 #ifdef ENABLE_CHECKING
1498 forward_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1500 for (i
= 0; i
< luid
; i
++)
1502 bitmap_initialize (&true_dependency_cache
[i
], 0);
1503 bitmap_initialize (&anti_dependency_cache
[i
], 0);
1504 bitmap_initialize (&output_dependency_cache
[i
], 0);
1505 #ifdef ENABLE_CHECKING
1506 bitmap_initialize (&forward_dependency_cache
[i
], 0);
1513 /* Free the caches allocated in init_dependency_caches. */
1516 free_dependency_caches (void)
1518 if (true_dependency_cache
)
1522 for (i
= 0; i
< cache_size
; i
++)
1524 bitmap_clear (&true_dependency_cache
[i
]);
1525 bitmap_clear (&anti_dependency_cache
[i
]);
1526 bitmap_clear (&output_dependency_cache
[i
]);
1527 #ifdef ENABLE_CHECKING
1528 bitmap_clear (&forward_dependency_cache
[i
]);
1531 free (true_dependency_cache
);
1532 true_dependency_cache
= NULL
;
1533 free (anti_dependency_cache
);
1534 anti_dependency_cache
= NULL
;
1535 free (output_dependency_cache
);
1536 output_dependency_cache
= NULL
;
1537 #ifdef ENABLE_CHECKING
1538 free (forward_dependency_cache
);
1539 forward_dependency_cache
= NULL
;
1544 /* Initialize some global variables needed by the dependency analysis
1548 init_deps_global (void)
1550 reg_pending_sets
= INITIALIZE_REG_SET (reg_pending_sets_head
);
1551 reg_pending_clobbers
= INITIALIZE_REG_SET (reg_pending_clobbers_head
);
1552 reg_pending_uses
= INITIALIZE_REG_SET (reg_pending_uses_head
);
1553 reg_pending_barrier
= NOT_A_BARRIER
;
1556 /* Free everything used by the dependency analysis code. */
1559 finish_deps_global (void)
1561 FREE_REG_SET (reg_pending_sets
);
1562 FREE_REG_SET (reg_pending_clobbers
);
1563 FREE_REG_SET (reg_pending_uses
);