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, 2007, 2008, 2009, 2010,
6 Free Software Foundation, Inc.
7 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
8 and currently maintained by, Jim Wilson (wilson@cygnus.com)
10 This file is part of GCC.
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 3, or (at your option) any later
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING3. If not see
24 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
30 #include "diagnostic-core.h"
32 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
34 #include "hard-reg-set.h"
38 #include "insn-config.h"
39 #include "insn-attr.h"
42 #include "sched-int.h"
48 #ifdef INSN_SCHEDULING
50 #ifdef ENABLE_CHECKING
56 /* Holds current parameters for the dependency analyzer. */
57 struct sched_deps_info_def
*sched_deps_info
;
59 /* The data is specific to the Haifa scheduler. */
60 VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
= NULL
;
62 /* Return the major type present in the DS. */
70 return REG_DEP_OUTPUT
;
73 return REG_DEP_CONTROL
;
75 gcc_assert (ds
& DEP_ANTI
);
80 /* Return equivalent dep_status. */
82 dk_to_ds (enum reg_note dk
)
96 gcc_assert (dk
== REG_DEP_ANTI
);
101 /* Functions to operate with dependence information container - dep_t. */
103 /* Init DEP with the arguments. */
105 init_dep_1 (dep_t dep
, rtx pro
, rtx con
, enum reg_note type
, ds_t ds
)
109 DEP_TYPE (dep
) = type
;
110 DEP_STATUS (dep
) = ds
;
111 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
114 /* Init DEP with the arguments.
115 While most of the scheduler (including targets) only need the major type
116 of the dependency, it is convenient to hide full dep_status from them. */
118 init_dep (dep_t dep
, rtx pro
, rtx con
, enum reg_note kind
)
122 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
123 ds
= dk_to_ds (kind
);
127 init_dep_1 (dep
, pro
, con
, kind
, ds
);
130 /* Make a copy of FROM in TO. */
132 copy_dep (dep_t to
, dep_t from
)
134 memcpy (to
, from
, sizeof (*to
));
137 static void dump_ds (FILE *, ds_t
);
139 /* Define flags for dump_dep (). */
141 /* Dump producer of the dependence. */
142 #define DUMP_DEP_PRO (2)
144 /* Dump consumer of the dependence. */
145 #define DUMP_DEP_CON (4)
147 /* Dump type of the dependence. */
148 #define DUMP_DEP_TYPE (8)
150 /* Dump status of the dependence. */
151 #define DUMP_DEP_STATUS (16)
153 /* Dump all information about the dependence. */
154 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
158 FLAGS is a bit mask specifying what information about DEP needs
160 If FLAGS has the very first bit set, then dump all information about DEP
161 and propagate this bit into the callee dump functions. */
163 dump_dep (FILE *dump
, dep_t dep
, int flags
)
166 flags
|= DUMP_DEP_ALL
;
170 if (flags
& DUMP_DEP_PRO
)
171 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
173 if (flags
& DUMP_DEP_CON
)
174 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
176 if (flags
& DUMP_DEP_TYPE
)
179 enum reg_note type
= DEP_TYPE (dep
);
191 case REG_DEP_CONTROL
:
204 fprintf (dump
, "%c; ", t
);
207 if (flags
& DUMP_DEP_STATUS
)
209 if (current_sched_info
->flags
& USE_DEPS_LIST
)
210 dump_ds (dump
, DEP_STATUS (dep
));
216 /* Default flags for dump_dep (). */
217 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
219 /* Dump all fields of DEP to STDERR. */
221 sd_debug_dep (dep_t dep
)
223 dump_dep (stderr
, dep
, 1);
224 fprintf (stderr
, "\n");
227 /* Determine whether DEP is a dependency link of a non-debug insn on a
231 depl_on_debug_p (dep_link_t dep
)
233 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
234 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
237 /* Functions to operate with a single link from the dependencies lists -
240 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
243 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
245 dep_link_t next
= *prev_nextp
;
247 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
248 && DEP_LINK_NEXT (l
) == NULL
);
250 /* Init node being inserted. */
251 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
252 DEP_LINK_NEXT (l
) = next
;
257 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
259 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
266 /* Add dep_link LINK to deps_list L. */
268 add_to_deps_list (dep_link_t link
, deps_list_t l
)
270 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
272 /* Don't count debug deps. */
273 if (!depl_on_debug_p (link
))
274 ++DEPS_LIST_N_LINKS (l
);
277 /* Detach dep_link L from the list. */
279 detach_dep_link (dep_link_t l
)
281 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
282 dep_link_t next
= DEP_LINK_NEXT (l
);
287 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
289 DEP_LINK_PREV_NEXTP (l
) = NULL
;
290 DEP_LINK_NEXT (l
) = NULL
;
293 /* Remove link LINK from list LIST. */
295 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
297 detach_dep_link (link
);
299 /* Don't count debug deps. */
300 if (!depl_on_debug_p (link
))
301 --DEPS_LIST_N_LINKS (list
);
304 /* Move link LINK from list FROM to list TO. */
306 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
308 remove_from_deps_list (link
, from
);
309 add_to_deps_list (link
, to
);
312 /* Return true of LINK is not attached to any list. */
314 dep_link_is_detached_p (dep_link_t link
)
316 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
319 /* Pool to hold all dependency nodes (dep_node_t). */
320 static alloc_pool dn_pool
;
322 /* Number of dep_nodes out there. */
323 static int dn_pool_diff
= 0;
325 /* Create a dep_node. */
327 create_dep_node (void)
329 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
330 dep_link_t back
= DEP_NODE_BACK (n
);
331 dep_link_t forw
= DEP_NODE_FORW (n
);
333 DEP_LINK_NODE (back
) = n
;
334 DEP_LINK_NEXT (back
) = NULL
;
335 DEP_LINK_PREV_NEXTP (back
) = NULL
;
337 DEP_LINK_NODE (forw
) = n
;
338 DEP_LINK_NEXT (forw
) = NULL
;
339 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
346 /* Delete dep_node N. N must not be connected to any deps_list. */
348 delete_dep_node (dep_node_t n
)
350 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
351 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
355 pool_free (dn_pool
, n
);
358 /* Pool to hold dependencies lists (deps_list_t). */
359 static alloc_pool dl_pool
;
361 /* Number of deps_lists out there. */
362 static int dl_pool_diff
= 0;
364 /* Functions to operate with dependences lists - deps_list_t. */
366 /* Return true if list L is empty. */
368 deps_list_empty_p (deps_list_t l
)
370 return DEPS_LIST_N_LINKS (l
) == 0;
373 /* Create a new deps_list. */
375 create_deps_list (void)
377 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
379 DEPS_LIST_FIRST (l
) = NULL
;
380 DEPS_LIST_N_LINKS (l
) = 0;
386 /* Free deps_list L. */
388 free_deps_list (deps_list_t l
)
390 gcc_assert (deps_list_empty_p (l
));
394 pool_free (dl_pool
, l
);
397 /* Return true if there is no dep_nodes and deps_lists out there.
398 After the region is scheduled all the dependency nodes and lists
399 should [generally] be returned to pool. */
401 deps_pools_are_empty_p (void)
403 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
406 /* Remove all elements from L. */
408 clear_deps_list (deps_list_t l
)
412 dep_link_t link
= DEPS_LIST_FIRST (l
);
417 remove_from_deps_list (link
, l
);
422 /* Decide whether a dependency should be treated as a hard or a speculative
425 dep_spec_p (dep_t dep
)
427 if (current_sched_info
->flags
& DO_SPECULATION
)
429 if (DEP_STATUS (dep
) & SPECULATIVE
)
432 if (current_sched_info
->flags
& DO_PREDICATION
)
434 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
440 static regset reg_pending_sets
;
441 static regset reg_pending_clobbers
;
442 static regset reg_pending_uses
;
443 static regset reg_pending_control_uses
;
444 static enum reg_pending_barrier_mode reg_pending_barrier
;
446 /* Hard registers implicitly clobbered or used (or may be implicitly
447 clobbered or used) by the currently analyzed insn. For example,
448 insn in its constraint has one register class. Even if there is
449 currently no hard register in the insn, the particular hard
450 register will be in the insn after reload pass because the
451 constraint requires it. */
452 static HARD_REG_SET implicit_reg_pending_clobbers
;
453 static HARD_REG_SET implicit_reg_pending_uses
;
455 /* To speed up the test for duplicate dependency links we keep a
456 record of dependencies created by add_dependence when the average
457 number of instructions in a basic block is very large.
459 Studies have shown that there is typically around 5 instructions between
460 branches for typical C code. So we can make a guess that the average
461 basic block is approximately 5 instructions long; we will choose 100X
462 the average size as a very large basic block.
464 Each insn has associated bitmaps for its dependencies. Each bitmap
465 has enough entries to represent a dependency on any other insn in
466 the insn chain. All bitmap for true dependencies cache is
467 allocated then the rest two ones are also allocated. */
468 static bitmap_head
*true_dependency_cache
= NULL
;
469 static bitmap_head
*output_dependency_cache
= NULL
;
470 static bitmap_head
*anti_dependency_cache
= NULL
;
471 static bitmap_head
*control_dependency_cache
= NULL
;
472 static bitmap_head
*spec_dependency_cache
= NULL
;
473 static int cache_size
;
475 static int deps_may_trap_p (const_rtx
);
476 static void add_dependence_1 (rtx
, rtx
, enum reg_note
);
477 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
);
478 static void add_dependence_list_and_free (struct deps_desc
*, rtx
,
479 rtx
*, int, enum reg_note
);
480 static void delete_all_dependences (rtx
);
481 static void chain_to_prev_insn (rtx
);
483 static void flush_pending_lists (struct deps_desc
*, rtx
, int, int);
484 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx
);
485 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx
);
486 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx
);
488 static bool sched_has_condition_p (const_rtx
);
489 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
491 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
493 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
495 #ifdef ENABLE_CHECKING
496 static void check_dep (dep_t
, bool);
499 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
502 deps_may_trap_p (const_rtx mem
)
504 const_rtx addr
= XEXP (mem
, 0);
506 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
508 const_rtx t
= get_reg_known_value (REGNO (addr
));
512 return rtx_addr_can_trap_p (addr
);
516 /* Find the condition under which INSN is executed. If REV is not NULL,
517 it is set to TRUE when the returned comparison should be reversed
518 to get the actual condition. */
520 sched_get_condition_with_rev_uncached (const_rtx insn
, bool *rev
)
522 rtx pat
= PATTERN (insn
);
528 if (GET_CODE (pat
) == COND_EXEC
)
529 return COND_EXEC_TEST (pat
);
531 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
534 src
= SET_SRC (pc_set (insn
));
536 if (XEXP (src
, 2) == pc_rtx
)
537 return XEXP (src
, 0);
538 else if (XEXP (src
, 1) == pc_rtx
)
540 rtx cond
= XEXP (src
, 0);
541 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
543 if (revcode
== UNKNOWN
)
554 /* Return the condition under which INSN does not execute (i.e. the
555 not-taken condition for a conditional branch), or NULL if we cannot
556 find such a condition. The caller should make a copy of the condition
559 sched_get_reverse_condition_uncached (const_rtx insn
)
562 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
563 if (cond
== NULL_RTX
)
567 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
568 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
575 /* Caching variant of sched_get_condition_with_rev_uncached.
576 We only do actual work the first time we come here for an insn; the
577 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
579 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
583 if (INSN_LUID (insn
) == 0)
584 return sched_get_condition_with_rev_uncached (insn
, rev
);
586 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
589 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
592 *rev
= INSN_REVERSE_COND (insn
);
593 return INSN_CACHED_COND (insn
);
596 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
597 INSN_REVERSE_COND (insn
) = tmp
;
599 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
601 INSN_CACHED_COND (insn
) = const_true_rtx
;
606 *rev
= INSN_REVERSE_COND (insn
);
607 return INSN_CACHED_COND (insn
);
610 /* True when we can find a condition under which INSN is executed. */
612 sched_has_condition_p (const_rtx insn
)
614 return !! sched_get_condition_with_rev (insn
, NULL
);
619 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
621 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
623 if (COMPARISON_P (cond1
)
624 && COMPARISON_P (cond2
)
625 && GET_CODE (cond1
) ==
627 ? reversed_comparison_code (cond2
, NULL
)
629 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
630 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
635 /* Return true if insn1 and insn2 can never depend on one another because
636 the conditions under which they are executed are mutually exclusive. */
638 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
641 bool rev1
= false, rev2
= false;
643 /* df doesn't handle conditional lifetimes entirely correctly;
644 calls mess up the conditional lifetimes. */
645 if (!CALL_P (insn1
) && !CALL_P (insn2
))
647 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
648 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
650 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
651 /* Make sure first instruction doesn't affect condition of second
652 instruction if switched. */
653 && !modified_in_p (cond1
, insn2
)
654 /* Make sure second instruction doesn't affect condition of first
655 instruction if switched. */
656 && !modified_in_p (cond2
, insn1
))
663 /* Return true if INSN can potentially be speculated with type DS. */
665 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
667 if (HAS_INTERNAL_DEP (insn
))
670 if (!NONJUMP_INSN_P (insn
))
673 if (SCHED_GROUP_P (insn
))
676 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
679 if (side_effects_p (PATTERN (insn
)))
683 /* The following instructions, which depend on a speculatively scheduled
684 instruction, cannot be speculatively scheduled along. */
686 if (may_trap_or_fault_p (PATTERN (insn
)))
687 /* If instruction might fault, it cannot be speculatively scheduled.
688 For control speculation it's obvious why and for data speculation
689 it's because the insn might get wrong input if speculation
690 wasn't successful. */
693 if ((ds
& BE_IN_DATA
)
694 && sched_has_condition_p (insn
))
695 /* If this is a predicated instruction, then it cannot be
696 speculatively scheduled. See PR35659. */
703 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
704 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
705 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
706 This function is used to switch sd_iterator to the next list.
707 !!! For internal use only. Might consider moving it to sched-int.h. */
709 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
710 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
712 sd_list_types_def types
= *types_ptr
;
714 if (types
& SD_LIST_HARD_BACK
)
716 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
717 *resolved_p_ptr
= false;
718 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
720 else if (types
& SD_LIST_SPEC_BACK
)
722 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
723 *resolved_p_ptr
= false;
724 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
726 else if (types
& SD_LIST_FORW
)
728 *list_ptr
= INSN_FORW_DEPS (insn
);
729 *resolved_p_ptr
= false;
730 *types_ptr
= types
& ~SD_LIST_FORW
;
732 else if (types
& SD_LIST_RES_BACK
)
734 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
735 *resolved_p_ptr
= true;
736 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
738 else if (types
& SD_LIST_RES_FORW
)
740 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
741 *resolved_p_ptr
= true;
742 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
747 *resolved_p_ptr
= false;
748 *types_ptr
= SD_LIST_NONE
;
752 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
754 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
758 while (list_types
!= SD_LIST_NONE
)
763 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
765 size
+= DEPS_LIST_N_LINKS (list
);
771 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
774 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
776 while (list_types
!= SD_LIST_NONE
)
781 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
782 if (!deps_list_empty_p (list
))
789 /* Initialize data for INSN. */
791 sd_init_insn (rtx insn
)
793 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
794 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
795 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
796 INSN_FORW_DEPS (insn
) = create_deps_list ();
797 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
799 /* ??? It would be nice to allocate dependency caches here. */
802 /* Free data for INSN. */
804 sd_finish_insn (rtx insn
)
806 /* ??? It would be nice to deallocate dependency caches here. */
808 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
809 INSN_HARD_BACK_DEPS (insn
) = NULL
;
811 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
812 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
814 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
815 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
817 free_deps_list (INSN_FORW_DEPS (insn
));
818 INSN_FORW_DEPS (insn
) = NULL
;
820 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
821 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
824 /* Find a dependency between producer PRO and consumer CON.
825 Search through resolved dependency lists if RESOLVED_P is true.
826 If no such dependency is found return NULL,
827 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
828 with an iterator pointing to it. */
830 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
831 sd_iterator_def
*sd_it_ptr
)
833 sd_list_types_def pro_list_type
;
834 sd_list_types_def con_list_type
;
835 sd_iterator_def sd_it
;
837 bool found_p
= false;
841 pro_list_type
= SD_LIST_RES_FORW
;
842 con_list_type
= SD_LIST_RES_BACK
;
846 pro_list_type
= SD_LIST_FORW
;
847 con_list_type
= SD_LIST_BACK
;
850 /* Walk through either back list of INSN or forw list of ELEM
851 depending on which one is shorter. */
852 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
854 /* Find the dep_link with producer PRO in consumer's back_deps. */
855 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
856 if (DEP_PRO (dep
) == pro
)
864 /* Find the dep_link with consumer CON in producer's forw_deps. */
865 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
866 if (DEP_CON (dep
) == con
)
875 if (sd_it_ptr
!= NULL
)
884 /* Find a dependency between producer PRO and consumer CON.
885 Use dependency [if available] to check if dependency is present at all.
886 Search through resolved dependency lists if RESOLVED_P is true.
887 If the dependency or NULL if none found. */
889 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
891 if (true_dependency_cache
!= NULL
)
892 /* Avoiding the list walk below can cut compile times dramatically
895 int elem_luid
= INSN_LUID (pro
);
896 int insn_luid
= INSN_LUID (con
);
898 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
899 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
900 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
901 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
905 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
908 /* Add or update a dependence described by DEP.
909 MEM1 and MEM2, if non-null, correspond to memory locations in case of
912 The function returns a value indicating if an old entry has been changed
913 or a new entry has been added to insn's backward deps.
915 This function merely checks if producer and consumer is the same insn
916 and doesn't create a dep in this case. Actual manipulation of
917 dependence data structures is performed in add_or_update_dep_1. */
918 static enum DEPS_ADJUST_RESULT
919 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
921 rtx elem
= DEP_PRO (dep
);
922 rtx insn
= DEP_CON (dep
);
924 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
926 /* Don't depend an insn on itself. */
929 if (sched_deps_info
->generate_spec_deps
)
930 /* INSN has an internal dependence, which we can't overcome. */
931 HAS_INTERNAL_DEP (insn
) = 1;
936 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
939 /* Ask dependency caches what needs to be done for dependence DEP.
940 Return DEP_CREATED if new dependence should be created and there is no
941 need to try to find one searching the dependencies lists.
942 Return DEP_PRESENT if there already is a dependence described by DEP and
943 hence nothing is to be done.
944 Return DEP_CHANGED if there already is a dependence, but it should be
945 updated to incorporate additional information from DEP. */
946 static enum DEPS_ADJUST_RESULT
947 ask_dependency_caches (dep_t dep
)
949 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
950 int insn_luid
= INSN_LUID (DEP_CON (dep
));
952 gcc_assert (true_dependency_cache
!= NULL
953 && output_dependency_cache
!= NULL
954 && anti_dependency_cache
!= NULL
955 && control_dependency_cache
!= NULL
);
957 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
959 enum reg_note present_dep_type
;
961 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
962 present_dep_type
= REG_DEP_TRUE
;
963 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
964 present_dep_type
= REG_DEP_OUTPUT
;
965 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
966 present_dep_type
= REG_DEP_ANTI
;
967 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
968 present_dep_type
= REG_DEP_CONTROL
;
970 /* There is no existing dep so it should be created. */
973 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
974 /* DEP does not add anything to the existing dependence. */
979 ds_t present_dep_types
= 0;
981 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
982 present_dep_types
|= DEP_TRUE
;
983 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
984 present_dep_types
|= DEP_OUTPUT
;
985 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
986 present_dep_types
|= DEP_ANTI
;
987 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
988 present_dep_types
|= DEP_CONTROL
;
990 if (present_dep_types
== 0)
991 /* There is no existing dep so it should be created. */
994 if (!(current_sched_info
->flags
& DO_SPECULATION
)
995 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
997 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
998 == present_dep_types
)
999 /* DEP does not add anything to the existing dependence. */
1004 /* Only true dependencies can be data speculative and
1005 only anti dependencies can be control speculative. */
1006 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1007 == present_dep_types
);
1009 /* if (DEP is SPECULATIVE) then
1010 ..we should update DEP_STATUS
1012 ..we should reset existing dep to non-speculative. */
1019 /* Set dependency caches according to DEP. */
1021 set_dependency_caches (dep_t dep
)
1023 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1024 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1026 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1028 switch (DEP_TYPE (dep
))
1031 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1034 case REG_DEP_OUTPUT
:
1035 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1039 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1042 case REG_DEP_CONTROL
:
1043 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1052 ds_t ds
= DEP_STATUS (dep
);
1055 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1056 if (ds
& DEP_OUTPUT
)
1057 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1059 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1060 if (ds
& DEP_CONTROL
)
1061 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1063 if (ds
& SPECULATIVE
)
1065 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1066 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1071 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1072 caches accordingly. */
1074 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1076 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1077 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1079 /* Clear corresponding cache entry because type of the link
1080 may have changed. Keep them if we use_deps_list. */
1081 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1085 case REG_DEP_OUTPUT
:
1086 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1090 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1093 case REG_DEP_CONTROL
:
1094 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1102 set_dependency_caches (dep
);
1105 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1107 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1109 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1110 dep_link_t link
= DEP_NODE_BACK (node
);
1111 dep_t dep
= DEP_NODE_DEP (node
);
1112 rtx elem
= DEP_PRO (dep
);
1113 rtx insn
= DEP_CON (dep
);
1115 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1117 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1119 if (true_dependency_cache
!= NULL
)
1120 /* Clear the cache entry. */
1121 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1125 /* Update DEP to incorporate information from NEW_DEP.
1126 SD_IT points to DEP in case it should be moved to another list.
1127 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1128 data-speculative dependence should be updated. */
1129 static enum DEPS_ADJUST_RESULT
1130 update_dep (dep_t dep
, dep_t new_dep
,
1131 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1132 rtx mem1 ATTRIBUTE_UNUSED
,
1133 rtx mem2 ATTRIBUTE_UNUSED
)
1135 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1136 enum reg_note old_type
= DEP_TYPE (dep
);
1137 bool was_spec
= dep_spec_p (dep
);
1139 /* If this is a more restrictive type of dependence than the
1140 existing one, then change the existing dependence to this
1142 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1144 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1148 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1149 /* Update DEP_STATUS. */
1151 ds_t dep_status
= DEP_STATUS (dep
);
1152 ds_t ds
= DEP_STATUS (new_dep
);
1153 ds_t new_status
= ds
| dep_status
;
1155 if (new_status
& SPECULATIVE
)
1157 /* Either existing dep or a dep we're adding or both are
1159 if (!(ds
& SPECULATIVE
)
1160 || !(dep_status
& SPECULATIVE
))
1161 /* The new dep can't be speculative. */
1162 new_status
&= ~SPECULATIVE
;
1165 /* Both are speculative. Merge probabilities. */
1170 dw
= estimate_dep_weak (mem1
, mem2
);
1171 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1174 new_status
= ds_merge (dep_status
, ds
);
1180 if (dep_status
!= ds
)
1182 DEP_STATUS (dep
) = ds
;
1187 if (was_spec
&& !dep_spec_p (dep
))
1188 /* The old dep was speculative, but now it isn't. */
1189 change_spec_dep_to_hard (sd_it
);
1191 if (true_dependency_cache
!= NULL
1192 && res
== DEP_CHANGED
)
1193 update_dependency_caches (dep
, old_type
);
1198 /* Add or update a dependence described by DEP.
1199 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1202 The function returns a value indicating if an old entry has been changed
1203 or a new entry has been added to insn's backward deps or nothing has
1204 been updated at all. */
1205 static enum DEPS_ADJUST_RESULT
1206 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1207 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1209 bool maybe_present_p
= true;
1210 bool present_p
= false;
1212 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1213 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1215 #ifdef ENABLE_CHECKING
1216 check_dep (new_dep
, mem1
!= NULL
);
1219 if (true_dependency_cache
!= NULL
)
1221 switch (ask_dependency_caches (new_dep
))
1227 maybe_present_p
= true;
1232 maybe_present_p
= false;
1242 /* Check that we don't already have this dependence. */
1243 if (maybe_present_p
)
1246 sd_iterator_def sd_it
;
1248 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1250 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1252 resolved_p
, &sd_it
);
1254 if (present_dep
!= NULL
)
1255 /* We found an existing dependency between ELEM and INSN. */
1256 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1258 /* We didn't find a dep, it shouldn't present in the cache. */
1259 gcc_assert (!present_p
);
1262 /* Might want to check one level of transitivity to save conses.
1263 This check should be done in maybe_add_or_update_dep_1.
1264 Since we made it to add_or_update_dep_1, we must create
1265 (or update) a link. */
1267 if (mem1
!= NULL_RTX
)
1269 gcc_assert (sched_deps_info
->generate_spec_deps
);
1270 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1271 estimate_dep_weak (mem1
, mem2
));
1274 sd_add_dep (new_dep
, resolved_p
);
1279 /* Initialize BACK_LIST_PTR with consumer's backward list and
1280 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1281 initialize with lists that hold resolved deps. */
1283 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1284 deps_list_t
*back_list_ptr
,
1285 deps_list_t
*forw_list_ptr
)
1287 rtx con
= DEP_CON (dep
);
1291 if (dep_spec_p (dep
))
1292 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1294 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1296 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1300 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1301 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1305 /* Add dependence described by DEP.
1306 If RESOLVED_P is true treat the dependence as a resolved one. */
1308 sd_add_dep (dep_t dep
, bool resolved_p
)
1310 dep_node_t n
= create_dep_node ();
1311 deps_list_t con_back_deps
;
1312 deps_list_t pro_forw_deps
;
1313 rtx elem
= DEP_PRO (dep
);
1314 rtx insn
= DEP_CON (dep
);
1316 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1318 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1319 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1320 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1322 copy_dep (DEP_NODE_DEP (n
), dep
);
1324 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1326 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1328 #ifdef ENABLE_CHECKING
1329 check_dep (dep
, false);
1332 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1334 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1335 in the bitmap caches of dependency information. */
1336 if (true_dependency_cache
!= NULL
)
1337 set_dependency_caches (dep
);
1340 /* Add or update backward dependence between INSN and ELEM
1341 with given type DEP_TYPE and dep_status DS.
1342 This function is a convenience wrapper. */
1343 enum DEPS_ADJUST_RESULT
1344 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1346 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1349 /* Resolved dependence pointed to by SD_IT.
1350 SD_IT will advance to the next element. */
1352 sd_resolve_dep (sd_iterator_def sd_it
)
1354 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1355 dep_t dep
= DEP_NODE_DEP (node
);
1356 rtx pro
= DEP_PRO (dep
);
1357 rtx con
= DEP_CON (dep
);
1359 if (dep_spec_p (dep
))
1360 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1361 INSN_RESOLVED_BACK_DEPS (con
));
1363 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1364 INSN_RESOLVED_BACK_DEPS (con
));
1366 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1367 INSN_RESOLVED_FORW_DEPS (pro
));
1370 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1371 pointed to by SD_IT to unresolved state. */
1373 sd_unresolve_dep (sd_iterator_def sd_it
)
1375 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1376 dep_t dep
= DEP_NODE_DEP (node
);
1377 rtx pro
= DEP_PRO (dep
);
1378 rtx con
= DEP_CON (dep
);
1380 if (dep_spec_p (dep
))
1381 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1382 INSN_SPEC_BACK_DEPS (con
));
1384 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1385 INSN_HARD_BACK_DEPS (con
));
1387 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1388 INSN_FORW_DEPS (pro
));
1391 /* Make TO depend on all the FROM's producers.
1392 If RESOLVED_P is true add dependencies to the resolved lists. */
1394 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1396 sd_list_types_def list_type
;
1397 sd_iterator_def sd_it
;
1400 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1402 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1404 dep_def _new_dep
, *new_dep
= &_new_dep
;
1406 copy_dep (new_dep
, dep
);
1407 DEP_CON (new_dep
) = to
;
1408 sd_add_dep (new_dep
, resolved_p
);
1412 /* Remove a dependency referred to by SD_IT.
1413 SD_IT will point to the next dependence after removal. */
1415 sd_delete_dep (sd_iterator_def sd_it
)
1417 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1418 dep_t dep
= DEP_NODE_DEP (n
);
1419 rtx pro
= DEP_PRO (dep
);
1420 rtx con
= DEP_CON (dep
);
1421 deps_list_t con_back_deps
;
1422 deps_list_t pro_forw_deps
;
1424 if (true_dependency_cache
!= NULL
)
1426 int elem_luid
= INSN_LUID (pro
);
1427 int insn_luid
= INSN_LUID (con
);
1429 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1430 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1431 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1432 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1434 if (current_sched_info
->flags
& DO_SPECULATION
)
1435 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1438 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1439 &con_back_deps
, &pro_forw_deps
);
1441 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1442 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1444 delete_dep_node (n
);
1447 /* Dump size of the lists. */
1448 #define DUMP_LISTS_SIZE (2)
1450 /* Dump dependencies of the lists. */
1451 #define DUMP_LISTS_DEPS (4)
1453 /* Dump all information about the lists. */
1454 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1456 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1457 FLAGS is a bit mask specifying what information about the lists needs
1459 If FLAGS has the very first bit set, then dump all information about
1460 the lists and propagate this bit into the callee dump functions. */
1462 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1464 sd_iterator_def sd_it
;
1471 flags
|= DUMP_LISTS_ALL
;
1473 fprintf (dump
, "[");
1475 if (flags
& DUMP_LISTS_SIZE
)
1476 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1478 if (flags
& DUMP_LISTS_DEPS
)
1480 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1482 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1483 fprintf (dump
, " ");
1488 /* Dump all information about deps_lists of INSN specified by TYPES
1491 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1493 dump_lists (stderr
, insn
, types
, 1);
1494 fprintf (stderr
, "\n");
1497 /* A wrapper around add_dependence_1, to add a dependence of CON on
1498 PRO, with type DEP_TYPE. This function implements special handling
1499 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1500 the type to REG_DEP_ANTI if we can determine that predication is
1501 impossible; otherwise we add additional true dependencies on the
1502 INSN_COND_DEPS list of the jump (which PRO must be). */
1504 add_dependence (rtx con
, rtx pro
, enum reg_note dep_type
)
1506 if (dep_type
== REG_DEP_CONTROL
1507 && !(current_sched_info
->flags
& DO_PREDICATION
))
1508 dep_type
= REG_DEP_ANTI
;
1510 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1511 so we must also make the insn dependent on the setter of the
1513 if (dep_type
== REG_DEP_CONTROL
)
1516 rtx other
= real_insn_for_shadow (real_pro
);
1519 if (other
!= NULL_RTX
)
1521 cond
= sched_get_reverse_condition_uncached (real_pro
);
1522 /* Verify that the insn does not use a different value in
1523 the condition register than the one that was present at
1525 if (cond
== NULL_RTX
)
1526 dep_type
= REG_DEP_ANTI
;
1527 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1530 CLEAR_HARD_REG_SET (uses
);
1531 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1532 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1533 dep_type
= REG_DEP_ANTI
;
1535 if (dep_type
== REG_DEP_CONTROL
)
1537 if (sched_verbose
>= 5)
1538 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1539 INSN_UID (real_pro
));
1540 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1545 add_dependence_1 (con
, pro
, dep_type
);
1548 /* A convenience wrapper to operate on an entire list. */
1551 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
)
1553 for (; list
; list
= XEXP (list
, 1))
1555 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1556 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1560 /* Similar, but free *LISTP at the same time, when the context
1564 add_dependence_list_and_free (struct deps_desc
*deps
, rtx insn
, rtx
*listp
,
1565 int uncond
, enum reg_note dep_type
)
1567 add_dependence_list (insn
, *listp
, uncond
, dep_type
);
1569 /* We don't want to short-circuit dependencies involving debug
1570 insns, because they may cause actual dependencies to be
1572 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1575 free_INSN_LIST_list (listp
);
1578 /* Remove all occurrences of INSN from LIST. Return the number of
1579 occurrences removed. */
1582 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1588 if (XEXP (*listp
, 0) == insn
)
1590 remove_free_INSN_LIST_node (listp
);
1595 listp
= &XEXP (*listp
, 1);
1601 /* Same as above, but process two lists at once. */
1603 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1609 if (XEXP (*listp
, 0) == insn
)
1611 remove_free_INSN_LIST_node (listp
);
1612 remove_free_EXPR_LIST_node (exprp
);
1617 listp
= &XEXP (*listp
, 1);
1618 exprp
= &XEXP (*exprp
, 1);
1624 /* Clear all dependencies for an insn. */
1626 delete_all_dependences (rtx insn
)
1628 sd_iterator_def sd_it
;
1631 /* The below cycle can be optimized to clear the caches and back_deps
1632 in one call but that would provoke duplication of code from
1635 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1636 sd_iterator_cond (&sd_it
, &dep
);)
1637 sd_delete_dep (sd_it
);
1640 /* All insns in a scheduling group except the first should only have
1641 dependencies on the previous insn in the group. So we find the
1642 first instruction in the scheduling group by walking the dependence
1643 chains backwards. Then we add the dependencies for the group to
1644 the previous nonnote insn. */
1647 chain_to_prev_insn (rtx insn
)
1649 sd_iterator_def sd_it
;
1653 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1656 rtx pro
= DEP_PRO (dep
);
1660 i
= prev_nonnote_insn (i
);
1664 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1666 if (! sched_insns_conditions_mutex_p (i
, pro
))
1667 add_dependence (i
, pro
, DEP_TYPE (dep
));
1671 delete_all_dependences (insn
);
1673 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1674 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1675 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1676 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1679 /* Process an insn's memory dependencies. There are four kinds of
1682 (0) read dependence: read follows read
1683 (1) true dependence: read follows write
1684 (2) output dependence: write follows write
1685 (3) anti dependence: write follows read
1687 We are careful to build only dependencies which actually exist, and
1688 use transitivity to avoid building too many links. */
1690 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1691 The MEM is a memory reference contained within INSN, which we are saving
1692 so that we can do memory aliasing on it. */
1695 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1702 gcc_assert (!deps
->readonly
);
1705 insn_list
= &deps
->pending_read_insns
;
1706 mem_list
= &deps
->pending_read_mems
;
1707 if (!DEBUG_INSN_P (insn
))
1708 deps
->pending_read_list_length
++;
1712 insn_list
= &deps
->pending_write_insns
;
1713 mem_list
= &deps
->pending_write_mems
;
1714 deps
->pending_write_list_length
++;
1717 link
= alloc_INSN_LIST (insn
, *insn_list
);
1720 if (sched_deps_info
->use_cselib
)
1722 mem
= shallow_copy_rtx (mem
);
1723 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1724 GET_MODE (mem
), insn
);
1726 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1730 /* Make a dependency between every memory reference on the pending lists
1731 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1732 dependencies for a read operation, similarly with FOR_WRITE. */
1735 flush_pending_lists (struct deps_desc
*deps
, rtx insn
, int for_read
,
1740 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1742 if (!deps
->readonly
)
1744 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1745 deps
->pending_read_list_length
= 0;
1749 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1750 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1752 add_dependence_list_and_free (deps
, insn
,
1753 &deps
->last_pending_memory_flush
, 1,
1754 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1756 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1759 if (DEBUG_INSN_P (insn
))
1762 free_INSN_LIST_list (&deps
->pending_read_insns
);
1763 free_INSN_LIST_list (&deps
->pending_write_insns
);
1764 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1765 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1768 if (!deps
->readonly
)
1770 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1771 deps
->pending_write_list_length
= 0;
1773 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1774 deps
->pending_flush_length
= 1;
1778 /* Instruction which dependencies we are analyzing. */
1779 static rtx cur_insn
= NULL_RTX
;
1781 /* Implement hooks for haifa scheduler. */
1784 haifa_start_insn (rtx insn
)
1786 gcc_assert (insn
&& !cur_insn
);
1792 haifa_finish_insn (void)
1798 haifa_note_reg_set (int regno
)
1800 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1804 haifa_note_reg_clobber (int regno
)
1806 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1810 haifa_note_reg_use (int regno
)
1812 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1816 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1818 if (!(ds
& SPECULATIVE
))
1821 pending_mem
= NULL_RTX
;
1824 gcc_assert (ds
& BEGIN_DATA
);
1827 dep_def _dep
, *dep
= &_dep
;
1829 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1830 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1831 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1837 haifa_note_dep (rtx elem
, ds_t ds
)
1842 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1843 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1847 note_reg_use (int r
)
1849 if (sched_deps_info
->note_reg_use
)
1850 sched_deps_info
->note_reg_use (r
);
1854 note_reg_set (int r
)
1856 if (sched_deps_info
->note_reg_set
)
1857 sched_deps_info
->note_reg_set (r
);
1861 note_reg_clobber (int r
)
1863 if (sched_deps_info
->note_reg_clobber
)
1864 sched_deps_info
->note_reg_clobber (r
);
1868 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1870 if (sched_deps_info
->note_mem_dep
)
1871 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1875 note_dep (rtx e
, ds_t ds
)
1877 if (sched_deps_info
->note_dep
)
1878 sched_deps_info
->note_dep (e
, ds
);
1881 /* Return corresponding to DS reg_note. */
1886 return REG_DEP_TRUE
;
1887 else if (ds
& DEP_OUTPUT
)
1888 return REG_DEP_OUTPUT
;
1889 else if (ds
& DEP_ANTI
)
1890 return REG_DEP_ANTI
;
1893 gcc_assert (ds
& DEP_CONTROL
);
1894 return REG_DEP_CONTROL
;
1900 /* Functions for computation of info needed for register pressure
1901 sensitive insn scheduling. */
1904 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1905 static struct reg_use_data
*
1906 create_insn_reg_use (int regno
, rtx insn
)
1908 struct reg_use_data
*use
;
1910 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1913 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1914 INSN_REG_USE_LIST (insn
) = use
;
1918 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1919 static struct reg_set_data
*
1920 create_insn_reg_set (int regno
, rtx insn
)
1922 struct reg_set_data
*set
;
1924 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1927 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1928 INSN_REG_SET_LIST (insn
) = set
;
1932 /* Set up insn register uses for INSN and dependency context DEPS. */
1934 setup_insn_reg_uses (struct deps_desc
*deps
, rtx insn
)
1937 reg_set_iterator rsi
;
1939 struct reg_use_data
*use
, *use2
, *next
;
1940 struct deps_reg
*reg_last
;
1942 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1944 if (i
< FIRST_PSEUDO_REGISTER
1945 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1948 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1949 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1950 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1951 /* Ignore use which is not dying. */
1954 use
= create_insn_reg_use (i
, insn
);
1955 use
->next_regno_use
= use
;
1956 reg_last
= &deps
->reg_last
[i
];
1958 /* Create the cycle list of uses. */
1959 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1961 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1962 next
= use
->next_regno_use
;
1963 use
->next_regno_use
= use2
;
1964 use2
->next_regno_use
= next
;
1969 /* Register pressure info for the currently processed insn. */
1970 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1972 /* Return TRUE if INSN has the use structure for REGNO. */
1974 insn_use_p (rtx insn
, int regno
)
1976 struct reg_use_data
*use
;
1978 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1979 if (use
->regno
== regno
)
1984 /* Update the register pressure info after birth of pseudo register REGNO
1985 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
1986 the register is in clobber or unused after the insn. */
1988 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
1993 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1994 cl
= sched_regno_pressure_class
[regno
];
1997 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2000 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2001 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2005 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2006 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2010 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2011 reg_pressure_info
[cl
].set_increase
= new_incr
;
2012 if (! insn_use_p (insn
, regno
))
2013 reg_pressure_info
[cl
].change
+= incr
;
2014 create_insn_reg_set (regno
, insn
);
2016 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2020 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2021 hard registers involved in the birth. */
2023 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2024 bool clobber_p
, bool unused_p
)
2027 int new_incr
, last
= regno
+ nregs
;
2029 while (regno
< last
)
2031 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2032 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2034 cl
= sched_regno_pressure_class
[regno
];
2039 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2040 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2044 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2045 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2049 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2050 reg_pressure_info
[cl
].set_increase
= new_incr
;
2051 if (! insn_use_p (insn
, regno
))
2052 reg_pressure_info
[cl
].change
+= 1;
2053 create_insn_reg_set (regno
, insn
);
2055 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2062 /* Update the register pressure info after birth of pseudo or hard
2063 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2064 correspondingly that the register is in clobber or unused after the
2067 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2071 if (GET_CODE (reg
) == SUBREG
)
2072 reg
= SUBREG_REG (reg
);
2077 regno
= REGNO (reg
);
2078 if (regno
< FIRST_PSEUDO_REGISTER
)
2079 mark_insn_hard_regno_birth (insn
, regno
,
2080 hard_regno_nregs
[regno
][GET_MODE (reg
)],
2081 clobber_p
, unused_p
);
2083 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2086 /* Update the register pressure info after death of pseudo register
2089 mark_pseudo_death (int regno
)
2094 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2095 cl
= sched_regno_pressure_class
[regno
];
2098 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2099 reg_pressure_info
[cl
].change
-= incr
;
2103 /* Like mark_pseudo_death except that NREGS saying how many hard
2104 registers involved in the death. */
2106 mark_hard_regno_death (int regno
, int nregs
)
2109 int last
= regno
+ nregs
;
2111 while (regno
< last
)
2113 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2114 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2116 cl
= sched_regno_pressure_class
[regno
];
2118 reg_pressure_info
[cl
].change
-= 1;
2124 /* Update the register pressure info after death of pseudo or hard
2127 mark_reg_death (rtx reg
)
2131 if (GET_CODE (reg
) == SUBREG
)
2132 reg
= SUBREG_REG (reg
);
2137 regno
= REGNO (reg
);
2138 if (regno
< FIRST_PSEUDO_REGISTER
)
2139 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
2141 mark_pseudo_death (regno
);
2144 /* Process SETTER of REG. DATA is an insn containing the setter. */
2146 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2148 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2151 ((rtx
) data
, reg
, false,
2152 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2155 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2157 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2159 if (GET_CODE (setter
) == CLOBBER
)
2160 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2163 /* Set up reg pressure info related to INSN. */
2165 init_insn_reg_pressure_info (rtx insn
)
2169 static struct reg_pressure_data
*pressure_info
;
2172 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2174 if (! INSN_P (insn
))
2177 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2179 cl
= ira_pressure_classes
[i
];
2180 reg_pressure_info
[cl
].clobber_increase
= 0;
2181 reg_pressure_info
[cl
].set_increase
= 0;
2182 reg_pressure_info
[cl
].unused_set_increase
= 0;
2183 reg_pressure_info
[cl
].change
= 0;
2186 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2188 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2191 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2192 if (REG_NOTE_KIND (link
) == REG_INC
)
2193 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2196 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2197 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2198 mark_reg_death (XEXP (link
, 0));
2200 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2202 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2203 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2204 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2206 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2208 cl
= ira_pressure_classes
[i
];
2209 pressure_info
[i
].clobber_increase
2210 = reg_pressure_info
[cl
].clobber_increase
;
2211 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2212 pressure_info
[i
].unused_set_increase
2213 = reg_pressure_info
[cl
].unused_set_increase
;
2214 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2221 /* Internal variable for sched_analyze_[12] () functions.
2222 If it is nonzero, this means that sched_analyze_[12] looks
2223 at the most toplevel SET. */
2224 static bool can_start_lhs_rhs_p
;
2226 /* Extend reg info for the deps context DEPS given that
2227 we have just generated a register numbered REGNO. */
2229 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2231 int max_regno
= regno
+ 1;
2233 gcc_assert (!reload_completed
);
2235 /* In a readonly context, it would not hurt to extend info,
2236 but it should not be needed. */
2237 if (reload_completed
&& deps
->readonly
)
2239 deps
->max_reg
= max_regno
;
2243 if (max_regno
> deps
->max_reg
)
2245 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2247 memset (&deps
->reg_last
[deps
->max_reg
],
2248 0, (max_regno
- deps
->max_reg
)
2249 * sizeof (struct deps_reg
));
2250 deps
->max_reg
= max_regno
;
2254 /* Extends REG_INFO_P if needed. */
2256 maybe_extend_reg_info_p (void)
2258 /* Extend REG_INFO_P, if needed. */
2259 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2261 size_t new_reg_info_p_size
= max_regno
+ 128;
2263 gcc_assert (!reload_completed
&& sel_sched_p ());
2265 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2266 new_reg_info_p_size
,
2268 sizeof (*reg_info_p
));
2269 reg_info_p_size
= new_reg_info_p_size
;
2273 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2274 The type of the reference is specified by REF and can be SET,
2275 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2278 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2279 enum rtx_code ref
, rtx insn
)
2281 /* We could emit new pseudos in renaming. Extend the reg structures. */
2282 if (!reload_completed
&& sel_sched_p ()
2283 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2284 extend_deps_reg_info (deps
, regno
);
2286 maybe_extend_reg_info_p ();
2288 /* A hard reg in a wide mode may really be multiple registers.
2289 If so, mark all of them just like the first. */
2290 if (regno
< FIRST_PSEUDO_REGISTER
)
2292 int i
= hard_regno_nregs
[regno
][mode
];
2296 note_reg_set (regno
+ i
);
2298 else if (ref
== USE
)
2301 note_reg_use (regno
+ i
);
2306 note_reg_clobber (regno
+ i
);
2310 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2311 it does not reload. Ignore these as they have served their
2313 else if (regno
>= deps
->max_reg
)
2315 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2316 gcc_assert (code
== USE
|| code
== CLOBBER
);
2322 note_reg_set (regno
);
2323 else if (ref
== USE
)
2324 note_reg_use (regno
);
2326 note_reg_clobber (regno
);
2328 /* Pseudos that are REG_EQUIV to something may be replaced
2329 by that during reloading. We need only add dependencies for
2330 the address in the REG_EQUIV note. */
2331 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2333 rtx t
= get_reg_known_value (regno
);
2335 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2338 /* Don't let it cross a call after scheduling if it doesn't
2339 already cross one. */
2340 if (REG_N_CALLS_CROSSED (regno
) == 0)
2342 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2343 deps
->sched_before_next_call
2344 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2346 add_dependence_list (insn
, deps
->last_function_call
, 1,
2352 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2353 rtx, X, creating all dependencies generated by the write to the
2354 destination of X, and reads of everything mentioned. */
2357 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2359 rtx dest
= XEXP (x
, 0);
2360 enum rtx_code code
= GET_CODE (x
);
2361 bool cslr_p
= can_start_lhs_rhs_p
;
2363 can_start_lhs_rhs_p
= false;
2369 if (cslr_p
&& sched_deps_info
->start_lhs
)
2370 sched_deps_info
->start_lhs (dest
);
2372 if (GET_CODE (dest
) == PARALLEL
)
2376 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2377 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2378 sched_analyze_1 (deps
,
2379 gen_rtx_CLOBBER (VOIDmode
,
2380 XEXP (XVECEXP (dest
, 0, i
), 0)),
2383 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2384 sched_deps_info
->finish_lhs ();
2388 can_start_lhs_rhs_p
= cslr_p
;
2390 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2392 can_start_lhs_rhs_p
= false;
2398 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2399 || GET_CODE (dest
) == ZERO_EXTRACT
)
2401 if (GET_CODE (dest
) == STRICT_LOW_PART
2402 || GET_CODE (dest
) == ZERO_EXTRACT
2403 || df_read_modify_subreg_p (dest
))
2405 /* These both read and modify the result. We must handle
2406 them as writes to get proper dependencies for following
2407 instructions. We must handle them as reads to get proper
2408 dependencies from this to previous instructions.
2409 Thus we need to call sched_analyze_2. */
2411 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2413 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2415 /* The second and third arguments are values read by this insn. */
2416 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2417 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2419 dest
= XEXP (dest
, 0);
2424 int regno
= REGNO (dest
);
2425 enum machine_mode mode
= GET_MODE (dest
);
2427 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2430 /* Treat all writes to a stack register as modifying the TOS. */
2431 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2433 /* Avoid analyzing the same register twice. */
2434 if (regno
!= FIRST_STACK_REG
)
2435 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2437 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2442 else if (MEM_P (dest
))
2444 /* Writing memory. */
2447 if (sched_deps_info
->use_cselib
)
2449 enum machine_mode address_mode
= get_address_mode (dest
);
2451 t
= shallow_copy_rtx (dest
);
2452 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2453 GET_MODE (t
), insn
);
2455 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2460 /* Pending lists can't get larger with a readonly context. */
2462 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2463 > MAX_PENDING_LIST_LENGTH
))
2465 /* Flush all pending reads and writes to prevent the pending lists
2466 from getting any larger. Insn scheduling runs too slowly when
2467 these lists get long. When compiling GCC with itself,
2468 this flush occurs 8 times for sparc, and 10 times for m88k using
2469 the default value of 32. */
2470 flush_pending_lists (deps
, insn
, false, true);
2474 rtx pending
, pending_mem
;
2476 pending
= deps
->pending_read_insns
;
2477 pending_mem
= deps
->pending_read_mems
;
2480 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2481 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2482 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2485 pending
= XEXP (pending
, 1);
2486 pending_mem
= XEXP (pending_mem
, 1);
2489 pending
= deps
->pending_write_insns
;
2490 pending_mem
= deps
->pending_write_mems
;
2493 if (output_dependence (XEXP (pending_mem
, 0), t
)
2494 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2495 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2498 pending
= XEXP (pending
, 1);
2499 pending_mem
= XEXP (pending_mem
, 1);
2502 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2504 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2507 if (!deps
->readonly
)
2508 add_insn_mem_dependence (deps
, false, insn
, dest
);
2510 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2513 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2514 sched_deps_info
->finish_lhs ();
2516 /* Analyze reads. */
2517 if (GET_CODE (x
) == SET
)
2519 can_start_lhs_rhs_p
= cslr_p
;
2521 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2523 can_start_lhs_rhs_p
= false;
2527 /* Analyze the uses of memory and registers in rtx X in INSN. */
2529 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2535 bool cslr_p
= can_start_lhs_rhs_p
;
2537 can_start_lhs_rhs_p
= false;
2543 if (cslr_p
&& sched_deps_info
->start_rhs
)
2544 sched_deps_info
->start_rhs (x
);
2546 code
= GET_CODE (x
);
2554 /* Ignore constants. */
2555 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2556 sched_deps_info
->finish_rhs ();
2562 /* User of CC0 depends on immediately preceding insn. */
2563 SCHED_GROUP_P (insn
) = 1;
2564 /* Don't move CC0 setter to another block (it can set up the
2565 same flag for previous CC0 users which is safe). */
2566 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2568 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2569 sched_deps_info
->finish_rhs ();
2576 int regno
= REGNO (x
);
2577 enum machine_mode mode
= GET_MODE (x
);
2579 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2582 /* Treat all reads of a stack register as modifying the TOS. */
2583 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2585 /* Avoid analyzing the same register twice. */
2586 if (regno
!= FIRST_STACK_REG
)
2587 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2588 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2592 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2593 sched_deps_info
->finish_rhs ();
2600 /* Reading memory. */
2602 rtx pending
, pending_mem
;
2605 if (sched_deps_info
->use_cselib
)
2607 enum machine_mode address_mode
= get_address_mode (t
);
2609 t
= shallow_copy_rtx (t
);
2610 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2611 GET_MODE (t
), insn
);
2613 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2617 if (!DEBUG_INSN_P (insn
))
2620 pending
= deps
->pending_read_insns
;
2621 pending_mem
= deps
->pending_read_mems
;
2624 if (read_dependence (XEXP (pending_mem
, 0), t
)
2625 && ! sched_insns_conditions_mutex_p (insn
,
2627 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2630 pending
= XEXP (pending
, 1);
2631 pending_mem
= XEXP (pending_mem
, 1);
2634 pending
= deps
->pending_write_insns
;
2635 pending_mem
= deps
->pending_write_mems
;
2638 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
, t
)
2639 && ! sched_insns_conditions_mutex_p (insn
,
2641 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2642 sched_deps_info
->generate_spec_deps
2643 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2645 pending
= XEXP (pending
, 1);
2646 pending_mem
= XEXP (pending_mem
, 1);
2649 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2650 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2652 for (u
= deps
->pending_jump_insns
; u
; u
= XEXP (u
, 1))
2653 if (deps_may_trap_p (x
))
2655 if ((sched_deps_info
->generate_spec_deps
)
2656 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2658 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2661 note_dep (XEXP (u
, 0), ds
);
2664 add_dependence (insn
, XEXP (u
, 0), REG_DEP_CONTROL
);
2668 /* Always add these dependencies to pending_reads, since
2669 this insn may be followed by a write. */
2670 if (!deps
->readonly
)
2671 add_insn_mem_dependence (deps
, true, insn
, x
);
2673 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2675 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2676 sched_deps_info
->finish_rhs ();
2681 /* Force pending stores to memory in case a trap handler needs them. */
2683 flush_pending_lists (deps
, insn
, true, false);
2687 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2688 reg_pending_barrier
= TRUE_BARRIER
;
2691 case UNSPEC_VOLATILE
:
2692 flush_pending_lists (deps
, insn
, true, true);
2698 /* Traditional and volatile asm instructions must be considered to use
2699 and clobber all hard registers, all pseudo-registers and all of
2700 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2702 Consider for instance a volatile asm that changes the fpu rounding
2703 mode. An insn should not be moved across this even if it only uses
2704 pseudo-regs because it might give an incorrectly rounded result. */
2705 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2706 reg_pending_barrier
= TRUE_BARRIER
;
2708 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2709 We can not just fall through here since then we would be confused
2710 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2711 traditional asms unlike their normal usage. */
2713 if (code
== ASM_OPERANDS
)
2715 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2716 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2718 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2719 sched_deps_info
->finish_rhs ();
2730 /* These both read and modify the result. We must handle them as writes
2731 to get proper dependencies for following instructions. We must handle
2732 them as reads to get proper dependencies from this to previous
2733 instructions. Thus we need to pass them to both sched_analyze_1
2734 and sched_analyze_2. We must call sched_analyze_2 first in order
2735 to get the proper antecedent for the read. */
2736 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2737 sched_analyze_1 (deps
, x
, insn
);
2739 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2740 sched_deps_info
->finish_rhs ();
2746 /* op0 = op0 + op1 */
2747 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2748 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2749 sched_analyze_1 (deps
, x
, insn
);
2751 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2752 sched_deps_info
->finish_rhs ();
2760 /* Other cases: walk the insn. */
2761 fmt
= GET_RTX_FORMAT (code
);
2762 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2765 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2766 else if (fmt
[i
] == 'E')
2767 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2768 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2771 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2772 sched_deps_info
->finish_rhs ();
2775 /* Analyze an INSN with pattern X to find all dependencies. */
2777 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx insn
)
2779 RTX_CODE code
= GET_CODE (x
);
2782 reg_set_iterator rsi
;
2784 if (! reload_completed
)
2788 extract_insn (insn
);
2789 preprocess_constraints ();
2790 ira_implicitly_set_insn_hard_regs (&temp
);
2791 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2792 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2795 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2799 /* Avoid moving trapping instructions across function calls that might
2800 not always return. */
2801 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2804 /* We must avoid creating a situation in which two successors of the
2805 current block have different unwind info after scheduling. If at any
2806 point the two paths re-join this leads to incorrect unwind info. */
2807 /* ??? There are certain situations involving a forced frame pointer in
2808 which, with extra effort, we could fix up the unwind info at a later
2809 CFG join. However, it seems better to notice these cases earlier
2810 during prologue generation and avoid marking the frame pointer setup
2811 as frame-related at all. */
2812 if (RTX_FRAME_RELATED_P (insn
))
2814 /* Make sure prologue insn is scheduled before next jump. */
2815 deps
->sched_before_next_jump
2816 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2818 /* Make sure epilogue insn is scheduled after preceding jumps. */
2819 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
);
2822 if (code
== COND_EXEC
)
2824 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2826 /* ??? Should be recording conditions so we reduce the number of
2827 false dependencies. */
2828 x
= COND_EXEC_CODE (x
);
2829 code
= GET_CODE (x
);
2831 if (code
== SET
|| code
== CLOBBER
)
2833 sched_analyze_1 (deps
, x
, insn
);
2835 /* Bare clobber insns are used for letting life analysis, reg-stack
2836 and others know that a value is dead. Depend on the last call
2837 instruction so that reg-stack won't get confused. */
2838 if (code
== CLOBBER
)
2839 add_dependence_list (insn
, deps
->last_function_call
, 1,
2842 else if (code
== PARALLEL
)
2844 for (i
= XVECLEN (x
, 0); i
--;)
2846 rtx sub
= XVECEXP (x
, 0, i
);
2847 code
= GET_CODE (sub
);
2849 if (code
== COND_EXEC
)
2851 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2852 sub
= COND_EXEC_CODE (sub
);
2853 code
= GET_CODE (sub
);
2855 if (code
== SET
|| code
== CLOBBER
)
2856 sched_analyze_1 (deps
, sub
, insn
);
2858 sched_analyze_2 (deps
, sub
, insn
);
2862 sched_analyze_2 (deps
, x
, insn
);
2864 /* Mark registers CLOBBERED or used by called function. */
2867 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2869 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2870 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2871 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2872 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2874 /* Don't schedule anything after a tail call, tail call needs
2875 to use at least all call-saved registers. */
2876 if (SIBLING_CALL_P (insn
))
2877 reg_pending_barrier
= TRUE_BARRIER
;
2878 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2879 reg_pending_barrier
= MOVE_BARRIER
;
2885 next
= next_nonnote_nondebug_insn (insn
);
2886 if (next
&& BARRIER_P (next
))
2887 reg_pending_barrier
= MOVE_BARRIER
;
2890 rtx pending
, pending_mem
;
2892 if (sched_deps_info
->compute_jump_reg_dependencies
)
2894 (*sched_deps_info
->compute_jump_reg_dependencies
)
2895 (insn
, reg_pending_control_uses
);
2897 /* Make latency of jump equal to 0 by using anti-dependence. */
2898 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
2900 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2901 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2902 add_dependence_list (insn
, reg_last
->implicit_sets
,
2904 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2909 /* All memory writes and volatile reads must happen before the
2910 jump. Non-volatile reads must happen before the jump iff
2911 the result is needed by the above register used mask. */
2913 pending
= deps
->pending_write_insns
;
2914 pending_mem
= deps
->pending_write_mems
;
2917 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2918 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2919 pending
= XEXP (pending
, 1);
2920 pending_mem
= XEXP (pending_mem
, 1);
2923 pending
= deps
->pending_read_insns
;
2924 pending_mem
= deps
->pending_read_mems
;
2927 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2928 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2929 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2930 pending
= XEXP (pending
, 1);
2931 pending_mem
= XEXP (pending_mem
, 1);
2934 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2936 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2941 /* If this instruction can throw an exception, then moving it changes
2942 where block boundaries fall. This is mighty confusing elsewhere.
2943 Therefore, prevent such an instruction from being moved. Same for
2944 non-jump instructions that define block boundaries.
2945 ??? Unclear whether this is still necessary in EBB mode. If not,
2946 add_branch_dependences should be adjusted for RGN mode instead. */
2947 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2948 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2949 reg_pending_barrier
= MOVE_BARRIER
;
2951 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2953 setup_insn_reg_uses (deps
, insn
);
2954 init_insn_reg_pressure_info (insn
);
2957 /* Add register dependencies for insn. */
2958 if (DEBUG_INSN_P (insn
))
2960 rtx prev
= deps
->last_debug_insn
;
2963 if (!deps
->readonly
)
2964 deps
->last_debug_insn
= insn
;
2967 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2969 add_dependence_list (insn
, deps
->last_function_call
, 1,
2972 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2973 if (!sel_sched_p ())
2974 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2976 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2978 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2979 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
);
2980 /* There's no point in making REG_DEP_CONTROL dependencies for
2982 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
);
2984 if (!deps
->readonly
)
2985 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2987 CLEAR_REG_SET (reg_pending_uses
);
2989 /* Quite often, a debug insn will refer to stuff in the
2990 previous instruction, but the reason we want this
2991 dependency here is to make sure the scheduler doesn't
2992 gratuitously move a debug insn ahead. This could dirty
2993 DF flags and cause additional analysis that wouldn't have
2994 occurred in compilation without debug insns, and such
2995 additional analysis can modify the generated code. */
2996 prev
= PREV_INSN (insn
);
2998 if (prev
&& NONDEBUG_INSN_P (prev
))
2999 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3003 regset_head set_or_clobbered
;
3005 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3007 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3008 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
3009 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
);
3010 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
3012 if (!deps
->readonly
)
3014 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3015 reg_last
->uses_length
++;
3019 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3020 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3022 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3023 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
3024 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3026 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
3028 if (!deps
->readonly
)
3030 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3031 reg_last
->uses_length
++;
3035 if (targetm
.sched
.exposed_pipeline
)
3037 INIT_REG_SET (&set_or_clobbered
);
3038 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3040 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3042 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3044 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3046 rtx other
= XEXP (list
, 0);
3047 if (INSN_CACHED_COND (other
) != const_true_rtx
3048 && refers_to_regno_p (i
, i
+ 1, INSN_CACHED_COND (other
), NULL
))
3049 INSN_CACHED_COND (other
) = const_true_rtx
;
3054 /* If the current insn is conditional, we can't free any
3056 if (sched_has_condition_p (insn
))
3058 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3060 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3061 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
3062 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3064 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3065 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3068 if (!deps
->readonly
)
3071 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3072 reg_last
->clobbers_length
++;
3075 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3077 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3078 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
3079 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3081 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
);
3082 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3083 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3086 if (!deps
->readonly
)
3087 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3092 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3094 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3095 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
3096 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
3098 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3100 add_dependence_list_and_free (deps
, insn
,
3101 ®_last
->implicit_sets
, 0,
3103 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3105 add_dependence_list_and_free (deps
, insn
,
3106 ®_last
->control_uses
, 0,
3108 add_dependence_list_and_free
3109 (deps
, insn
, ®_last
->clobbers
, 0, REG_DEP_OUTPUT
);
3111 if (!deps
->readonly
)
3113 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3114 reg_last
->clobbers_length
= 0;
3115 reg_last
->uses_length
= 0;
3120 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
3121 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3123 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3124 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3128 if (!deps
->readonly
)
3130 reg_last
->clobbers_length
++;
3132 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3135 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3137 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3139 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3141 add_dependence_list_and_free (deps
, insn
,
3142 ®_last
->implicit_sets
,
3144 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3146 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3148 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3151 if (!deps
->readonly
)
3153 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3154 reg_last
->uses_length
= 0;
3155 reg_last
->clobbers_length
= 0;
3159 if (!deps
->readonly
)
3161 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3163 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3164 reg_last
->control_uses
3165 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3170 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3171 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3173 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3174 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
3175 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
);
3176 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3177 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
);
3179 if (!deps
->readonly
)
3180 reg_last
->implicit_sets
3181 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3184 if (!deps
->readonly
)
3186 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3187 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3188 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3189 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3190 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3191 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3192 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3194 /* Set up the pending barrier found. */
3195 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3198 CLEAR_REG_SET (reg_pending_uses
);
3199 CLEAR_REG_SET (reg_pending_clobbers
);
3200 CLEAR_REG_SET (reg_pending_sets
);
3201 CLEAR_REG_SET (reg_pending_control_uses
);
3202 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3203 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3205 /* Add dependencies if a scheduling barrier was found. */
3206 if (reg_pending_barrier
)
3208 /* In the case of barrier the most added dependencies are not
3209 real, so we use anti-dependence here. */
3210 if (sched_has_condition_p (insn
))
3212 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3214 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3215 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3216 add_dependence_list (insn
, reg_last
->sets
, 0,
3217 reg_pending_barrier
== TRUE_BARRIER
3218 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3219 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3221 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3222 reg_pending_barrier
== TRUE_BARRIER
3223 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3228 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3230 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3231 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3233 add_dependence_list_and_free (deps
, insn
,
3234 ®_last
->control_uses
, 0,
3236 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3237 reg_pending_barrier
== TRUE_BARRIER
3238 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3239 add_dependence_list_and_free (deps
, insn
,
3240 ®_last
->implicit_sets
, 0,
3242 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3243 reg_pending_barrier
== TRUE_BARRIER
3244 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3246 if (!deps
->readonly
)
3248 reg_last
->uses_length
= 0;
3249 reg_last
->clobbers_length
= 0;
3254 if (!deps
->readonly
)
3255 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3257 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3258 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3259 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3262 /* Flush pending lists on jumps, but not on speculative checks. */
3263 if (JUMP_P (insn
) && !(sel_sched_p ()
3264 && sel_insn_is_speculation_check (insn
)))
3265 flush_pending_lists (deps
, insn
, true, true);
3267 reg_pending_barrier
= NOT_A_BARRIER
;
3270 /* If a post-call group is still open, see if it should remain so.
3271 This insn must be a simple move of a hard reg to a pseudo or
3274 We must avoid moving these insns for correctness on targets
3275 with small register classes, and for special registers like
3276 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3277 hard regs for all targets. */
3279 if (deps
->in_post_call_group_p
)
3281 rtx tmp
, set
= single_set (insn
);
3282 int src_regno
, dest_regno
;
3286 if (DEBUG_INSN_P (insn
))
3287 /* We don't want to mark debug insns as part of the same
3288 sched group. We know they really aren't, but if we use
3289 debug insns to tell that a call group is over, we'll
3290 get different code if debug insns are not there and
3291 instructions that follow seem like they should be part
3294 Also, if we did, chain_to_prev_insn would move the
3295 deps of the debug insn to the call insn, modifying
3296 non-debug post-dependency counts of the debug insn
3297 dependencies and otherwise messing with the scheduling
3300 Instead, let such debug insns be scheduled freely, but
3301 keep the call group open in case there are insns that
3302 should be part of it afterwards. Since we grant debug
3303 insns higher priority than even sched group insns, it
3304 will all turn out all right. */
3305 goto debug_dont_end_call_group
;
3307 goto end_call_group
;
3310 tmp
= SET_DEST (set
);
3311 if (GET_CODE (tmp
) == SUBREG
)
3312 tmp
= SUBREG_REG (tmp
);
3314 dest_regno
= REGNO (tmp
);
3316 goto end_call_group
;
3318 tmp
= SET_SRC (set
);
3319 if (GET_CODE (tmp
) == SUBREG
)
3320 tmp
= SUBREG_REG (tmp
);
3321 if ((GET_CODE (tmp
) == PLUS
3322 || GET_CODE (tmp
) == MINUS
)
3323 && REG_P (XEXP (tmp
, 0))
3324 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3325 && dest_regno
== STACK_POINTER_REGNUM
)
3326 src_regno
= STACK_POINTER_REGNUM
;
3327 else if (REG_P (tmp
))
3328 src_regno
= REGNO (tmp
);
3330 goto end_call_group
;
3332 if (src_regno
< FIRST_PSEUDO_REGISTER
3333 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3336 && deps
->in_post_call_group_p
== post_call_initial
)
3337 deps
->in_post_call_group_p
= post_call
;
3339 if (!sel_sched_p () || sched_emulate_haifa_p
)
3341 SCHED_GROUP_P (insn
) = 1;
3342 CANT_MOVE (insn
) = 1;
3348 if (!deps
->readonly
)
3349 deps
->in_post_call_group_p
= not_post_call
;
3353 debug_dont_end_call_group
:
3354 if ((current_sched_info
->flags
& DO_SPECULATION
)
3355 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3356 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3360 sel_mark_hard_insn (insn
);
3363 sd_iterator_def sd_it
;
3366 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3367 sd_iterator_cond (&sd_it
, &dep
);)
3368 change_spec_dep_to_hard (sd_it
);
3373 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3374 longjmp, loop forever, ...). */
3375 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3376 test for ECF_NORETURN? */
3378 call_may_noreturn_p (rtx insn
)
3382 /* const or pure calls that aren't looping will always return. */
3383 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3384 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3387 call
= PATTERN (insn
);
3388 if (GET_CODE (call
) == PARALLEL
)
3389 call
= XVECEXP (call
, 0, 0);
3390 if (GET_CODE (call
) == SET
)
3391 call
= SET_SRC (call
);
3392 if (GET_CODE (call
) == CALL
3393 && MEM_P (XEXP (call
, 0))
3394 && GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3396 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3397 if (SYMBOL_REF_DECL (symbol
)
3398 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3400 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3402 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3405 case BUILT_IN_BCOPY
:
3406 case BUILT_IN_BZERO
:
3407 case BUILT_IN_INDEX
:
3408 case BUILT_IN_MEMCHR
:
3409 case BUILT_IN_MEMCMP
:
3410 case BUILT_IN_MEMCPY
:
3411 case BUILT_IN_MEMMOVE
:
3412 case BUILT_IN_MEMPCPY
:
3413 case BUILT_IN_MEMSET
:
3414 case BUILT_IN_RINDEX
:
3415 case BUILT_IN_STPCPY
:
3416 case BUILT_IN_STPNCPY
:
3417 case BUILT_IN_STRCAT
:
3418 case BUILT_IN_STRCHR
:
3419 case BUILT_IN_STRCMP
:
3420 case BUILT_IN_STRCPY
:
3421 case BUILT_IN_STRCSPN
:
3422 case BUILT_IN_STRLEN
:
3423 case BUILT_IN_STRNCAT
:
3424 case BUILT_IN_STRNCMP
:
3425 case BUILT_IN_STRNCPY
:
3426 case BUILT_IN_STRPBRK
:
3427 case BUILT_IN_STRRCHR
:
3428 case BUILT_IN_STRSPN
:
3429 case BUILT_IN_STRSTR
:
3430 /* Assume certain string/memory builtins always return. */
3438 /* For all other calls assume that they might not always return. */
3442 /* Return true if INSN should be made dependent on the previous instruction
3443 group, and if all INSN's dependencies should be moved to the first
3444 instruction of that group. */
3447 chain_to_prev_insn_p (rtx insn
)
3451 /* INSN forms a group with the previous instruction. */
3452 if (SCHED_GROUP_P (insn
))
3455 /* If the previous instruction clobbers a register R and this one sets
3456 part of R, the clobber was added specifically to help us track the
3457 liveness of R. There's no point scheduling the clobber and leaving
3458 INSN behind, especially if we move the clobber to another block. */
3459 prev
= prev_nonnote_nondebug_insn (insn
);
3462 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3463 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3465 x
= XEXP (PATTERN (prev
), 0);
3466 if (set_of (x
, insn
))
3473 /* Analyze INSN with DEPS as a context. */
3475 deps_analyze_insn (struct deps_desc
*deps
, rtx insn
)
3477 if (sched_deps_info
->start_insn
)
3478 sched_deps_info
->start_insn (insn
);
3480 /* Record the condition for this insn. */
3481 if (NONDEBUG_INSN_P (insn
))
3484 sched_get_condition_with_rev (insn
, NULL
);
3485 t
= INSN_CACHED_COND (insn
);
3486 INSN_COND_DEPS (insn
) = NULL_RTX
;
3487 if (reload_completed
3488 && (current_sched_info
->flags
& DO_PREDICATION
)
3490 && REG_P (XEXP (t
, 0))
3491 && CONSTANT_P (XEXP (t
, 1)))
3497 nregs
= hard_regno_nregs
[regno
][GET_MODE (t
)];
3501 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3502 t
= concat_INSN_LIST (reg_last
->sets
, t
);
3503 t
= concat_INSN_LIST (reg_last
->clobbers
, t
);
3504 t
= concat_INSN_LIST (reg_last
->implicit_sets
, t
);
3506 INSN_COND_DEPS (insn
) = t
;
3512 /* Make each JUMP_INSN (but not a speculative check)
3513 a scheduling barrier for memory references. */
3516 && sel_insn_is_speculation_check (insn
)))
3518 /* Keep the list a reasonable size. */
3519 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3520 flush_pending_lists (deps
, insn
, true, true);
3522 deps
->pending_jump_insns
3523 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3526 /* For each insn which shouldn't cross a jump, add a dependence. */
3527 add_dependence_list_and_free (deps
, insn
,
3528 &deps
->sched_before_next_jump
, 1,
3531 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3533 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3535 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3537 else if (CALL_P (insn
))
3541 CANT_MOVE (insn
) = 1;
3543 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3545 /* This is setjmp. Assume that all registers, not just
3546 hard registers, may be clobbered by this call. */
3547 reg_pending_barrier
= MOVE_BARRIER
;
3551 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3552 /* A call may read and modify global register variables. */
3555 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3556 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3558 /* Other call-clobbered hard regs may be clobbered.
3559 Since we only have a choice between 'might be clobbered'
3560 and 'definitely not clobbered', we must include all
3561 partly call-clobbered registers here. */
3562 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3563 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3564 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3565 /* We don't know what set of fixed registers might be used
3566 by the function, but it is certain that the stack pointer
3567 is among them, but be conservative. */
3568 else if (fixed_regs
[i
])
3569 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3570 /* The frame pointer is normally not used by the function
3571 itself, but by the debugger. */
3572 /* ??? MIPS o32 is an exception. It uses the frame pointer
3573 in the macro expansion of jal but does not represent this
3574 fact in the call_insn rtl. */
3575 else if (i
== FRAME_POINTER_REGNUM
3576 || (i
== HARD_FRAME_POINTER_REGNUM
3577 && (! reload_completed
|| frame_pointer_needed
)))
3578 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3581 /* For each insn which shouldn't cross a call, add a dependence
3582 between that insn and this call insn. */
3583 add_dependence_list_and_free (deps
, insn
,
3584 &deps
->sched_before_next_call
, 1,
3587 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3589 /* If CALL would be in a sched group, then this will violate
3590 convention that sched group insns have dependencies only on the
3591 previous instruction.
3593 Of course one can say: "Hey! What about head of the sched group?"
3594 And I will answer: "Basic principles (one dep per insn) are always
3596 gcc_assert (!SCHED_GROUP_P (insn
));
3598 /* In the absence of interprocedural alias analysis, we must flush
3599 all pending reads and writes, and start new dependencies starting
3600 from here. But only flush writes for constant calls (which may
3601 be passed a pointer to something we haven't written yet). */
3602 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3604 if (!deps
->readonly
)
3606 /* Remember the last function call for limiting lifetimes. */
3607 free_INSN_LIST_list (&deps
->last_function_call
);
3608 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3610 if (call_may_noreturn_p (insn
))
3612 /* Remember the last function call that might not always return
3613 normally for limiting moves of trapping insns. */
3614 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3615 deps
->last_function_call_may_noreturn
3616 = alloc_INSN_LIST (insn
, NULL_RTX
);
3619 /* Before reload, begin a post-call group, so as to keep the
3620 lifetimes of hard registers correct. */
3621 if (! reload_completed
)
3622 deps
->in_post_call_group_p
= post_call
;
3626 if (sched_deps_info
->use_cselib
)
3627 cselib_process_insn (insn
);
3629 /* EH_REGION insn notes can not appear until well after we complete
3632 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3633 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3635 if (sched_deps_info
->finish_insn
)
3636 sched_deps_info
->finish_insn ();
3638 /* Fixup the dependencies in the sched group. */
3639 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3640 && chain_to_prev_insn_p (insn
)
3642 chain_to_prev_insn (insn
);
3645 /* Initialize DEPS for the new block beginning with HEAD. */
3647 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3649 gcc_assert (!deps
->readonly
);
3651 /* Before reload, if the previous block ended in a call, show that
3652 we are inside a post-call group, so as to keep the lifetimes of
3653 hard registers correct. */
3654 if (! reload_completed
&& !LABEL_P (head
))
3656 rtx insn
= prev_nonnote_nondebug_insn (head
);
3658 if (insn
&& CALL_P (insn
))
3659 deps
->in_post_call_group_p
= post_call_initial
;
3663 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3664 dependencies for each insn. */
3666 sched_analyze (struct deps_desc
*deps
, rtx head
, rtx tail
)
3670 if (sched_deps_info
->use_cselib
)
3671 cselib_init (CSELIB_RECORD_MEMORY
);
3673 deps_start_bb (deps
, head
);
3675 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3680 /* And initialize deps_lists. */
3681 sd_init_insn (insn
);
3684 deps_analyze_insn (deps
, insn
);
3688 if (sched_deps_info
->use_cselib
)
3696 /* Helper for sched_free_deps ().
3697 Delete INSN's (RESOLVED_P) backward dependencies. */
3699 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3701 sd_iterator_def sd_it
;
3703 sd_list_types_def types
;
3706 types
= SD_LIST_RES_BACK
;
3708 types
= SD_LIST_BACK
;
3710 for (sd_it
= sd_iterator_start (insn
, types
);
3711 sd_iterator_cond (&sd_it
, &dep
);)
3713 dep_link_t link
= *sd_it
.linkp
;
3714 dep_node_t node
= DEP_LINK_NODE (link
);
3715 deps_list_t back_list
;
3716 deps_list_t forw_list
;
3718 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3719 remove_from_deps_list (link
, back_list
);
3720 delete_dep_node (node
);
3724 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3727 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3730 rtx next_tail
= NEXT_INSN (tail
);
3732 /* We make two passes since some insns may be scheduled before their
3733 dependencies are resolved. */
3734 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3735 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3737 /* Clear forward deps and leave the dep_nodes to the
3738 corresponding back_deps list. */
3740 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3742 clear_deps_list (INSN_FORW_DEPS (insn
));
3744 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3745 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3747 /* Clear resolved back deps together with its dep_nodes. */
3748 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3750 sd_finish_insn (insn
);
3754 /* Initialize variables for region data dependence analysis.
3755 When LAZY_REG_LAST is true, do not allocate reg_last array
3756 of struct deps_desc immediately. */
3759 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3761 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3763 deps
->max_reg
= max_reg
;
3765 deps
->reg_last
= NULL
;
3767 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3768 INIT_REG_SET (&deps
->reg_last_in_use
);
3770 deps
->pending_read_insns
= 0;
3771 deps
->pending_read_mems
= 0;
3772 deps
->pending_write_insns
= 0;
3773 deps
->pending_write_mems
= 0;
3774 deps
->pending_jump_insns
= 0;
3775 deps
->pending_read_list_length
= 0;
3776 deps
->pending_write_list_length
= 0;
3777 deps
->pending_flush_length
= 0;
3778 deps
->last_pending_memory_flush
= 0;
3779 deps
->last_function_call
= 0;
3780 deps
->last_function_call_may_noreturn
= 0;
3781 deps
->sched_before_next_call
= 0;
3782 deps
->sched_before_next_jump
= 0;
3783 deps
->in_post_call_group_p
= not_post_call
;
3784 deps
->last_debug_insn
= 0;
3785 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3789 /* Init only reg_last field of DEPS, which was not allocated before as
3790 we inited DEPS lazily. */
3792 init_deps_reg_last (struct deps_desc
*deps
)
3794 gcc_assert (deps
&& deps
->max_reg
> 0);
3795 gcc_assert (deps
->reg_last
== NULL
);
3797 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3801 /* Free insn lists found in DEPS. */
3804 free_deps (struct deps_desc
*deps
)
3807 reg_set_iterator rsi
;
3809 /* We set max_reg to 0 when this context was already freed. */
3810 if (deps
->max_reg
== 0)
3812 gcc_assert (deps
->reg_last
== NULL
);
3817 free_INSN_LIST_list (&deps
->pending_read_insns
);
3818 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3819 free_INSN_LIST_list (&deps
->pending_write_insns
);
3820 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3821 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3823 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3824 times. For a testcase with 42000 regs and 8000 small basic blocks,
3825 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3826 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3828 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3830 free_INSN_LIST_list (®_last
->uses
);
3832 free_INSN_LIST_list (®_last
->sets
);
3833 if (reg_last
->implicit_sets
)
3834 free_INSN_LIST_list (®_last
->implicit_sets
);
3835 if (reg_last
->control_uses
)
3836 free_INSN_LIST_list (®_last
->control_uses
);
3837 if (reg_last
->clobbers
)
3838 free_INSN_LIST_list (®_last
->clobbers
);
3840 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3842 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3844 free (deps
->reg_last
);
3845 deps
->reg_last
= NULL
;
3850 /* Remove INSN from dependence contexts DEPS. */
3852 remove_from_deps (struct deps_desc
*deps
, rtx insn
)
3856 reg_set_iterator rsi
;
3858 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3859 &deps
->pending_read_mems
);
3860 if (!DEBUG_INSN_P (insn
))
3861 deps
->pending_read_list_length
-= removed
;
3862 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3863 &deps
->pending_write_mems
);
3864 deps
->pending_write_list_length
-= removed
;
3866 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
3867 deps
->pending_flush_length
-= removed
;
3868 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3869 deps
->pending_flush_length
-= removed
;
3871 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3873 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3875 remove_from_dependence_list (insn
, ®_last
->uses
);
3877 remove_from_dependence_list (insn
, ®_last
->sets
);
3878 if (reg_last
->implicit_sets
)
3879 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3880 if (reg_last
->clobbers
)
3881 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3882 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3883 && !reg_last
->clobbers
)
3884 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3889 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3890 remove_from_dependence_list (insn
,
3891 &deps
->last_function_call_may_noreturn
);
3893 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3896 /* Init deps data vector. */
3898 init_deps_data_vector (void)
3900 int reserve
= (sched_max_luid
+ 1
3901 - VEC_length (haifa_deps_insn_data_def
, h_d_i_d
));
3903 && ! VEC_space (haifa_deps_insn_data_def
, h_d_i_d
, reserve
))
3904 VEC_safe_grow_cleared (haifa_deps_insn_data_def
, heap
, h_d_i_d
,
3905 3 * sched_max_luid
/ 2);
3908 /* If it is profitable to use them, initialize or extend (depending on
3909 GLOBAL_P) dependency data. */
3911 sched_deps_init (bool global_p
)
3913 /* Average number of insns in the basic block.
3914 '+ 1' is used to make it nonzero. */
3915 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3917 init_deps_data_vector ();
3919 /* We use another caching mechanism for selective scheduling, so
3920 we don't use this one. */
3921 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3923 /* ?!? We could save some memory by computing a per-region luid mapping
3924 which could reduce both the number of vectors in the cache and the
3925 size of each vector. Instead we just avoid the cache entirely unless
3926 the average number of instructions in a basic block is very high. See
3927 the comment before the declaration of true_dependency_cache for
3928 what we consider "very high". */
3930 extend_dependency_caches (sched_max_luid
, true);
3935 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3936 /* Allocate lists for one block at a time. */
3938 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3939 /* Allocate nodes for one block at a time.
3940 We assume that average insn has
3942 5 * insns_in_block
);
3947 /* Create or extend (depending on CREATE_P) dependency caches to
3950 extend_dependency_caches (int n
, bool create_p
)
3952 if (create_p
|| true_dependency_cache
)
3954 int i
, luid
= cache_size
+ n
;
3956 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
3958 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
3959 output_dependency_cache
, luid
);
3960 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
3962 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
3965 if (current_sched_info
->flags
& DO_SPECULATION
)
3966 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
3969 for (i
= cache_size
; i
< luid
; i
++)
3971 bitmap_initialize (&true_dependency_cache
[i
], 0);
3972 bitmap_initialize (&output_dependency_cache
[i
], 0);
3973 bitmap_initialize (&anti_dependency_cache
[i
], 0);
3974 bitmap_initialize (&control_dependency_cache
[i
], 0);
3976 if (current_sched_info
->flags
& DO_SPECULATION
)
3977 bitmap_initialize (&spec_dependency_cache
[i
], 0);
3983 /* Finalize dependency information for the whole function. */
3985 sched_deps_finish (void)
3987 gcc_assert (deps_pools_are_empty_p ());
3988 free_alloc_pool_if_empty (&dn_pool
);
3989 free_alloc_pool_if_empty (&dl_pool
);
3990 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
3992 VEC_free (haifa_deps_insn_data_def
, heap
, h_d_i_d
);
3995 if (true_dependency_cache
)
3999 for (i
= 0; i
< cache_size
; i
++)
4001 bitmap_clear (&true_dependency_cache
[i
]);
4002 bitmap_clear (&output_dependency_cache
[i
]);
4003 bitmap_clear (&anti_dependency_cache
[i
]);
4004 bitmap_clear (&control_dependency_cache
[i
]);
4006 if (sched_deps_info
->generate_spec_deps
)
4007 bitmap_clear (&spec_dependency_cache
[i
]);
4009 free (true_dependency_cache
);
4010 true_dependency_cache
= NULL
;
4011 free (output_dependency_cache
);
4012 output_dependency_cache
= NULL
;
4013 free (anti_dependency_cache
);
4014 anti_dependency_cache
= NULL
;
4015 free (control_dependency_cache
);
4016 control_dependency_cache
= NULL
;
4018 if (sched_deps_info
->generate_spec_deps
)
4020 free (spec_dependency_cache
);
4021 spec_dependency_cache
= NULL
;
4027 /* Initialize some global variables needed by the dependency analysis
4031 init_deps_global (void)
4033 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4034 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4035 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4036 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4037 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4038 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4039 reg_pending_barrier
= NOT_A_BARRIER
;
4041 if (!sel_sched_p () || sched_emulate_haifa_p
)
4043 sched_deps_info
->start_insn
= haifa_start_insn
;
4044 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4046 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4047 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4048 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4050 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4051 sched_deps_info
->note_dep
= haifa_note_dep
;
4055 /* Free everything used by the dependency analysis code. */
4058 finish_deps_global (void)
4060 FREE_REG_SET (reg_pending_sets
);
4061 FREE_REG_SET (reg_pending_clobbers
);
4062 FREE_REG_SET (reg_pending_uses
);
4063 FREE_REG_SET (reg_pending_control_uses
);
4066 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4068 estimate_dep_weak (rtx mem1
, rtx mem2
)
4073 /* MEMs are the same - don't speculate. */
4074 return MIN_DEP_WEAK
;
4076 r1
= XEXP (mem1
, 0);
4077 r2
= XEXP (mem2
, 0);
4080 || (REG_P (r1
) && REG_P (r2
)
4081 && REGNO (r1
) == REGNO (r2
)))
4082 /* Again, MEMs are the same. */
4083 return MIN_DEP_WEAK
;
4084 else if ((REG_P (r1
) && !REG_P (r2
))
4085 || (!REG_P (r1
) && REG_P (r2
)))
4086 /* Different addressing modes - reason to be more speculative,
4088 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4090 /* We can't say anything about the dependence. */
4091 return UNCERTAIN_DEP_WEAK
;
4094 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4095 This function can handle same INSN and ELEM (INSN == ELEM).
4096 It is a convenience wrapper. */
4098 add_dependence_1 (rtx insn
, rtx elem
, enum reg_note dep_type
)
4103 if (dep_type
== REG_DEP_TRUE
)
4105 else if (dep_type
== REG_DEP_OUTPUT
)
4107 else if (dep_type
== REG_DEP_CONTROL
)
4111 gcc_assert (dep_type
== REG_DEP_ANTI
);
4115 /* When add_dependence is called from inside sched-deps.c, we expect
4116 cur_insn to be non-null. */
4117 internal
= cur_insn
!= NULL
;
4119 gcc_assert (insn
== cur_insn
);
4123 note_dep (elem
, ds
);
4128 /* Return weakness of speculative type TYPE in the dep_status DS. */
4130 get_dep_weak_1 (ds_t ds
, ds_t type
)
4136 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4137 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4138 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4139 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4140 default: gcc_unreachable ();
4147 get_dep_weak (ds_t ds
, ds_t type
)
4149 dw_t dw
= get_dep_weak_1 (ds
, type
);
4151 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4155 /* Return the dep_status, which has the same parameters as DS, except for
4156 speculative type TYPE, that will have weakness DW. */
4158 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4160 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4165 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4166 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4167 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4168 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4169 default: gcc_unreachable ();
4174 /* Return the join of two dep_statuses DS1 and DS2.
4175 If MAX_P is true then choose the greater probability,
4176 otherwise multiply probabilities.
4177 This function assumes that both DS1 and DS2 contain speculative bits. */
4179 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4183 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4185 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4187 t
= FIRST_SPEC_TYPE
;
4190 if ((ds1
& t
) && !(ds2
& t
))
4192 else if (!(ds1
& t
) && (ds2
& t
))
4194 else if ((ds1
& t
) && (ds2
& t
))
4196 dw_t dw1
= get_dep_weak (ds1
, t
);
4197 dw_t dw2
= get_dep_weak (ds2
, t
);
4202 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4204 if (dw
< MIN_DEP_WEAK
)
4215 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4218 if (t
== LAST_SPEC_TYPE
)
4220 t
<<= SPEC_TYPE_SHIFT
;
4227 /* Return the join of two dep_statuses DS1 and DS2.
4228 This function assumes that both DS1 and DS2 contain speculative bits. */
4230 ds_merge (ds_t ds1
, ds_t ds2
)
4232 return ds_merge_1 (ds1
, ds2
, false);
4235 /* Return the join of two dep_statuses DS1 and DS2. */
4237 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4239 ds_t new_status
= ds
| ds2
;
4241 if (new_status
& SPECULATIVE
)
4243 if ((ds
&& !(ds
& SPECULATIVE
))
4244 || (ds2
&& !(ds2
& SPECULATIVE
)))
4245 /* Then this dep can't be speculative. */
4246 new_status
&= ~SPECULATIVE
;
4249 /* Both are speculative. Merging probabilities. */
4254 dw
= estimate_dep_weak (mem1
, mem2
);
4255 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4263 new_status
= ds_merge (ds2
, ds
);
4270 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4273 ds_max_merge (ds_t ds1
, ds_t ds2
)
4275 if (ds1
== 0 && ds2
== 0)
4278 if (ds1
== 0 && ds2
!= 0)
4281 if (ds1
!= 0 && ds2
== 0)
4284 return ds_merge_1 (ds1
, ds2
, true);
4287 /* Return the probability of speculation success for the speculation
4295 dt
= FIRST_SPEC_TYPE
;
4300 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4304 if (dt
== LAST_SPEC_TYPE
)
4306 dt
<<= SPEC_TYPE_SHIFT
;
4312 res
/= MAX_DEP_WEAK
;
4314 if (res
< MIN_DEP_WEAK
)
4317 gcc_assert (res
<= MAX_DEP_WEAK
);
4322 /* Return a dep status that contains all speculation types of DS. */
4324 ds_get_speculation_types (ds_t ds
)
4326 if (ds
& BEGIN_DATA
)
4328 if (ds
& BE_IN_DATA
)
4330 if (ds
& BEGIN_CONTROL
)
4331 ds
|= BEGIN_CONTROL
;
4332 if (ds
& BE_IN_CONTROL
)
4333 ds
|= BE_IN_CONTROL
;
4335 return ds
& SPECULATIVE
;
4338 /* Return a dep status that contains maximal weakness for each speculation
4339 type present in DS. */
4341 ds_get_max_dep_weak (ds_t ds
)
4343 if (ds
& BEGIN_DATA
)
4344 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4345 if (ds
& BE_IN_DATA
)
4346 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4347 if (ds
& BEGIN_CONTROL
)
4348 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4349 if (ds
& BE_IN_CONTROL
)
4350 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4355 /* Dump information about the dependence status S. */
4357 dump_ds (FILE *f
, ds_t s
)
4362 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4364 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4365 if (s
& BEGIN_CONTROL
)
4366 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4367 if (s
& BE_IN_CONTROL
)
4368 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4371 fprintf (f
, "HARD_DEP; ");
4374 fprintf (f
, "DEP_TRUE; ");
4376 fprintf (f
, "DEP_OUTPUT; ");
4378 fprintf (f
, "DEP_ANTI; ");
4379 if (s
& DEP_CONTROL
)
4380 fprintf (f
, "DEP_CONTROL; ");
4388 dump_ds (stderr
, s
);
4389 fprintf (stderr
, "\n");
4392 #ifdef ENABLE_CHECKING
4393 /* Verify that dependence type and status are consistent.
4394 If RELAXED_P is true, then skip dep_weakness checks. */
4396 check_dep (dep_t dep
, bool relaxed_p
)
4398 enum reg_note dt
= DEP_TYPE (dep
);
4399 ds_t ds
= DEP_STATUS (dep
);
4401 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4403 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4405 gcc_assert (ds
== 0);
4409 /* Check that dependence type contains the same bits as the status. */
4410 if (dt
== REG_DEP_TRUE
)
4411 gcc_assert (ds
& DEP_TRUE
);
4412 else if (dt
== REG_DEP_OUTPUT
)
4413 gcc_assert ((ds
& DEP_OUTPUT
)
4414 && !(ds
& DEP_TRUE
));
4415 else if (dt
== REG_DEP_ANTI
)
4416 gcc_assert ((ds
& DEP_ANTI
)
4417 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4419 gcc_assert (dt
== REG_DEP_CONTROL
4420 && (ds
& DEP_CONTROL
)
4421 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4423 /* HARD_DEP can not appear in dep_status of a link. */
4424 gcc_assert (!(ds
& HARD_DEP
));
4426 /* Check that dependence status is set correctly when speculation is not
4428 if (!sched_deps_info
->generate_spec_deps
)
4429 gcc_assert (!(ds
& SPECULATIVE
));
4430 else if (ds
& SPECULATIVE
)
4434 ds_t type
= FIRST_SPEC_TYPE
;
4436 /* Check that dependence weakness is in proper range. */
4440 get_dep_weak (ds
, type
);
4442 if (type
== LAST_SPEC_TYPE
)
4444 type
<<= SPEC_TYPE_SHIFT
;
4449 if (ds
& BEGIN_SPEC
)
4451 /* Only true dependence can be data speculative. */
4452 if (ds
& BEGIN_DATA
)
4453 gcc_assert (ds
& DEP_TRUE
);
4455 /* Control dependencies in the insn scheduler are represented by
4456 anti-dependencies, therefore only anti dependence can be
4457 control speculative. */
4458 if (ds
& BEGIN_CONTROL
)
4459 gcc_assert (ds
& DEP_ANTI
);
4463 /* Subsequent speculations should resolve true dependencies. */
4464 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4467 /* Check that true and anti dependencies can't have other speculative
4470 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4471 /* An output dependence can't be speculative at all. */
4472 gcc_assert (!(ds
& DEP_OUTPUT
));
4474 gcc_assert (ds
& BEGIN_CONTROL
);
4477 #endif /* ENABLE_CHECKING */
4479 #endif /* INSN_SCHEDULING */