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"
47 extern char *reg_known_equiv_p
;
48 extern rtx
*reg_known_value
;
50 static regset_head reg_pending_sets_head
;
51 static regset_head reg_pending_clobbers_head
;
52 static regset_head reg_pending_uses_head
;
54 static regset reg_pending_sets
;
55 static regset reg_pending_clobbers
;
56 static regset reg_pending_uses
;
58 /* The following enumeration values tell us what dependencies we
59 should use to implement the barrier. We use true-dependencies for
60 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
61 enum reg_pending_barrier_mode
68 static enum reg_pending_barrier_mode reg_pending_barrier
;
70 /* To speed up the test for duplicate dependency links we keep a
71 record of dependencies created by add_dependence when the average
72 number of instructions in a basic block is very large.
74 Studies have shown that there is typically around 5 instructions between
75 branches for typical C code. So we can make a guess that the average
76 basic block is approximately 5 instructions long; we will choose 100X
77 the average size as a very large basic block.
79 Each insn has associated bitmaps for its dependencies. Each bitmap
80 has enough entries to represent a dependency on any other insn in
81 the insn chain. All bitmap for true dependencies cache is
82 allocated then the rest two ones are also allocated. */
83 static bitmap_head
*true_dependency_cache
;
84 static bitmap_head
*anti_dependency_cache
;
85 static bitmap_head
*output_dependency_cache
;
88 /* To speed up checking consistency of formed forward insn
89 dependencies we use the following cache. Another possible solution
90 could be switching off checking duplication of insns in forward
92 #ifdef ENABLE_CHECKING
93 static bitmap_head
*forward_dependency_cache
;
96 static int deps_may_trap_p (rtx
);
97 static void add_dependence_list (rtx
, rtx
, enum reg_note
);
98 static void add_dependence_list_and_free (rtx
, rtx
*, enum reg_note
);
99 static void set_sched_group_p (rtx
);
101 static void flush_pending_lists (struct deps
*, rtx
, int, int);
102 static void sched_analyze_1 (struct deps
*, rtx
, rtx
);
103 static void sched_analyze_2 (struct deps
*, rtx
, rtx
);
104 static void sched_analyze_insn (struct deps
*, rtx
, rtx
, rtx
);
106 static rtx
get_condition (rtx
);
107 static int conditions_mutex_p (rtx
, rtx
);
109 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
112 deps_may_trap_p (rtx mem
)
114 rtx addr
= XEXP (mem
, 0);
117 && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
118 && reg_known_value
[REGNO (addr
)])
119 addr
= 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
);
148 if (GET_CODE (pat
) == COND_EXEC
)
149 return COND_EXEC_TEST (pat
);
150 if (GET_CODE (insn
) != JUMP_INSN
)
152 if (GET_CODE (pat
) != SET
|| SET_SRC (pat
) != pc_rtx
)
154 if (GET_CODE (SET_DEST (pat
)) != IF_THEN_ELSE
)
156 pat
= SET_DEST (pat
);
157 cond
= XEXP (pat
, 0);
158 if (GET_CODE (XEXP (cond
, 1)) == LABEL_REF
159 && XEXP (cond
, 2) == pc_rtx
)
161 else if (GET_CODE (XEXP (cond
, 2)) == LABEL_REF
162 && XEXP (cond
, 1) == pc_rtx
)
163 return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)), GET_MODE (cond
),
164 XEXP (cond
, 0), XEXP (cond
, 1));
169 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
172 conditions_mutex_p (rtx cond1
, rtx cond2
)
174 if (COMPARISON_P (cond1
)
175 && COMPARISON_P (cond2
)
176 && GET_CODE (cond1
) == reverse_condition (GET_CODE (cond2
))
177 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
178 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
183 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
184 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
185 type of dependence that this link represents. The function returns
186 nonzero if a new entry has been added to insn's LOG_LINK. */
189 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
195 /* Don't depend an insn on itself. */
199 /* We can get a dependency on deleted insns due to optimizations in
200 the register allocation and reloading or due to splitting. Any
201 such dependency is useless and can be ignored. */
202 if (GET_CODE (elem
) == NOTE
)
205 /* flow.c doesn't handle conditional lifetimes entirely correctly;
206 calls mess up the conditional lifetimes. */
207 /* ??? add_dependence is the wrong place to be eliding dependencies,
208 as that forgets that the condition expressions themselves may
210 if (GET_CODE (insn
) != CALL_INSN
&& GET_CODE (elem
) != CALL_INSN
)
212 cond1
= get_condition (insn
);
213 cond2
= get_condition (elem
);
215 && conditions_mutex_p (cond1
, cond2
)
216 /* Make sure first instruction doesn't affect condition of second
217 instruction if switched. */
218 && !modified_in_p (cond1
, elem
)
219 /* Make sure second instruction doesn't affect condition of first
220 instruction if switched. */
221 && !modified_in_p (cond2
, insn
))
226 #ifdef INSN_SCHEDULING
227 /* ??? No good way to tell from here whether we're doing interblock
228 scheduling. Possibly add another callback. */
230 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
231 No need for interblock dependences with calls, since
232 calls are not moved between blocks. Note: the edge where
233 elem is a CALL is still required. */
234 if (GET_CODE (insn
) == CALL_INSN
235 && (INSN_BB (elem
) != INSN_BB (insn
)))
239 /* If we already have a dependency for ELEM, then we do not need to
240 do anything. Avoiding the list walk below can cut compile times
241 dramatically for some code. */
242 if (true_dependency_cache
!= NULL
)
244 enum reg_note present_dep_type
= 0;
246 if (anti_dependency_cache
== NULL
|| output_dependency_cache
== NULL
)
248 if (bitmap_bit_p (&true_dependency_cache
[INSN_LUID (insn
)],
250 /* Do nothing (present_set_type is already 0). */
252 else if (bitmap_bit_p (&anti_dependency_cache
[INSN_LUID (insn
)],
254 present_dep_type
= REG_DEP_ANTI
;
255 else if (bitmap_bit_p (&output_dependency_cache
[INSN_LUID (insn
)],
257 present_dep_type
= REG_DEP_OUTPUT
;
260 if (present_p
&& (int) dep_type
>= (int) present_dep_type
)
265 /* Check that we don't already have this dependence. */
267 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
268 if (XEXP (link
, 0) == elem
)
270 #ifdef INSN_SCHEDULING
271 /* Clear corresponding cache entry because type of the link
273 if (true_dependency_cache
!= NULL
)
275 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
276 bitmap_clear_bit (&anti_dependency_cache
[INSN_LUID (insn
)],
278 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
279 && output_dependency_cache
)
280 bitmap_clear_bit (&output_dependency_cache
[INSN_LUID (insn
)],
287 /* If this is a more restrictive type of dependence than the existing
288 one, then change the existing dependence to this type. */
289 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
290 PUT_REG_NOTE_KIND (link
, dep_type
);
292 #ifdef INSN_SCHEDULING
293 /* If we are adding a dependency to INSN's LOG_LINKs, then
294 note that in the bitmap caches of dependency information. */
295 if (true_dependency_cache
!= NULL
)
297 if ((int) REG_NOTE_KIND (link
) == 0)
298 bitmap_set_bit (&true_dependency_cache
[INSN_LUID (insn
)],
300 else if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
301 bitmap_set_bit (&anti_dependency_cache
[INSN_LUID (insn
)],
303 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
304 bitmap_set_bit (&output_dependency_cache
[INSN_LUID (insn
)],
310 /* Might want to check one level of transitivity to save conses. */
312 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
313 LOG_LINKS (insn
) = link
;
315 /* Insn dependency, not data dependency. */
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 note that
320 in the bitmap caches of dependency information. */
321 if (true_dependency_cache
!= NULL
)
323 if ((int) dep_type
== 0)
324 bitmap_set_bit (&true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
325 else if (dep_type
== REG_DEP_ANTI
)
326 bitmap_set_bit (&anti_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
327 else if (dep_type
== REG_DEP_OUTPUT
)
328 bitmap_set_bit (&output_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
334 /* A convenience wrapper to operate on an entire list. */
337 add_dependence_list (rtx insn
, rtx list
, enum reg_note dep_type
)
339 for (; list
; list
= XEXP (list
, 1))
340 add_dependence (insn
, XEXP (list
, 0), dep_type
);
343 /* Similar, but free *LISTP at the same time. */
346 add_dependence_list_and_free (rtx insn
, rtx
*listp
, enum reg_note dep_type
)
349 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
351 next
= XEXP (list
, 1);
352 add_dependence (insn
, XEXP (list
, 0), dep_type
);
353 free_INSN_LIST_node (list
);
357 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
358 goes along with that. */
361 set_sched_group_p (rtx insn
)
365 SCHED_GROUP_P (insn
) = 1;
367 prev
= prev_nonnote_insn (insn
);
368 add_dependence (insn
, prev
, REG_DEP_ANTI
);
371 /* Process an insn's memory dependencies. There are four kinds of
374 (0) read dependence: read follows read
375 (1) true dependence: read follows write
376 (2) anti dependence: write follows read
377 (3) output dependence: write follows write
379 We are careful to build only dependencies which actually exist, and
380 use transitivity to avoid building too many links. */
382 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
383 The MEM is a memory reference contained within INSN, which we are saving
384 so that we can do memory aliasing on it. */
387 add_insn_mem_dependence (struct deps
*deps
, rtx
*insn_list
, rtx
*mem_list
,
392 link
= alloc_INSN_LIST (insn
, *insn_list
);
395 if (current_sched_info
->use_cselib
)
397 mem
= shallow_copy_rtx (mem
);
398 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
400 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
403 deps
->pending_lists_length
++;
406 /* Make a dependency between every memory reference on the pending lists
407 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
408 dependencies for a read operation, similarly with FOR_WRITE. */
411 flush_pending_lists (struct deps
*deps
, rtx insn
, int for_read
,
416 add_dependence_list_and_free (insn
, &deps
->pending_read_insns
,
418 free_EXPR_LIST_list (&deps
->pending_read_mems
);
421 add_dependence_list_and_free (insn
, &deps
->pending_write_insns
,
422 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
423 free_EXPR_LIST_list (&deps
->pending_write_mems
);
424 deps
->pending_lists_length
= 0;
426 add_dependence_list_and_free (insn
, &deps
->last_pending_memory_flush
,
427 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
428 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
429 deps
->pending_flush_length
= 1;
432 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
433 rtx, X, creating all dependencies generated by the write to the
434 destination of X, and reads of everything mentioned. */
437 sched_analyze_1 (struct deps
*deps
, rtx x
, rtx insn
)
440 rtx dest
= XEXP (x
, 0);
441 enum rtx_code code
= GET_CODE (x
);
446 if (GET_CODE (dest
) == PARALLEL
)
450 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
451 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
452 sched_analyze_1 (deps
,
453 gen_rtx_CLOBBER (VOIDmode
,
454 XEXP (XVECEXP (dest
, 0, i
), 0)),
457 if (GET_CODE (x
) == SET
)
458 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
462 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
463 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
465 if (GET_CODE (dest
) == STRICT_LOW_PART
466 || GET_CODE (dest
) == ZERO_EXTRACT
467 || GET_CODE (dest
) == SIGN_EXTRACT
468 || read_modify_subreg_p (dest
))
470 /* These both read and modify the result. We must handle
471 them as writes to get proper dependencies for following
472 instructions. We must handle them as reads to get proper
473 dependencies from this to previous instructions.
474 Thus we need to call sched_analyze_2. */
476 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
478 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
480 /* The second and third arguments are values read by this insn. */
481 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
482 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
484 dest
= XEXP (dest
, 0);
487 if (GET_CODE (dest
) == REG
)
489 regno
= REGNO (dest
);
491 /* A hard reg in a wide mode may really be multiple registers.
492 If so, mark all of them just like the first. */
493 if (regno
< FIRST_PSEUDO_REGISTER
)
495 int i
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
499 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
504 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
507 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
508 it does not reload. Ignore these as they have served their
510 else if (regno
>= deps
->max_reg
)
512 if (GET_CODE (PATTERN (insn
)) != USE
513 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
519 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
521 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
523 /* Pseudos that are REG_EQUIV to something may be replaced
524 by that during reloading. We need only add dependencies for
525 the address in the REG_EQUIV note. */
526 if (!reload_completed
527 && reg_known_equiv_p
[regno
]
528 && GET_CODE (reg_known_value
[regno
]) == MEM
)
529 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
531 /* Don't let it cross a call after scheduling if it doesn't
532 already cross one. */
533 if (REG_N_CALLS_CROSSED (regno
) == 0)
534 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_ANTI
);
537 else if (GET_CODE (dest
) == MEM
)
539 /* Writing memory. */
542 if (current_sched_info
->use_cselib
)
544 t
= shallow_copy_rtx (dest
);
545 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
546 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
550 if (deps
->pending_lists_length
> MAX_PENDING_LIST_LENGTH
)
552 /* Flush all pending reads and writes to prevent the pending lists
553 from getting any larger. Insn scheduling runs too slowly when
554 these lists get long. When compiling GCC with itself,
555 this flush occurs 8 times for sparc, and 10 times for m88k using
556 the default value of 32. */
557 flush_pending_lists (deps
, insn
, false, true);
561 rtx pending
, pending_mem
;
563 pending
= deps
->pending_read_insns
;
564 pending_mem
= deps
->pending_read_mems
;
567 if (anti_dependence (XEXP (pending_mem
, 0), t
))
568 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
570 pending
= XEXP (pending
, 1);
571 pending_mem
= XEXP (pending_mem
, 1);
574 pending
= deps
->pending_write_insns
;
575 pending_mem
= deps
->pending_write_mems
;
578 if (output_dependence (XEXP (pending_mem
, 0), t
))
579 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
581 pending
= XEXP (pending
, 1);
582 pending_mem
= XEXP (pending_mem
, 1);
585 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
588 add_insn_mem_dependence (deps
, &deps
->pending_write_insns
,
589 &deps
->pending_write_mems
, insn
, dest
);
591 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
595 if (GET_CODE (x
) == SET
)
596 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
599 /* Analyze the uses of memory and registers in rtx X in INSN. */
602 sched_analyze_2 (struct deps
*deps
, rtx x
, rtx insn
)
622 /* Ignore constants. Note that we must handle CONST_DOUBLE here
623 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
624 this does not mean that this insn is using cc0. */
629 /* User of CC0 depends on immediately preceding insn. */
630 set_sched_group_p (insn
);
631 /* Don't move CC0 setter to another block (it can set up the
632 same flag for previous CC0 users which is safe). */
633 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
639 int regno
= REGNO (x
);
640 if (regno
< FIRST_PSEUDO_REGISTER
)
642 int i
= hard_regno_nregs
[regno
][GET_MODE (x
)];
644 SET_REGNO_REG_SET (reg_pending_uses
, regno
+ i
);
646 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
647 it does not reload. Ignore these as they have served their
649 else if (regno
>= deps
->max_reg
)
651 if (GET_CODE (PATTERN (insn
)) != USE
652 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
657 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
659 /* Pseudos that are REG_EQUIV to something may be replaced
660 by that during reloading. We need only add dependencies for
661 the address in the REG_EQUIV note. */
662 if (!reload_completed
663 && reg_known_equiv_p
[regno
]
664 && GET_CODE (reg_known_value
[regno
]) == MEM
)
665 sched_analyze_2 (deps
, XEXP (reg_known_value
[regno
], 0), insn
);
667 /* If the register does not already cross any calls, then add this
668 insn to the sched_before_next_call list so that it will still
669 not cross calls after scheduling. */
670 if (REG_N_CALLS_CROSSED (regno
) == 0)
671 deps
->sched_before_next_call
672 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
679 /* Reading memory. */
681 rtx pending
, pending_mem
;
684 if (current_sched_info
->use_cselib
)
686 t
= shallow_copy_rtx (t
);
687 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
688 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
691 pending
= deps
->pending_read_insns
;
692 pending_mem
= deps
->pending_read_mems
;
695 if (read_dependence (XEXP (pending_mem
, 0), t
))
696 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
698 pending
= XEXP (pending
, 1);
699 pending_mem
= XEXP (pending_mem
, 1);
702 pending
= deps
->pending_write_insns
;
703 pending_mem
= deps
->pending_write_mems
;
706 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
708 add_dependence (insn
, XEXP (pending
, 0), 0);
710 pending
= XEXP (pending
, 1);
711 pending_mem
= XEXP (pending_mem
, 1);
714 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
715 if (GET_CODE (XEXP (u
, 0)) != JUMP_INSN
716 || deps_may_trap_p (x
))
717 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
719 /* Always add these dependencies to pending_reads, since
720 this insn may be followed by a write. */
721 add_insn_mem_dependence (deps
, &deps
->pending_read_insns
,
722 &deps
->pending_read_mems
, insn
, x
);
724 /* Take advantage of tail recursion here. */
725 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
729 /* Force pending stores to memory in case a trap handler needs them. */
731 flush_pending_lists (deps
, insn
, true, false);
736 case UNSPEC_VOLATILE
:
738 /* Traditional and volatile asm instructions must be considered to use
739 and clobber all hard registers, all pseudo-registers and all of
740 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
742 Consider for instance a volatile asm that changes the fpu rounding
743 mode. An insn should not be moved across this even if it only uses
744 pseudo-regs because it might give an incorrectly rounded result. */
745 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
746 reg_pending_barrier
= TRUE_BARRIER
;
748 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
749 We can not just fall through here since then we would be confused
750 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
751 traditional asms unlike their normal usage. */
753 if (code
== ASM_OPERANDS
)
755 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
756 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
766 /* These both read and modify the result. We must handle them as writes
767 to get proper dependencies for following instructions. We must handle
768 them as reads to get proper dependencies from this to previous
769 instructions. Thus we need to pass them to both sched_analyze_1
770 and sched_analyze_2. We must call sched_analyze_2 first in order
771 to get the proper antecedent for the read. */
772 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
773 sched_analyze_1 (deps
, x
, insn
);
778 /* op0 = op0 + op1 */
779 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
780 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
781 sched_analyze_1 (deps
, x
, insn
);
788 /* Other cases: walk the insn. */
789 fmt
= GET_RTX_FORMAT (code
);
790 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
793 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
794 else if (fmt
[i
] == 'E')
795 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
796 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
800 /* Analyze an INSN with pattern X to find all dependencies. */
803 sched_analyze_insn (struct deps
*deps
, rtx x
, rtx insn
, rtx loop_notes
)
805 RTX_CODE code
= GET_CODE (x
);
809 if (code
== COND_EXEC
)
811 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
813 /* ??? Should be recording conditions so we reduce the number of
814 false dependencies. */
815 x
= COND_EXEC_CODE (x
);
818 if (code
== SET
|| code
== CLOBBER
)
820 sched_analyze_1 (deps
, x
, insn
);
822 /* Bare clobber insns are used for letting life analysis, reg-stack
823 and others know that a value is dead. Depend on the last call
824 instruction so that reg-stack won't get confused. */
826 add_dependence_list (insn
, deps
->last_function_call
, REG_DEP_OUTPUT
);
828 else if (code
== PARALLEL
)
831 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
833 rtx sub
= XVECEXP (x
, 0, i
);
834 code
= GET_CODE (sub
);
836 if (code
== COND_EXEC
)
838 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
839 sub
= COND_EXEC_CODE (sub
);
840 code
= GET_CODE (sub
);
842 if (code
== SET
|| code
== CLOBBER
)
843 sched_analyze_1 (deps
, sub
, insn
);
845 sched_analyze_2 (deps
, sub
, insn
);
849 sched_analyze_2 (deps
, x
, insn
);
851 /* Mark registers CLOBBERED or used by called function. */
852 if (GET_CODE (insn
) == CALL_INSN
)
854 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
856 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
857 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
859 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
861 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
862 reg_pending_barrier
= MOVE_BARRIER
;
865 if (GET_CODE (insn
) == JUMP_INSN
)
868 next
= next_nonnote_insn (insn
);
869 if (next
&& GET_CODE (next
) == BARRIER
)
870 reg_pending_barrier
= TRUE_BARRIER
;
873 rtx pending
, pending_mem
;
874 regset_head tmp_uses
, tmp_sets
;
875 INIT_REG_SET (&tmp_uses
);
876 INIT_REG_SET (&tmp_sets
);
878 (*current_sched_info
->compute_jump_reg_dependencies
)
879 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
880 /* Make latency of jump equal to 0 by using anti-dependence. */
881 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
,
883 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
884 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_ANTI
);
885 add_dependence_list (insn
, reg_last
->clobbers
, REG_DEP_ANTI
);
886 reg_last
->uses_length
++;
887 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
889 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
891 CLEAR_REG_SET (&tmp_uses
);
892 CLEAR_REG_SET (&tmp_sets
);
894 /* All memory writes and volatile reads must happen before the
895 jump. Non-volatile reads must happen before the jump iff
896 the result is needed by the above register used mask. */
898 pending
= deps
->pending_write_insns
;
899 pending_mem
= deps
->pending_write_mems
;
902 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
903 pending
= XEXP (pending
, 1);
904 pending_mem
= XEXP (pending_mem
, 1);
907 pending
= deps
->pending_read_insns
;
908 pending_mem
= deps
->pending_read_mems
;
911 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0)))
912 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
913 pending
= XEXP (pending
, 1);
914 pending_mem
= XEXP (pending_mem
, 1);
917 add_dependence_list (insn
, deps
->last_pending_memory_flush
,
922 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
923 block, then we must be sure that no instructions are scheduled across it.
924 Otherwise, the reg_n_refs info (which depends on loop_depth) would
930 /* Update loop_notes with any notes from this insn. Also determine
931 if any of the notes on the list correspond to instruction scheduling
932 barriers (loop, eh & setjmp notes, but not range notes). */
934 while (XEXP (link
, 1))
936 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
937 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
938 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
939 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
)
940 reg_pending_barrier
= MOVE_BARRIER
;
942 link
= XEXP (link
, 1);
944 XEXP (link
, 1) = REG_NOTES (insn
);
945 REG_NOTES (insn
) = loop_notes
;
948 /* If this instruction can throw an exception, then moving it changes
949 where block boundaries fall. This is mighty confusing elsewhere.
950 Therefore, prevent such an instruction from being moved. */
951 if (can_throw_internal (insn
))
952 reg_pending_barrier
= MOVE_BARRIER
;
954 /* Add dependencies if a scheduling barrier was found. */
955 if (reg_pending_barrier
)
957 /* In the case of barrier the most added dependencies are not
958 real, so we use anti-dependence here. */
959 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
961 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
963 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
964 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
966 (insn
, reg_last
->sets
,
967 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
969 (insn
, reg_last
->clobbers
,
970 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
975 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
977 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
978 add_dependence_list_and_free (insn
, ®_last
->uses
,
980 add_dependence_list_and_free
981 (insn
, ®_last
->sets
,
982 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
983 add_dependence_list_and_free
984 (insn
, ®_last
->clobbers
,
985 reg_pending_barrier
== TRUE_BARRIER
? 0 : REG_DEP_ANTI
);
986 reg_last
->uses_length
= 0;
987 reg_last
->clobbers_length
= 0;
991 for (i
= 0; i
< deps
->max_reg
; i
++)
993 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
994 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
995 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
998 flush_pending_lists (deps
, insn
, true, true);
999 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
1000 reg_pending_barrier
= NOT_A_BARRIER
;
1004 /* If the current insn is conditional, we can't free any
1006 if (GET_CODE (PATTERN (insn
)) == COND_EXEC
)
1008 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1010 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1011 add_dependence_list (insn
, reg_last
->sets
, 0);
1012 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1013 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1014 reg_last
->uses_length
++;
1016 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1018 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1019 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1020 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1021 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1022 reg_last
->clobbers_length
++;
1024 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1026 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1027 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1028 add_dependence_list (insn
, reg_last
->clobbers
, REG_DEP_OUTPUT
);
1029 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1030 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1031 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
1036 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
,
1038 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1039 add_dependence_list (insn
, reg_last
->sets
, 0);
1040 add_dependence_list (insn
, reg_last
->clobbers
, 0);
1041 reg_last
->uses_length
++;
1042 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
1044 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
1046 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1047 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
1048 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
1050 add_dependence_list_and_free (insn
, ®_last
->sets
,
1052 add_dependence_list_and_free (insn
, ®_last
->uses
,
1054 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1056 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1057 reg_last
->clobbers_length
= 0;
1058 reg_last
->uses_length
= 0;
1062 add_dependence_list (insn
, reg_last
->sets
, REG_DEP_OUTPUT
);
1063 add_dependence_list (insn
, reg_last
->uses
, REG_DEP_ANTI
);
1065 reg_last
->clobbers_length
++;
1066 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
1068 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
1070 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1071 add_dependence_list_and_free (insn
, ®_last
->sets
,
1073 add_dependence_list_and_free (insn
, ®_last
->clobbers
,
1075 add_dependence_list_and_free (insn
, ®_last
->uses
,
1077 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
1078 reg_last
->uses_length
= 0;
1079 reg_last
->clobbers_length
= 0;
1080 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
1084 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
1085 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
1086 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
1088 CLEAR_REG_SET (reg_pending_uses
);
1089 CLEAR_REG_SET (reg_pending_clobbers
);
1090 CLEAR_REG_SET (reg_pending_sets
);
1092 /* If we are currently in a libcall scheduling group, then mark the
1093 current insn as being in a scheduling group and that it can not
1094 be moved into a different basic block. */
1096 if (deps
->libcall_block_tail_insn
)
1098 set_sched_group_p (insn
);
1099 CANT_MOVE (insn
) = 1;
1102 /* If a post-call group is still open, see if it should remain so.
1103 This insn must be a simple move of a hard reg to a pseudo or
1106 We must avoid moving these insns for correctness on
1107 SMALL_REGISTER_CLASS machines, and for special registers like
1108 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1109 hard regs for all targets. */
1111 if (deps
->in_post_call_group_p
)
1113 rtx tmp
, set
= single_set (insn
);
1114 int src_regno
, dest_regno
;
1117 goto end_call_group
;
1119 tmp
= SET_DEST (set
);
1120 if (GET_CODE (tmp
) == SUBREG
)
1121 tmp
= SUBREG_REG (tmp
);
1122 if (GET_CODE (tmp
) == REG
)
1123 dest_regno
= REGNO (tmp
);
1125 goto end_call_group
;
1127 tmp
= SET_SRC (set
);
1128 if (GET_CODE (tmp
) == SUBREG
)
1129 tmp
= SUBREG_REG (tmp
);
1130 if (GET_CODE (tmp
) == REG
)
1131 src_regno
= REGNO (tmp
);
1133 goto end_call_group
;
1135 if (src_regno
< FIRST_PSEUDO_REGISTER
1136 || dest_regno
< FIRST_PSEUDO_REGISTER
)
1138 set_sched_group_p (insn
);
1139 CANT_MOVE (insn
) = 1;
1144 deps
->in_post_call_group_p
= false;
1149 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1150 for every dependency. */
1153 sched_analyze (struct deps
*deps
, rtx head
, rtx tail
)
1158 if (current_sched_info
->use_cselib
)
1161 for (insn
= head
;; insn
= NEXT_INSN (insn
))
1163 rtx link
, end_seq
, r0
, set
;
1165 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
1167 /* Clear out the stale LOG_LINKS from flow. */
1168 free_INSN_LIST_list (&LOG_LINKS (insn
));
1170 /* Make each JUMP_INSN a scheduling barrier for memory
1172 if (GET_CODE (insn
) == JUMP_INSN
)
1174 /* Keep the list a reasonable size. */
1175 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
1176 flush_pending_lists (deps
, insn
, true, true);
1178 deps
->last_pending_memory_flush
1179 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
1181 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1184 else if (GET_CODE (insn
) == CALL_INSN
)
1188 CANT_MOVE (insn
) = 1;
1190 /* Clear out the stale LOG_LINKS from flow. */
1191 free_INSN_LIST_list (&LOG_LINKS (insn
));
1193 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
1195 /* This is setjmp. Assume that all registers, not just
1196 hard registers, may be clobbered by this call. */
1197 reg_pending_barrier
= MOVE_BARRIER
;
1201 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1202 /* A call may read and modify global register variables. */
1205 SET_REGNO_REG_SET (reg_pending_sets
, i
);
1206 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1208 /* Other call-clobbered hard regs may be clobbered.
1209 Since we only have a choice between 'might be clobbered'
1210 and 'definitely not clobbered', we must include all
1211 partly call-clobbered registers here. */
1212 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
1213 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1214 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
1215 /* We don't know what set of fixed registers might be used
1216 by the function, but it is certain that the stack pointer
1217 is among them, but be conservative. */
1218 else if (fixed_regs
[i
])
1219 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1220 /* The frame pointer is normally not used by the function
1221 itself, but by the debugger. */
1222 /* ??? MIPS o32 is an exception. It uses the frame pointer
1223 in the macro expansion of jal but does not represent this
1224 fact in the call_insn rtl. */
1225 else if (i
== FRAME_POINTER_REGNUM
1226 || (i
== HARD_FRAME_POINTER_REGNUM
1227 && (! reload_completed
|| frame_pointer_needed
)))
1228 SET_REGNO_REG_SET (reg_pending_uses
, i
);
1231 /* For each insn which shouldn't cross a call, add a dependence
1232 between that insn and this call insn. */
1233 add_dependence_list_and_free (insn
, &deps
->sched_before_next_call
,
1236 sched_analyze_insn (deps
, PATTERN (insn
), insn
, loop_notes
);
1239 /* In the absence of interprocedural alias analysis, we must flush
1240 all pending reads and writes, and start new dependencies starting
1241 from here. But only flush writes for constant calls (which may
1242 be passed a pointer to something we haven't written yet). */
1243 flush_pending_lists (deps
, insn
, true, !CONST_OR_PURE_CALL_P (insn
));
1245 /* Remember the last function call for limiting lifetimes. */
1246 free_INSN_LIST_list (&deps
->last_function_call
);
1247 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
1249 /* Before reload, begin a post-call group, so as to keep the
1250 lifetimes of hard registers correct. */
1251 if (! reload_completed
)
1252 deps
->in_post_call_group_p
= true;
1255 /* See comments on reemit_notes as to why we do this.
1256 ??? Actually, the reemit_notes just say what is done, not why. */
1258 if (GET_CODE (insn
) == NOTE
1259 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
1260 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
1261 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1262 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
))
1266 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
1267 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
1268 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
1270 rtx_region
= const0_rtx
;
1272 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1275 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
1276 GEN_INT (NOTE_LINE_NUMBER (insn
)),
1278 CONST_OR_PURE_CALL_P (loop_notes
) = CONST_OR_PURE_CALL_P (insn
);
1281 if (current_sched_info
->use_cselib
)
1282 cselib_process_insn (insn
);
1284 /* Now that we have completed handling INSN, check and see if it is
1285 a CLOBBER beginning a libcall block. If it is, record the
1286 end of the libcall sequence.
1288 We want to schedule libcall blocks as a unit before reload. While
1289 this restricts scheduling, it preserves the meaning of a libcall
1292 As a side effect, we may get better code due to decreased register
1293 pressure as well as less chance of a foreign insn appearing in
1295 if (!reload_completed
1296 /* Note we may have nested libcall sequences. We only care about
1297 the outermost libcall sequence. */
1298 && deps
->libcall_block_tail_insn
== 0
1299 /* The sequence must start with a clobber of a register. */
1300 && GET_CODE (insn
) == INSN
1301 && GET_CODE (PATTERN (insn
)) == CLOBBER
1302 && (r0
= XEXP (PATTERN (insn
), 0), GET_CODE (r0
) == REG
)
1303 && GET_CODE (XEXP (PATTERN (insn
), 0)) == REG
1304 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1305 && (link
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)) != 0
1306 && (end_seq
= XEXP (link
, 0)) != 0
1307 /* The insn referenced by the REG_LIBCALL note must be a
1308 simple nop copy with the same destination as the register
1309 mentioned in the clobber. */
1310 && (set
= single_set (end_seq
)) != 0
1311 && SET_DEST (set
) == r0
&& SET_SRC (set
) == r0
1312 /* And finally the insn referenced by the REG_LIBCALL must
1313 also contain a REG_EQUAL note and a REG_RETVAL note. */
1314 && find_reg_note (end_seq
, REG_EQUAL
, NULL_RTX
) != 0
1315 && find_reg_note (end_seq
, REG_RETVAL
, NULL_RTX
) != 0)
1316 deps
->libcall_block_tail_insn
= XEXP (link
, 0);
1318 /* If we have reached the end of a libcall block, then close the
1320 if (deps
->libcall_block_tail_insn
== insn
)
1321 deps
->libcall_block_tail_insn
= 0;
1325 if (current_sched_info
->use_cselib
)
1334 /* The following function adds forward dependence (FROM, TO) with
1335 given DEP_TYPE. The forward dependence should be not exist before. */
1338 add_forward_dependence (rtx from
, rtx to
, enum reg_note dep_type
)
1342 #ifdef ENABLE_CHECKING
1343 /* If add_dependence is working properly there should never
1344 be notes, deleted insns or duplicates in the backward
1345 links. Thus we need not check for them here.
1347 However, if we have enabled checking we might as well go
1348 ahead and verify that add_dependence worked properly. */
1349 if (GET_CODE (from
) == NOTE
1350 || INSN_DELETED_P (from
)
1351 || (forward_dependency_cache
!= NULL
1352 && bitmap_bit_p (&forward_dependency_cache
[INSN_LUID (from
)],
1354 || (forward_dependency_cache
== NULL
1355 && find_insn_list (to
, INSN_DEPEND (from
))))
1357 if (forward_dependency_cache
!= NULL
)
1358 bitmap_bit_p (&forward_dependency_cache
[INSN_LUID (from
)],
1362 new_link
= alloc_INSN_LIST (to
, INSN_DEPEND (from
));
1364 PUT_REG_NOTE_KIND (new_link
, dep_type
);
1366 INSN_DEPEND (from
) = new_link
;
1367 INSN_DEP_COUNT (to
) += 1;
1370 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1371 dependences from LOG_LINKS to build forward dependences in
1375 compute_forward_dependences (rtx head
, rtx tail
)
1380 next_tail
= NEXT_INSN (tail
);
1381 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1383 if (! INSN_P (insn
))
1386 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
1387 add_forward_dependence (XEXP (link
, 0), insn
, REG_NOTE_KIND (link
));
1391 /* Initialize variables for region data dependence analysis.
1392 n_bbs is the number of region blocks. */
1395 init_deps (struct deps
*deps
)
1397 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
1399 deps
->max_reg
= max_reg
;
1400 deps
->reg_last
= xcalloc (max_reg
, sizeof (struct deps_reg
));
1401 INIT_REG_SET (&deps
->reg_last_in_use
);
1402 INIT_REG_SET (&deps
->reg_conditional_sets
);
1404 deps
->pending_read_insns
= 0;
1405 deps
->pending_read_mems
= 0;
1406 deps
->pending_write_insns
= 0;
1407 deps
->pending_write_mems
= 0;
1408 deps
->pending_lists_length
= 0;
1409 deps
->pending_flush_length
= 0;
1410 deps
->last_pending_memory_flush
= 0;
1411 deps
->last_function_call
= 0;
1412 deps
->sched_before_next_call
= 0;
1413 deps
->in_post_call_group_p
= false;
1414 deps
->libcall_block_tail_insn
= 0;
1417 /* Free insn lists found in DEPS. */
1420 free_deps (struct deps
*deps
)
1424 free_INSN_LIST_list (&deps
->pending_read_insns
);
1425 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1426 free_INSN_LIST_list (&deps
->pending_write_insns
);
1427 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1428 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1430 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1431 times. For a testcase with 42000 regs and 8000 small basic blocks,
1432 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1433 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
,
1435 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
1437 free_INSN_LIST_list (®_last
->uses
);
1439 free_INSN_LIST_list (®_last
->sets
);
1440 if (reg_last
->clobbers
)
1441 free_INSN_LIST_list (®_last
->clobbers
);
1443 CLEAR_REG_SET (&deps
->reg_last_in_use
);
1444 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
1446 free (deps
->reg_last
);
1449 /* If it is profitable to use them, initialize caches for tracking
1450 dependency information. LUID is the number of insns to be scheduled,
1451 it is used in the estimate of profitability. */
1454 init_dependency_caches (int luid
)
1456 /* ?!? We could save some memory by computing a per-region luid mapping
1457 which could reduce both the number of vectors in the cache and the size
1458 of each vector. Instead we just avoid the cache entirely unless the
1459 average number of instructions in a basic block is very high. See
1460 the comment before the declaration of true_dependency_cache for
1461 what we consider "very high". */
1462 if (luid
/ n_basic_blocks
> 100 * 5)
1465 true_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1466 anti_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1467 output_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1468 #ifdef ENABLE_CHECKING
1469 forward_dependency_cache
= xmalloc (luid
* sizeof (bitmap_head
));
1471 for (i
= 0; i
< luid
; i
++)
1473 bitmap_initialize (&true_dependency_cache
[i
], 0);
1474 bitmap_initialize (&anti_dependency_cache
[i
], 0);
1475 bitmap_initialize (&output_dependency_cache
[i
], 0);
1476 #ifdef ENABLE_CHECKING
1477 bitmap_initialize (&forward_dependency_cache
[i
], 0);
1484 /* Free the caches allocated in init_dependency_caches. */
1487 free_dependency_caches (void)
1489 if (true_dependency_cache
)
1493 for (i
= 0; i
< cache_size
; i
++)
1495 bitmap_clear (&true_dependency_cache
[i
]);
1496 bitmap_clear (&anti_dependency_cache
[i
]);
1497 bitmap_clear (&output_dependency_cache
[i
]);
1498 #ifdef ENABLE_CHECKING
1499 bitmap_clear (&forward_dependency_cache
[i
]);
1502 free (true_dependency_cache
);
1503 true_dependency_cache
= NULL
;
1504 free (anti_dependency_cache
);
1505 anti_dependency_cache
= NULL
;
1506 free (output_dependency_cache
);
1507 output_dependency_cache
= NULL
;
1508 #ifdef ENABLE_CHECKING
1509 free (forward_dependency_cache
);
1510 forward_dependency_cache
= NULL
;
1515 /* Initialize some global variables needed by the dependency analysis
1519 init_deps_global (void)
1521 reg_pending_sets
= INITIALIZE_REG_SET (reg_pending_sets_head
);
1522 reg_pending_clobbers
= INITIALIZE_REG_SET (reg_pending_clobbers_head
);
1523 reg_pending_uses
= INITIALIZE_REG_SET (reg_pending_uses_head
);
1524 reg_pending_barrier
= NOT_A_BARRIER
;
1527 /* Free everything used by the dependency analysis code. */
1530 finish_deps_global (void)
1532 FREE_REG_SET (reg_pending_sets
);
1533 FREE_REG_SET (reg_pending_clobbers
);
1534 FREE_REG_SET (reg_pending_uses
);