1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002 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"
46 extern char *reg_known_equiv_p
;
47 extern rtx
*reg_known_value
;
49 static regset_head reg_pending_sets_head
;
50 static regset_head reg_pending_clobbers_head
;
51 static regset_head reg_pending_uses_head
;
53 static regset reg_pending_sets
;
54 static regset reg_pending_clobbers
;
55 static regset reg_pending_uses
;
56 static bool reg_pending_barrier
;
58 /* To speed up the test for duplicate dependency links we keep a
59 record of dependencies created by add_dependence when the average
60 number of instructions in a basic block is very large.
62 Studies have shown that there is typically around 5 instructions between
63 branches for typical C code. So we can make a guess that the average
64 basic block is approximately 5 instructions long; we will choose 100X
65 the average size as a very large basic block.
67 Each insn has associated bitmaps for its dependencies. Each bitmap
68 has enough entries to represent a dependency on any other insn in
69 the insn chain. All bitmap for true dependencies cache is
70 allocated then the rest two ones are also allocated. */
71 static sbitmap
*true_dependency_cache
;
72 static sbitmap
*anti_dependency_cache
;
73 static sbitmap
*output_dependency_cache
;
75 /* To speed up checking consistency of formed forward insn
76 dependencies we use the following cache. Another possible solution
77 could be switching off checking duplication of insns in forward
79 #ifdef ENABLE_CHECKING
80 static sbitmap
*forward_dependency_cache
;
83 static int deps_may_trap_p
PARAMS ((rtx
));
84 static void add_dependence_list
PARAMS ((rtx
, rtx
, enum reg_note
));
85 static void add_dependence_list_and_free
PARAMS ((rtx
, rtx
*, enum reg_note
));
86 static void remove_dependence
PARAMS ((rtx
, rtx
));
87 static void set_sched_group_p
PARAMS ((rtx
));
89 static void flush_pending_lists
PARAMS ((struct deps
*, rtx
, int, int));
90 static void sched_analyze_1
PARAMS ((struct deps
*, rtx
, rtx
));
91 static void sched_analyze_2
PARAMS ((struct deps
*, rtx
, rtx
));
92 static void sched_analyze_insn
PARAMS ((struct deps
*, rtx
, rtx
, rtx
));
93 static rtx group_leader
PARAMS ((rtx
));
95 static rtx get_condition
PARAMS ((rtx
));
96 static int conditions_mutex_p
PARAMS ((rtx
, rtx
));
98 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
101 deps_may_trap_p (mem
)
104 rtx addr
= XEXP (mem
, 0);
107 && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
108 && reg_known_value
[REGNO (addr
)])
109 addr
= reg_known_value
[REGNO (addr
)];
110 return rtx_addr_can_trap_p (addr
);
113 /* Return the INSN_LIST containing INSN in LIST, or NULL
114 if LIST does not contain INSN. */
117 find_insn_list (insn
, list
)
123 if (XEXP (list
, 0) == insn
)
125 list
= XEXP (list
, 1);
130 /* Find the condition under which INSN is executed. */
136 rtx pat
= PATTERN (insn
);
141 if (GET_CODE (pat
) == COND_EXEC
)
142 return COND_EXEC_TEST (pat
);
143 if (GET_CODE (insn
) != JUMP_INSN
)
145 if (GET_CODE (pat
) != SET
|| SET_SRC (pat
) != pc_rtx
)
147 if (GET_CODE (SET_DEST (pat
)) != IF_THEN_ELSE
)
149 pat
= SET_DEST (pat
);
150 cond
= XEXP (pat
, 0);
151 if (GET_CODE (XEXP (cond
, 1)) == LABEL_REF
152 && XEXP (cond
, 2) == pc_rtx
)
154 else if (GET_CODE (XEXP (cond
, 2)) == LABEL_REF
155 && XEXP (cond
, 1) == pc_rtx
)
156 return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)), GET_MODE (cond
),
157 XEXP (cond
, 0), XEXP (cond
, 1));
162 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
165 conditions_mutex_p (cond1
, cond2
)
168 if (GET_RTX_CLASS (GET_CODE (cond1
)) == '<'
169 && GET_RTX_CLASS (GET_CODE (cond2
)) == '<'
170 && GET_CODE (cond1
) == reverse_condition (GET_CODE (cond2
))
171 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
172 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
177 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
178 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
179 of dependence that this link represents. */
182 add_dependence (insn
, elem
, dep_type
)
185 enum reg_note dep_type
;
191 /* Don't depend an insn on itself. */
195 /* We can get a dependency on deleted insns due to optimizations in
196 the register allocation and reloading or due to splitting. Any
197 such dependency is useless and can be ignored. */
198 if (GET_CODE (elem
) == NOTE
)
201 /* flow.c doesn't handle conditional lifetimes entirely correctly;
202 calls mess up the conditional lifetimes. */
203 /* ??? add_dependence is the wrong place to be eliding dependencies,
204 as that forgets that the condition expressions themselves may
206 if (GET_CODE (insn
) != CALL_INSN
&& GET_CODE (elem
) != CALL_INSN
)
208 cond1
= get_condition (insn
);
209 cond2
= get_condition (elem
);
211 && conditions_mutex_p (cond1
, cond2
)
212 /* Make sure first instruction doesn't affect condition of second
213 instruction if switched. */
214 && !modified_in_p (cond1
, elem
)
215 /* Make sure second instruction doesn't affect condition of first
216 instruction if switched. */
217 && !modified_in_p (cond2
, insn
))
221 /* If elem is part of a sequence that must be scheduled together, then
222 make the dependence point to the last insn of the sequence.
223 When HAVE_cc0, it is possible for NOTEs to exist between users and
224 setters of the condition codes, so we must skip past notes here.
225 Otherwise, NOTEs are impossible here. */
226 next
= next_nonnote_insn (elem
);
227 if (next
&& INSN_P (next
) && SCHED_GROUP_P (next
))
229 /* Notes will never intervene here though, so don't bother checking
232 /* We must reject CODE_LABELs, so that we don't get confused by one
233 that has LABEL_PRESERVE_P set, which is represented by the same
234 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
238 while ((nnext
= next_nonnote_insn (next
)) != NULL
240 && SCHED_GROUP_P (nnext
))
243 /* Again, don't depend an insn on itself. */
247 /* Make the dependence to NEXT, the last insn of the group, instead
248 of the original ELEM. */
253 #ifdef INSN_SCHEDULING
254 /* ??? No good way to tell from here whether we're doing interblock
255 scheduling. Possibly add another callback. */
257 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
258 No need for interblock dependences with calls, since
259 calls are not moved between blocks. Note: the edge where
260 elem is a CALL is still required. */
261 if (GET_CODE (insn
) == CALL_INSN
262 && (INSN_BB (elem
) != INSN_BB (insn
)))
266 /* If we already have a dependency for ELEM, then we do not need to
267 do anything. Avoiding the list walk below can cut compile times
268 dramatically for some code. */
269 if (true_dependency_cache
!= NULL
)
271 enum reg_note present_dep_type
= 0;
273 if (anti_dependency_cache
== NULL
|| output_dependency_cache
== NULL
)
275 if (TEST_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
)))
276 /* Do nothing (present_set_type is already 0). */
278 else if (TEST_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
280 present_dep_type
= REG_DEP_ANTI
;
281 else if (TEST_BIT (output_dependency_cache
[INSN_LUID (insn
)],
283 present_dep_type
= REG_DEP_OUTPUT
;
286 if (present_p
&& (int) dep_type
>= (int) present_dep_type
)
291 /* Check that we don't already have this dependence. */
293 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
294 if (XEXP (link
, 0) == elem
)
296 #ifdef INSN_SCHEDULING
297 /* Clear corresponding cache entry because type of the link
299 if (true_dependency_cache
!= NULL
)
301 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
302 RESET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
304 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
305 && output_dependency_cache
)
306 RESET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
313 /* If this is a more restrictive type of dependence than the existing
314 one, then change the existing dependence to this type. */
315 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
316 PUT_REG_NOTE_KIND (link
, dep_type
);
318 #ifdef INSN_SCHEDULING
319 /* If we are adding a dependency to INSN's LOG_LINKs, then
320 note that in the bitmap caches of dependency information. */
321 if (true_dependency_cache
!= NULL
)
323 if ((int) REG_NOTE_KIND (link
) == 0)
324 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
326 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
327 SET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
329 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
330 SET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
336 /* Might want to check one level of transitivity to save conses. */
338 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
339 LOG_LINKS (insn
) = link
;
341 /* Insn dependency, not data dependency. */
342 PUT_REG_NOTE_KIND (link
, dep_type
);
344 #ifdef INSN_SCHEDULING
345 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
346 in the bitmap caches of dependency information. */
347 if (true_dependency_cache
!= NULL
)
349 if ((int) dep_type
== 0)
350 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
351 else if (dep_type
== REG_DEP_ANTI
)
352 SET_BIT (anti_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
353 else if (dep_type
== REG_DEP_OUTPUT
)
354 SET_BIT (output_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
359 /* A convenience wrapper to operate on an entire list. */
362 add_dependence_list (insn
, list
, dep_type
)
364 enum reg_note dep_type
;
366 for (; list
; list
= XEXP (list
, 1))
367 add_dependence (insn
, XEXP (list
, 0), dep_type
);
370 /* Similar, but free *LISTP at the same time. */
373 add_dependence_list_and_free (insn
, listp
, dep_type
)
376 enum reg_note dep_type
;
379 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
381 next
= XEXP (list
, 1);
382 add_dependence (insn
, XEXP (list
, 0), dep_type
);
383 free_INSN_LIST_node (list
);
387 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
388 of INSN. Abort if not found. */
391 remove_dependence (insn
, elem
)
395 rtx prev
, link
, next
;
398 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
400 next
= XEXP (link
, 1);
401 if (XEXP (link
, 0) == elem
)
404 XEXP (prev
, 1) = next
;
406 LOG_LINKS (insn
) = next
;
408 #ifdef INSN_SCHEDULING
409 /* If we are removing a dependency from the LOG_LINKS list,
410 make sure to remove it from the cache too. */
411 if (true_dependency_cache
!= NULL
)
413 if (REG_NOTE_KIND (link
) == 0)
414 RESET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
416 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
417 RESET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
419 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
420 RESET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
425 free_INSN_LIST_node (link
);
438 /* Return an insn which represents a SCHED_GROUP, which is
439 the last insn in the group. */
450 insn
= next_nonnote_insn (insn
);
452 while (insn
&& INSN_P (insn
) && SCHED_GROUP_P (insn
));
457 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
458 goes along with that. */
461 set_sched_group_p (insn
)
466 SCHED_GROUP_P (insn
) = 1;
468 /* There may be a note before this insn now, but all notes will
469 be removed before we actually try to schedule the insns, so
470 it won't cause a problem later. We must avoid it here though. */
471 prev
= prev_nonnote_insn (insn
);
473 /* Make a copy of all dependencies on the immediately previous insn,
474 and add to this insn. This is so that all the dependencies will
475 apply to the group. Remove an explicit dependence on this insn
476 as SCHED_GROUP_P now represents it. */
478 if (find_insn_list (prev
, LOG_LINKS (insn
)))
479 remove_dependence (insn
, prev
);
481 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
482 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
485 /* Process an insn's memory dependencies. There are four kinds of
488 (0) read dependence: read follows read
489 (1) true dependence: read follows write
490 (2) anti dependence: write follows read
491 (3) output dependence: write follows write
493 We are careful to build only dependencies which actually exist, and
494 use transitivity to avoid building too many links. */
496 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
497 The MEM is a memory reference contained within INSN, which we are saving
498 so that we can do memory aliasing on it. */
501 add_insn_mem_dependence (deps
, insn_list
, mem_list
, insn
, mem
)
503 rtx
*insn_list
, *mem_list
, insn
, mem
;
507 link
= alloc_INSN_LIST (insn
, *insn_list
);
510 if (current_sched_info
->use_cselib
)
512 mem
= shallow_copy_rtx (mem
);
513 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
515 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
518 deps
->pending_lists_length
++;
521 /* Make a dependency between every memory reference on the pending lists
522 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
523 dependencies for a read operation, similarly with FOR_WRITE. */
526 flush_pending_lists (deps
, insn
, for_read
, for_write
)
529 int for_read
, for_write
;
533 add_dependence_list_and_free (insn
, &deps
->pending_read_insns
,
535 free_EXPR_LIST_list (&deps
->pending_read_mems
);
538 add_dependence_list_and_free (insn
, &deps
->pending_write_insns
,
539 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
540 free_EXPR_LIST_list (&deps
->pending_write_mems
);
541 deps
->pending_lists_length
= 0;
543 add_dependence_list_and_free (insn
, &deps
->last_pending_memory_flush
,
544 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
545 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
546 deps
->pending_flush_length
= 1;
549 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
550 rtx, X, creating all dependencies generated by the write to the
551 destination of X, and reads of everything mentioned. */
554 sched_analyze_1 (deps
, x
, insn
)
560 rtx dest
= XEXP (x
, 0);
561 enum rtx_code code
= GET_CODE (x
);
566 if (GET_CODE (dest
) == PARALLEL
)
570 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
571 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
572 sched_analyze_1 (deps
,
573 gen_rtx_CLOBBER (VOIDmode
,
574 XEXP (XVECEXP (dest
, 0, i
), 0)),
577 if (GET_CODE (x
) == SET
)
578 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
582 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
583 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
585 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
587 /* The second and third arguments are values read by this insn. */
588 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
589 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
591 dest
= XEXP (dest
, 0);
594 if (GET_CODE (dest
) == REG
)
596 regno
= REGNO (dest
);
598 /* A hard reg in a wide mode may really be multiple registers.
599 If so, mark all of them just like the first. */
600 if (regno
< FIRST_PSEUDO_REGISTER
)
602 int i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
606 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
611 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
614 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
615 it does not reload. Ignore these as they have served their
617 else if (regno
>= deps
->max_reg
)
619 if (GET_CODE (PATTERN (insn
)) != USE
620 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
626 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
628 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
630 /* Pseudos that are REG_EQUIV to something may be replaced
631 by that during reloading. We need only add dependencies for
632 the address in the REG_EQUIV note. */
633 if (!reload_completed
634 && reg_known_equiv_p
[regno
]
635 && GET_CODE (reg_known_value
[regno
]) == MEM
)
636 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
638 /* Don't let it cross a call after scheduling if it doesn't
639 already cross one. */
640 if (REG_N_CALLS_CROSSED (regno
) == 0)
641 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_ANTI
);
644 else if (GET_CODE (dest
) == MEM
)
646 /* Writing memory. */
649 if (current_sched_info
->use_cselib
)
651 t
= shallow_copy_rtx (dest
);
652 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
653 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
656 if (deps
->pending_lists_length
> MAX_PENDING_LIST_LENGTH
)
658 /* Flush all pending reads and writes to prevent the pending lists
659 from getting any larger. Insn scheduling runs too slowly when
660 these lists get long. When compiling GCC with itself,
661 this flush occurs 8 times for sparc, and 10 times for m88k using
662 the default value of 32. */
663 flush_pending_lists (deps
, insn
, false, true);
667 rtx pending
, pending_mem
;
669 pending
= deps
->pending_read_insns
;
670 pending_mem
= deps
->pending_read_mems
;
673 if (anti_dependence (XEXP (pending_mem
, 0), t
))
674 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
676 pending
= XEXP (pending
, 1);
677 pending_mem
= XEXP (pending_mem
, 1);
680 pending
= deps
->pending_write_insns
;
681 pending_mem
= deps
->pending_write_mems
;
684 if (output_dependence (XEXP (pending_mem
, 0), t
))
685 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
687 pending
= XEXP (pending
, 1);
688 pending_mem
= XEXP (pending_mem
, 1);
691 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
694 add_insn_mem_dependence (deps
, &deps
->pending_write_insns
,
695 &deps
->pending_write_mems
, insn
, dest
);
697 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
701 if (GET_CODE (x
) == SET
)
702 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
705 /* Analyze the uses of memory and registers in rtx X in INSN. */
708 sched_analyze_2 (deps
, x
, insn
)
731 /* Ignore constants. Note that we must handle CONST_DOUBLE here
732 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
733 this does not mean that this insn is using cc0. */
738 /* User of CC0 depends on immediately preceding insn. */
739 set_sched_group_p (insn
);
745 int regno
= REGNO (x
);
746 if (regno
< FIRST_PSEUDO_REGISTER
)
748 int i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
750 SET_REGNO_REG_SET (reg_pending_uses
, regno
+ i
);
752 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
753 it does not reload. Ignore these as they have served their
755 else if (regno
>= deps
->max_reg
)
757 if (GET_CODE (PATTERN (insn
)) != USE
758 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
763 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
765 /* Pseudos that are REG_EQUIV to something may be replaced
766 by that during reloading. We need only add dependencies for
767 the address in the REG_EQUIV note. */
768 if (!reload_completed
769 && reg_known_equiv_p
[regno
]
770 && GET_CODE (reg_known_value
[regno
]) == MEM
)
771 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
773 /* If the register does not already cross any calls, then add this
774 insn to the sched_before_next_call list so that it will still
775 not cross calls after scheduling. */
776 if (REG_N_CALLS_CROSSED (regno
) == 0)
777 deps
->sched_before_next_call
778 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
785 /* Reading memory. */
787 rtx pending
, pending_mem
;
790 if (current_sched_info
->use_cselib
)
792 t
= shallow_copy_rtx (t
);
793 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
794 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
796 pending
= deps
->pending_read_insns
;
797 pending_mem
= deps
->pending_read_mems
;
800 if (read_dependence (XEXP (pending_mem
, 0), t
))
801 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
803 pending
= XEXP (pending
, 1);
804 pending_mem
= XEXP (pending_mem
, 1);
807 pending
= deps
->pending_write_insns
;
808 pending_mem
= deps
->pending_write_mems
;
811 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
813 add_dependence (insn
, XEXP (pending
, 0), 0);
815 pending
= XEXP (pending
, 1);
816 pending_mem
= XEXP (pending_mem
, 1);
819 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
820 if (GET_CODE (XEXP (u
, 0)) != JUMP_INSN
821 || deps_may_trap_p (x
))
822 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
824 /* Always add these dependencies to pending_reads, since
825 this insn may be followed by a write. */
826 add_insn_mem_dependence (deps
, &deps
->pending_read_insns
,
827 &deps
->pending_read_mems
, insn
, x
);
829 /* Take advantage of tail recursion here. */
830 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
834 /* Force pending stores to memory in case a trap handler needs them. */
836 flush_pending_lists (deps
, insn
, true, false);
841 case UNSPEC_VOLATILE
:
843 /* Traditional and volatile asm instructions must be considered to use
844 and clobber all hard registers, all pseudo-registers and all of
845 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
847 Consider for instance a volatile asm that changes the fpu rounding
848 mode. An insn should not be moved across this even if it only uses
849 pseudo-regs because it might give an incorrectly rounded result. */
850 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
851 reg_pending_barrier
= true;
853 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
854 We can not just fall through here since then we would be confused
855 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
856 traditional asms unlike their normal usage. */
858 if (code
== ASM_OPERANDS
)
860 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
861 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
871 /* These both read and modify the result. We must handle them as writes
872 to get proper dependencies for following instructions. We must handle
873 them as reads to get proper dependencies from this to previous
874 instructions. Thus we need to pass them to both sched_analyze_1
875 and sched_analyze_2. We must call sched_analyze_2 first in order
876 to get the proper antecedent for the read. */
877 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
878 sched_analyze_1 (deps
, x
, insn
);
883 /* op0 = op0 + op1 */
884 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
885 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
886 sched_analyze_1 (deps
, x
, insn
);
893 /* Other cases: walk the insn. */
894 fmt
= GET_RTX_FORMAT (code
);
895 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
898 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
899 else if (fmt
[i
] == 'E')
900 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
901 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
905 /* Analyze an INSN with pattern X to find all dependencies. */
908 sched_analyze_insn (deps
, x
, insn
, loop_notes
)
913 RTX_CODE code
= GET_CODE (x
);
917 if (code
== COND_EXEC
)
919 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
921 /* ??? Should be recording conditions so we reduce the number of
922 false dependencies. */
923 x
= COND_EXEC_CODE (x
);
926 if (code
== SET
|| code
== CLOBBER
)
928 sched_analyze_1 (deps
, x
, insn
);
930 /* Bare clobber insns are used for letting life analysis, reg-stack
931 and others know that a value is dead. Depend on the last call
932 instruction so that reg-stack won't get confused. */
934 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_OUTPUT
);
936 else if (code
== PARALLEL
)
939 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
941 rtx sub
= XVECEXP (x
, 0, i
);
942 code
= GET_CODE (sub
);
944 if (code
== COND_EXEC
)
946 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
947 sub
= COND_EXEC_CODE (sub
);
948 code
= GET_CODE (sub
);
950 if (code
== SET
|| code
== CLOBBER
)
951 sched_analyze_1 (deps
, sub
, insn
);
953 sched_analyze_2 (deps
, sub
, insn
);
957 sched_analyze_2 (deps
, x
, insn
);
959 /* Mark registers CLOBBERED or used by called function. */
960 if (GET_CODE (insn
) == CALL_INSN
)
962 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
964 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
965 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
967 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
969 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
970 reg_pending_barrier
= true;
973 if (GET_CODE (insn
) == JUMP_INSN
)
976 next
= next_nonnote_insn (insn
);
977 if (next
&& GET_CODE (next
) == BARRIER
)
978 reg_pending_barrier
= true;
981 rtx pending
, pending_mem
;
985 (*current_sched_info
->compute_jump_reg_dependencies
) (insn
, &tmp
);
986 IOR_REG_SET (reg_pending_uses
, &tmp
);
987 CLEAR_REG_SET (&tmp
);
989 /* All memory writes and volatile reads must happen before the
990 jump. Non-volatile reads must happen before the jump iff
991 the result is needed by the above register used mask. */
993 pending
= deps
->pending_write_insns
;
994 pending_mem
= deps
->pending_write_mems
;
997 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
998 pending
= XEXP (pending
, 1);
999 pending_mem
= XEXP (pending_mem
, 1);
1002 pending
= deps
->pending_read_insns
;
1003 pending_mem
= deps
->pending_read_mems
;
1006 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0)))
1007 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
1008 pending
= XEXP (pending
, 1);
1009 pending_mem
= XEXP (pending_mem
, 1);
1012 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
1017 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1018 block, then we must be sure that no instructions are scheduled across it.
1019 Otherwise, the reg_n_refs info (which depends on loop_depth) would
1020 become incorrect. */
1025 /* Update loop_notes with any notes from this insn. Also determine
1026 if any of the notes on the list correspond to instruction scheduling
1027 barriers (loop, eh & setjmp notes, but not range notes). */
1029 while (XEXP (link
, 1))
1031 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
1032 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
1033 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
1034 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
)
1035 reg_pending_barrier
= true;
1037 link
= XEXP (link
, 1);
1039 XEXP (link
, 1) = REG_NOTES (insn
);
1040 REG_NOTES (insn
) = loop_notes
;
1043 /* If this instruction can throw an exception, then moving it changes
1044 where block boundaries fall. This is mighty confusing elsewhere.
1045 Therefore, prevent such an instruction from being moved. */
1046 if (can_throw_internal (insn
))
1047 reg_pending_barrier
= true;
1049 /* Add dependencies if a scheduling barrier was found. */
1050 if (reg_pending_barrier
)
1052 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
1054 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1056 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1057 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1058 add_dependence_list (insn
, reg_last
->sets
, 0);
1059 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1064 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1066 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1067 add_dependence_list_and_free (insn
, ®_last
->uses
,
1069 add_dependence_list_and_free (insn
, ®_last
->sets
, 0);
1070 add_dependence_list_and_free (insn
, ®_last
->clobbers
, 0);
1071 reg_last
->uses_length
= 0;
1072 reg_last
->clobbers_length
= 0;
1076 for (i
= 0; i
< deps
->max_reg
; i
++)
1078 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1079 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1080 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1083 flush_pending_lists (deps
, insn
, true, true);
1084 reg_pending_barrier
= false;
1088 /* If the current insn is conditional, we can't free any
1090 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
1092 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1094 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1095 add_dependence_list (insn
, reg_last
->sets
, 0);
1096 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1097 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1098 reg_last
->uses_length
++;
1100 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1102 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1103 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1104 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1105 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1106 reg_last
->clobbers_length
++;
1108 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1110 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1111 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1112 add_dependence_list (insn
, reg_last
->clobbers
, REG_DEP_OUTPUT
);
1113 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1114 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1119 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1121 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1122 add_dependence_list (insn
, reg_last
->sets
, 0);
1123 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1124 reg_last
->uses_length
++;
1125 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1127 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1129 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1130 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
1131 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
1133 add_dependence_list_and_free (insn
, ®_last
->sets
,
1135 add_dependence_list_and_free (insn
, ®_last
->uses
,
1137 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1139 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1140 reg_last
->clobbers_length
= 0;
1141 reg_last
->uses_length
= 0;
1145 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1146 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1148 reg_last
->clobbers_length
++;
1149 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1151 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1153 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1154 add_dependence_list_and_free (insn
, ®_last
->sets
,
1156 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1158 add_dependence_list_and_free (insn
, ®_last
->uses
,
1160 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1161 reg_last
->uses_length
= 0;
1162 reg_last
->clobbers_length
= 0;
1166 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
1167 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
1168 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
1170 CLEAR_REG_SET (reg_pending_uses
);
1171 CLEAR_REG_SET (reg_pending_clobbers
);
1172 CLEAR_REG_SET (reg_pending_sets
);
1174 /* If we are currently in a libcall scheduling group, then mark the
1175 current insn as being in a scheduling group and that it can not
1176 be moved into a different basic block. */
1178 if (deps
->libcall_block_tail_insn
)
1180 set_sched_group_p (insn
);
1181 CANT_MOVE (insn
) = 1;
1184 /* If a post-call group is still open, see if it should remain so.
1185 This insn must be a simple move of a hard reg to a pseudo or
1188 We must avoid moving these insns for correctness on
1189 SMALL_REGISTER_CLASS machines, and for special registers like
1190 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1191 hard regs for all targets. */
1193 if (deps
->in_post_call_group_p
)
1195 rtx tmp
, set
= single_set (insn
);
1196 int src_regno
, dest_regno
;
1199 goto end_call_group
;
1201 tmp
= SET_DEST (set
);
1202 if (GET_CODE (tmp
) == SUBREG
)
1203 tmp
= SUBREG_REG (tmp
);
1204 if (GET_CODE (tmp
) == REG
)
1205 dest_regno
= REGNO (tmp
);
1207 goto end_call_group
;
1209 tmp
= SET_SRC (set
);
1210 if (GET_CODE (tmp
) == SUBREG
)
1211 tmp
= SUBREG_REG (tmp
);
1212 if (GET_CODE (tmp
) == REG
)
1213 src_regno
= REGNO (tmp
);
1215 goto end_call_group
;
1217 if (src_regno
< FIRST_PSEUDO_REGISTER
1218 || dest_regno
< FIRST_PSEUDO_REGISTER
)
1220 set_sched_group_p (insn
);
1221 CANT_MOVE (insn
) = 1;
1226 deps
->in_post_call_group_p
= false;
1231 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1232 for every dependency. */
1235 sched_analyze (deps
, head
, tail
)
1242 if (current_sched_info
->use_cselib
)
1245 for (insn
= head
;; insn
= NEXT_INSN (insn
))
1247 rtx link
, end_seq
, r0
, set
;
1249 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
1251 /* Clear out the stale LOG_LINKS from flow. */
1252 free_INSN_LIST_list (&LOG_LINKS (insn
));
1254 /* Make each JUMP_INSN a scheduling barrier for memory
1256 if (GET_CODE (insn
) == JUMP_INSN
)
1258 /* Keep the list a reasonable size. */
1259 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
1260 flush_pending_lists (deps
, insn
, true, true);
1262 deps
->last_pending_memory_flush
1263 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
1265 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1268 else if (GET_CODE (insn
) == CALL_INSN
)
1272 CANT_MOVE (insn
) = 1;
1274 /* Clear out the stale LOG_LINKS from flow. */
1275 free_INSN_LIST_list (&LOG_LINKS (insn
));
1277 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
1279 /* This is setjmp. Assume that all registers, not just
1280 hard registers, may be clobbered by this call. */
1281 reg_pending_barrier
= true;
1285 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1286 /* A call may read and modify global register variables. */
1289 SET_REGNO_REG_SET (reg_pending_sets
, i
);
1290 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1292 /* Other call-clobbered hard regs may be clobbered.
1293 Since we only have a choice between 'might be clobbered'
1294 and 'definitely not clobbered', we must include all
1295 partly call-clobbered registers here. */
1296 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
1297 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1298 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
1299 /* We don't know what set of fixed registers might be used
1300 by the function, but it is certain that the stack pointer
1301 is among them, but be conservative. */
1302 else if (fixed_regs
[i
])
1303 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1304 /* The frame pointer is normally not used by the function
1305 itself, but by the debugger. */
1306 /* ??? MIPS o32 is an exception. It uses the frame pointer
1307 in the macro expansion of jal but does not represent this
1308 fact in the call_insn rtl. */
1309 else if (i
== FRAME_POINTER_REGNUM
1310 || (i
== HARD_FRAME_POINTER_REGNUM
1311 && (! reload_completed
|| frame_pointer_needed
)))
1312 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1315 /* For each insn which shouldn't cross a call, add a dependence
1316 between that insn and this call insn. */
1317 add_dependence_list_and_free (insn
, &deps
->sched_before_next_call
,
1320 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1323 /* In the absence of interprocedural alias analysis, we must flush
1324 all pending reads and writes, and start new dependencies starting
1325 from here. But only flush writes for constant calls (which may
1326 be passed a pointer to something we haven't written yet). */
1327 flush_pending_lists (deps
, insn
, true, !CONST_OR_PURE_CALL_P (insn
));
1329 /* Remember the last function call for limiting lifetimes. */
1330 free_INSN_LIST_list (&deps
->last_function_call
);
1331 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
1333 /* Before reload, begin a post-call group, so as to keep the
1334 lifetimes of hard registers correct. */
1335 if (! reload_completed
)
1336 deps
->in_post_call_group_p
= true;
1339 /* See comments on reemit_notes as to why we do this.
1340 ??? Actually, the reemit_notes just say what is done, not why. */
1342 if (GET_CODE (insn
) == NOTE
1343 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
1344 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
1345 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1346 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
))
1350 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1351 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
1352 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
1354 rtx_region
= GEN_INT (0);
1356 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1359 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1360 GEN_INT (NOTE_LINE_NUMBER (insn
)),
1362 CONST_OR_PURE_CALL_P (loop_notes
) = CONST_OR_PURE_CALL_P (insn
);
1365 if (current_sched_info
->use_cselib
)
1366 cselib_process_insn (insn
);
1368 /* Now that we have completed handling INSN, check and see if it is
1369 a CLOBBER beginning a libcall block. If it is, record the
1370 end of the libcall sequence.
1372 We want to schedule libcall blocks as a unit before reload. While
1373 this restricts scheduling, it preserves the meaning of a libcall
1376 As a side effect, we may get better code due to decreased register
1377 pressure as well as less chance of a foreign insn appearing in
1379 if (!reload_completed
1380 /* Note we may have nested libcall sequences. We only care about
1381 the outermost libcall sequence. */
1382 && deps
->libcall_block_tail_insn
== 0
1383 /* The sequence must start with a clobber of a register. */
1384 && GET_CODE (insn
) == INSN
1385 && GET_CODE (PATTERN (insn
)) == CLOBBER
1386 && (r0
= XEXP (PATTERN (insn
), 0), GET_CODE (r0
) == REG
)
1387 && GET_CODE (XEXP (PATTERN (insn
), 0)) == REG
1388 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1389 && (link
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)) != 0
1390 && (end_seq
= XEXP (link
, 0)) != 0
1391 /* The insn referenced by the REG_LIBCALL note must be a
1392 simple nop copy with the same destination as the register
1393 mentioned in the clobber. */
1394 && (set
= single_set (end_seq
)) != 0
1395 && SET_DEST (set
) == r0
&& SET_SRC (set
) == r0
1396 /* And finally the insn referenced by the REG_LIBCALL must
1397 also contain a REG_EQUAL note and a REG_RETVAL note. */
1398 && find_reg_note (end_seq
, REG_EQUAL
, NULL_RTX
) != 0
1399 && find_reg_note (end_seq
, REG_RETVAL
, NULL_RTX
) != 0)
1400 deps
->libcall_block_tail_insn
= XEXP (link
, 0);
1402 /* If we have reached the end of a libcall block, then close the
1404 if (deps
->libcall_block_tail_insn
== insn
)
1405 deps
->libcall_block_tail_insn
= 0;
1409 if (current_sched_info
->use_cselib
)
1417 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1418 dependences from LOG_LINKS to build forward dependences in
1422 compute_forward_dependences (head
, tail
)
1427 enum reg_note dep_type
;
1429 next_tail
= NEXT_INSN (tail
);
1430 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1432 if (! INSN_P (insn
))
1435 insn
= group_leader (insn
);
1437 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
1439 rtx x
= group_leader (XEXP (link
, 0));
1442 if (x
!= XEXP (link
, 0))
1445 #ifdef ENABLE_CHECKING
1446 /* If add_dependence is working properly there should never
1447 be notes, deleted insns or duplicates in the backward
1448 links. Thus we need not check for them here.
1450 However, if we have enabled checking we might as well go
1451 ahead and verify that add_dependence worked properly. */
1452 if (GET_CODE (x
) == NOTE
1453 || INSN_DELETED_P (x
)
1454 || (forward_dependency_cache
!= NULL
1455 && TEST_BIT (forward_dependency_cache
[INSN_LUID (x
)],
1457 || (forward_dependency_cache
== NULL
1458 && find_insn_list (insn
, INSN_DEPEND (x
))))
1460 if (forward_dependency_cache
!= NULL
)
1461 SET_BIT (forward_dependency_cache
[INSN_LUID (x
)],
1465 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
1467 dep_type
= REG_NOTE_KIND (link
);
1468 PUT_REG_NOTE_KIND (new_link
, dep_type
);
1470 INSN_DEPEND (x
) = new_link
;
1471 INSN_DEP_COUNT (insn
) += 1;
1476 /* Initialize variables for region data dependence analysis.
1477 n_bbs is the number of region blocks. */
1483 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
1485 deps
->max_reg
= max_reg
;
1486 deps
->reg_last
= (struct deps_reg
*)
1487 xcalloc (max_reg
, sizeof (struct deps_reg
));
1488 INIT_REG_SET (&deps
->reg_last_in_use
);
1490 deps
->pending_read_insns
= 0;
1491 deps
->pending_read_mems
= 0;
1492 deps
->pending_write_insns
= 0;
1493 deps
->pending_write_mems
= 0;
1494 deps
->pending_lists_length
= 0;
1495 deps
->pending_flush_length
= 0;
1496 deps
->last_pending_memory_flush
= 0;
1497 deps
->last_function_call
= 0;
1498 deps
->sched_before_next_call
= 0;
1499 deps
->in_post_call_group_p
= false;
1500 deps
->libcall_block_tail_insn
= 0;
1503 /* Free insn lists found in DEPS. */
1511 free_INSN_LIST_list (&deps
->pending_read_insns
);
1512 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1513 free_INSN_LIST_list (&deps
->pending_write_insns
);
1514 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1515 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1517 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1518 times. For a test case with 42000 regs and 8000 small basic blocks,
1519 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1520 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1522 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1524 free_INSN_LIST_list (®_last
->uses
);
1526 free_INSN_LIST_list (®_last
->sets
);
1527 if (reg_last
->clobbers
)
1528 free_INSN_LIST_list (®_last
->clobbers
);
1530 CLEAR_REG_SET (&deps
->reg_last_in_use
);
1532 free (deps
->reg_last
);
1535 /* If it is profitable to use them, initialize caches for tracking
1536 dependency information. LUID is the number of insns to be scheduled,
1537 it is used in the estimate of profitability. */
1540 init_dependency_caches (luid
)
1543 /* ?!? We could save some memory by computing a per-region luid mapping
1544 which could reduce both the number of vectors in the cache and the size
1545 of each vector. Instead we just avoid the cache entirely unless the
1546 average number of instructions in a basic block is very high. See
1547 the comment before the declaration of true_dependency_cache for
1548 what we consider "very high". */
1549 if (luid
/ n_basic_blocks
> 100 * 5)
1551 true_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1552 sbitmap_vector_zero (true_dependency_cache
, luid
);
1553 anti_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1554 sbitmap_vector_zero (anti_dependency_cache
, luid
);
1555 output_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1556 sbitmap_vector_zero (output_dependency_cache
, luid
);
1557 #ifdef ENABLE_CHECKING
1558 forward_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1559 sbitmap_vector_zero (forward_dependency_cache
, luid
);
1564 /* Free the caches allocated in init_dependency_caches. */
1567 free_dependency_caches ()
1569 if (true_dependency_cache
)
1571 sbitmap_vector_free (true_dependency_cache
);
1572 true_dependency_cache
= NULL
;
1573 sbitmap_vector_free (anti_dependency_cache
);
1574 anti_dependency_cache
= NULL
;
1575 sbitmap_vector_free (output_dependency_cache
);
1576 output_dependency_cache
= NULL
;
1577 #ifdef ENABLE_CHECKING
1578 sbitmap_vector_free (forward_dependency_cache
);
1579 forward_dependency_cache
= NULL
;
1584 /* Initialize some global variables needed by the dependency analysis
1590 reg_pending_sets
= INITIALIZE_REG_SET (reg_pending_sets_head
);
1591 reg_pending_clobbers
= INITIALIZE_REG_SET (reg_pending_clobbers_head
);
1592 reg_pending_uses
= INITIALIZE_REG_SET (reg_pending_uses_head
);
1593 reg_pending_barrier
= false;
1596 /* Free everything used by the dependency analysis code. */
1599 finish_deps_global ()
1601 FREE_REG_SET (reg_pending_sets
);
1602 FREE_REG_SET (reg_pending_clobbers
);
1603 FREE_REG_SET (reg_pending_uses
);