1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001 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 GNU CC.
10 GNU CC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 2, or (at your option) any
15 GNU CC is distributed in the hope that it will be useful, but WITHOUT
16 ANY 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 GNU CC; see the file COPYING. If not, write to the Free
22 the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 extern char *reg_known_equiv_p
;
43 extern rtx
*reg_known_value
;
45 static regset_head reg_pending_sets_head
;
46 static regset_head reg_pending_clobbers_head
;
48 static regset reg_pending_sets
;
49 static regset reg_pending_clobbers
;
50 static int reg_pending_sets_all
;
52 /* To speed up the test for duplicate dependency links we keep a
53 record of dependencies created by add_dependence when the average
54 number of instructions in a basic block is very large.
56 Studies have shown that there is typically around 5 instructions between
57 branches for typical C code. So we can make a guess that the average
58 basic block is approximately 5 instructions long; we will choose 100X
59 the average size as a very large basic block.
61 Each insn has associated bitmaps for its dependencies. Each bitmap
62 has enough entries to represent a dependency on any other insn in
63 the insn chain. All bitmap for true dependencies cache is
64 allocated then the rest two ones are also allocated. */
65 static sbitmap
*true_dependency_cache
;
66 static sbitmap
*anti_dependency_cache
;
67 static sbitmap
*output_dependency_cache
;
69 /* To speed up checking consistency of formed forward insn
70 dependencies we use the following cache. Another possible solution
71 could be switching off checking duplication of insns in forward
73 #ifdef ENABLE_CHECKING
74 static sbitmap
*forward_dependency_cache
;
77 static int deps_may_trap_p
PARAMS ((rtx
));
78 static void remove_dependence
PARAMS ((rtx
, rtx
));
79 static void set_sched_group_p
PARAMS ((rtx
));
81 static void flush_pending_lists
PARAMS ((struct deps
*, rtx
, int));
82 static void sched_analyze_1
PARAMS ((struct deps
*, rtx
, rtx
));
83 static void sched_analyze_2
PARAMS ((struct deps
*, rtx
, rtx
));
84 static void sched_analyze_insn
PARAMS ((struct deps
*, rtx
, rtx
, rtx
));
85 static rtx group_leader
PARAMS ((rtx
));
87 static rtx get_condition
PARAMS ((rtx
));
88 static int conditions_mutex_p
PARAMS ((rtx
, rtx
));
90 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
96 rtx addr
= XEXP (mem
, 0);
99 && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
100 && reg_known_value
[REGNO (addr
)])
101 addr
= reg_known_value
[REGNO (addr
)];
102 return rtx_addr_can_trap_p (addr
);
105 /* Return the INSN_LIST containing INSN in LIST, or NULL
106 if LIST does not contain INSN. */
109 find_insn_list (insn
, list
)
115 if (XEXP (list
, 0) == insn
)
117 list
= XEXP (list
, 1);
122 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
126 find_insn_mem_list (insn
, x
, list
, list1
)
132 if (XEXP (list
, 0) == insn
133 && XEXP (list1
, 0) == x
)
135 list
= XEXP (list
, 1);
136 list1
= XEXP (list1
, 1);
141 /* Find the condition under which INSN is executed. */
147 rtx pat
= PATTERN (insn
);
152 if (GET_CODE (pat
) == COND_EXEC
)
153 return COND_EXEC_TEST (pat
);
154 if (GET_CODE (insn
) != JUMP_INSN
)
156 if (GET_CODE (pat
) != SET
|| SET_SRC (pat
) != pc_rtx
)
158 if (GET_CODE (SET_DEST (pat
)) != IF_THEN_ELSE
)
160 pat
= SET_DEST (pat
);
161 cond
= XEXP (pat
, 0);
162 if (GET_CODE (XEXP (cond
, 1)) == LABEL_REF
163 && XEXP (cond
, 2) == pc_rtx
)
165 else if (GET_CODE (XEXP (cond
, 2)) == LABEL_REF
166 && XEXP (cond
, 1) == pc_rtx
)
167 return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)), GET_MODE (cond
),
168 XEXP (cond
, 0), XEXP (cond
, 1));
173 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
176 conditions_mutex_p (cond1
, cond2
)
179 if (GET_RTX_CLASS (GET_CODE (cond1
)) == '<'
180 && GET_RTX_CLASS (GET_CODE (cond2
)) == '<'
181 && GET_CODE (cond1
) == reverse_condition (GET_CODE (cond2
))
182 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
183 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
188 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
189 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
190 of dependence that this link represents. */
193 add_dependence (insn
, elem
, dep_type
)
196 enum reg_note dep_type
;
202 /* Don't depend an insn on itself. */
206 /* We can get a dependency on deleted insns due to optimizations in
207 the register allocation and reloading or due to splitting. Any
208 such dependency is useless and can be ignored. */
209 if (GET_CODE (elem
) == NOTE
)
212 /* flow.c doesn't handle conditional lifetimes entirely correctly;
213 calls mess up the conditional lifetimes. */
214 if (GET_CODE (insn
) != CALL_INSN
&& GET_CODE (elem
) != CALL_INSN
)
216 cond1
= get_condition (insn
);
217 cond2
= get_condition (elem
);
218 if (cond1
&& cond2
&& conditions_mutex_p (cond1
, cond2
))
222 /* If elem is part of a sequence that must be scheduled together, then
223 make the dependence point to the last insn of the sequence.
224 When HAVE_cc0, it is possible for NOTEs to exist between users and
225 setters of the condition codes, so we must skip past notes here.
226 Otherwise, NOTEs are impossible here. */
227 next
= next_nonnote_insn (elem
);
228 if (next
&& SCHED_GROUP_P (next
)
229 && GET_CODE (next
) != CODE_LABEL
)
231 /* Notes will never intervene here though, so don't bother checking
234 /* We must reject CODE_LABELs, so that we don't get confused by one
235 that has LABEL_PRESERVE_P set, which is represented by the same
236 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
240 while ((nnext
= next_nonnote_insn (next
)) != NULL
241 && SCHED_GROUP_P (nnext
)
242 && GET_CODE (nnext
) != CODE_LABEL
)
245 /* Again, don't depend an insn on itself. */
249 /* Make the dependence to NEXT, the last insn of the group, instead
250 of the original ELEM. */
255 #ifdef INSN_SCHEDULING
256 /* ??? No good way to tell from here whether we're doing interblock
257 scheduling. Possibly add another callback. */
259 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
260 No need for interblock dependences with calls, since
261 calls are not moved between blocks. Note: the edge where
262 elem is a CALL is still required. */
263 if (GET_CODE (insn
) == CALL_INSN
264 && (INSN_BB (elem
) != INSN_BB (insn
)))
268 /* If we already have a dependency for ELEM, then we do not need to
269 do anything. Avoiding the list walk below can cut compile times
270 dramatically for some code. */
271 if (true_dependency_cache
!= NULL
)
273 enum reg_note present_dep_type
= 0;
275 if (anti_dependency_cache
== NULL
|| output_dependency_cache
== NULL
)
277 if (TEST_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
)))
278 /* Do nothing (present_set_type is already 0). */
280 else if (TEST_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
282 present_dep_type
= REG_DEP_ANTI
;
283 else if (TEST_BIT (output_dependency_cache
[INSN_LUID (insn
)],
285 present_dep_type
= REG_DEP_OUTPUT
;
288 if (present_p
&& (int) dep_type
>= (int) present_dep_type
)
293 /* Check that we don't already have this dependence. */
295 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
296 if (XEXP (link
, 0) == elem
)
298 #ifdef INSN_SCHEDULING
299 /* Clear corresponding cache entry because type of the link
301 if (true_dependency_cache
!= NULL
)
303 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
304 RESET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
306 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
307 && output_dependency_cache
)
308 RESET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
315 /* If this is a more restrictive type of dependence than the existing
316 one, then change the existing dependence to this type. */
317 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
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
322 note that in the bitmap caches of dependency information. */
323 if (true_dependency_cache
!= NULL
)
325 if ((int)REG_NOTE_KIND (link
) == 0)
326 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
328 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
329 SET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
331 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
332 SET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
338 /* Might want to check one level of transitivity to save conses. */
340 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
341 LOG_LINKS (insn
) = link
;
343 /* Insn dependency, not data dependency. */
344 PUT_REG_NOTE_KIND (link
, dep_type
);
346 #ifdef INSN_SCHEDULING
347 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
348 in the bitmap caches of dependency information. */
349 if (true_dependency_cache
!= NULL
)
351 if ((int)dep_type
== 0)
352 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
353 else if (dep_type
== REG_DEP_ANTI
)
354 SET_BIT (anti_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
355 else if (dep_type
== REG_DEP_OUTPUT
)
356 SET_BIT (output_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
361 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
362 of INSN. Abort if not found. */
365 remove_dependence (insn
, elem
)
369 rtx prev
, link
, next
;
372 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
374 next
= XEXP (link
, 1);
375 if (XEXP (link
, 0) == elem
)
378 XEXP (prev
, 1) = next
;
380 LOG_LINKS (insn
) = next
;
382 #ifdef INSN_SCHEDULING
383 /* If we are removing a dependency from the LOG_LINKS list,
384 make sure to remove it from the cache too. */
385 if (true_dependency_cache
!= NULL
)
387 if (REG_NOTE_KIND (link
) == 0)
388 RESET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
390 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
391 RESET_BIT (anti_dependency_cache
[INSN_LUID (insn
)],
393 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
394 RESET_BIT (output_dependency_cache
[INSN_LUID (insn
)],
399 free_INSN_LIST_node (link
);
412 /* Return an insn which represents a SCHED_GROUP, which is
413 the last insn in the group. */
424 insn
= next_nonnote_insn (insn
);
426 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
431 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
432 goes along with that. */
435 set_sched_group_p (insn
)
440 SCHED_GROUP_P (insn
) = 1;
442 /* There may be a note before this insn now, but all notes will
443 be removed before we actually try to schedule the insns, so
444 it won't cause a problem later. We must avoid it here though. */
445 prev
= prev_nonnote_insn (insn
);
447 /* Make a copy of all dependencies on the immediately previous insn,
448 and add to this insn. This is so that all the dependencies will
449 apply to the group. Remove an explicit dependence on this insn
450 as SCHED_GROUP_P now represents it. */
452 if (find_insn_list (prev
, LOG_LINKS (insn
)))
453 remove_dependence (insn
, prev
);
455 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
456 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
459 /* Process an insn's memory dependencies. There are four kinds of
462 (0) read dependence: read follows read
463 (1) true dependence: read follows write
464 (2) anti dependence: write follows read
465 (3) output dependence: write follows write
467 We are careful to build only dependencies which actually exist, and
468 use transitivity to avoid building too many links. */
470 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
471 The MEM is a memory reference contained within INSN, which we are saving
472 so that we can do memory aliasing on it. */
475 add_insn_mem_dependence (deps
, insn_list
, mem_list
, insn
, mem
)
477 rtx
*insn_list
, *mem_list
, insn
, mem
;
481 link
= alloc_INSN_LIST (insn
, *insn_list
);
484 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
487 deps
->pending_lists_length
++;
490 /* Make a dependency between every memory reference on the pending lists
491 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
495 flush_pending_lists (deps
, insn
, only_write
)
503 while (deps
->pending_read_insns
&& ! only_write
)
505 add_dependence (insn
, XEXP (deps
->pending_read_insns
, 0),
508 link
= deps
->pending_read_insns
;
509 deps
->pending_read_insns
= XEXP (deps
->pending_read_insns
, 1);
510 free_INSN_LIST_node (link
);
512 link
= deps
->pending_read_mems
;
513 deps
->pending_read_mems
= XEXP (deps
->pending_read_mems
, 1);
514 free_EXPR_LIST_node (link
);
516 while (deps
->pending_write_insns
)
518 add_dependence (insn
, XEXP (deps
->pending_write_insns
, 0),
521 link
= deps
->pending_write_insns
;
522 deps
->pending_write_insns
= XEXP (deps
->pending_write_insns
, 1);
523 free_INSN_LIST_node (link
);
525 link
= deps
->pending_write_mems
;
526 deps
->pending_write_mems
= XEXP (deps
->pending_write_mems
, 1);
527 free_EXPR_LIST_node (link
);
529 deps
->pending_lists_length
= 0;
531 /* last_pending_memory_flush is now a list of insns. */
532 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
533 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
535 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
536 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
539 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
540 rtx, X, creating all dependencies generated by the write to the
541 destination of X, and reads of everything mentioned. */
544 sched_analyze_1 (deps
, x
, insn
)
550 register rtx dest
= XEXP (x
, 0);
551 enum rtx_code code
= GET_CODE (x
);
556 if (GET_CODE (dest
) == PARALLEL
)
560 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
561 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
562 sched_analyze_1 (deps
,
563 gen_rtx_CLOBBER (VOIDmode
,
564 XEXP (XVECEXP (dest
, 0, i
), 0)),
567 if (GET_CODE (x
) == SET
)
568 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
572 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
573 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
575 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
577 /* The second and third arguments are values read by this insn. */
578 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
579 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
581 dest
= XEXP (dest
, 0);
584 if (GET_CODE (dest
) == REG
)
588 regno
= REGNO (dest
);
590 /* A hard reg in a wide mode may really be multiple registers.
591 If so, mark all of them just like the first. */
592 if (regno
< FIRST_PSEUDO_REGISTER
)
594 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
600 for (u
= deps
->reg_last
[r
].uses
; u
; u
= XEXP (u
, 1))
601 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
603 for (u
= deps
->reg_last
[r
].sets
; u
; u
= XEXP (u
, 1))
604 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
606 /* Clobbers need not be ordered with respect to one
607 another, but sets must be ordered with respect to a
611 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
612 free_INSN_LIST_list (&deps
->reg_last
[r
].uses
);
613 for (u
= deps
->reg_last
[r
].clobbers
; u
; u
= XEXP (u
, 1))
614 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
615 SET_REGNO_REG_SET (reg_pending_sets
, r
);
618 SET_REGNO_REG_SET (reg_pending_clobbers
, r
);
620 /* Function calls clobber all call_used regs. */
623 && TEST_HARD_REG_BIT (regs_invalidated_by_call
, r
)))
624 for (u
= deps
->last_function_call
; u
; u
= XEXP (u
, 1))
625 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
628 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
629 it does not reload. Ignore these as they have served their
631 else if (regno
>= deps
->max_reg
)
633 if (GET_CODE (PATTERN (insn
)) != USE
634 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
641 for (u
= deps
->reg_last
[regno
].uses
; u
; u
= XEXP (u
, 1))
642 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
644 for (u
= deps
->reg_last
[regno
].sets
; u
; u
= XEXP (u
, 1))
645 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
649 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
650 free_INSN_LIST_list (&deps
->reg_last
[regno
].uses
);
651 for (u
= deps
->reg_last
[regno
].clobbers
; u
; u
= XEXP (u
, 1))
652 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
653 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
656 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
658 /* Pseudos that are REG_EQUIV to something may be replaced
659 by that during reloading. We need only add dependencies for
660 the address in the REG_EQUIV note. */
661 if (!reload_completed
662 && reg_known_equiv_p
[regno
]
663 && GET_CODE (reg_known_value
[regno
]) == MEM
)
664 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
666 /* Don't let it cross a call after scheduling if it doesn't
667 already cross one. */
669 if (REG_N_CALLS_CROSSED (regno
) == 0)
670 for (u
= deps
->last_function_call
; u
; u
= XEXP (u
, 1))
671 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
674 else if (GET_CODE (dest
) == MEM
)
676 /* Writing memory. */
678 if (deps
->pending_lists_length
> 32)
680 /* Flush all pending reads and writes to prevent the pending lists
681 from getting any larger. Insn scheduling runs too slowly when
682 these lists get long. The number 32 was chosen because it
683 seems like a reasonable number. When compiling GCC with itself,
684 this flush occurs 8 times for sparc, and 10 times for m88k using
686 flush_pending_lists (deps
, insn
, 0);
691 rtx pending
, pending_mem
;
693 pending
= deps
->pending_read_insns
;
694 pending_mem
= deps
->pending_read_mems
;
697 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
698 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
700 pending
= XEXP (pending
, 1);
701 pending_mem
= XEXP (pending_mem
, 1);
704 pending
= deps
->pending_write_insns
;
705 pending_mem
= deps
->pending_write_mems
;
708 if (output_dependence (XEXP (pending_mem
, 0), dest
))
709 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
711 pending
= XEXP (pending
, 1);
712 pending_mem
= XEXP (pending_mem
, 1);
715 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
716 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
718 add_insn_mem_dependence (deps
, &deps
->pending_write_insns
,
719 &deps
->pending_write_mems
, insn
, dest
);
721 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
725 if (GET_CODE (x
) == SET
)
726 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
729 /* Analyze the uses of memory and registers in rtx X in INSN. */
732 sched_analyze_2 (deps
, x
, insn
)
739 register enum rtx_code code
;
740 register const char *fmt
;
754 /* Ignore constants. Note that we must handle CONST_DOUBLE here
755 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
756 this does not mean that this insn is using cc0. */
761 /* User of CC0 depends on immediately preceding insn. */
762 set_sched_group_p (insn
);
769 int regno
= REGNO (x
);
770 if (regno
< FIRST_PSEUDO_REGISTER
)
774 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
778 deps
->reg_last
[r
].uses
779 = alloc_INSN_LIST (insn
, deps
->reg_last
[r
].uses
);
780 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, r
);
782 for (u
= deps
->reg_last
[r
].sets
; u
; u
= XEXP (u
, 1))
783 add_dependence (insn
, XEXP (u
, 0), 0);
785 /* ??? This should never happen. */
786 for (u
= deps
->reg_last
[r
].clobbers
; u
; u
= XEXP (u
, 1))
787 add_dependence (insn
, XEXP (u
, 0), 0);
789 if (call_used_regs
[r
] || global_regs
[r
])
790 /* Function calls clobber all call_used regs. */
791 for (u
= deps
->last_function_call
; u
; u
= XEXP (u
, 1))
792 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
795 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
796 it does not reload. Ignore these as they have served their
798 else if (regno
>= deps
->max_reg
)
800 if (GET_CODE (PATTERN (insn
)) != USE
801 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
806 deps
->reg_last
[regno
].uses
807 = alloc_INSN_LIST (insn
, deps
->reg_last
[regno
].uses
);
808 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, regno
);
810 for (u
= deps
->reg_last
[regno
].sets
; u
; u
= XEXP (u
, 1))
811 add_dependence (insn
, XEXP (u
, 0), 0);
813 /* ??? This should never happen. */
814 for (u
= deps
->reg_last
[regno
].clobbers
; u
; u
= XEXP (u
, 1))
815 add_dependence (insn
, XEXP (u
, 0), 0);
817 /* Pseudos that are REG_EQUIV to something may be replaced
818 by that during reloading. We need only add dependencies for
819 the address in the REG_EQUIV note. */
820 if (!reload_completed
821 && reg_known_equiv_p
[regno
]
822 && GET_CODE (reg_known_value
[regno
]) == MEM
)
823 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
825 /* If the register does not already cross any calls, then add this
826 insn to the sched_before_next_call list so that it will still
827 not cross calls after scheduling. */
828 if (REG_N_CALLS_CROSSED (regno
) == 0)
829 add_dependence (deps
->sched_before_next_call
, insn
,
837 /* Reading memory. */
839 rtx pending
, pending_mem
;
841 pending
= deps
->pending_read_insns
;
842 pending_mem
= deps
->pending_read_mems
;
845 if (read_dependence (XEXP (pending_mem
, 0), x
))
846 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
848 pending
= XEXP (pending
, 1);
849 pending_mem
= XEXP (pending_mem
, 1);
852 pending
= deps
->pending_write_insns
;
853 pending_mem
= deps
->pending_write_mems
;
856 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
858 add_dependence (insn
, XEXP (pending
, 0), 0);
860 pending
= XEXP (pending
, 1);
861 pending_mem
= XEXP (pending_mem
, 1);
864 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
865 if (GET_CODE (XEXP (u
, 0)) != JUMP_INSN
866 || deps_may_trap_p (x
))
867 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
869 /* Always add these dependencies to pending_reads, since
870 this insn may be followed by a write. */
871 add_insn_mem_dependence (deps
, &deps
->pending_read_insns
,
872 &deps
->pending_read_mems
, insn
, x
);
874 /* Take advantage of tail recursion here. */
875 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
879 /* Force pending stores to memory in case a trap handler needs them. */
881 flush_pending_lists (deps
, insn
, 1);
886 case UNSPEC_VOLATILE
:
890 /* Traditional and volatile asm instructions must be considered to use
891 and clobber all hard registers, all pseudo-registers and all of
892 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
894 Consider for instance a volatile asm that changes the fpu rounding
895 mode. An insn should not be moved across this even if it only uses
896 pseudo-regs because it might give an incorrectly rounded result. */
897 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
899 for (i
= 0; i
< deps
->max_reg
; i
++)
901 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
903 for (u
= reg_last
->uses
; u
; u
= XEXP (u
, 1))
904 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
905 for (u
= reg_last
->sets
; u
; u
= XEXP (u
, 1))
906 add_dependence (insn
, XEXP (u
, 0), 0);
907 for (u
= reg_last
->clobbers
; u
; u
= XEXP (u
, 1))
908 add_dependence (insn
, XEXP (u
, 0), 0);
910 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
911 free_INSN_LIST_list (®_last
->uses
);
913 reg_pending_sets_all
= 1;
915 flush_pending_lists (deps
, insn
, 0);
918 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
919 We can not just fall through here since then we would be confused
920 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
921 traditional asms unlike their normal usage. */
923 if (code
== ASM_OPERANDS
)
925 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
926 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
936 /* These both read and modify the result. We must handle them as writes
937 to get proper dependencies for following instructions. We must handle
938 them as reads to get proper dependencies from this to previous
939 instructions. Thus we need to pass them to both sched_analyze_1
940 and sched_analyze_2. We must call sched_analyze_2 first in order
941 to get the proper antecedent for the read. */
942 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
943 sched_analyze_1 (deps
, x
, insn
);
948 /* op0 = op0 + op1 */
949 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
950 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
951 sched_analyze_1 (deps
, x
, insn
);
958 /* Other cases: walk the insn. */
959 fmt
= GET_RTX_FORMAT (code
);
960 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
963 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
964 else if (fmt
[i
] == 'E')
965 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
966 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
970 /* Analyze an INSN with pattern X to find all dependencies. */
973 sched_analyze_insn (deps
, x
, insn
, loop_notes
)
978 register RTX_CODE code
= GET_CODE (x
);
979 int schedule_barrier_found
= 0;
983 if (code
== COND_EXEC
)
985 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
987 /* ??? Should be recording conditions so we reduce the number of
988 false dependancies. */
989 x
= COND_EXEC_CODE (x
);
992 if (code
== SET
|| code
== CLOBBER
)
993 sched_analyze_1 (deps
, x
, insn
);
994 else if (code
== PARALLEL
)
997 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
999 rtx sub
= XVECEXP (x
, 0, i
);
1000 code
= GET_CODE (sub
);
1002 if (code
== COND_EXEC
)
1004 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
1005 sub
= COND_EXEC_CODE (sub
);
1006 code
= GET_CODE (sub
);
1008 if (code
== SET
|| code
== CLOBBER
)
1009 sched_analyze_1 (deps
, sub
, insn
);
1011 sched_analyze_2 (deps
, sub
, insn
);
1015 sched_analyze_2 (deps
, x
, insn
);
1017 /* Mark registers CLOBBERED or used by called function. */
1018 if (GET_CODE (insn
) == CALL_INSN
)
1019 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
1021 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
1022 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
1024 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
1027 if (GET_CODE (insn
) == JUMP_INSN
)
1030 next
= next_nonnote_insn (insn
);
1031 if (next
&& GET_CODE (next
) == BARRIER
)
1032 schedule_barrier_found
= 1;
1035 rtx pending
, pending_mem
, u
;
1037 INIT_REG_SET (&tmp
);
1039 (*current_sched_info
->compute_jump_reg_dependencies
) (insn
, &tmp
);
1040 EXECUTE_IF_SET_IN_REG_SET (&tmp
, 0, i
,
1042 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1043 for (u
= reg_last
->sets
; u
; u
= XEXP (u
, 1))
1044 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1045 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1046 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1049 CLEAR_REG_SET (&tmp
);
1051 /* All memory writes and volatile reads must happen before the
1052 jump. Non-volatile reads must happen before the jump iff
1053 the result is needed by the above register used mask. */
1055 pending
= deps
->pending_write_insns
;
1056 pending_mem
= deps
->pending_write_mems
;
1059 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
1060 pending
= XEXP (pending
, 1);
1061 pending_mem
= XEXP (pending_mem
, 1);
1064 pending
= deps
->pending_read_insns
;
1065 pending_mem
= deps
->pending_read_mems
;
1068 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0)))
1069 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
1070 pending
= XEXP (pending
, 1);
1071 pending_mem
= XEXP (pending_mem
, 1);
1074 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
1075 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1079 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1080 block, then we must be sure that no instructions are scheduled across it.
1081 Otherwise, the reg_n_refs info (which depends on loop_depth) would
1082 become incorrect. */
1087 /* Update loop_notes with any notes from this insn. Also determine
1088 if any of the notes on the list correspond to instruction scheduling
1089 barriers (loop, eh & setjmp notes, but not range notes). */
1091 while (XEXP (link
, 1))
1093 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
1094 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
1095 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
1096 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
1097 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
1098 schedule_barrier_found
= 1;
1100 link
= XEXP (link
, 1);
1102 XEXP (link
, 1) = REG_NOTES (insn
);
1103 REG_NOTES (insn
) = loop_notes
;
1106 /* If this instruction can throw an exception, then moving it changes
1107 where block boundaries fall. This is mighty confusing elsewhere.
1108 Therefore, prevent such an instruction from being moved. */
1109 if (flag_non_call_exceptions
&& can_throw_internal (insn
))
1110 schedule_barrier_found
= 1;
1112 /* Add dependencies if a scheduling barrier was found. */
1113 if (schedule_barrier_found
)
1117 for (i
= 0; i
< deps
->max_reg
; i
++)
1119 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1121 for (u
= reg_last
->uses
; u
; u
= XEXP (u
, 1))
1122 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1123 for (u
= reg_last
->sets
; u
; u
= XEXP (u
, 1))
1124 add_dependence (insn
, XEXP (u
, 0), 0);
1125 for (u
= reg_last
->clobbers
; u
; u
= XEXP (u
, 1))
1126 add_dependence (insn
, XEXP (u
, 0), 0);
1128 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
1129 free_INSN_LIST_list (®_last
->uses
);
1131 flush_pending_lists (deps
, insn
, 0);
1133 reg_pending_sets_all
= 1;
1136 /* Accumulate clobbers until the next set so that it will be output
1137 dependent on all of them. At the next set we can clear the clobber
1138 list, since subsequent sets will be output dependent on it. */
1139 if (reg_pending_sets_all
)
1141 reg_pending_sets_all
= 0;
1142 for (i
= 0; i
< deps
->max_reg
; i
++)
1144 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1145 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
1147 free_INSN_LIST_list (®_last
->sets
);
1148 free_INSN_LIST_list (®_last
->clobbers
);
1150 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1151 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1156 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1158 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1159 if (GET_CODE (PATTERN (insn
)) != COND_EXEC
)
1161 free_INSN_LIST_list (®_last
->sets
);
1162 free_INSN_LIST_list (®_last
->clobbers
);
1164 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1165 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1167 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1169 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1170 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1171 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
1174 CLEAR_REG_SET (reg_pending_sets
);
1175 CLEAR_REG_SET (reg_pending_clobbers
);
1177 /* If a post-call group is still open, see if it should remain so.
1178 This insn must be a simple move of a hard reg to a pseudo or
1181 We must avoid moving these insns for correctness on
1182 SMALL_REGISTER_CLASS machines, and for special registers like
1183 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1184 hard regs for all targets. */
1186 if (deps
->in_post_call_group_p
)
1188 rtx tmp
, set
= single_set (insn
);
1189 int src_regno
, dest_regno
;
1192 goto end_call_group
;
1194 tmp
= SET_DEST (set
);
1195 if (GET_CODE (tmp
) == SUBREG
)
1196 tmp
= SUBREG_REG (tmp
);
1197 if (GET_CODE (tmp
) == REG
)
1198 dest_regno
= REGNO (tmp
);
1200 goto end_call_group
;
1202 tmp
= SET_SRC (set
);
1203 if (GET_CODE (tmp
) == SUBREG
)
1204 tmp
= SUBREG_REG (tmp
);
1205 if (GET_CODE (tmp
) == REG
)
1206 src_regno
= REGNO (tmp
);
1208 goto end_call_group
;
1210 if (src_regno
< FIRST_PSEUDO_REGISTER
1211 || dest_regno
< FIRST_PSEUDO_REGISTER
)
1213 set_sched_group_p (insn
);
1214 CANT_MOVE (insn
) = 1;
1219 deps
->in_post_call_group_p
= 0;
1224 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1225 for every dependency. */
1228 sched_analyze (deps
, head
, tail
)
1236 for (insn
= head
;; insn
= NEXT_INSN (insn
))
1238 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
1240 /* Clear out the stale LOG_LINKS from flow. */
1241 free_INSN_LIST_list (&LOG_LINKS (insn
));
1243 /* Clear out stale SCHED_GROUP_P. */
1244 SCHED_GROUP_P (insn
) = 0;
1246 /* Make each JUMP_INSN a scheduling barrier for memory
1248 if (GET_CODE (insn
) == JUMP_INSN
)
1249 deps
->last_pending_memory_flush
1250 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
1251 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1254 else if (GET_CODE (insn
) == CALL_INSN
)
1259 /* Clear out stale SCHED_GROUP_P. */
1260 SCHED_GROUP_P (insn
) = 0;
1262 CANT_MOVE (insn
) = 1;
1264 /* Clear out the stale LOG_LINKS from flow. */
1265 free_INSN_LIST_list (&LOG_LINKS (insn
));
1267 /* Any instruction using a hard register which may get clobbered
1268 by a call needs to be marked as dependent on this call.
1269 This prevents a use of a hard return reg from being moved
1270 past a void call (i.e. it does not explicitly set the hard
1273 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
1274 all registers, not just hard registers, may be clobbered by this
1277 /* Insn, being a CALL_INSN, magically depends on
1278 `last_function_call' already. */
1280 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
1281 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
1283 for (i
= 0; i
< deps
->max_reg
; i
++)
1285 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1287 for (u
= reg_last
->uses
; u
; u
= XEXP (u
, 1))
1288 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1289 for (u
= reg_last
->sets
; u
; u
= XEXP (u
, 1))
1290 add_dependence (insn
, XEXP (u
, 0), 0);
1291 for (u
= reg_last
->clobbers
; u
; u
= XEXP (u
, 1))
1292 add_dependence (insn
, XEXP (u
, 0), 0);
1294 free_INSN_LIST_list (®_last
->uses
);
1296 reg_pending_sets_all
= 1;
1298 /* Add a pair of REG_SAVE_NOTEs which we will later
1299 convert back into a NOTE_INSN_SETJMP note. See
1300 reemit_notes for why we use a pair of NOTEs. */
1301 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
1304 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
1305 GEN_INT (NOTE_INSN_SETJMP
),
1310 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1311 if (call_used_regs
[i
] || global_regs
[i
])
1313 for (u
= deps
->reg_last
[i
].uses
; u
; u
= XEXP (u
, 1))
1314 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1315 for (u
= deps
->reg_last
[i
].sets
; u
; u
= XEXP (u
, 1))
1316 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
1318 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
1322 /* For each insn which shouldn't cross a call, add a dependence
1323 between that insn and this call insn. */
1324 x
= LOG_LINKS (deps
->sched_before_next_call
);
1327 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
1330 free_INSN_LIST_list (&LOG_LINKS (deps
->sched_before_next_call
));
1332 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1335 /* In the absence of interprocedural alias analysis, we must flush
1336 all pending reads and writes, and start new dependencies starting
1337 from here. But only flush writes for constant calls (which may
1338 be passed a pointer to something we haven't written yet). */
1339 flush_pending_lists (deps
, insn
, CONST_CALL_P (insn
));
1341 /* Depend this function call (actually, the user of this
1342 function call) on all hard register clobberage. */
1344 /* last_function_call is now a list of insns. */
1345 free_INSN_LIST_list (&deps
->last_function_call
);
1346 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
1348 /* Before reload, begin a post-call group, so as to keep the
1349 lifetimes of hard registers correct. */
1350 if (! reload_completed
)
1351 deps
->in_post_call_group_p
= 1;
1354 /* See comments on reemit_notes as to why we do this.
1355 ??? Actually, the reemit_notes just say what is done, not why. */
1357 else if (GET_CODE (insn
) == NOTE
1358 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_BEG
1359 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
1361 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
, NOTE_RANGE_INFO (insn
),
1363 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1364 GEN_INT (NOTE_LINE_NUMBER (insn
)),
1367 else if (GET_CODE (insn
) == NOTE
1368 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
1369 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
1370 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1371 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
1372 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
1373 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
1377 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1378 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
1379 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
1381 rtx_region
= GEN_INT (0);
1383 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1386 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1387 GEN_INT (NOTE_LINE_NUMBER (insn
)),
1389 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
1398 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1399 dependences from LOG_LINKS to build forward dependences in
1403 compute_forward_dependences (head
, tail
)
1408 enum reg_note dep_type
;
1410 next_tail
= NEXT_INSN (tail
);
1411 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1413 if (! INSN_P (insn
))
1416 insn
= group_leader (insn
);
1418 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
1420 rtx x
= group_leader (XEXP (link
, 0));
1423 if (x
!= XEXP (link
, 0))
1426 #ifdef ENABLE_CHECKING
1427 /* If add_dependence is working properly there should never
1428 be notes, deleted insns or duplicates in the backward
1429 links. Thus we need not check for them here.
1431 However, if we have enabled checking we might as well go
1432 ahead and verify that add_dependence worked properly. */
1433 if (GET_CODE (x
) == NOTE
1434 || INSN_DELETED_P (x
)
1435 || (forward_dependency_cache
!= NULL
1436 && TEST_BIT (forward_dependency_cache
[INSN_LUID (x
)],
1438 || (forward_dependency_cache
== NULL
1439 && find_insn_list (insn
, INSN_DEPEND (x
))))
1441 if (forward_dependency_cache
!= NULL
)
1442 SET_BIT (forward_dependency_cache
[INSN_LUID (x
)],
1446 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
1448 dep_type
= REG_NOTE_KIND (link
);
1449 PUT_REG_NOTE_KIND (new_link
, dep_type
);
1451 INSN_DEPEND (x
) = new_link
;
1452 INSN_DEP_COUNT (insn
) += 1;
1457 /* Initialize variables for region data dependence analysis.
1458 n_bbs is the number of region blocks. */
1464 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
1466 deps
->max_reg
= max_reg
;
1467 deps
->reg_last
= (struct deps_reg
*)
1468 xcalloc (max_reg
, sizeof (struct deps_reg
));
1469 INIT_REG_SET (&deps
->reg_last_in_use
);
1471 deps
->pending_read_insns
= 0;
1472 deps
->pending_read_mems
= 0;
1473 deps
->pending_write_insns
= 0;
1474 deps
->pending_write_mems
= 0;
1475 deps
->pending_lists_length
= 0;
1476 deps
->last_pending_memory_flush
= 0;
1477 deps
->last_function_call
= 0;
1478 deps
->in_post_call_group_p
= 0;
1480 deps
->sched_before_next_call
1481 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
1482 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
1483 LOG_LINKS (deps
->sched_before_next_call
) = 0;
1486 /* Free insn lists found in DEPS. */
1494 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1495 times. For a test case with 42000 regs and 8000 small basic blocks,
1496 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1497 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1499 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1500 free_INSN_LIST_list (®_last
->uses
);
1501 free_INSN_LIST_list (®_last
->sets
);
1502 free_INSN_LIST_list (®_last
->clobbers
);
1504 CLEAR_REG_SET (&deps
->reg_last_in_use
);
1506 free (deps
->reg_last
);
1507 deps
->reg_last
= NULL
;
1510 /* If it is profitable to use them, initialize caches for tracking
1511 dependency informatino. LUID is the number of insns to be scheduled,
1512 it is used in the estimate of profitability. */
1515 init_dependency_caches (luid
)
1518 /* ?!? We could save some memory by computing a per-region luid mapping
1519 which could reduce both the number of vectors in the cache and the size
1520 of each vector. Instead we just avoid the cache entirely unless the
1521 average number of instructions in a basic block is very high. See
1522 the comment before the declaration of true_dependency_cache for
1523 what we consider "very high". */
1524 if (luid
/ n_basic_blocks
> 100 * 5)
1526 true_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1527 sbitmap_vector_zero (true_dependency_cache
, luid
);
1528 anti_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1529 sbitmap_vector_zero (anti_dependency_cache
, luid
);
1530 output_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1531 sbitmap_vector_zero (output_dependency_cache
, luid
);
1532 #ifdef ENABLE_CHECKING
1533 forward_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
1534 sbitmap_vector_zero (forward_dependency_cache
, luid
);
1539 /* Free the caches allocated in init_dependency_caches. */
1542 free_dependency_caches ()
1544 if (true_dependency_cache
)
1546 sbitmap_vector_free (true_dependency_cache
);
1547 true_dependency_cache
= NULL
;
1548 sbitmap_vector_free (anti_dependency_cache
);
1549 anti_dependency_cache
= NULL
;
1550 sbitmap_vector_free (output_dependency_cache
);
1551 output_dependency_cache
= NULL
;
1552 #ifdef ENABLE_CHECKING
1553 sbitmap_vector_free (forward_dependency_cache
);
1554 forward_dependency_cache
= NULL
;
1559 /* Initialize some global variables needed by the dependency analysis
1565 reg_pending_sets
= INITIALIZE_REG_SET (reg_pending_sets_head
);
1566 reg_pending_clobbers
= INITIALIZE_REG_SET (reg_pending_clobbers_head
);
1567 reg_pending_sets_all
= 0;
1570 /* Free everything used by the dependency analysis code. */
1573 finish_deps_global ()
1575 FREE_REG_SET (reg_pending_sets
);
1576 FREE_REG_SET (reg_pending_clobbers
);