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, 2005, 2006
5 Free Software Foundation, Inc.
6 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
7 and currently maintained by, Jim Wilson (wilson@cygnus.com)
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 2, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
28 #include "coretypes.h"
33 #include "hard-reg-set.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
42 #include "sched-int.h"
48 static regset reg_pending_sets;
49 static regset reg_pending_clobbers;
50 static regset reg_pending_uses;
52 /* The following enumeration values tell us what dependencies we
53 should use to implement the barrier. We use true-dependencies for
54 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
55 enum reg_pending_barrier_mode
62 static enum reg_pending_barrier_mode reg_pending_barrier;
64 /* To speed up the test for duplicate dependency links we keep a
65 record of dependencies created by add_dependence when the average
66 number of instructions in a basic block is very large.
68 Studies have shown that there is typically around 5 instructions between
69 branches for typical C code. So we can make a guess that the average
70 basic block is approximately 5 instructions long; we will choose 100X
71 the average size as a very large basic block.
73 Each insn has associated bitmaps for its dependencies. Each bitmap
74 has enough entries to represent a dependency on any other insn in
75 the insn chain. All bitmap for true dependencies cache is
76 allocated then the rest two ones are also allocated. */
77 static bitmap_head *true_dependency_cache;
78 static bitmap_head *output_dependency_cache;
79 static bitmap_head *anti_dependency_cache;
80 static bitmap_head *spec_dependency_cache;
81 static int cache_size;
83 /* To speed up checking consistency of formed forward insn
84 dependencies we use the following cache. Another possible solution
85 could be switching off checking duplication of insns in forward
87 #ifdef ENABLE_CHECKING
88 static bitmap_head *forward_dependency_cache;
91 static int deps_may_trap_p (rtx);
92 static void add_dependence_list (rtx, rtx, int, enum reg_note);
93 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
94 static void delete_all_dependences (rtx);
95 static void fixup_sched_groups (rtx);
97 static void flush_pending_lists (struct deps *, rtx, int, int);
98 static void sched_analyze_1 (struct deps *, rtx, rtx);
99 static void sched_analyze_2 (struct deps *, rtx, rtx);
100 static void sched_analyze_insn (struct deps *, rtx, rtx);
102 static rtx sched_get_condition (rtx);
103 static int conditions_mutex_p (rtx, rtx);
105 static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
106 enum reg_note, ds_t, rtx, rtx, rtx **);
107 static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
108 enum reg_note, ds_t, rtx, rtx, rtx **);
109 static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
111 static void adjust_add_sorted_back_dep (rtx, rtx, rtx *);
112 static void adjust_back_add_forw_dep (rtx, rtx *);
113 static void delete_forw_dep (rtx, rtx);
114 static dw_t estimate_dep_weak (rtx, rtx);
115 static dw_t get_dep_weak (ds_t, ds_t);
116 static ds_t ds_merge (ds_t, ds_t);
117 #ifdef INSN_SCHEDULING
118 #ifdef ENABLE_CHECKING
119 static void check_dep_status (enum reg_note, ds_t, bool);
123 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
126 deps_may_trap_p (rtx mem)
128 rtx addr = XEXP (mem, 0);
130 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
132 rtx t = get_reg_known_value (REGNO (addr));
136 return rtx_addr_can_trap_p (addr);
139 /* Return the INSN_LIST containing INSN in LIST, or NULL
140 if LIST does not contain INSN. */
143 find_insn_list (rtx insn, rtx list)
147 if (XEXP (list, 0) == insn)
149 list = XEXP (list, 1);
154 /* Find the condition under which INSN is executed. */
157 sched_get_condition (rtx insn)
159 rtx pat = PATTERN (insn);
165 if (GET_CODE (pat) == COND_EXEC)
166 return COND_EXEC_TEST (pat);
168 if (!any_condjump_p (insn) || !onlyjump_p (insn))
171 src = SET_SRC (pc_set (insn));
173 if (XEXP (src, 2) == pc_rtx)
174 return XEXP (src, 0);
175 else if (XEXP (src, 1) == pc_rtx)
177 rtx cond = XEXP (src, 0);
178 enum rtx_code revcode = reversed_comparison_code (cond, insn);
180 if (revcode == UNKNOWN)
182 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
190 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
193 conditions_mutex_p (rtx cond1, rtx cond2)
195 if (COMPARISON_P (cond1)
196 && COMPARISON_P (cond2)
197 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
198 && XEXP (cond1, 0) == XEXP (cond2, 0)
199 && XEXP (cond1, 1) == XEXP (cond2, 1))
204 /* Return true if insn1 and insn2 can never depend on one another because
205 the conditions under which they are executed are mutually exclusive. */
207 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
211 /* flow.c doesn't handle conditional lifetimes entirely correctly;
212 calls mess up the conditional lifetimes. */
213 if (!CALL_P (insn1) && !CALL_P (insn2))
215 cond1 = sched_get_condition (insn1);
216 cond2 = sched_get_condition (insn2);
218 && conditions_mutex_p (cond1, cond2)
219 /* Make sure first instruction doesn't affect condition of second
220 instruction if switched. */
221 && !modified_in_p (cond1, insn2)
222 /* Make sure second instruction doesn't affect condition of first
223 instruction if switched. */
224 && !modified_in_p (cond2, insn1))
230 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
231 LOG_LINKS of INSN, if it is not already there. DEP_TYPE indicates the
232 type of dependence that this link represents. DS, if non-zero,
233 indicates speculations, through which this dependence can be overcome.
234 MEM1 and MEM2, if non-null, corresponds to memory locations in case of
235 data speculation. The function returns a value indicating if an old entry
236 has been changed or a new entry has been added to insn's LOG_LINK.
237 In case of changed entry CHANGED_LINKPP sets to its address.
238 See also the definition of enum DEPS_ADJUST_RESULT in sched-int.h.
239 Actual manipulation of dependence data structures is performed in
240 add_or_update_back_dep_1. */
242 static enum DEPS_ADJUST_RESULT
243 maybe_add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
244 ds_t ds, rtx mem1, rtx mem2,
245 rtx **changed_linkpp)
247 gcc_assert (INSN_P (insn) && INSN_P (elem));
249 /* Don't depend an insn on itself. */
252 #ifdef INSN_SCHEDULING
253 if (current_sched_info->flags & DO_SPECULATION)
254 /* INSN has an internal dependence, which we can't overcome. */
255 HAS_INTERNAL_DEP (insn) = 1;
260 return add_or_update_back_dep_1 (insn, elem, dep_type,
261 ds, mem1, mem2, changed_linkpp);
264 /* This function has the same meaning of parameters and return values
265 as maybe_add_or_update_back_dep_1. The only difference between these
266 two functions is that INSN and ELEM are guaranteed not to be the same
268 static enum DEPS_ADJUST_RESULT
269 add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
270 ds_t ds ATTRIBUTE_UNUSED,
271 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED,
272 rtx **changed_linkpp ATTRIBUTE_UNUSED)
274 bool maybe_present_p = true, present_p = false;
276 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
278 #ifdef INSN_SCHEDULING
280 #ifdef ENABLE_CHECKING
281 check_dep_status (dep_type, ds, mem1 != NULL);
284 /* If we already have a dependency for ELEM, then we do not need to
285 do anything. Avoiding the list walk below can cut compile times
286 dramatically for some code. */
287 if (true_dependency_cache != NULL)
289 enum reg_note present_dep_type;
291 gcc_assert (output_dependency_cache);
292 gcc_assert (anti_dependency_cache);
293 if (!(current_sched_info->flags & USE_DEPS_LIST))
295 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
297 present_dep_type = REG_DEP_TRUE;
298 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
300 present_dep_type = REG_DEP_OUTPUT;
301 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
303 present_dep_type = REG_DEP_ANTI;
305 maybe_present_p = false;
309 if ((int) dep_type >= (int) present_dep_type)
317 ds_t present_dep_types = 0;
319 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
321 present_dep_types |= DEP_TRUE;
322 if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
324 present_dep_types |= DEP_OUTPUT;
325 if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
327 present_dep_types |= DEP_ANTI;
329 if (present_dep_types)
331 if (!(current_sched_info->flags & DO_SPECULATION)
332 || !bitmap_bit_p (&spec_dependency_cache[INSN_LUID (insn)],
335 if ((present_dep_types | (ds & DEP_TYPES))
336 == present_dep_types)
337 /* We already have all these bits. */
342 /* Only true dependencies can be data speculative and
343 only anti dependencies can be control speculative. */
344 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
345 == present_dep_types);
347 /* if (additional dep is SPECULATIVE) then
348 we should update DEP_STATUS
350 we should reset existing dep to non-speculative. */
356 maybe_present_p = false;
361 /* Check that we don't already have this dependence. */
366 for (linkp = &LOG_LINKS (insn); *linkp; linkp = &XEXP (*linkp, 1))
370 gcc_assert (true_dependency_cache == 0 || present_p);
372 if (XEXP (link, 0) == elem)
374 enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
376 #ifdef INSN_SCHEDULING
377 if (current_sched_info->flags & USE_DEPS_LIST)
379 ds_t new_status = ds | DEP_STATUS (link);
381 if (new_status & SPECULATIVE)
383 if (!(ds & SPECULATIVE)
384 || !(DEP_STATUS (link) & SPECULATIVE))
385 /* Then this dep can't be speculative. */
387 new_status &= ~SPECULATIVE;
388 if (true_dependency_cache
389 && (DEP_STATUS (link) & SPECULATIVE))
390 bitmap_clear_bit (&spec_dependency_cache
396 /* Both are speculative. Merging probabilities. */
401 dw = estimate_dep_weak (mem1, mem2);
402 ds = set_dep_weak (ds, BEGIN_DATA, dw);
405 new_status = ds_merge (DEP_STATUS (link), ds);
412 /* Clear corresponding cache entry because type of the link
413 may have changed. Keep them if we use_deps_list. */
414 if (true_dependency_cache != NULL
415 && !(current_sched_info->flags & USE_DEPS_LIST))
417 enum reg_note kind = REG_NOTE_KIND (link);
422 bitmap_clear_bit (&output_dependency_cache
423 [INSN_LUID (insn)], INSN_LUID (elem));
426 bitmap_clear_bit (&anti_dependency_cache
427 [INSN_LUID (insn)], INSN_LUID (elem));
434 if ((current_sched_info->flags & USE_DEPS_LIST)
435 && DEP_STATUS (link) != ds)
437 DEP_STATUS (link) = ds;
438 changed_p = DEP_CHANGED;
442 /* If this is a more restrictive type of dependence than the
443 existing one, then change the existing dependence to this
445 if ((int) dep_type < (int) REG_NOTE_KIND (link))
447 PUT_REG_NOTE_KIND (link, dep_type);
448 changed_p = DEP_CHANGED;
451 #ifdef INSN_SCHEDULING
452 /* If we are adding a dependency to INSN's LOG_LINKs, then
453 note that in the bitmap caches of dependency information. */
454 if (true_dependency_cache != NULL)
456 if (!(current_sched_info->flags & USE_DEPS_LIST))
458 if (REG_NOTE_KIND (link) == REG_DEP_TRUE)
459 bitmap_set_bit (&true_dependency_cache
460 [INSN_LUID (insn)], INSN_LUID (elem));
461 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
462 bitmap_set_bit (&output_dependency_cache
463 [INSN_LUID (insn)], INSN_LUID (elem));
464 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
465 bitmap_set_bit (&anti_dependency_cache
466 [INSN_LUID (insn)], INSN_LUID (elem));
471 bitmap_set_bit (&true_dependency_cache
472 [INSN_LUID (insn)], INSN_LUID (elem));
474 bitmap_set_bit (&output_dependency_cache
475 [INSN_LUID (insn)], INSN_LUID (elem));
477 bitmap_set_bit (&anti_dependency_cache
478 [INSN_LUID (insn)], INSN_LUID (elem));
479 /* Note, that dep can become speculative only
480 at the moment of creation. Thus, we don't need to
481 check for it here. */
485 if (changed_linkpp && changed_p == DEP_CHANGED)
486 *changed_linkpp = linkp;
491 /* We didn't find a dep. It shouldn't be present in the cache. */
492 gcc_assert (!present_p);
495 /* Might want to check one level of transitivity to save conses.
496 This check should be done in maybe_add_or_update_back_dep_1.
497 Since we made it to add_or_update_back_dep_1, we must create
498 (or update) a link. */
502 gcc_assert (current_sched_info->flags & DO_SPECULATION);
503 ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
506 add_back_dep (insn, elem, dep_type, ds);
511 /* This function creates a link between INSN and ELEM under any
512 conditions. DS describes speculative status of the link. */
514 add_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
516 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
518 if (current_sched_info->flags & USE_DEPS_LIST)
519 LOG_LINKS (insn) = alloc_DEPS_LIST (elem, LOG_LINKS (insn), ds);
521 LOG_LINKS (insn) = alloc_INSN_LIST (elem, LOG_LINKS (insn));
523 /* Insn dependency, not data dependency. */
524 PUT_REG_NOTE_KIND (LOG_LINKS (insn), dep_type);
526 #ifdef INSN_SCHEDULING
527 #ifdef ENABLE_CHECKING
528 check_dep_status (dep_type, ds, false);
531 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
532 in the bitmap caches of dependency information. */
533 if (true_dependency_cache != NULL)
535 if (!(current_sched_info->flags & USE_DEPS_LIST))
537 if (dep_type == REG_DEP_TRUE)
538 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
540 else if (dep_type == REG_DEP_OUTPUT)
541 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
543 else if (dep_type == REG_DEP_ANTI)
544 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
550 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
553 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
556 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
558 if (ds & SPECULATIVE)
560 gcc_assert (current_sched_info->flags & DO_SPECULATION);
561 bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
569 /* A convenience wrapper to operate on an entire list. */
572 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
574 for (; list; list = XEXP (list, 1))
576 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
577 add_dependence (insn, XEXP (list, 0), dep_type);
581 /* Similar, but free *LISTP at the same time. */
584 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
585 enum reg_note dep_type)
588 for (list = *listp, *listp = NULL; list ; list = next)
590 next = XEXP (list, 1);
591 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
592 add_dependence (insn, XEXP (list, 0), dep_type);
593 free_INSN_LIST_node (list);
597 /* Clear all dependencies for an insn. */
600 delete_all_dependences (rtx insn)
602 /* Clear caches, if they exist, as well as free the dependence. */
604 #ifdef INSN_SCHEDULING
605 if (true_dependency_cache != NULL)
607 bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
608 bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
609 bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
610 /* We don't have to clear forward_dependency_cache here,
611 because it is formed later. */
612 if (current_sched_info->flags & DO_SPECULATION)
613 bitmap_clear (&spec_dependency_cache[INSN_LUID (insn)]);
617 if (!(current_sched_info->flags & USE_DEPS_LIST))
618 /* In this case LOG_LINKS are formed from the DEPS_LISTs,
619 not the INSN_LISTs. */
620 free_INSN_LIST_list (&LOG_LINKS (insn));
622 free_DEPS_LIST_list (&LOG_LINKS (insn));
625 /* All insns in a scheduling group except the first should only have
626 dependencies on the previous insn in the group. So we find the
627 first instruction in the scheduling group by walking the dependence
628 chains backwards. Then we add the dependencies for the group to
629 the previous nonnote insn. */
632 fixup_sched_groups (rtx insn)
634 rtx link, prev_nonnote;
636 for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
641 i = prev_nonnote_insn (i);
643 if (XEXP (link, 0) == i)
645 } while (SCHED_GROUP_P (i));
646 if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
647 add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
651 delete_all_dependences (insn);
653 prev_nonnote = prev_nonnote_insn (insn);
654 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
655 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
656 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
659 /* Process an insn's memory dependencies. There are four kinds of
662 (0) read dependence: read follows read
663 (1) true dependence: read follows write
664 (2) output dependence: write follows write
665 (3) anti dependence: write follows read
667 We are careful to build only dependencies which actually exist, and
668 use transitivity to avoid building too many links. */
670 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
671 The MEM is a memory reference contained within INSN, which we are saving
672 so that we can do memory aliasing on it. */
675 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
680 link = alloc_INSN_LIST (insn, *insn_list);
683 if (current_sched_info->use_cselib)
685 mem = shallow_copy_rtx (mem);
686 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
688 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
691 deps->pending_lists_length++;
694 /* Make a dependency between every memory reference on the pending lists
695 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
696 dependencies for a read operation, similarly with FOR_WRITE. */
699 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
704 add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
706 free_EXPR_LIST_list (&deps->pending_read_mems);
709 add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
710 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
711 free_EXPR_LIST_list (&deps->pending_write_mems);
712 deps->pending_lists_length = 0;
714 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
715 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
716 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
717 deps->pending_flush_length = 1;
720 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
721 rtx, X, creating all dependencies generated by the write to the
722 destination of X, and reads of everything mentioned. */
725 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
728 rtx dest = XEXP (x, 0);
729 enum rtx_code code = GET_CODE (x);
734 if (GET_CODE (dest) == PARALLEL)
738 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
739 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
740 sched_analyze_1 (deps,
741 gen_rtx_CLOBBER (VOIDmode,
742 XEXP (XVECEXP (dest, 0, i), 0)),
745 if (GET_CODE (x) == SET)
746 sched_analyze_2 (deps, SET_SRC (x), insn);
750 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
751 || GET_CODE (dest) == ZERO_EXTRACT)
753 if (GET_CODE (dest) == STRICT_LOW_PART
754 || GET_CODE (dest) == ZERO_EXTRACT
755 || df_read_modify_subreg_p (dest))
757 /* These both read and modify the result. We must handle
758 them as writes to get proper dependencies for following
759 instructions. We must handle them as reads to get proper
760 dependencies from this to previous instructions.
761 Thus we need to call sched_analyze_2. */
763 sched_analyze_2 (deps, XEXP (dest, 0), insn);
765 if (GET_CODE (dest) == ZERO_EXTRACT)
767 /* The second and third arguments are values read by this insn. */
768 sched_analyze_2 (deps, XEXP (dest, 1), insn);
769 sched_analyze_2 (deps, XEXP (dest, 2), insn);
771 dest = XEXP (dest, 0);
776 regno = REGNO (dest);
779 /* Treat all writes to a stack register as modifying the TOS. */
780 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
782 SET_REGNO_REG_SET (reg_pending_uses, FIRST_STACK_REG);
783 regno = FIRST_STACK_REG;
787 /* A hard reg in a wide mode may really be multiple registers.
788 If so, mark all of them just like the first. */
789 if (regno < FIRST_PSEUDO_REGISTER)
791 int i = hard_regno_nregs[regno][GET_MODE (dest)];
795 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
800 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
803 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
804 it does not reload. Ignore these as they have served their
806 else if (regno >= deps->max_reg)
808 gcc_assert (GET_CODE (PATTERN (insn)) == USE
809 || GET_CODE (PATTERN (insn)) == CLOBBER);
814 SET_REGNO_REG_SET (reg_pending_sets, regno);
816 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
818 /* Pseudos that are REG_EQUIV to something may be replaced
819 by that during reloading. We need only add dependencies for
820 the address in the REG_EQUIV note. */
821 if (!reload_completed && get_reg_known_equiv_p (regno))
823 rtx t = get_reg_known_value (regno);
825 sched_analyze_2 (deps, XEXP (t, 0), insn);
828 /* Don't let it cross a call after scheduling if it doesn't
829 already cross one. */
830 if (REG_N_CALLS_CROSSED (regno) == 0)
831 add_dependence_list (insn, deps->last_function_call, 1,
835 else if (MEM_P (dest))
837 /* Writing memory. */
840 if (current_sched_info->use_cselib)
842 t = shallow_copy_rtx (dest);
843 cselib_lookup (XEXP (t, 0), Pmode, 1);
844 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
848 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
850 /* Flush all pending reads and writes to prevent the pending lists
851 from getting any larger. Insn scheduling runs too slowly when
852 these lists get long. When compiling GCC with itself,
853 this flush occurs 8 times for sparc, and 10 times for m88k using
854 the default value of 32. */
855 flush_pending_lists (deps, insn, false, true);
859 rtx pending, pending_mem;
861 pending = deps->pending_read_insns;
862 pending_mem = deps->pending_read_mems;
865 if (anti_dependence (XEXP (pending_mem, 0), t)
866 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
867 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
869 pending = XEXP (pending, 1);
870 pending_mem = XEXP (pending_mem, 1);
873 pending = deps->pending_write_insns;
874 pending_mem = deps->pending_write_mems;
877 if (output_dependence (XEXP (pending_mem, 0), t)
878 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
879 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
881 pending = XEXP (pending, 1);
882 pending_mem = XEXP (pending_mem, 1);
885 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
888 add_insn_mem_dependence (deps, &deps->pending_write_insns,
889 &deps->pending_write_mems, insn, dest);
891 sched_analyze_2 (deps, XEXP (dest, 0), insn);
895 if (GET_CODE (x) == SET)
896 sched_analyze_2 (deps, SET_SRC (x), insn);
899 /* Analyze the uses of memory and registers in rtx X in INSN. */
902 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
922 /* Ignore constants. Note that we must handle CONST_DOUBLE here
923 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
924 this does not mean that this insn is using cc0. */
929 /* User of CC0 depends on immediately preceding insn. */
930 SCHED_GROUP_P (insn) = 1;
931 /* Don't move CC0 setter to another block (it can set up the
932 same flag for previous CC0 users which is safe). */
933 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
939 int regno = REGNO (x);
942 /* Treat all reads of a stack register as modifying the TOS. */
943 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
945 SET_REGNO_REG_SET (reg_pending_sets, FIRST_STACK_REG);
946 regno = FIRST_STACK_REG;
950 if (regno < FIRST_PSEUDO_REGISTER)
952 int i = hard_regno_nregs[regno][GET_MODE (x)];
954 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
956 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
957 it does not reload. Ignore these as they have served their
959 else if (regno >= deps->max_reg)
961 gcc_assert (GET_CODE (PATTERN (insn)) == USE
962 || GET_CODE (PATTERN (insn)) == CLOBBER);
966 SET_REGNO_REG_SET (reg_pending_uses, regno);
968 /* Pseudos that are REG_EQUIV to something may be replaced
969 by that during reloading. We need only add dependencies for
970 the address in the REG_EQUIV note. */
971 if (!reload_completed && get_reg_known_equiv_p (regno))
973 rtx t = get_reg_known_value (regno);
975 sched_analyze_2 (deps, XEXP (t, 0), insn);
978 /* If the register does not already cross any calls, then add this
979 insn to the sched_before_next_call list so that it will still
980 not cross calls after scheduling. */
981 if (REG_N_CALLS_CROSSED (regno) == 0)
982 deps->sched_before_next_call
983 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
990 /* Reading memory. */
992 rtx pending, pending_mem;
995 if (current_sched_info->use_cselib)
997 t = shallow_copy_rtx (t);
998 cselib_lookup (XEXP (t, 0), Pmode, 1);
999 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
1002 pending = deps->pending_read_insns;
1003 pending_mem = deps->pending_read_mems;
1006 if (read_dependence (XEXP (pending_mem, 0), t)
1007 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1008 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1010 pending = XEXP (pending, 1);
1011 pending_mem = XEXP (pending_mem, 1);
1014 pending = deps->pending_write_insns;
1015 pending_mem = deps->pending_write_mems;
1018 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1020 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1022 if (current_sched_info->flags & DO_SPECULATION)
1023 maybe_add_or_update_back_dep_1 (insn, XEXP (pending, 0),
1025 BEGIN_DATA | DEP_TRUE,
1026 XEXP (pending_mem, 0), t, 0);
1028 add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
1031 pending = XEXP (pending, 1);
1032 pending_mem = XEXP (pending_mem, 1);
1035 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
1036 if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
1037 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1039 /* Always add these dependencies to pending_reads, since
1040 this insn may be followed by a write. */
1041 add_insn_mem_dependence (deps, &deps->pending_read_insns,
1042 &deps->pending_read_mems, insn, x);
1044 /* Take advantage of tail recursion here. */
1045 sched_analyze_2 (deps, XEXP (x, 0), insn);
1049 /* Force pending stores to memory in case a trap handler needs them. */
1051 flush_pending_lists (deps, insn, true, false);
1056 case UNSPEC_VOLATILE:
1058 /* Traditional and volatile asm instructions must be considered to use
1059 and clobber all hard registers, all pseudo-registers and all of
1060 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1062 Consider for instance a volatile asm that changes the fpu rounding
1063 mode. An insn should not be moved across this even if it only uses
1064 pseudo-regs because it might give an incorrectly rounded result. */
1065 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1066 reg_pending_barrier = TRUE_BARRIER;
1068 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1069 We can not just fall through here since then we would be confused
1070 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1071 traditional asms unlike their normal usage. */
1073 if (code == ASM_OPERANDS)
1075 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1076 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
1086 /* These both read and modify the result. We must handle them as writes
1087 to get proper dependencies for following instructions. We must handle
1088 them as reads to get proper dependencies from this to previous
1089 instructions. Thus we need to pass them to both sched_analyze_1
1090 and sched_analyze_2. We must call sched_analyze_2 first in order
1091 to get the proper antecedent for the read. */
1092 sched_analyze_2 (deps, XEXP (x, 0), insn);
1093 sched_analyze_1 (deps, x, insn);
1098 /* op0 = op0 + op1 */
1099 sched_analyze_2 (deps, XEXP (x, 0), insn);
1100 sched_analyze_2 (deps, XEXP (x, 1), insn);
1101 sched_analyze_1 (deps, x, insn);
1108 /* Other cases: walk the insn. */
1109 fmt = GET_RTX_FORMAT (code);
1110 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1113 sched_analyze_2 (deps, XEXP (x, i), insn);
1114 else if (fmt[i] == 'E')
1115 for (j = 0; j < XVECLEN (x, i); j++)
1116 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
1120 /* Analyze an INSN with pattern X to find all dependencies. */
1123 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
1125 RTX_CODE code = GET_CODE (x);
1128 reg_set_iterator rsi;
1130 if (code == COND_EXEC)
1132 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
1134 /* ??? Should be recording conditions so we reduce the number of
1135 false dependencies. */
1136 x = COND_EXEC_CODE (x);
1137 code = GET_CODE (x);
1139 if (code == SET || code == CLOBBER)
1141 sched_analyze_1 (deps, x, insn);
1143 /* Bare clobber insns are used for letting life analysis, reg-stack
1144 and others know that a value is dead. Depend on the last call
1145 instruction so that reg-stack won't get confused. */
1146 if (code == CLOBBER)
1147 add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
1149 else if (code == PARALLEL)
1151 for (i = XVECLEN (x, 0); i--;)
1153 rtx sub = XVECEXP (x, 0, i);
1154 code = GET_CODE (sub);
1156 if (code == COND_EXEC)
1158 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
1159 sub = COND_EXEC_CODE (sub);
1160 code = GET_CODE (sub);
1162 if (code == SET || code == CLOBBER)
1163 sched_analyze_1 (deps, sub, insn);
1165 sched_analyze_2 (deps, sub, insn);
1169 sched_analyze_2 (deps, x, insn);
1171 /* Mark registers CLOBBERED or used by called function. */
1174 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1176 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1177 sched_analyze_1 (deps, XEXP (link, 0), insn);
1179 sched_analyze_2 (deps, XEXP (link, 0), insn);
1181 if (find_reg_note (insn, REG_SETJMP, NULL))
1182 reg_pending_barrier = MOVE_BARRIER;
1188 next = next_nonnote_insn (insn);
1189 if (next && BARRIER_P (next))
1190 reg_pending_barrier = TRUE_BARRIER;
1193 rtx pending, pending_mem;
1194 regset_head tmp_uses, tmp_sets;
1195 INIT_REG_SET (&tmp_uses);
1196 INIT_REG_SET (&tmp_sets);
1198 (*current_sched_info->compute_jump_reg_dependencies)
1199 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
1200 /* Make latency of jump equal to 0 by using anti-dependence. */
1201 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
1203 struct deps_reg *reg_last = &deps->reg_last[i];
1204 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
1205 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
1206 reg_last->uses_length++;
1207 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1209 IOR_REG_SET (reg_pending_sets, &tmp_sets);
1211 CLEAR_REG_SET (&tmp_uses);
1212 CLEAR_REG_SET (&tmp_sets);
1214 /* All memory writes and volatile reads must happen before the
1215 jump. Non-volatile reads must happen before the jump iff
1216 the result is needed by the above register used mask. */
1218 pending = deps->pending_write_insns;
1219 pending_mem = deps->pending_write_mems;
1222 if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1223 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1224 pending = XEXP (pending, 1);
1225 pending_mem = XEXP (pending_mem, 1);
1228 pending = deps->pending_read_insns;
1229 pending_mem = deps->pending_read_mems;
1232 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
1233 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1234 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1235 pending = XEXP (pending, 1);
1236 pending_mem = XEXP (pending_mem, 1);
1239 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1244 /* If this instruction can throw an exception, then moving it changes
1245 where block boundaries fall. This is mighty confusing elsewhere.
1246 Therefore, prevent such an instruction from being moved. */
1247 if (can_throw_internal (insn))
1248 reg_pending_barrier = MOVE_BARRIER;
1250 /* Add dependencies if a scheduling barrier was found. */
1251 if (reg_pending_barrier)
1253 /* In the case of barrier the most added dependencies are not
1254 real, so we use anti-dependence here. */
1255 if (sched_get_condition (insn))
1257 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1259 struct deps_reg *reg_last = &deps->reg_last[i];
1260 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1262 (insn, reg_last->sets, 0,
1263 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1265 (insn, reg_last->clobbers, 0,
1266 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1271 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1273 struct deps_reg *reg_last = &deps->reg_last[i];
1274 add_dependence_list_and_free (insn, ®_last->uses, 0,
1276 add_dependence_list_and_free
1277 (insn, ®_last->sets, 0,
1278 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1279 add_dependence_list_and_free
1280 (insn, ®_last->clobbers, 0,
1281 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1282 reg_last->uses_length = 0;
1283 reg_last->clobbers_length = 0;
1287 for (i = 0; i < (unsigned)deps->max_reg; i++)
1289 struct deps_reg *reg_last = &deps->reg_last[i];
1290 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1291 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1294 flush_pending_lists (deps, insn, true, true);
1295 CLEAR_REG_SET (&deps->reg_conditional_sets);
1296 reg_pending_barrier = NOT_A_BARRIER;
1300 /* If the current insn is conditional, we can't free any
1302 if (sched_get_condition (insn))
1304 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1306 struct deps_reg *reg_last = &deps->reg_last[i];
1307 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1308 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1309 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1310 reg_last->uses_length++;
1312 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1314 struct deps_reg *reg_last = &deps->reg_last[i];
1315 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1316 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1317 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1318 reg_last->clobbers_length++;
1320 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1322 struct deps_reg *reg_last = &deps->reg_last[i];
1323 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1324 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
1325 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1326 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1327 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1332 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1334 struct deps_reg *reg_last = &deps->reg_last[i];
1335 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1336 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1337 reg_last->uses_length++;
1338 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1340 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1342 struct deps_reg *reg_last = &deps->reg_last[i];
1343 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1344 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1346 add_dependence_list_and_free (insn, ®_last->sets, 0,
1348 add_dependence_list_and_free (insn, ®_last->uses, 0,
1350 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
1352 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1353 reg_last->clobbers_length = 0;
1354 reg_last->uses_length = 0;
1358 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1359 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1361 reg_last->clobbers_length++;
1362 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1364 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1366 struct deps_reg *reg_last = &deps->reg_last[i];
1367 add_dependence_list_and_free (insn, ®_last->sets, 0,
1369 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
1371 add_dependence_list_and_free (insn, ®_last->uses, 0,
1373 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1374 reg_last->uses_length = 0;
1375 reg_last->clobbers_length = 0;
1376 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1380 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1381 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1382 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1384 CLEAR_REG_SET (reg_pending_uses);
1385 CLEAR_REG_SET (reg_pending_clobbers);
1386 CLEAR_REG_SET (reg_pending_sets);
1388 /* If we are currently in a libcall scheduling group, then mark the
1389 current insn as being in a scheduling group and that it can not
1390 be moved into a different basic block. */
1392 if (deps->libcall_block_tail_insn)
1394 SCHED_GROUP_P (insn) = 1;
1395 CANT_MOVE (insn) = 1;
1398 /* If a post-call group is still open, see if it should remain so.
1399 This insn must be a simple move of a hard reg to a pseudo or
1402 We must avoid moving these insns for correctness on
1403 SMALL_REGISTER_CLASS machines, and for special registers like
1404 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1405 hard regs for all targets. */
1407 if (deps->in_post_call_group_p)
1409 rtx tmp, set = single_set (insn);
1410 int src_regno, dest_regno;
1413 goto end_call_group;
1415 tmp = SET_DEST (set);
1416 if (GET_CODE (tmp) == SUBREG)
1417 tmp = SUBREG_REG (tmp);
1419 dest_regno = REGNO (tmp);
1421 goto end_call_group;
1423 tmp = SET_SRC (set);
1424 if (GET_CODE (tmp) == SUBREG)
1425 tmp = SUBREG_REG (tmp);
1426 if ((GET_CODE (tmp) == PLUS
1427 || GET_CODE (tmp) == MINUS)
1428 && REG_P (XEXP (tmp, 0))
1429 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1430 && dest_regno == STACK_POINTER_REGNUM)
1431 src_regno = STACK_POINTER_REGNUM;
1432 else if (REG_P (tmp))
1433 src_regno = REGNO (tmp);
1435 goto end_call_group;
1437 if (src_regno < FIRST_PSEUDO_REGISTER
1438 || dest_regno < FIRST_PSEUDO_REGISTER)
1440 if (deps->in_post_call_group_p == post_call_initial)
1441 deps->in_post_call_group_p = post_call;
1443 SCHED_GROUP_P (insn) = 1;
1444 CANT_MOVE (insn) = 1;
1449 deps->in_post_call_group_p = not_post_call;
1453 /* Fixup the dependencies in the sched group. */
1454 if (SCHED_GROUP_P (insn))
1455 fixup_sched_groups (insn);
1458 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1459 for every dependency. */
1462 sched_analyze (struct deps *deps, rtx head, rtx tail)
1466 if (current_sched_info->use_cselib)
1469 /* Before reload, if the previous block ended in a call, show that
1470 we are inside a post-call group, so as to keep the lifetimes of
1471 hard registers correct. */
1472 if (! reload_completed && !LABEL_P (head))
1474 insn = prev_nonnote_insn (head);
1475 if (insn && CALL_P (insn))
1476 deps->in_post_call_group_p = post_call_initial;
1478 for (insn = head;; insn = NEXT_INSN (insn))
1480 rtx link, end_seq, r0, set;
1482 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1484 /* Clear out the stale LOG_LINKS from flow. */
1485 free_INSN_LIST_list (&LOG_LINKS (insn));
1487 /* Make each JUMP_INSN a scheduling barrier for memory
1491 /* Keep the list a reasonable size. */
1492 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1493 flush_pending_lists (deps, insn, true, true);
1495 deps->last_pending_memory_flush
1496 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1498 sched_analyze_insn (deps, PATTERN (insn), insn);
1500 else if (CALL_P (insn))
1504 CANT_MOVE (insn) = 1;
1506 /* Clear out the stale LOG_LINKS from flow. */
1507 free_INSN_LIST_list (&LOG_LINKS (insn));
1509 if (find_reg_note (insn, REG_SETJMP, NULL))
1511 /* This is setjmp. Assume that all registers, not just
1512 hard registers, may be clobbered by this call. */
1513 reg_pending_barrier = MOVE_BARRIER;
1517 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1518 /* A call may read and modify global register variables. */
1521 SET_REGNO_REG_SET (reg_pending_sets, i);
1522 SET_REGNO_REG_SET (reg_pending_uses, i);
1524 /* Other call-clobbered hard regs may be clobbered.
1525 Since we only have a choice between 'might be clobbered'
1526 and 'definitely not clobbered', we must include all
1527 partly call-clobbered registers here. */
1528 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1529 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1530 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1531 /* We don't know what set of fixed registers might be used
1532 by the function, but it is certain that the stack pointer
1533 is among them, but be conservative. */
1534 else if (fixed_regs[i])
1535 SET_REGNO_REG_SET (reg_pending_uses, i);
1536 /* The frame pointer is normally not used by the function
1537 itself, but by the debugger. */
1538 /* ??? MIPS o32 is an exception. It uses the frame pointer
1539 in the macro expansion of jal but does not represent this
1540 fact in the call_insn rtl. */
1541 else if (i == FRAME_POINTER_REGNUM
1542 || (i == HARD_FRAME_POINTER_REGNUM
1543 && (! reload_completed || frame_pointer_needed)))
1544 SET_REGNO_REG_SET (reg_pending_uses, i);
1547 /* For each insn which shouldn't cross a call, add a dependence
1548 between that insn and this call insn. */
1549 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
1552 sched_analyze_insn (deps, PATTERN (insn), insn);
1554 /* In the absence of interprocedural alias analysis, we must flush
1555 all pending reads and writes, and start new dependencies starting
1556 from here. But only flush writes for constant calls (which may
1557 be passed a pointer to something we haven't written yet). */
1558 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1560 /* Remember the last function call for limiting lifetimes. */
1561 free_INSN_LIST_list (&deps->last_function_call);
1562 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1564 /* Before reload, begin a post-call group, so as to keep the
1565 lifetimes of hard registers correct. */
1566 if (! reload_completed)
1567 deps->in_post_call_group_p = post_call;
1570 /* EH_REGION insn notes can not appear until well after we complete
1573 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1574 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1576 if (current_sched_info->use_cselib)
1577 cselib_process_insn (insn);
1579 /* Now that we have completed handling INSN, check and see if it is
1580 a CLOBBER beginning a libcall block. If it is, record the
1581 end of the libcall sequence.
1583 We want to schedule libcall blocks as a unit before reload. While
1584 this restricts scheduling, it preserves the meaning of a libcall
1587 As a side effect, we may get better code due to decreased register
1588 pressure as well as less chance of a foreign insn appearing in
1590 if (!reload_completed
1591 /* Note we may have nested libcall sequences. We only care about
1592 the outermost libcall sequence. */
1593 && deps->libcall_block_tail_insn == 0
1594 /* The sequence must start with a clobber of a register. */
1595 && NONJUMP_INSN_P (insn)
1596 && GET_CODE (PATTERN (insn)) == CLOBBER
1597 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1598 && REG_P (XEXP (PATTERN (insn), 0))
1599 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1600 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1601 && (end_seq = XEXP (link, 0)) != 0
1602 /* The insn referenced by the REG_LIBCALL note must be a
1603 simple nop copy with the same destination as the register
1604 mentioned in the clobber. */
1605 && (set = single_set (end_seq)) != 0
1606 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1607 /* And finally the insn referenced by the REG_LIBCALL must
1608 also contain a REG_EQUAL note and a REG_RETVAL note. */
1609 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1610 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1611 deps->libcall_block_tail_insn = XEXP (link, 0);
1613 /* If we have reached the end of a libcall block, then close the
1615 if (deps->libcall_block_tail_insn == insn)
1616 deps->libcall_block_tail_insn = 0;
1620 if (current_sched_info->use_cselib)
1629 /* The following function adds forward dependence (FROM, TO) with
1630 given DEP_TYPE. The forward dependence should be not exist before. */
1633 add_forw_dep (rtx to, rtx link)
1637 from = XEXP (link, 0);
1639 #ifdef ENABLE_CHECKING
1640 /* If add_dependence is working properly there should never
1641 be notes, deleted insns or duplicates in the backward
1642 links. Thus we need not check for them here.
1644 However, if we have enabled checking we might as well go
1645 ahead and verify that add_dependence worked properly. */
1646 gcc_assert (INSN_P (from));
1647 gcc_assert (!INSN_DELETED_P (from));
1648 if (true_dependency_cache)
1650 gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1652 bitmap_set_bit (&forward_dependency_cache[INSN_LUID (from)],
1656 gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1659 if (!(current_sched_info->flags & USE_DEPS_LIST))
1660 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1662 new_link = alloc_DEPS_LIST (to, INSN_DEPEND (from), DEP_STATUS (link));
1664 PUT_REG_NOTE_KIND (new_link, REG_NOTE_KIND (link));
1666 INSN_DEPEND (from) = new_link;
1667 INSN_DEP_COUNT (to) += 1;
1670 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1671 dependences from LOG_LINKS to build forward dependences in
1675 compute_forward_dependences (rtx head, rtx tail)
1680 next_tail = NEXT_INSN (tail);
1681 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1685 if (! INSN_P (insn))
1688 if (current_sched_info->flags & DO_SPECULATION)
1690 rtx new = 0, link, next;
1692 for (link = LOG_LINKS (insn); link; link = next)
1694 next = XEXP (link, 1);
1695 adjust_add_sorted_back_dep (insn, link, &new);
1698 LOG_LINKS (insn) = new;
1701 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1702 add_forw_dep (insn, link);
1706 /* Initialize variables for region data dependence analysis.
1707 n_bbs is the number of region blocks. */
1710 init_deps (struct deps *deps)
1712 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1714 deps->max_reg = max_reg;
1715 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
1716 INIT_REG_SET (&deps->reg_last_in_use);
1717 INIT_REG_SET (&deps->reg_conditional_sets);
1719 deps->pending_read_insns = 0;
1720 deps->pending_read_mems = 0;
1721 deps->pending_write_insns = 0;
1722 deps->pending_write_mems = 0;
1723 deps->pending_lists_length = 0;
1724 deps->pending_flush_length = 0;
1725 deps->last_pending_memory_flush = 0;
1726 deps->last_function_call = 0;
1727 deps->sched_before_next_call = 0;
1728 deps->in_post_call_group_p = not_post_call;
1729 deps->libcall_block_tail_insn = 0;
1732 /* Free insn lists found in DEPS. */
1735 free_deps (struct deps *deps)
1738 reg_set_iterator rsi;
1740 free_INSN_LIST_list (&deps->pending_read_insns);
1741 free_EXPR_LIST_list (&deps->pending_read_mems);
1742 free_INSN_LIST_list (&deps->pending_write_insns);
1743 free_EXPR_LIST_list (&deps->pending_write_mems);
1744 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1746 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1747 times. For a testcase with 42000 regs and 8000 small basic blocks,
1748 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1749 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1751 struct deps_reg *reg_last = &deps->reg_last[i];
1753 free_INSN_LIST_list (®_last->uses);
1755 free_INSN_LIST_list (®_last->sets);
1756 if (reg_last->clobbers)
1757 free_INSN_LIST_list (®_last->clobbers);
1759 CLEAR_REG_SET (&deps->reg_last_in_use);
1760 CLEAR_REG_SET (&deps->reg_conditional_sets);
1762 free (deps->reg_last);
1765 /* If it is profitable to use them, initialize caches for tracking
1766 dependency information. LUID is the number of insns to be scheduled,
1767 it is used in the estimate of profitability. */
1770 init_dependency_caches (int luid)
1772 /* ?!? We could save some memory by computing a per-region luid mapping
1773 which could reduce both the number of vectors in the cache and the size
1774 of each vector. Instead we just avoid the cache entirely unless the
1775 average number of instructions in a basic block is very high. See
1776 the comment before the declaration of true_dependency_cache for
1777 what we consider "very high". */
1778 if (luid / n_basic_blocks > 100 * 5)
1782 true_dependency_cache = XNEWVEC (bitmap_head, luid);
1783 anti_dependency_cache = XNEWVEC (bitmap_head, luid);
1784 output_dependency_cache = XNEWVEC (bitmap_head, luid);
1785 #ifdef ENABLE_CHECKING
1786 forward_dependency_cache = XNEWVEC (bitmap_head, luid);
1788 if (current_sched_info->flags & DO_SPECULATION)
1789 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
1792 for (i = 0; i < luid; i++)
1794 bitmap_initialize (&true_dependency_cache[i], 0);
1795 bitmap_initialize (&output_dependency_cache[i], 0);
1796 bitmap_initialize (&anti_dependency_cache[i], 0);
1797 #ifdef ENABLE_CHECKING
1798 bitmap_initialize (&forward_dependency_cache[i], 0);
1800 if (current_sched_info->flags & DO_SPECULATION)
1801 bitmap_initialize (&spec_dependency_cache[i], 0);
1807 /* Free the caches allocated in init_dependency_caches. */
1810 free_dependency_caches (void)
1812 if (true_dependency_cache)
1816 for (i = 0; i < cache_size; i++)
1818 bitmap_clear (&true_dependency_cache[i]);
1819 bitmap_clear (&output_dependency_cache[i]);
1820 bitmap_clear (&anti_dependency_cache[i]);
1821 #ifdef ENABLE_CHECKING
1822 bitmap_clear (&forward_dependency_cache[i]);
1824 if (current_sched_info->flags & DO_SPECULATION)
1825 bitmap_clear (&spec_dependency_cache[i]);
1827 free (true_dependency_cache);
1828 true_dependency_cache = NULL;
1829 free (output_dependency_cache);
1830 output_dependency_cache = NULL;
1831 free (anti_dependency_cache);
1832 anti_dependency_cache = NULL;
1833 #ifdef ENABLE_CHECKING
1834 free (forward_dependency_cache);
1835 forward_dependency_cache = NULL;
1837 if (current_sched_info->flags & DO_SPECULATION)
1839 free (spec_dependency_cache);
1840 spec_dependency_cache = NULL;
1845 /* Initialize some global variables needed by the dependency analysis
1849 init_deps_global (void)
1851 reg_pending_sets = ALLOC_REG_SET (®_obstack);
1852 reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
1853 reg_pending_uses = ALLOC_REG_SET (®_obstack);
1854 reg_pending_barrier = NOT_A_BARRIER;
1857 /* Free everything used by the dependency analysis code. */
1860 finish_deps_global (void)
1862 FREE_REG_SET (reg_pending_sets);
1863 FREE_REG_SET (reg_pending_clobbers);
1864 FREE_REG_SET (reg_pending_uses);
1867 /* Insert LINK into the dependence chain pointed to by LINKP and
1868 maintain the sort order. */
1870 adjust_add_sorted_back_dep (rtx insn, rtx link, rtx *linkp)
1872 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1874 /* If the insn cannot move speculatively, but the link is speculative,
1875 make it hard dependence. */
1876 if (HAS_INTERNAL_DEP (insn)
1877 && (DEP_STATUS (link) & SPECULATIVE))
1879 DEP_STATUS (link) &= ~SPECULATIVE;
1881 if (true_dependency_cache)
1882 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1883 INSN_LUID (XEXP (link, 0)));
1886 /* Non-speculative links go at the head of LOG_LINKS, followed by
1887 speculative links. */
1888 if (DEP_STATUS (link) & SPECULATIVE)
1889 while (*linkp && !(DEP_STATUS (*linkp) & SPECULATIVE))
1890 linkp = &XEXP (*linkp, 1);
1892 XEXP (link, 1) = *linkp;
1896 /* Move the dependence pointed to by LINKP to the back dependencies
1897 of INSN, and also add this dependence to the forward ones. All LOG_LINKS,
1898 except one pointed to by LINKP, must be sorted. */
1900 adjust_back_add_forw_dep (rtx insn, rtx *linkp)
1904 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1907 *linkp = XEXP (*linkp, 1);
1909 adjust_add_sorted_back_dep (insn, link, &LOG_LINKS (insn));
1910 add_forw_dep (insn, link);
1913 /* Remove forward dependence ELEM from the DEPS_LIST of INSN. */
1915 delete_forw_dep (rtx insn, rtx elem)
1917 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1919 #ifdef ENABLE_CHECKING
1920 if (true_dependency_cache)
1921 bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (elem)],
1925 remove_free_DEPS_LIST_elem (insn, &INSN_DEPEND (elem));
1926 INSN_DEP_COUNT (insn)--;
1929 /* Estimate the weakness of dependence between MEM1 and MEM2. */
1931 estimate_dep_weak (rtx mem1, rtx mem2)
1936 /* MEMs are the same - don't speculate. */
1937 return MIN_DEP_WEAK;
1939 r1 = XEXP (mem1, 0);
1940 r2 = XEXP (mem2, 0);
1943 || (REG_P (r1) && REG_P (r2)
1944 && REGNO (r1) == REGNO (r2)))
1945 /* Again, MEMs are the same. */
1946 return MIN_DEP_WEAK;
1947 else if ((REG_P (r1) && !REG_P (r2))
1948 || (!REG_P (r1) && REG_P (r2)))
1949 /* Different addressing modes - reason to be more speculative,
1951 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
1953 /* We can't say anything about the dependence. */
1954 return UNCERTAIN_DEP_WEAK;
1957 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
1958 This function can handle same INSN and ELEM (INSN == ELEM).
1959 It is a convenience wrapper. */
1961 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
1965 if (dep_type == REG_DEP_TRUE)
1967 else if (dep_type == REG_DEP_OUTPUT)
1969 else if (dep_type == REG_DEP_ANTI)
1974 maybe_add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1977 /* Add or update backward dependence between INSN and ELEM
1978 with given type DEP_TYPE and dep_status DS.
1979 This function is a convenience wrapper. */
1980 enum DEPS_ADJUST_RESULT
1981 add_or_update_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
1983 return add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1986 /* Add or update both backward and forward dependencies between INSN and ELEM
1987 with given type DEP_TYPE and dep_status DS. */
1989 add_or_update_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type,
1992 enum DEPS_ADJUST_RESULT res;
1995 res = add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, &linkp);
1997 if (res == DEP_CHANGED || res == DEP_CREATED)
1999 if (res == DEP_CHANGED)
2000 delete_forw_dep (insn, elem);
2001 else if (res == DEP_CREATED)
2002 linkp = &LOG_LINKS (insn);
2004 adjust_back_add_forw_dep (insn, linkp);
2008 /* Add both backward and forward dependencies between INSN and ELEM
2009 with given type DEP_TYPE and dep_status DS. */
2011 add_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
2013 add_back_dep (insn, elem, dep_type, ds);
2014 adjust_back_add_forw_dep (insn, &LOG_LINKS (insn));
2017 /* Remove both backward and forward dependencies between INSN and ELEM. */
2019 delete_back_forw_dep (rtx insn, rtx elem)
2021 gcc_assert (current_sched_info->flags & DO_SPECULATION);
2023 if (true_dependency_cache != NULL)
2025 bitmap_clear_bit (&true_dependency_cache[INSN_LUID (insn)],
2027 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
2029 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
2031 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
2035 remove_free_DEPS_LIST_elem (elem, &LOG_LINKS (insn));
2036 delete_forw_dep (insn, elem);
2039 /* Return weakness of speculative type TYPE in the dep_status DS. */
2041 get_dep_weak (ds_t ds, ds_t type)
2046 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2047 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2048 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2049 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2050 default: gcc_unreachable ();
2053 gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
2057 /* Return the dep_status, which has the same parameters as DS, except for
2058 speculative type TYPE, that will have weakness DW. */
2060 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2062 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2067 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2068 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2069 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2070 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2071 default: gcc_unreachable ();
2076 /* Return the join of two dep_statuses DS1 and DS2. */
2078 ds_merge (ds_t ds1, ds_t ds2)
2082 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2084 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2086 t = FIRST_SPEC_TYPE;
2089 if ((ds1 & t) && !(ds2 & t))
2091 else if (!(ds1 & t) && (ds2 & t))
2093 else if ((ds1 & t) && (ds2 & t))
2097 dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2099 if (dw < MIN_DEP_WEAK)
2102 ds = set_dep_weak (ds, t, (dw_t) dw);
2105 if (t == LAST_SPEC_TYPE)
2107 t <<= SPEC_TYPE_SHIFT;
2114 #ifdef INSN_SCHEDULING
2115 #ifdef ENABLE_CHECKING
2116 /* Verify that dependence type and status are consistent.
2117 If RELAXED_P is true, then skip dep_weakness checks. */
2119 check_dep_status (enum reg_note dt, ds_t ds, bool relaxed_p)
2121 /* Check that dependence type contains the same bits as the status. */
2122 if (dt == REG_DEP_TRUE)
2123 gcc_assert (ds & DEP_TRUE);
2124 else if (dt == REG_DEP_OUTPUT)
2125 gcc_assert ((ds & DEP_OUTPUT)
2126 && !(ds & DEP_TRUE));
2128 gcc_assert ((dt == REG_DEP_ANTI)
2130 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2132 /* HARD_DEP can not appear in dep_status of a link. */
2133 gcc_assert (!(ds & HARD_DEP));
2135 /* Check that dependence status is set correctly when speculation is not
2137 if (!(current_sched_info->flags & DO_SPECULATION))
2138 gcc_assert (!(ds & SPECULATIVE));
2139 else if (ds & SPECULATIVE)
2143 ds_t type = FIRST_SPEC_TYPE;
2145 /* Check that dependence weakness is in proper range. */
2149 get_dep_weak (ds, type);
2151 if (type == LAST_SPEC_TYPE)
2153 type <<= SPEC_TYPE_SHIFT;
2158 if (ds & BEGIN_SPEC)
2160 /* Only true dependence can be data speculative. */
2161 if (ds & BEGIN_DATA)
2162 gcc_assert (ds & DEP_TRUE);
2164 /* Control dependencies in the insn scheduler are represented by
2165 anti-dependencies, therefore only anti dependence can be
2166 control speculative. */
2167 if (ds & BEGIN_CONTROL)
2168 gcc_assert (ds & DEP_ANTI);
2172 /* Subsequent speculations should resolve true dependencies. */
2173 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2176 /* Check that true and anti depencies can't have other speculative
2179 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2180 /* An output dependence can't be speculative at all. */
2181 gcc_assert (!(ds & DEP_OUTPUT));
2183 gcc_assert (ds & BEGIN_CONTROL);