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
5 Free Software Foundation, Inc.
6 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
7 and currently maintained by, Jim Wilson (wilson@cygnus.com)
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
32 #include "hard-reg-set.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
41 #include "sched-int.h"
47 #ifdef INSN_SCHEDULING
49 #ifdef ENABLE_CHECKING
55 /* Holds current parameters for the dependency analyzer. */
56 struct sched_deps_info_def
*sched_deps_info
;
58 /* The data is specific to the Haifa scheduler. */
59 VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
= NULL
;
61 /* Return the major type present in the DS. */
69 return REG_DEP_OUTPUT
;
71 gcc_assert (ds
& DEP_ANTI
);
76 /* Return equivalent dep_status. */
78 dk_to_ds (enum reg_note dk
)
89 gcc_assert (dk
== REG_DEP_ANTI
);
94 /* Functions to operate with dependence information container - dep_t. */
96 /* Init DEP with the arguments. */
98 init_dep_1 (dep_t dep
, rtx pro
, rtx con
, enum reg_note type
, ds_t ds
)
102 DEP_TYPE (dep
) = type
;
103 DEP_STATUS (dep
) = ds
;
106 /* Init DEP with the arguments.
107 While most of the scheduler (including targets) only need the major type
108 of the dependency, it is convenient to hide full dep_status from them. */
110 init_dep (dep_t dep
, rtx pro
, rtx con
, enum reg_note kind
)
114 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
115 ds
= dk_to_ds (kind
);
119 init_dep_1 (dep
, pro
, con
, kind
, ds
);
122 /* Make a copy of FROM in TO. */
124 copy_dep (dep_t to
, dep_t from
)
126 memcpy (to
, from
, sizeof (*to
));
129 static void dump_ds (FILE *, ds_t
);
131 /* Define flags for dump_dep (). */
133 /* Dump producer of the dependence. */
134 #define DUMP_DEP_PRO (2)
136 /* Dump consumer of the dependence. */
137 #define DUMP_DEP_CON (4)
139 /* Dump type of the dependence. */
140 #define DUMP_DEP_TYPE (8)
142 /* Dump status of the dependence. */
143 #define DUMP_DEP_STATUS (16)
145 /* Dump all information about the dependence. */
146 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
150 FLAGS is a bit mask specifying what information about DEP needs
152 If FLAGS has the very first bit set, then dump all information about DEP
153 and propagate this bit into the callee dump functions. */
155 dump_dep (FILE *dump
, dep_t dep
, int flags
)
158 flags
|= DUMP_DEP_ALL
;
162 if (flags
& DUMP_DEP_PRO
)
163 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
165 if (flags
& DUMP_DEP_CON
)
166 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
168 if (flags
& DUMP_DEP_TYPE
)
171 enum reg_note type
= DEP_TYPE (dep
);
192 fprintf (dump
, "%c; ", t
);
195 if (flags
& DUMP_DEP_STATUS
)
197 if (current_sched_info
->flags
& USE_DEPS_LIST
)
198 dump_ds (dump
, DEP_STATUS (dep
));
204 /* Default flags for dump_dep (). */
205 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
207 /* Dump all fields of DEP to STDERR. */
209 sd_debug_dep (dep_t dep
)
211 dump_dep (stderr
, dep
, 1);
212 fprintf (stderr
, "\n");
215 /* Determine whether DEP is a dependency link of a non-debug insn on a
219 depl_on_debug_p (dep_link_t dep
)
221 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
222 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
225 /* Functions to operate with a single link from the dependencies lists -
228 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
231 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
233 dep_link_t next
= *prev_nextp
;
235 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
236 && DEP_LINK_NEXT (l
) == NULL
);
238 /* Init node being inserted. */
239 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
240 DEP_LINK_NEXT (l
) = next
;
245 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
247 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
254 /* Add dep_link LINK to deps_list L. */
256 add_to_deps_list (dep_link_t link
, deps_list_t l
)
258 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
260 /* Don't count debug deps. */
261 if (!depl_on_debug_p (link
))
262 ++DEPS_LIST_N_LINKS (l
);
265 /* Detach dep_link L from the list. */
267 detach_dep_link (dep_link_t l
)
269 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
270 dep_link_t next
= DEP_LINK_NEXT (l
);
275 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
277 DEP_LINK_PREV_NEXTP (l
) = NULL
;
278 DEP_LINK_NEXT (l
) = NULL
;
281 /* Remove link LINK from list LIST. */
283 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
285 detach_dep_link (link
);
287 /* Don't count debug deps. */
288 if (!depl_on_debug_p (link
))
289 --DEPS_LIST_N_LINKS (list
);
292 /* Move link LINK from list FROM to list TO. */
294 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
296 remove_from_deps_list (link
, from
);
297 add_to_deps_list (link
, to
);
300 /* Return true of LINK is not attached to any list. */
302 dep_link_is_detached_p (dep_link_t link
)
304 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
307 /* Pool to hold all dependency nodes (dep_node_t). */
308 static alloc_pool dn_pool
;
310 /* Number of dep_nodes out there. */
311 static int dn_pool_diff
= 0;
313 /* Create a dep_node. */
315 create_dep_node (void)
317 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
318 dep_link_t back
= DEP_NODE_BACK (n
);
319 dep_link_t forw
= DEP_NODE_FORW (n
);
321 DEP_LINK_NODE (back
) = n
;
322 DEP_LINK_NEXT (back
) = NULL
;
323 DEP_LINK_PREV_NEXTP (back
) = NULL
;
325 DEP_LINK_NODE (forw
) = n
;
326 DEP_LINK_NEXT (forw
) = NULL
;
327 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
334 /* Delete dep_node N. N must not be connected to any deps_list. */
336 delete_dep_node (dep_node_t n
)
338 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
339 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
343 pool_free (dn_pool
, n
);
346 /* Pool to hold dependencies lists (deps_list_t). */
347 static alloc_pool dl_pool
;
349 /* Number of deps_lists out there. */
350 static int dl_pool_diff
= 0;
352 /* Functions to operate with dependences lists - deps_list_t. */
354 /* Return true if list L is empty. */
356 deps_list_empty_p (deps_list_t l
)
358 return DEPS_LIST_N_LINKS (l
) == 0;
361 /* Create a new deps_list. */
363 create_deps_list (void)
365 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
367 DEPS_LIST_FIRST (l
) = NULL
;
368 DEPS_LIST_N_LINKS (l
) = 0;
374 /* Free deps_list L. */
376 free_deps_list (deps_list_t l
)
378 gcc_assert (deps_list_empty_p (l
));
382 pool_free (dl_pool
, l
);
385 /* Return true if there is no dep_nodes and deps_lists out there.
386 After the region is scheduled all the dependency nodes and lists
387 should [generally] be returned to pool. */
389 deps_pools_are_empty_p (void)
391 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
394 /* Remove all elements from L. */
396 clear_deps_list (deps_list_t l
)
400 dep_link_t link
= DEPS_LIST_FIRST (l
);
405 remove_from_deps_list (link
, l
);
410 static regset reg_pending_sets
;
411 static regset reg_pending_clobbers
;
412 static regset reg_pending_uses
;
413 static enum reg_pending_barrier_mode reg_pending_barrier
;
415 /* Hard registers implicitly clobbered or used (or may be implicitly
416 clobbered or used) by the currently analyzed insn. For example,
417 insn in its constraint has one register class. Even if there is
418 currently no hard register in the insn, the particular hard
419 register will be in the insn after reload pass because the
420 constraint requires it. */
421 static HARD_REG_SET implicit_reg_pending_clobbers
;
422 static HARD_REG_SET implicit_reg_pending_uses
;
424 /* To speed up the test for duplicate dependency links we keep a
425 record of dependencies created by add_dependence when the average
426 number of instructions in a basic block is very large.
428 Studies have shown that there is typically around 5 instructions between
429 branches for typical C code. So we can make a guess that the average
430 basic block is approximately 5 instructions long; we will choose 100X
431 the average size as a very large basic block.
433 Each insn has associated bitmaps for its dependencies. Each bitmap
434 has enough entries to represent a dependency on any other insn in
435 the insn chain. All bitmap for true dependencies cache is
436 allocated then the rest two ones are also allocated. */
437 static bitmap_head
*true_dependency_cache
= NULL
;
438 static bitmap_head
*output_dependency_cache
= NULL
;
439 static bitmap_head
*anti_dependency_cache
= NULL
;
440 static bitmap_head
*spec_dependency_cache
= NULL
;
441 static int cache_size
;
443 static int deps_may_trap_p (const_rtx
);
444 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
);
445 static void add_dependence_list_and_free (struct deps_desc
*, rtx
,
446 rtx
*, int, enum reg_note
);
447 static void delete_all_dependences (rtx
);
448 static void fixup_sched_groups (rtx
);
450 static void flush_pending_lists (struct deps_desc
*, rtx
, int, int);
451 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx
);
452 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx
);
453 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx
);
455 static bool sched_has_condition_p (const_rtx
);
456 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
458 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
460 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
462 #ifdef ENABLE_CHECKING
463 static void check_dep (dep_t
, bool);
466 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
469 deps_may_trap_p (const_rtx mem
)
471 const_rtx addr
= XEXP (mem
, 0);
473 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
475 const_rtx t
= get_reg_known_value (REGNO (addr
));
479 return rtx_addr_can_trap_p (addr
);
483 /* Find the condition under which INSN is executed. If REV is not NULL,
484 it is set to TRUE when the returned comparison should be reversed
485 to get the actual condition. */
487 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
489 rtx pat
= PATTERN (insn
);
498 if (GET_CODE (pat
) == COND_EXEC
)
499 return COND_EXEC_TEST (pat
);
501 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
504 src
= SET_SRC (pc_set (insn
));
506 if (XEXP (src
, 2) == pc_rtx
)
507 return XEXP (src
, 0);
508 else if (XEXP (src
, 1) == pc_rtx
)
510 rtx cond
= XEXP (src
, 0);
511 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
513 if (revcode
== UNKNOWN
)
524 /* True when we can find a condition under which INSN is executed. */
526 sched_has_condition_p (const_rtx insn
)
528 return !! sched_get_condition_with_rev (insn
, NULL
);
533 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
535 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
537 if (COMPARISON_P (cond1
)
538 && COMPARISON_P (cond2
)
539 && GET_CODE (cond1
) ==
541 ? reversed_comparison_code (cond2
, NULL
)
543 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
544 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
549 /* Return true if insn1 and insn2 can never depend on one another because
550 the conditions under which they are executed are mutually exclusive. */
552 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
555 bool rev1
= false, rev2
= false;
557 /* df doesn't handle conditional lifetimes entirely correctly;
558 calls mess up the conditional lifetimes. */
559 if (!CALL_P (insn1
) && !CALL_P (insn2
))
561 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
562 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
564 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
565 /* Make sure first instruction doesn't affect condition of second
566 instruction if switched. */
567 && !modified_in_p (cond1
, insn2
)
568 /* Make sure second instruction doesn't affect condition of first
569 instruction if switched. */
570 && !modified_in_p (cond2
, insn1
))
577 /* Return true if INSN can potentially be speculated with type DS. */
579 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
581 if (HAS_INTERNAL_DEP (insn
))
584 if (!NONJUMP_INSN_P (insn
))
587 if (SCHED_GROUP_P (insn
))
590 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
593 if (side_effects_p (PATTERN (insn
)))
597 /* The following instructions, which depend on a speculatively scheduled
598 instruction, cannot be speculatively scheduled along. */
600 if (may_trap_p (PATTERN (insn
)))
601 /* If instruction might trap, it cannot be speculatively scheduled.
602 For control speculation it's obvious why and for data speculation
603 it's because the insn might get wrong input if speculation
604 wasn't successful. */
607 if ((ds
& BE_IN_DATA
)
608 && sched_has_condition_p (insn
))
609 /* If this is a predicated instruction, then it cannot be
610 speculatively scheduled. See PR35659. */
617 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
618 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
619 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
620 This function is used to switch sd_iterator to the next list.
621 !!! For internal use only. Might consider moving it to sched-int.h. */
623 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
624 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
626 sd_list_types_def types
= *types_ptr
;
628 if (types
& SD_LIST_HARD_BACK
)
630 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
631 *resolved_p_ptr
= false;
632 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
634 else if (types
& SD_LIST_SPEC_BACK
)
636 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
637 *resolved_p_ptr
= false;
638 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
640 else if (types
& SD_LIST_FORW
)
642 *list_ptr
= INSN_FORW_DEPS (insn
);
643 *resolved_p_ptr
= false;
644 *types_ptr
= types
& ~SD_LIST_FORW
;
646 else if (types
& SD_LIST_RES_BACK
)
648 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
649 *resolved_p_ptr
= true;
650 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
652 else if (types
& SD_LIST_RES_FORW
)
654 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
655 *resolved_p_ptr
= true;
656 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
661 *resolved_p_ptr
= false;
662 *types_ptr
= SD_LIST_NONE
;
666 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
668 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
672 while (list_types
!= SD_LIST_NONE
)
677 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
679 size
+= DEPS_LIST_N_LINKS (list
);
685 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
688 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
690 while (list_types
!= SD_LIST_NONE
)
695 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
696 if (!deps_list_empty_p (list
))
703 /* Initialize data for INSN. */
705 sd_init_insn (rtx insn
)
707 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
708 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
709 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
710 INSN_FORW_DEPS (insn
) = create_deps_list ();
711 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
713 if (DEBUG_INSN_P (insn
))
714 DEBUG_INSN_SCHED_P (insn
) = TRUE
;
716 /* ??? It would be nice to allocate dependency caches here. */
719 /* Free data for INSN. */
721 sd_finish_insn (rtx insn
)
723 /* ??? It would be nice to deallocate dependency caches here. */
725 if (DEBUG_INSN_P (insn
))
727 gcc_assert (DEBUG_INSN_SCHED_P (insn
));
728 DEBUG_INSN_SCHED_P (insn
) = FALSE
;
731 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
732 INSN_HARD_BACK_DEPS (insn
) = NULL
;
734 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
735 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
737 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
738 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
740 free_deps_list (INSN_FORW_DEPS (insn
));
741 INSN_FORW_DEPS (insn
) = NULL
;
743 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
744 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
747 /* Find a dependency between producer PRO and consumer CON.
748 Search through resolved dependency lists if RESOLVED_P is true.
749 If no such dependency is found return NULL,
750 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
751 with an iterator pointing to it. */
753 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
754 sd_iterator_def
*sd_it_ptr
)
756 sd_list_types_def pro_list_type
;
757 sd_list_types_def con_list_type
;
758 sd_iterator_def sd_it
;
760 bool found_p
= false;
764 pro_list_type
= SD_LIST_RES_FORW
;
765 con_list_type
= SD_LIST_RES_BACK
;
769 pro_list_type
= SD_LIST_FORW
;
770 con_list_type
= SD_LIST_BACK
;
773 /* Walk through either back list of INSN or forw list of ELEM
774 depending on which one is shorter. */
775 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
777 /* Find the dep_link with producer PRO in consumer's back_deps. */
778 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
779 if (DEP_PRO (dep
) == pro
)
787 /* Find the dep_link with consumer CON in producer's forw_deps. */
788 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
789 if (DEP_CON (dep
) == con
)
798 if (sd_it_ptr
!= NULL
)
807 /* Find a dependency between producer PRO and consumer CON.
808 Use dependency [if available] to check if dependency is present at all.
809 Search through resolved dependency lists if RESOLVED_P is true.
810 If the dependency or NULL if none found. */
812 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
814 if (true_dependency_cache
!= NULL
)
815 /* Avoiding the list walk below can cut compile times dramatically
818 int elem_luid
= INSN_LUID (pro
);
819 int insn_luid
= INSN_LUID (con
);
821 gcc_assert (output_dependency_cache
!= NULL
822 && anti_dependency_cache
!= NULL
);
824 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
825 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
826 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
830 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
833 /* Add or update a dependence described by DEP.
834 MEM1 and MEM2, if non-null, correspond to memory locations in case of
837 The function returns a value indicating if an old entry has been changed
838 or a new entry has been added to insn's backward deps.
840 This function merely checks if producer and consumer is the same insn
841 and doesn't create a dep in this case. Actual manipulation of
842 dependence data structures is performed in add_or_update_dep_1. */
843 static enum DEPS_ADJUST_RESULT
844 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
846 rtx elem
= DEP_PRO (dep
);
847 rtx insn
= DEP_CON (dep
);
849 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
851 /* Don't depend an insn on itself. */
854 if (sched_deps_info
->generate_spec_deps
)
855 /* INSN has an internal dependence, which we can't overcome. */
856 HAS_INTERNAL_DEP (insn
) = 1;
861 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
864 /* Ask dependency caches what needs to be done for dependence DEP.
865 Return DEP_CREATED if new dependence should be created and there is no
866 need to try to find one searching the dependencies lists.
867 Return DEP_PRESENT if there already is a dependence described by DEP and
868 hence nothing is to be done.
869 Return DEP_CHANGED if there already is a dependence, but it should be
870 updated to incorporate additional information from DEP. */
871 static enum DEPS_ADJUST_RESULT
872 ask_dependency_caches (dep_t dep
)
874 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
875 int insn_luid
= INSN_LUID (DEP_CON (dep
));
877 gcc_assert (true_dependency_cache
!= NULL
878 && output_dependency_cache
!= NULL
879 && anti_dependency_cache
!= NULL
);
881 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
883 enum reg_note present_dep_type
;
885 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
886 present_dep_type
= REG_DEP_TRUE
;
887 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
888 present_dep_type
= REG_DEP_OUTPUT
;
889 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
890 present_dep_type
= REG_DEP_ANTI
;
892 /* There is no existing dep so it should be created. */
895 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
896 /* DEP does not add anything to the existing dependence. */
901 ds_t present_dep_types
= 0;
903 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
904 present_dep_types
|= DEP_TRUE
;
905 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
906 present_dep_types
|= DEP_OUTPUT
;
907 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
908 present_dep_types
|= DEP_ANTI
;
910 if (present_dep_types
== 0)
911 /* There is no existing dep so it should be created. */
914 if (!(current_sched_info
->flags
& DO_SPECULATION
)
915 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
917 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
918 == present_dep_types
)
919 /* DEP does not add anything to the existing dependence. */
924 /* Only true dependencies can be data speculative and
925 only anti dependencies can be control speculative. */
926 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
927 == present_dep_types
);
929 /* if (DEP is SPECULATIVE) then
930 ..we should update DEP_STATUS
932 ..we should reset existing dep to non-speculative. */
939 /* Set dependency caches according to DEP. */
941 set_dependency_caches (dep_t dep
)
943 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
944 int insn_luid
= INSN_LUID (DEP_CON (dep
));
946 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
948 switch (DEP_TYPE (dep
))
951 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
955 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
959 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
968 ds_t ds
= DEP_STATUS (dep
);
971 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
973 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
975 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
977 if (ds
& SPECULATIVE
)
979 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
980 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
985 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
986 caches accordingly. */
988 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
990 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
991 int insn_luid
= INSN_LUID (DEP_CON (dep
));
993 /* Clear corresponding cache entry because type of the link
994 may have changed. Keep them if we use_deps_list. */
995 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1000 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1004 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1012 set_dependency_caches (dep
);
1015 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1017 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1019 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1020 dep_link_t link
= DEP_NODE_BACK (node
);
1021 dep_t dep
= DEP_NODE_DEP (node
);
1022 rtx elem
= DEP_PRO (dep
);
1023 rtx insn
= DEP_CON (dep
);
1025 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1027 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1029 if (true_dependency_cache
!= NULL
)
1030 /* Clear the cache entry. */
1031 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1035 /* Update DEP to incorporate information from NEW_DEP.
1036 SD_IT points to DEP in case it should be moved to another list.
1037 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1038 data-speculative dependence should be updated. */
1039 static enum DEPS_ADJUST_RESULT
1040 update_dep (dep_t dep
, dep_t new_dep
,
1041 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1042 rtx mem1 ATTRIBUTE_UNUSED
,
1043 rtx mem2 ATTRIBUTE_UNUSED
)
1045 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1046 enum reg_note old_type
= DEP_TYPE (dep
);
1048 /* If this is a more restrictive type of dependence than the
1049 existing one, then change the existing dependence to this
1051 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1053 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1057 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1058 /* Update DEP_STATUS. */
1060 ds_t dep_status
= DEP_STATUS (dep
);
1061 ds_t ds
= DEP_STATUS (new_dep
);
1062 ds_t new_status
= ds
| dep_status
;
1064 if (new_status
& SPECULATIVE
)
1065 /* Either existing dep or a dep we're adding or both are
1068 if (!(ds
& SPECULATIVE
)
1069 || !(dep_status
& SPECULATIVE
))
1070 /* The new dep can't be speculative. */
1072 new_status
&= ~SPECULATIVE
;
1074 if (dep_status
& SPECULATIVE
)
1075 /* The old dep was speculative, but now it
1077 change_spec_dep_to_hard (sd_it
);
1081 /* Both are speculative. Merge probabilities. */
1086 dw
= estimate_dep_weak (mem1
, mem2
);
1087 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1090 new_status
= ds_merge (dep_status
, ds
);
1096 if (dep_status
!= ds
)
1098 DEP_STATUS (dep
) = ds
;
1103 if (true_dependency_cache
!= NULL
1104 && res
== DEP_CHANGED
)
1105 update_dependency_caches (dep
, old_type
);
1110 /* Add or update a dependence described by DEP.
1111 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1114 The function returns a value indicating if an old entry has been changed
1115 or a new entry has been added to insn's backward deps or nothing has
1116 been updated at all. */
1117 static enum DEPS_ADJUST_RESULT
1118 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1119 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1121 bool maybe_present_p
= true;
1122 bool present_p
= false;
1124 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1125 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1127 #ifdef ENABLE_CHECKING
1128 check_dep (new_dep
, mem1
!= NULL
);
1131 if (true_dependency_cache
!= NULL
)
1133 switch (ask_dependency_caches (new_dep
))
1139 maybe_present_p
= true;
1144 maybe_present_p
= false;
1154 /* Check that we don't already have this dependence. */
1155 if (maybe_present_p
)
1158 sd_iterator_def sd_it
;
1160 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1162 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1164 resolved_p
, &sd_it
);
1166 if (present_dep
!= NULL
)
1167 /* We found an existing dependency between ELEM and INSN. */
1168 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1170 /* We didn't find a dep, it shouldn't present in the cache. */
1171 gcc_assert (!present_p
);
1174 /* Might want to check one level of transitivity to save conses.
1175 This check should be done in maybe_add_or_update_dep_1.
1176 Since we made it to add_or_update_dep_1, we must create
1177 (or update) a link. */
1179 if (mem1
!= NULL_RTX
)
1181 gcc_assert (sched_deps_info
->generate_spec_deps
);
1182 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1183 estimate_dep_weak (mem1
, mem2
));
1186 sd_add_dep (new_dep
, resolved_p
);
1191 /* Initialize BACK_LIST_PTR with consumer's backward list and
1192 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1193 initialize with lists that hold resolved deps. */
1195 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1196 deps_list_t
*back_list_ptr
,
1197 deps_list_t
*forw_list_ptr
)
1199 rtx con
= DEP_CON (dep
);
1203 if ((current_sched_info
->flags
& DO_SPECULATION
)
1204 && (DEP_STATUS (dep
) & SPECULATIVE
))
1205 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1207 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1209 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1213 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1214 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1218 /* Add dependence described by DEP.
1219 If RESOLVED_P is true treat the dependence as a resolved one. */
1221 sd_add_dep (dep_t dep
, bool resolved_p
)
1223 dep_node_t n
= create_dep_node ();
1224 deps_list_t con_back_deps
;
1225 deps_list_t pro_forw_deps
;
1226 rtx elem
= DEP_PRO (dep
);
1227 rtx insn
= DEP_CON (dep
);
1229 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1231 if ((current_sched_info
->flags
& DO_SPECULATION
)
1232 && !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1233 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1235 copy_dep (DEP_NODE_DEP (n
), dep
);
1237 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1239 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1241 #ifdef ENABLE_CHECKING
1242 check_dep (dep
, false);
1245 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1247 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1248 in the bitmap caches of dependency information. */
1249 if (true_dependency_cache
!= NULL
)
1250 set_dependency_caches (dep
);
1253 /* Add or update backward dependence between INSN and ELEM
1254 with given type DEP_TYPE and dep_status DS.
1255 This function is a convenience wrapper. */
1256 enum DEPS_ADJUST_RESULT
1257 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1259 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1262 /* Resolved dependence pointed to by SD_IT.
1263 SD_IT will advance to the next element. */
1265 sd_resolve_dep (sd_iterator_def sd_it
)
1267 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1268 dep_t dep
= DEP_NODE_DEP (node
);
1269 rtx pro
= DEP_PRO (dep
);
1270 rtx con
= DEP_CON (dep
);
1272 if ((current_sched_info
->flags
& DO_SPECULATION
)
1273 && (DEP_STATUS (dep
) & SPECULATIVE
))
1274 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1275 INSN_RESOLVED_BACK_DEPS (con
));
1277 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1278 INSN_RESOLVED_BACK_DEPS (con
));
1280 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1281 INSN_RESOLVED_FORW_DEPS (pro
));
1284 /* Make TO depend on all the FROM's producers.
1285 If RESOLVED_P is true add dependencies to the resolved lists. */
1287 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1289 sd_list_types_def list_type
;
1290 sd_iterator_def sd_it
;
1293 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1295 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1297 dep_def _new_dep
, *new_dep
= &_new_dep
;
1299 copy_dep (new_dep
, dep
);
1300 DEP_CON (new_dep
) = to
;
1301 sd_add_dep (new_dep
, resolved_p
);
1305 /* Remove a dependency referred to by SD_IT.
1306 SD_IT will point to the next dependence after removal. */
1308 sd_delete_dep (sd_iterator_def sd_it
)
1310 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1311 dep_t dep
= DEP_NODE_DEP (n
);
1312 rtx pro
= DEP_PRO (dep
);
1313 rtx con
= DEP_CON (dep
);
1314 deps_list_t con_back_deps
;
1315 deps_list_t pro_forw_deps
;
1317 if (true_dependency_cache
!= NULL
)
1319 int elem_luid
= INSN_LUID (pro
);
1320 int insn_luid
= INSN_LUID (con
);
1322 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1323 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1324 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1326 if (current_sched_info
->flags
& DO_SPECULATION
)
1327 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1330 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1331 &con_back_deps
, &pro_forw_deps
);
1333 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1334 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1336 delete_dep_node (n
);
1339 /* Dump size of the lists. */
1340 #define DUMP_LISTS_SIZE (2)
1342 /* Dump dependencies of the lists. */
1343 #define DUMP_LISTS_DEPS (4)
1345 /* Dump all information about the lists. */
1346 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1348 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1349 FLAGS is a bit mask specifying what information about the lists needs
1351 If FLAGS has the very first bit set, then dump all information about
1352 the lists and propagate this bit into the callee dump functions. */
1354 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1356 sd_iterator_def sd_it
;
1363 flags
|= DUMP_LISTS_ALL
;
1365 fprintf (dump
, "[");
1367 if (flags
& DUMP_LISTS_SIZE
)
1368 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1370 if (flags
& DUMP_LISTS_DEPS
)
1372 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1374 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1375 fprintf (dump
, " ");
1380 /* Dump all information about deps_lists of INSN specified by TYPES
1383 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1385 dump_lists (stderr
, insn
, types
, 1);
1386 fprintf (stderr
, "\n");
1389 /* A convenience wrapper to operate on an entire list. */
1392 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
)
1394 for (; list
; list
= XEXP (list
, 1))
1396 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1397 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1401 /* Similar, but free *LISTP at the same time, when the context
1405 add_dependence_list_and_free (struct deps_desc
*deps
, rtx insn
, rtx
*listp
,
1406 int uncond
, enum reg_note dep_type
)
1410 /* We don't want to short-circuit dependencies involving debug
1411 insns, because they may cause actual dependencies to be
1413 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1415 add_dependence_list (insn
, *listp
, uncond
, dep_type
);
1419 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
1421 next
= XEXP (list
, 1);
1422 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1423 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1424 free_INSN_LIST_node (list
);
1428 /* Remove all occurences of INSN from LIST. Return the number of
1429 occurences removed. */
1432 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1438 if (XEXP (*listp
, 0) == insn
)
1440 remove_free_INSN_LIST_node (listp
);
1445 listp
= &XEXP (*listp
, 1);
1451 /* Same as above, but process two lists at once. */
1453 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1459 if (XEXP (*listp
, 0) == insn
)
1461 remove_free_INSN_LIST_node (listp
);
1462 remove_free_EXPR_LIST_node (exprp
);
1467 listp
= &XEXP (*listp
, 1);
1468 exprp
= &XEXP (*exprp
, 1);
1474 /* Clear all dependencies for an insn. */
1476 delete_all_dependences (rtx insn
)
1478 sd_iterator_def sd_it
;
1481 /* The below cycle can be optimized to clear the caches and back_deps
1482 in one call but that would provoke duplication of code from
1485 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1486 sd_iterator_cond (&sd_it
, &dep
);)
1487 sd_delete_dep (sd_it
);
1490 /* All insns in a scheduling group except the first should only have
1491 dependencies on the previous insn in the group. So we find the
1492 first instruction in the scheduling group by walking the dependence
1493 chains backwards. Then we add the dependencies for the group to
1494 the previous nonnote insn. */
1497 fixup_sched_groups (rtx insn
)
1499 sd_iterator_def sd_it
;
1503 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1506 rtx pro
= DEP_PRO (dep
);
1510 i
= prev_nonnote_insn (i
);
1514 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1516 if (! sched_insns_conditions_mutex_p (i
, pro
))
1517 add_dependence (i
, pro
, DEP_TYPE (dep
));
1521 delete_all_dependences (insn
);
1523 prev_nonnote
= prev_nonnote_insn (insn
);
1524 while (DEBUG_INSN_P (prev_nonnote
))
1525 prev_nonnote
= prev_nonnote_insn (prev_nonnote
);
1526 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1527 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1528 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1531 /* Process an insn's memory dependencies. There are four kinds of
1534 (0) read dependence: read follows read
1535 (1) true dependence: read follows write
1536 (2) output dependence: write follows write
1537 (3) anti dependence: write follows read
1539 We are careful to build only dependencies which actually exist, and
1540 use transitivity to avoid building too many links. */
1542 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1543 The MEM is a memory reference contained within INSN, which we are saving
1544 so that we can do memory aliasing on it. */
1547 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1554 gcc_assert (!deps
->readonly
);
1557 insn_list
= &deps
->pending_read_insns
;
1558 mem_list
= &deps
->pending_read_mems
;
1559 if (!DEBUG_INSN_P (insn
))
1560 deps
->pending_read_list_length
++;
1564 insn_list
= &deps
->pending_write_insns
;
1565 mem_list
= &deps
->pending_write_mems
;
1566 deps
->pending_write_list_length
++;
1569 link
= alloc_INSN_LIST (insn
, *insn_list
);
1572 if (sched_deps_info
->use_cselib
)
1574 mem
= shallow_copy_rtx (mem
);
1575 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
1577 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1581 /* Make a dependency between every memory reference on the pending lists
1582 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1583 dependencies for a read operation, similarly with FOR_WRITE. */
1586 flush_pending_lists (struct deps_desc
*deps
, rtx insn
, int for_read
,
1591 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1593 if (!deps
->readonly
)
1595 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1596 deps
->pending_read_list_length
= 0;
1600 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1601 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1603 add_dependence_list_and_free (deps
, insn
,
1604 &deps
->last_pending_memory_flush
, 1,
1605 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1606 if (!deps
->readonly
)
1608 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1609 deps
->pending_write_list_length
= 0;
1611 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1612 deps
->pending_flush_length
= 1;
1616 /* Instruction which dependencies we are analyzing. */
1617 static rtx cur_insn
= NULL_RTX
;
1619 /* Implement hooks for haifa scheduler. */
1622 haifa_start_insn (rtx insn
)
1624 gcc_assert (insn
&& !cur_insn
);
1630 haifa_finish_insn (void)
1636 haifa_note_reg_set (int regno
)
1638 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1642 haifa_note_reg_clobber (int regno
)
1644 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1648 haifa_note_reg_use (int regno
)
1650 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1654 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1656 if (!(ds
& SPECULATIVE
))
1659 pending_mem
= NULL_RTX
;
1662 gcc_assert (ds
& BEGIN_DATA
);
1665 dep_def _dep
, *dep
= &_dep
;
1667 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1668 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: -1);
1669 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1675 haifa_note_dep (rtx elem
, ds_t ds
)
1680 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1681 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1685 note_reg_use (int r
)
1687 if (sched_deps_info
->note_reg_use
)
1688 sched_deps_info
->note_reg_use (r
);
1692 note_reg_set (int r
)
1694 if (sched_deps_info
->note_reg_set
)
1695 sched_deps_info
->note_reg_set (r
);
1699 note_reg_clobber (int r
)
1701 if (sched_deps_info
->note_reg_clobber
)
1702 sched_deps_info
->note_reg_clobber (r
);
1706 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1708 if (sched_deps_info
->note_mem_dep
)
1709 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1713 note_dep (rtx e
, ds_t ds
)
1715 if (sched_deps_info
->note_dep
)
1716 sched_deps_info
->note_dep (e
, ds
);
1719 /* Return corresponding to DS reg_note. */
1724 return REG_DEP_TRUE
;
1725 else if (ds
& DEP_OUTPUT
)
1726 return REG_DEP_OUTPUT
;
1729 gcc_assert (ds
& DEP_ANTI
);
1730 return REG_DEP_ANTI
;
1736 /* Functions for computation of info needed for register pressure
1737 sensitive insn scheduling. */
1740 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1741 static struct reg_use_data
*
1742 create_insn_reg_use (int regno
, rtx insn
)
1744 struct reg_use_data
*use
;
1746 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1749 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1750 INSN_REG_USE_LIST (insn
) = use
;
1754 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1755 static struct reg_set_data
*
1756 create_insn_reg_set (int regno
, rtx insn
)
1758 struct reg_set_data
*set
;
1760 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1763 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1764 INSN_REG_SET_LIST (insn
) = set
;
1768 /* Set up insn register uses for INSN and dependency context DEPS. */
1770 setup_insn_reg_uses (struct deps_desc
*deps
, rtx insn
)
1773 reg_set_iterator rsi
;
1775 struct reg_use_data
*use
, *use2
, *next
;
1776 struct deps_reg
*reg_last
;
1778 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1780 if (i
< FIRST_PSEUDO_REGISTER
1781 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1784 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1785 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1786 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1787 /* Ignore use which is not dying. */
1790 use
= create_insn_reg_use (i
, insn
);
1791 use
->next_regno_use
= use
;
1792 reg_last
= &deps
->reg_last
[i
];
1794 /* Create the cycle list of uses. */
1795 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1797 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1798 next
= use
->next_regno_use
;
1799 use
->next_regno_use
= use2
;
1800 use2
->next_regno_use
= next
;
1805 /* Register pressure info for the currently processed insn. */
1806 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1808 /* Return TRUE if INSN has the use structure for REGNO. */
1810 insn_use_p (rtx insn
, int regno
)
1812 struct reg_use_data
*use
;
1814 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1815 if (use
->regno
== regno
)
1820 /* Update the register pressure info after birth of pseudo register REGNO
1821 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
1822 the register is in clobber or unused after the insn. */
1824 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
1829 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1830 cl
= sched_regno_cover_class
[regno
];
1833 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1836 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
1837 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1841 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
1842 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1846 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
1847 reg_pressure_info
[cl
].set_increase
= new_incr
;
1848 if (! insn_use_p (insn
, regno
))
1849 reg_pressure_info
[cl
].change
+= incr
;
1850 create_insn_reg_set (regno
, insn
);
1852 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1856 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
1857 hard registers involved in the birth. */
1859 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
1860 bool clobber_p
, bool unused_p
)
1863 int new_incr
, last
= regno
+ nregs
;
1865 while (regno
< last
)
1867 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1868 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1870 cl
= sched_regno_cover_class
[regno
];
1875 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
1876 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1880 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
1881 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1885 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
1886 reg_pressure_info
[cl
].set_increase
= new_incr
;
1887 if (! insn_use_p (insn
, regno
))
1888 reg_pressure_info
[cl
].change
+= 1;
1889 create_insn_reg_set (regno
, insn
);
1891 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1898 /* Update the register pressure info after birth of pseudo or hard
1899 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
1900 correspondingly that the register is in clobber or unused after the
1903 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
1907 if (GET_CODE (reg
) == SUBREG
)
1908 reg
= SUBREG_REG (reg
);
1913 regno
= REGNO (reg
);
1914 if (regno
< FIRST_PSEUDO_REGISTER
)
1915 mark_insn_hard_regno_birth (insn
, regno
,
1916 hard_regno_nregs
[regno
][GET_MODE (reg
)],
1917 clobber_p
, unused_p
);
1919 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
1922 /* Update the register pressure info after death of pseudo register
1925 mark_pseudo_death (int regno
)
1930 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1931 cl
= sched_regno_cover_class
[regno
];
1934 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1935 reg_pressure_info
[cl
].change
-= incr
;
1939 /* Like mark_pseudo_death except that NREGS saying how many hard
1940 registers involved in the death. */
1942 mark_hard_regno_death (int regno
, int nregs
)
1945 int last
= regno
+ nregs
;
1947 while (regno
< last
)
1949 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1950 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1952 cl
= sched_regno_cover_class
[regno
];
1954 reg_pressure_info
[cl
].change
-= 1;
1960 /* Update the register pressure info after death of pseudo or hard
1963 mark_reg_death (rtx reg
)
1967 if (GET_CODE (reg
) == SUBREG
)
1968 reg
= SUBREG_REG (reg
);
1973 regno
= REGNO (reg
);
1974 if (regno
< FIRST_PSEUDO_REGISTER
)
1975 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1977 mark_pseudo_death (regno
);
1980 /* Process SETTER of REG. DATA is an insn containing the setter. */
1982 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
1984 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
1987 ((rtx
) data
, reg
, false,
1988 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
1991 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
1993 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1995 if (GET_CODE (setter
) == CLOBBER
)
1996 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
1999 /* Set up reg pressure info related to INSN. */
2001 setup_insn_reg_pressure_info (rtx insn
)
2005 static struct reg_pressure_data
*pressure_info
;
2008 gcc_assert (sched_pressure_p
);
2010 if (! INSN_P (insn
))
2013 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2015 cl
= ira_reg_class_cover
[i
];
2016 reg_pressure_info
[cl
].clobber_increase
= 0;
2017 reg_pressure_info
[cl
].set_increase
= 0;
2018 reg_pressure_info
[cl
].unused_set_increase
= 0;
2019 reg_pressure_info
[cl
].change
= 0;
2022 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2024 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2027 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2028 if (REG_NOTE_KIND (link
) == REG_INC
)
2029 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2032 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2033 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2034 mark_reg_death (XEXP (link
, 0));
2036 len
= sizeof (struct reg_pressure_data
) * ira_reg_class_cover_size
;
2038 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2039 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_reg_class_cover_size
2041 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2043 cl
= ira_reg_class_cover
[i
];
2044 pressure_info
[i
].clobber_increase
2045 = reg_pressure_info
[cl
].clobber_increase
;
2046 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2047 pressure_info
[i
].unused_set_increase
2048 = reg_pressure_info
[cl
].unused_set_increase
;
2049 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2056 /* Internal variable for sched_analyze_[12] () functions.
2057 If it is nonzero, this means that sched_analyze_[12] looks
2058 at the most toplevel SET. */
2059 static bool can_start_lhs_rhs_p
;
2061 /* Extend reg info for the deps context DEPS given that
2062 we have just generated a register numbered REGNO. */
2064 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2066 int max_regno
= regno
+ 1;
2068 gcc_assert (!reload_completed
);
2070 /* In a readonly context, it would not hurt to extend info,
2071 but it should not be needed. */
2072 if (reload_completed
&& deps
->readonly
)
2074 deps
->max_reg
= max_regno
;
2078 if (max_regno
> deps
->max_reg
)
2080 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2082 memset (&deps
->reg_last
[deps
->max_reg
],
2083 0, (max_regno
- deps
->max_reg
)
2084 * sizeof (struct deps_reg
));
2085 deps
->max_reg
= max_regno
;
2089 /* Extends REG_INFO_P if needed. */
2091 maybe_extend_reg_info_p (void)
2093 /* Extend REG_INFO_P, if needed. */
2094 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2096 size_t new_reg_info_p_size
= max_regno
+ 128;
2098 gcc_assert (!reload_completed
&& sel_sched_p ());
2100 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2101 new_reg_info_p_size
,
2103 sizeof (*reg_info_p
));
2104 reg_info_p_size
= new_reg_info_p_size
;
2108 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2109 The type of the reference is specified by REF and can be SET,
2110 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2113 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2114 enum rtx_code ref
, rtx insn
)
2116 /* We could emit new pseudos in renaming. Extend the reg structures. */
2117 if (!reload_completed
&& sel_sched_p ()
2118 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2119 extend_deps_reg_info (deps
, regno
);
2121 maybe_extend_reg_info_p ();
2123 /* A hard reg in a wide mode may really be multiple registers.
2124 If so, mark all of them just like the first. */
2125 if (regno
< FIRST_PSEUDO_REGISTER
)
2127 int i
= hard_regno_nregs
[regno
][mode
];
2131 note_reg_set (regno
+ i
);
2133 else if (ref
== USE
)
2136 note_reg_use (regno
+ i
);
2141 note_reg_clobber (regno
+ i
);
2145 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2146 it does not reload. Ignore these as they have served their
2148 else if (regno
>= deps
->max_reg
)
2150 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2151 gcc_assert (code
== USE
|| code
== CLOBBER
);
2157 note_reg_set (regno
);
2158 else if (ref
== USE
)
2159 note_reg_use (regno
);
2161 note_reg_clobber (regno
);
2163 /* Pseudos that are REG_EQUIV to something may be replaced
2164 by that during reloading. We need only add dependencies for
2165 the address in the REG_EQUIV note. */
2166 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2168 rtx t
= get_reg_known_value (regno
);
2170 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2173 /* Don't let it cross a call after scheduling if it doesn't
2174 already cross one. */
2175 if (REG_N_CALLS_CROSSED (regno
) == 0)
2177 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2178 deps
->sched_before_next_call
2179 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2181 add_dependence_list (insn
, deps
->last_function_call
, 1,
2187 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2188 rtx, X, creating all dependencies generated by the write to the
2189 destination of X, and reads of everything mentioned. */
2192 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2194 rtx dest
= XEXP (x
, 0);
2195 enum rtx_code code
= GET_CODE (x
);
2196 bool cslr_p
= can_start_lhs_rhs_p
;
2198 can_start_lhs_rhs_p
= false;
2204 if (cslr_p
&& sched_deps_info
->start_lhs
)
2205 sched_deps_info
->start_lhs (dest
);
2207 if (GET_CODE (dest
) == PARALLEL
)
2211 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2212 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2213 sched_analyze_1 (deps
,
2214 gen_rtx_CLOBBER (VOIDmode
,
2215 XEXP (XVECEXP (dest
, 0, i
), 0)),
2218 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2219 sched_deps_info
->finish_lhs ();
2223 can_start_lhs_rhs_p
= cslr_p
;
2225 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2227 can_start_lhs_rhs_p
= false;
2233 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2234 || GET_CODE (dest
) == ZERO_EXTRACT
)
2236 if (GET_CODE (dest
) == STRICT_LOW_PART
2237 || GET_CODE (dest
) == ZERO_EXTRACT
2238 || df_read_modify_subreg_p (dest
))
2240 /* These both read and modify the result. We must handle
2241 them as writes to get proper dependencies for following
2242 instructions. We must handle them as reads to get proper
2243 dependencies from this to previous instructions.
2244 Thus we need to call sched_analyze_2. */
2246 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2248 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2250 /* The second and third arguments are values read by this insn. */
2251 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2252 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2254 dest
= XEXP (dest
, 0);
2259 int regno
= REGNO (dest
);
2260 enum machine_mode mode
= GET_MODE (dest
);
2262 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2265 /* Treat all writes to a stack register as modifying the TOS. */
2266 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2270 /* Avoid analyzing the same register twice. */
2271 if (regno
!= FIRST_STACK_REG
)
2272 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2274 nregs
= hard_regno_nregs
[FIRST_STACK_REG
][mode
];
2275 while (--nregs
>= 0)
2276 SET_HARD_REG_BIT (implicit_reg_pending_uses
,
2277 FIRST_STACK_REG
+ nregs
);
2281 else if (MEM_P (dest
))
2283 /* Writing memory. */
2286 if (sched_deps_info
->use_cselib
)
2288 enum machine_mode address_mode
2289 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (dest
));
2291 t
= shallow_copy_rtx (dest
);
2292 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1, insn
);
2293 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2297 /* Pending lists can't get larger with a readonly context. */
2299 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2300 > MAX_PENDING_LIST_LENGTH
))
2302 /* Flush all pending reads and writes to prevent the pending lists
2303 from getting any larger. Insn scheduling runs too slowly when
2304 these lists get long. When compiling GCC with itself,
2305 this flush occurs 8 times for sparc, and 10 times for m88k using
2306 the default value of 32. */
2307 flush_pending_lists (deps
, insn
, false, true);
2311 rtx pending
, pending_mem
;
2313 pending
= deps
->pending_read_insns
;
2314 pending_mem
= deps
->pending_read_mems
;
2317 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2318 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2319 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2322 pending
= XEXP (pending
, 1);
2323 pending_mem
= XEXP (pending_mem
, 1);
2326 pending
= deps
->pending_write_insns
;
2327 pending_mem
= deps
->pending_write_mems
;
2330 if (output_dependence (XEXP (pending_mem
, 0), t
)
2331 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2332 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2335 pending
= XEXP (pending
, 1);
2336 pending_mem
= XEXP (pending_mem
, 1);
2339 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2342 if (!deps
->readonly
)
2343 add_insn_mem_dependence (deps
, false, insn
, dest
);
2345 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2348 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2349 sched_deps_info
->finish_lhs ();
2351 /* Analyze reads. */
2352 if (GET_CODE (x
) == SET
)
2354 can_start_lhs_rhs_p
= cslr_p
;
2356 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2358 can_start_lhs_rhs_p
= false;
2362 /* Analyze the uses of memory and registers in rtx X in INSN. */
2364 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2370 bool cslr_p
= can_start_lhs_rhs_p
;
2372 can_start_lhs_rhs_p
= false;
2378 if (cslr_p
&& sched_deps_info
->start_rhs
)
2379 sched_deps_info
->start_rhs (x
);
2381 code
= GET_CODE (x
);
2392 /* Ignore constants. */
2393 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2394 sched_deps_info
->finish_rhs ();
2400 /* User of CC0 depends on immediately preceding insn. */
2401 SCHED_GROUP_P (insn
) = 1;
2402 /* Don't move CC0 setter to another block (it can set up the
2403 same flag for previous CC0 users which is safe). */
2404 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2406 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2407 sched_deps_info
->finish_rhs ();
2414 int regno
= REGNO (x
);
2415 enum machine_mode mode
= GET_MODE (x
);
2417 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2420 /* Treat all reads of a stack register as modifying the TOS. */
2421 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2423 /* Avoid analyzing the same register twice. */
2424 if (regno
!= FIRST_STACK_REG
)
2425 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2426 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2430 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2431 sched_deps_info
->finish_rhs ();
2438 /* Reading memory. */
2440 rtx pending
, pending_mem
;
2443 if (sched_deps_info
->use_cselib
)
2445 enum machine_mode address_mode
2446 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (t
));
2448 t
= shallow_copy_rtx (t
);
2449 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1, insn
);
2450 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2453 if (!DEBUG_INSN_P (insn
))
2456 pending
= deps
->pending_read_insns
;
2457 pending_mem
= deps
->pending_read_mems
;
2460 if (read_dependence (XEXP (pending_mem
, 0), t
)
2461 && ! sched_insns_conditions_mutex_p (insn
,
2463 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2466 pending
= XEXP (pending
, 1);
2467 pending_mem
= XEXP (pending_mem
, 1);
2470 pending
= deps
->pending_write_insns
;
2471 pending_mem
= deps
->pending_write_mems
;
2474 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
2476 && ! sched_insns_conditions_mutex_p (insn
,
2478 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2479 sched_deps_info
->generate_spec_deps
2480 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2482 pending
= XEXP (pending
, 1);
2483 pending_mem
= XEXP (pending_mem
, 1);
2486 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2488 if (! JUMP_P (XEXP (u
, 0)))
2489 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2490 else if (deps_may_trap_p (x
))
2492 if ((sched_deps_info
->generate_spec_deps
)
2493 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2495 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2498 note_dep (XEXP (u
, 0), ds
);
2501 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2506 /* Always add these dependencies to pending_reads, since
2507 this insn may be followed by a write. */
2508 if (!deps
->readonly
)
2509 add_insn_mem_dependence (deps
, true, insn
, x
);
2511 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2513 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2514 sched_deps_info
->finish_rhs ();
2519 /* Force pending stores to memory in case a trap handler needs them. */
2521 flush_pending_lists (deps
, insn
, true, false);
2525 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2526 reg_pending_barrier
= TRUE_BARRIER
;
2529 case UNSPEC_VOLATILE
:
2530 flush_pending_lists (deps
, insn
, true, true);
2536 /* Traditional and volatile asm instructions must be considered to use
2537 and clobber all hard registers, all pseudo-registers and all of
2538 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2540 Consider for instance a volatile asm that changes the fpu rounding
2541 mode. An insn should not be moved across this even if it only uses
2542 pseudo-regs because it might give an incorrectly rounded result. */
2543 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2544 reg_pending_barrier
= TRUE_BARRIER
;
2546 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2547 We can not just fall through here since then we would be confused
2548 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2549 traditional asms unlike their normal usage. */
2551 if (code
== ASM_OPERANDS
)
2553 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2554 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2556 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2557 sched_deps_info
->finish_rhs ();
2568 /* These both read and modify the result. We must handle them as writes
2569 to get proper dependencies for following instructions. We must handle
2570 them as reads to get proper dependencies from this to previous
2571 instructions. Thus we need to pass them to both sched_analyze_1
2572 and sched_analyze_2. We must call sched_analyze_2 first in order
2573 to get the proper antecedent for the read. */
2574 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2575 sched_analyze_1 (deps
, x
, insn
);
2577 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2578 sched_deps_info
->finish_rhs ();
2584 /* op0 = op0 + op1 */
2585 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2586 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2587 sched_analyze_1 (deps
, x
, insn
);
2589 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2590 sched_deps_info
->finish_rhs ();
2598 /* Other cases: walk the insn. */
2599 fmt
= GET_RTX_FORMAT (code
);
2600 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2603 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2604 else if (fmt
[i
] == 'E')
2605 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2606 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2609 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2610 sched_deps_info
->finish_rhs ();
2613 /* Analyze an INSN with pattern X to find all dependencies. */
2615 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx insn
)
2617 RTX_CODE code
= GET_CODE (x
);
2620 reg_set_iterator rsi
;
2622 if (! reload_completed
)
2626 extract_insn (insn
);
2627 preprocess_constraints ();
2628 ira_implicitly_set_insn_hard_regs (&temp
);
2629 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2630 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2633 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2637 /* Avoid moving trapping instructions accross function calls that might
2638 not always return. */
2639 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2642 if (code
== COND_EXEC
)
2644 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2646 /* ??? Should be recording conditions so we reduce the number of
2647 false dependencies. */
2648 x
= COND_EXEC_CODE (x
);
2649 code
= GET_CODE (x
);
2651 if (code
== SET
|| code
== CLOBBER
)
2653 sched_analyze_1 (deps
, x
, insn
);
2655 /* Bare clobber insns are used for letting life analysis, reg-stack
2656 and others know that a value is dead. Depend on the last call
2657 instruction so that reg-stack won't get confused. */
2658 if (code
== CLOBBER
)
2659 add_dependence_list (insn
, deps
->last_function_call
, 1,
2662 else if (code
== PARALLEL
)
2664 for (i
= XVECLEN (x
, 0); i
--;)
2666 rtx sub
= XVECEXP (x
, 0, i
);
2667 code
= GET_CODE (sub
);
2669 if (code
== COND_EXEC
)
2671 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2672 sub
= COND_EXEC_CODE (sub
);
2673 code
= GET_CODE (sub
);
2675 if (code
== SET
|| code
== CLOBBER
)
2676 sched_analyze_1 (deps
, sub
, insn
);
2678 sched_analyze_2 (deps
, sub
, insn
);
2682 sched_analyze_2 (deps
, x
, insn
);
2684 /* Mark registers CLOBBERED or used by called function. */
2687 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2689 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2690 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2692 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2694 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2695 reg_pending_barrier
= MOVE_BARRIER
;
2701 next
= next_nonnote_insn (insn
);
2702 while (next
&& DEBUG_INSN_P (next
))
2703 next
= next_nonnote_insn (next
);
2704 if (next
&& BARRIER_P (next
))
2705 reg_pending_barrier
= MOVE_BARRIER
;
2708 rtx pending
, pending_mem
;
2710 if (sched_deps_info
->compute_jump_reg_dependencies
)
2712 regset_head tmp_uses
, tmp_sets
;
2713 INIT_REG_SET (&tmp_uses
);
2714 INIT_REG_SET (&tmp_sets
);
2716 (*sched_deps_info
->compute_jump_reg_dependencies
)
2717 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
2718 /* Make latency of jump equal to 0 by using anti-dependence. */
2719 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
, rsi
)
2721 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2722 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2723 add_dependence_list (insn
, reg_last
->implicit_sets
,
2725 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2728 if (!deps
->readonly
)
2730 reg_last
->uses_length
++;
2731 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2734 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
2736 CLEAR_REG_SET (&tmp_uses
);
2737 CLEAR_REG_SET (&tmp_sets
);
2740 /* All memory writes and volatile reads must happen before the
2741 jump. Non-volatile reads must happen before the jump iff
2742 the result is needed by the above register used mask. */
2744 pending
= deps
->pending_write_insns
;
2745 pending_mem
= deps
->pending_write_mems
;
2748 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2749 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2750 pending
= XEXP (pending
, 1);
2751 pending_mem
= XEXP (pending_mem
, 1);
2754 pending
= deps
->pending_read_insns
;
2755 pending_mem
= deps
->pending_read_mems
;
2758 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2759 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2760 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2761 pending
= XEXP (pending
, 1);
2762 pending_mem
= XEXP (pending_mem
, 1);
2765 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2770 /* If this instruction can throw an exception, then moving it changes
2771 where block boundaries fall. This is mighty confusing elsewhere.
2772 Therefore, prevent such an instruction from being moved. Same for
2773 non-jump instructions that define block boundaries.
2774 ??? Unclear whether this is still necessary in EBB mode. If not,
2775 add_branch_dependences should be adjusted for RGN mode instead. */
2776 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2777 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2778 reg_pending_barrier
= MOVE_BARRIER
;
2780 if (sched_pressure_p
)
2782 setup_insn_reg_uses (deps
, insn
);
2783 setup_insn_reg_pressure_info (insn
);
2786 /* Add register dependencies for insn. */
2787 if (DEBUG_INSN_P (insn
))
2789 rtx prev
= deps
->last_debug_insn
;
2792 if (!deps
->readonly
)
2793 deps
->last_debug_insn
= insn
;
2796 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2798 add_dependence_list (insn
, deps
->last_function_call
, 1,
2801 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2802 if (! JUMP_P (XEXP (u
, 0))
2804 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2806 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2808 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2809 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
);
2810 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
);
2812 if (!deps
->readonly
)
2813 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2815 CLEAR_REG_SET (reg_pending_uses
);
2817 /* Quite often, a debug insn will refer to stuff in the
2818 previous instruction, but the reason we want this
2819 dependency here is to make sure the scheduler doesn't
2820 gratuitously move a debug insn ahead. This could dirty
2821 DF flags and cause additional analysis that wouldn't have
2822 occurred in compilation without debug insns, and such
2823 additional analysis can modify the generated code. */
2824 prev
= PREV_INSN (insn
);
2826 if (prev
&& NONDEBUG_INSN_P (prev
))
2827 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2831 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2833 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2834 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2835 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
);
2836 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2838 if (!deps
->readonly
)
2840 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2841 reg_last
->uses_length
++;
2845 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2846 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
2848 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2849 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2850 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2852 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2854 if (!deps
->readonly
)
2856 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2857 reg_last
->uses_length
++;
2861 /* If the current insn is conditional, we can't free any
2863 if (sched_has_condition_p (insn
))
2865 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2867 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2868 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2869 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2871 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2873 if (!deps
->readonly
)
2876 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2877 reg_last
->clobbers_length
++;
2880 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2882 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2883 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2884 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2886 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2887 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2889 if (!deps
->readonly
)
2891 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2892 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2898 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2900 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2901 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
2902 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
2904 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2906 add_dependence_list_and_free (deps
, insn
,
2907 ®_last
->implicit_sets
, 0,
2909 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2911 add_dependence_list_and_free
2912 (deps
, insn
, ®_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2914 if (!deps
->readonly
)
2916 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2917 reg_last
->clobbers_length
= 0;
2918 reg_last
->uses_length
= 0;
2923 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2924 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2926 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2929 if (!deps
->readonly
)
2931 reg_last
->clobbers_length
++;
2933 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2936 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2938 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2940 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2942 add_dependence_list_and_free (deps
, insn
,
2943 ®_last
->implicit_sets
,
2945 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
2947 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2950 if (!deps
->readonly
)
2952 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2953 reg_last
->uses_length
= 0;
2954 reg_last
->clobbers_length
= 0;
2955 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2961 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2962 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2964 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2965 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2966 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
);
2967 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2969 if (!deps
->readonly
)
2970 reg_last
->implicit_sets
2971 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
2974 if (!deps
->readonly
)
2976 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
2977 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
2978 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
2979 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2980 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
2981 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2982 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
2984 /* Set up the pending barrier found. */
2985 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
2988 CLEAR_REG_SET (reg_pending_uses
);
2989 CLEAR_REG_SET (reg_pending_clobbers
);
2990 CLEAR_REG_SET (reg_pending_sets
);
2991 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
2992 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
2994 /* Add dependencies if a scheduling barrier was found. */
2995 if (reg_pending_barrier
)
2997 /* In the case of barrier the most added dependencies are not
2998 real, so we use anti-dependence here. */
2999 if (sched_has_condition_p (insn
))
3001 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3003 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3004 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3005 add_dependence_list (insn
, reg_last
->sets
, 0,
3006 reg_pending_barrier
== TRUE_BARRIER
3007 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3008 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3010 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3011 reg_pending_barrier
== TRUE_BARRIER
3012 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3017 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3019 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3020 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3022 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3023 reg_pending_barrier
== TRUE_BARRIER
3024 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3025 add_dependence_list_and_free (deps
, insn
,
3026 ®_last
->implicit_sets
, 0,
3028 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3029 reg_pending_barrier
== TRUE_BARRIER
3030 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3032 if (!deps
->readonly
)
3034 reg_last
->uses_length
= 0;
3035 reg_last
->clobbers_length
= 0;
3040 if (!deps
->readonly
)
3041 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3043 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3044 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3045 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3048 /* Flush pending lists on jumps, but not on speculative checks. */
3049 if (JUMP_P (insn
) && !(sel_sched_p ()
3050 && sel_insn_is_speculation_check (insn
)))
3051 flush_pending_lists (deps
, insn
, true, true);
3053 if (!deps
->readonly
)
3054 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3055 reg_pending_barrier
= NOT_A_BARRIER
;
3058 /* If a post-call group is still open, see if it should remain so.
3059 This insn must be a simple move of a hard reg to a pseudo or
3062 We must avoid moving these insns for correctness on targets
3063 with small register classes, and for special registers like
3064 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3065 hard regs for all targets. */
3067 if (deps
->in_post_call_group_p
)
3069 rtx tmp
, set
= single_set (insn
);
3070 int src_regno
, dest_regno
;
3074 if (DEBUG_INSN_P (insn
))
3075 /* We don't want to mark debug insns as part of the same
3076 sched group. We know they really aren't, but if we use
3077 debug insns to tell that a call group is over, we'll
3078 get different code if debug insns are not there and
3079 instructions that follow seem like they should be part
3082 Also, if we did, fixup_sched_groups() would move the
3083 deps of the debug insn to the call insn, modifying
3084 non-debug post-dependency counts of the debug insn
3085 dependencies and otherwise messing with the scheduling
3088 Instead, let such debug insns be scheduled freely, but
3089 keep the call group open in case there are insns that
3090 should be part of it afterwards. Since we grant debug
3091 insns higher priority than even sched group insns, it
3092 will all turn out all right. */
3093 goto debug_dont_end_call_group
;
3095 goto end_call_group
;
3098 tmp
= SET_DEST (set
);
3099 if (GET_CODE (tmp
) == SUBREG
)
3100 tmp
= SUBREG_REG (tmp
);
3102 dest_regno
= REGNO (tmp
);
3104 goto end_call_group
;
3106 tmp
= SET_SRC (set
);
3107 if (GET_CODE (tmp
) == SUBREG
)
3108 tmp
= SUBREG_REG (tmp
);
3109 if ((GET_CODE (tmp
) == PLUS
3110 || GET_CODE (tmp
) == MINUS
)
3111 && REG_P (XEXP (tmp
, 0))
3112 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3113 && dest_regno
== STACK_POINTER_REGNUM
)
3114 src_regno
= STACK_POINTER_REGNUM
;
3115 else if (REG_P (tmp
))
3116 src_regno
= REGNO (tmp
);
3118 goto end_call_group
;
3120 if (src_regno
< FIRST_PSEUDO_REGISTER
3121 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3124 && deps
->in_post_call_group_p
== post_call_initial
)
3125 deps
->in_post_call_group_p
= post_call
;
3127 if (!sel_sched_p () || sched_emulate_haifa_p
)
3129 SCHED_GROUP_P (insn
) = 1;
3130 CANT_MOVE (insn
) = 1;
3136 if (!deps
->readonly
)
3137 deps
->in_post_call_group_p
= not_post_call
;
3141 debug_dont_end_call_group
:
3142 if ((current_sched_info
->flags
& DO_SPECULATION
)
3143 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3144 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3148 sel_mark_hard_insn (insn
);
3151 sd_iterator_def sd_it
;
3154 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3155 sd_iterator_cond (&sd_it
, &dep
);)
3156 change_spec_dep_to_hard (sd_it
);
3161 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3162 longjmp, loop forever, ...). */
3164 call_may_noreturn_p (rtx insn
)
3168 /* const or pure calls that aren't looping will always return. */
3169 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3170 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3173 call
= PATTERN (insn
);
3174 if (GET_CODE (call
) == PARALLEL
)
3175 call
= XVECEXP (call
, 0, 0);
3176 if (GET_CODE (call
) == SET
)
3177 call
= SET_SRC (call
);
3178 if (GET_CODE (call
) == CALL
3179 && MEM_P (XEXP (call
, 0))
3180 && GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3182 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3183 if (SYMBOL_REF_DECL (symbol
)
3184 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3186 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3188 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3191 case BUILT_IN_BCOPY
:
3192 case BUILT_IN_BZERO
:
3193 case BUILT_IN_INDEX
:
3194 case BUILT_IN_MEMCHR
:
3195 case BUILT_IN_MEMCMP
:
3196 case BUILT_IN_MEMCPY
:
3197 case BUILT_IN_MEMMOVE
:
3198 case BUILT_IN_MEMPCPY
:
3199 case BUILT_IN_MEMSET
:
3200 case BUILT_IN_RINDEX
:
3201 case BUILT_IN_STPCPY
:
3202 case BUILT_IN_STPNCPY
:
3203 case BUILT_IN_STRCAT
:
3204 case BUILT_IN_STRCHR
:
3205 case BUILT_IN_STRCMP
:
3206 case BUILT_IN_STRCPY
:
3207 case BUILT_IN_STRCSPN
:
3208 case BUILT_IN_STRLEN
:
3209 case BUILT_IN_STRNCAT
:
3210 case BUILT_IN_STRNCMP
:
3211 case BUILT_IN_STRNCPY
:
3212 case BUILT_IN_STRPBRK
:
3213 case BUILT_IN_STRRCHR
:
3214 case BUILT_IN_STRSPN
:
3215 case BUILT_IN_STRSTR
:
3216 /* Assume certain string/memory builtins always return. */
3224 /* For all other calls assume that they might not always return. */
3228 /* Analyze INSN with DEPS as a context. */
3230 deps_analyze_insn (struct deps_desc
*deps
, rtx insn
)
3232 if (sched_deps_info
->start_insn
)
3233 sched_deps_info
->start_insn (insn
);
3235 if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
) || JUMP_P (insn
))
3237 /* Make each JUMP_INSN (but not a speculative check)
3238 a scheduling barrier for memory references. */
3242 && sel_insn_is_speculation_check (insn
)))
3244 /* Keep the list a reasonable size. */
3245 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3246 flush_pending_lists (deps
, insn
, true, true);
3248 deps
->last_pending_memory_flush
3249 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
3252 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3254 else if (CALL_P (insn
))
3258 CANT_MOVE (insn
) = 1;
3260 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3262 /* This is setjmp. Assume that all registers, not just
3263 hard registers, may be clobbered by this call. */
3264 reg_pending_barrier
= MOVE_BARRIER
;
3268 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3269 /* A call may read and modify global register variables. */
3272 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3273 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3275 /* Other call-clobbered hard regs may be clobbered.
3276 Since we only have a choice between 'might be clobbered'
3277 and 'definitely not clobbered', we must include all
3278 partly call-clobbered registers here. */
3279 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3280 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3281 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3282 /* We don't know what set of fixed registers might be used
3283 by the function, but it is certain that the stack pointer
3284 is among them, but be conservative. */
3285 else if (fixed_regs
[i
])
3286 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3287 /* The frame pointer is normally not used by the function
3288 itself, but by the debugger. */
3289 /* ??? MIPS o32 is an exception. It uses the frame pointer
3290 in the macro expansion of jal but does not represent this
3291 fact in the call_insn rtl. */
3292 else if (i
== FRAME_POINTER_REGNUM
3293 || (i
== HARD_FRAME_POINTER_REGNUM
3294 && (! reload_completed
|| frame_pointer_needed
)))
3295 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3298 /* For each insn which shouldn't cross a call, add a dependence
3299 between that insn and this call insn. */
3300 add_dependence_list_and_free (deps
, insn
,
3301 &deps
->sched_before_next_call
, 1,
3304 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3306 /* If CALL would be in a sched group, then this will violate
3307 convention that sched group insns have dependencies only on the
3308 previous instruction.
3310 Of course one can say: "Hey! What about head of the sched group?"
3311 And I will answer: "Basic principles (one dep per insn) are always
3313 gcc_assert (!SCHED_GROUP_P (insn
));
3315 /* In the absence of interprocedural alias analysis, we must flush
3316 all pending reads and writes, and start new dependencies starting
3317 from here. But only flush writes for constant calls (which may
3318 be passed a pointer to something we haven't written yet). */
3319 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3321 if (!deps
->readonly
)
3323 /* Remember the last function call for limiting lifetimes. */
3324 free_INSN_LIST_list (&deps
->last_function_call
);
3325 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3327 if (call_may_noreturn_p (insn
))
3329 /* Remember the last function call that might not always return
3330 normally for limiting moves of trapping insns. */
3331 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3332 deps
->last_function_call_may_noreturn
3333 = alloc_INSN_LIST (insn
, NULL_RTX
);
3336 /* Before reload, begin a post-call group, so as to keep the
3337 lifetimes of hard registers correct. */
3338 if (! reload_completed
)
3339 deps
->in_post_call_group_p
= post_call
;
3343 if (sched_deps_info
->use_cselib
)
3344 cselib_process_insn (insn
);
3346 /* EH_REGION insn notes can not appear until well after we complete
3349 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3350 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3352 if (sched_deps_info
->finish_insn
)
3353 sched_deps_info
->finish_insn ();
3355 /* Fixup the dependencies in the sched group. */
3356 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3357 && SCHED_GROUP_P (insn
) && !sel_sched_p ())
3358 fixup_sched_groups (insn
);
3361 /* Initialize DEPS for the new block beginning with HEAD. */
3363 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3365 gcc_assert (!deps
->readonly
);
3367 /* Before reload, if the previous block ended in a call, show that
3368 we are inside a post-call group, so as to keep the lifetimes of
3369 hard registers correct. */
3370 if (! reload_completed
&& !LABEL_P (head
))
3372 rtx insn
= prev_nonnote_insn (head
);
3374 while (insn
&& DEBUG_INSN_P (insn
))
3375 insn
= prev_nonnote_insn (insn
);
3376 if (insn
&& CALL_P (insn
))
3377 deps
->in_post_call_group_p
= post_call_initial
;
3381 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3382 dependencies for each insn. */
3384 sched_analyze (struct deps_desc
*deps
, rtx head
, rtx tail
)
3388 if (sched_deps_info
->use_cselib
)
3389 cselib_init (CSELIB_RECORD_MEMORY
);
3391 deps_start_bb (deps
, head
);
3393 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3398 /* And initialize deps_lists. */
3399 sd_init_insn (insn
);
3402 deps_analyze_insn (deps
, insn
);
3406 if (sched_deps_info
->use_cselib
)
3414 /* Helper for sched_free_deps ().
3415 Delete INSN's (RESOLVED_P) backward dependencies. */
3417 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3419 sd_iterator_def sd_it
;
3421 sd_list_types_def types
;
3424 types
= SD_LIST_RES_BACK
;
3426 types
= SD_LIST_BACK
;
3428 for (sd_it
= sd_iterator_start (insn
, types
);
3429 sd_iterator_cond (&sd_it
, &dep
);)
3431 dep_link_t link
= *sd_it
.linkp
;
3432 dep_node_t node
= DEP_LINK_NODE (link
);
3433 deps_list_t back_list
;
3434 deps_list_t forw_list
;
3436 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3437 remove_from_deps_list (link
, back_list
);
3438 delete_dep_node (node
);
3442 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3445 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3448 rtx next_tail
= NEXT_INSN (tail
);
3450 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3451 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3453 /* Clear resolved back deps together with its dep_nodes. */
3454 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3456 /* Clear forward deps and leave the dep_nodes to the
3457 corresponding back_deps list. */
3459 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3461 clear_deps_list (INSN_FORW_DEPS (insn
));
3463 sd_finish_insn (insn
);
3467 /* Initialize variables for region data dependence analysis.
3468 When LAZY_REG_LAST is true, do not allocate reg_last array
3469 of struct deps_desc immediately. */
3472 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3474 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3476 deps
->max_reg
= max_reg
;
3478 deps
->reg_last
= NULL
;
3480 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3481 INIT_REG_SET (&deps
->reg_last_in_use
);
3482 INIT_REG_SET (&deps
->reg_conditional_sets
);
3484 deps
->pending_read_insns
= 0;
3485 deps
->pending_read_mems
= 0;
3486 deps
->pending_write_insns
= 0;
3487 deps
->pending_write_mems
= 0;
3488 deps
->pending_read_list_length
= 0;
3489 deps
->pending_write_list_length
= 0;
3490 deps
->pending_flush_length
= 0;
3491 deps
->last_pending_memory_flush
= 0;
3492 deps
->last_function_call
= 0;
3493 deps
->last_function_call_may_noreturn
= 0;
3494 deps
->sched_before_next_call
= 0;
3495 deps
->in_post_call_group_p
= not_post_call
;
3496 deps
->last_debug_insn
= 0;
3497 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3501 /* Init only reg_last field of DEPS, which was not allocated before as
3502 we inited DEPS lazily. */
3504 init_deps_reg_last (struct deps_desc
*deps
)
3506 gcc_assert (deps
&& deps
->max_reg
> 0);
3507 gcc_assert (deps
->reg_last
== NULL
);
3509 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3513 /* Free insn lists found in DEPS. */
3516 free_deps (struct deps_desc
*deps
)
3519 reg_set_iterator rsi
;
3521 /* We set max_reg to 0 when this context was already freed. */
3522 if (deps
->max_reg
== 0)
3524 gcc_assert (deps
->reg_last
== NULL
);
3529 free_INSN_LIST_list (&deps
->pending_read_insns
);
3530 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3531 free_INSN_LIST_list (&deps
->pending_write_insns
);
3532 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3533 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3535 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3536 times. For a testcase with 42000 regs and 8000 small basic blocks,
3537 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3538 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3540 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3542 free_INSN_LIST_list (®_last
->uses
);
3544 free_INSN_LIST_list (®_last
->sets
);
3545 if (reg_last
->implicit_sets
)
3546 free_INSN_LIST_list (®_last
->implicit_sets
);
3547 if (reg_last
->clobbers
)
3548 free_INSN_LIST_list (®_last
->clobbers
);
3550 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3551 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3553 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3556 free (deps
->reg_last
);
3557 deps
->reg_last
= NULL
;
3562 /* Remove INSN from dependence contexts DEPS. Caution: reg_conditional_sets
3565 remove_from_deps (struct deps_desc
*deps
, rtx insn
)
3569 reg_set_iterator rsi
;
3571 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3572 &deps
->pending_read_mems
);
3573 if (!DEBUG_INSN_P (insn
))
3574 deps
->pending_read_list_length
-= removed
;
3575 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3576 &deps
->pending_write_mems
);
3577 deps
->pending_write_list_length
-= removed
;
3578 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3579 deps
->pending_flush_length
-= removed
;
3581 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3583 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3585 remove_from_dependence_list (insn
, ®_last
->uses
);
3587 remove_from_dependence_list (insn
, ®_last
->sets
);
3588 if (reg_last
->implicit_sets
)
3589 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3590 if (reg_last
->clobbers
)
3591 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3592 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3593 && !reg_last
->clobbers
)
3594 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3599 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3600 remove_from_dependence_list (insn
,
3601 &deps
->last_function_call_may_noreturn
);
3603 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3606 /* Init deps data vector. */
3608 init_deps_data_vector (void)
3610 int reserve
= (sched_max_luid
+ 1
3611 - VEC_length (haifa_deps_insn_data_def
, h_d_i_d
));
3613 && ! VEC_space (haifa_deps_insn_data_def
, h_d_i_d
, reserve
))
3614 VEC_safe_grow_cleared (haifa_deps_insn_data_def
, heap
, h_d_i_d
,
3615 3 * sched_max_luid
/ 2);
3618 /* If it is profitable to use them, initialize or extend (depending on
3619 GLOBAL_P) dependency data. */
3621 sched_deps_init (bool global_p
)
3623 /* Average number of insns in the basic block.
3624 '+ 1' is used to make it nonzero. */
3625 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3627 init_deps_data_vector ();
3629 /* We use another caching mechanism for selective scheduling, so
3630 we don't use this one. */
3631 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3633 /* ?!? We could save some memory by computing a per-region luid mapping
3634 which could reduce both the number of vectors in the cache and the
3635 size of each vector. Instead we just avoid the cache entirely unless
3636 the average number of instructions in a basic block is very high. See
3637 the comment before the declaration of true_dependency_cache for
3638 what we consider "very high". */
3640 extend_dependency_caches (sched_max_luid
, true);
3645 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3646 /* Allocate lists for one block at a time. */
3648 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3649 /* Allocate nodes for one block at a time.
3650 We assume that average insn has
3652 5 * insns_in_block
);
3657 /* Create or extend (depending on CREATE_P) dependency caches to
3660 extend_dependency_caches (int n
, bool create_p
)
3662 if (create_p
|| true_dependency_cache
)
3664 int i
, luid
= cache_size
+ n
;
3666 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
3668 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
3669 output_dependency_cache
, luid
);
3670 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
3673 if (current_sched_info
->flags
& DO_SPECULATION
)
3674 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
3677 for (i
= cache_size
; i
< luid
; i
++)
3679 bitmap_initialize (&true_dependency_cache
[i
], 0);
3680 bitmap_initialize (&output_dependency_cache
[i
], 0);
3681 bitmap_initialize (&anti_dependency_cache
[i
], 0);
3683 if (current_sched_info
->flags
& DO_SPECULATION
)
3684 bitmap_initialize (&spec_dependency_cache
[i
], 0);
3690 /* Finalize dependency information for the whole function. */
3692 sched_deps_finish (void)
3694 gcc_assert (deps_pools_are_empty_p ());
3695 free_alloc_pool_if_empty (&dn_pool
);
3696 free_alloc_pool_if_empty (&dl_pool
);
3697 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
3699 VEC_free (haifa_deps_insn_data_def
, heap
, h_d_i_d
);
3702 if (true_dependency_cache
)
3706 for (i
= 0; i
< cache_size
; i
++)
3708 bitmap_clear (&true_dependency_cache
[i
]);
3709 bitmap_clear (&output_dependency_cache
[i
]);
3710 bitmap_clear (&anti_dependency_cache
[i
]);
3712 if (sched_deps_info
->generate_spec_deps
)
3713 bitmap_clear (&spec_dependency_cache
[i
]);
3715 free (true_dependency_cache
);
3716 true_dependency_cache
= NULL
;
3717 free (output_dependency_cache
);
3718 output_dependency_cache
= NULL
;
3719 free (anti_dependency_cache
);
3720 anti_dependency_cache
= NULL
;
3722 if (sched_deps_info
->generate_spec_deps
)
3724 free (spec_dependency_cache
);
3725 spec_dependency_cache
= NULL
;
3731 /* Initialize some global variables needed by the dependency analysis
3735 init_deps_global (void)
3737 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3738 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3739 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
3740 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
3741 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
3742 reg_pending_barrier
= NOT_A_BARRIER
;
3744 if (!sel_sched_p () || sched_emulate_haifa_p
)
3746 sched_deps_info
->start_insn
= haifa_start_insn
;
3747 sched_deps_info
->finish_insn
= haifa_finish_insn
;
3749 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
3750 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
3751 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
3753 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
3754 sched_deps_info
->note_dep
= haifa_note_dep
;
3758 /* Free everything used by the dependency analysis code. */
3761 finish_deps_global (void)
3763 FREE_REG_SET (reg_pending_sets
);
3764 FREE_REG_SET (reg_pending_clobbers
);
3765 FREE_REG_SET (reg_pending_uses
);
3768 /* Estimate the weakness of dependence between MEM1 and MEM2. */
3770 estimate_dep_weak (rtx mem1
, rtx mem2
)
3775 /* MEMs are the same - don't speculate. */
3776 return MIN_DEP_WEAK
;
3778 r1
= XEXP (mem1
, 0);
3779 r2
= XEXP (mem2
, 0);
3782 || (REG_P (r1
) && REG_P (r2
)
3783 && REGNO (r1
) == REGNO (r2
)))
3784 /* Again, MEMs are the same. */
3785 return MIN_DEP_WEAK
;
3786 else if ((REG_P (r1
) && !REG_P (r2
))
3787 || (!REG_P (r1
) && REG_P (r2
)))
3788 /* Different addressing modes - reason to be more speculative,
3790 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
3792 /* We can't say anything about the dependence. */
3793 return UNCERTAIN_DEP_WEAK
;
3796 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3797 This function can handle same INSN and ELEM (INSN == ELEM).
3798 It is a convenience wrapper. */
3800 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
3805 if (dep_type
== REG_DEP_TRUE
)
3807 else if (dep_type
== REG_DEP_OUTPUT
)
3811 gcc_assert (dep_type
== REG_DEP_ANTI
);
3815 /* When add_dependence is called from inside sched-deps.c, we expect
3816 cur_insn to be non-null. */
3817 internal
= cur_insn
!= NULL
;
3819 gcc_assert (insn
== cur_insn
);
3823 note_dep (elem
, ds
);
3828 /* Return weakness of speculative type TYPE in the dep_status DS. */
3830 get_dep_weak_1 (ds_t ds
, ds_t type
)
3836 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
3837 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
3838 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
3839 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
3840 default: gcc_unreachable ();
3847 get_dep_weak (ds_t ds
, ds_t type
)
3849 dw_t dw
= get_dep_weak_1 (ds
, type
);
3851 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3855 /* Return the dep_status, which has the same parameters as DS, except for
3856 speculative type TYPE, that will have weakness DW. */
3858 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
3860 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3865 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
3866 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
3867 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
3868 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
3869 default: gcc_unreachable ();
3874 /* Return the join of two dep_statuses DS1 and DS2.
3875 If MAX_P is true then choose the greater probability,
3876 otherwise multiply probabilities.
3877 This function assumes that both DS1 and DS2 contain speculative bits. */
3879 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
3883 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
3885 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
3887 t
= FIRST_SPEC_TYPE
;
3890 if ((ds1
& t
) && !(ds2
& t
))
3892 else if (!(ds1
& t
) && (ds2
& t
))
3894 else if ((ds1
& t
) && (ds2
& t
))
3896 dw_t dw1
= get_dep_weak (ds1
, t
);
3897 dw_t dw2
= get_dep_weak (ds2
, t
);
3902 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
3904 if (dw
< MIN_DEP_WEAK
)
3915 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
3918 if (t
== LAST_SPEC_TYPE
)
3920 t
<<= SPEC_TYPE_SHIFT
;
3927 /* Return the join of two dep_statuses DS1 and DS2.
3928 This function assumes that both DS1 and DS2 contain speculative bits. */
3930 ds_merge (ds_t ds1
, ds_t ds2
)
3932 return ds_merge_1 (ds1
, ds2
, false);
3935 /* Return the join of two dep_statuses DS1 and DS2. */
3937 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
3939 ds_t new_status
= ds
| ds2
;
3941 if (new_status
& SPECULATIVE
)
3943 if ((ds
&& !(ds
& SPECULATIVE
))
3944 || (ds2
&& !(ds2
& SPECULATIVE
)))
3945 /* Then this dep can't be speculative. */
3946 new_status
&= ~SPECULATIVE
;
3949 /* Both are speculative. Merging probabilities. */
3954 dw
= estimate_dep_weak (mem1
, mem2
);
3955 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
3963 new_status
= ds_merge (ds2
, ds
);
3970 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
3973 ds_max_merge (ds_t ds1
, ds_t ds2
)
3975 if (ds1
== 0 && ds2
== 0)
3978 if (ds1
== 0 && ds2
!= 0)
3981 if (ds1
!= 0 && ds2
== 0)
3984 return ds_merge_1 (ds1
, ds2
, true);
3987 /* Return the probability of speculation success for the speculation
3995 dt
= FIRST_SPEC_TYPE
;
4000 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4004 if (dt
== LAST_SPEC_TYPE
)
4006 dt
<<= SPEC_TYPE_SHIFT
;
4012 res
/= MAX_DEP_WEAK
;
4014 if (res
< MIN_DEP_WEAK
)
4017 gcc_assert (res
<= MAX_DEP_WEAK
);
4022 /* Return a dep status that contains all speculation types of DS. */
4024 ds_get_speculation_types (ds_t ds
)
4026 if (ds
& BEGIN_DATA
)
4028 if (ds
& BE_IN_DATA
)
4030 if (ds
& BEGIN_CONTROL
)
4031 ds
|= BEGIN_CONTROL
;
4032 if (ds
& BE_IN_CONTROL
)
4033 ds
|= BE_IN_CONTROL
;
4035 return ds
& SPECULATIVE
;
4038 /* Return a dep status that contains maximal weakness for each speculation
4039 type present in DS. */
4041 ds_get_max_dep_weak (ds_t ds
)
4043 if (ds
& BEGIN_DATA
)
4044 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4045 if (ds
& BE_IN_DATA
)
4046 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4047 if (ds
& BEGIN_CONTROL
)
4048 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4049 if (ds
& BE_IN_CONTROL
)
4050 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4055 /* Dump information about the dependence status S. */
4057 dump_ds (FILE *f
, ds_t s
)
4062 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4064 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4065 if (s
& BEGIN_CONTROL
)
4066 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4067 if (s
& BE_IN_CONTROL
)
4068 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4071 fprintf (f
, "HARD_DEP; ");
4074 fprintf (f
, "DEP_TRUE; ");
4076 fprintf (f
, "DEP_ANTI; ");
4078 fprintf (f
, "DEP_OUTPUT; ");
4086 dump_ds (stderr
, s
);
4087 fprintf (stderr
, "\n");
4090 #ifdef ENABLE_CHECKING
4091 /* Verify that dependence type and status are consistent.
4092 If RELAXED_P is true, then skip dep_weakness checks. */
4094 check_dep (dep_t dep
, bool relaxed_p
)
4096 enum reg_note dt
= DEP_TYPE (dep
);
4097 ds_t ds
= DEP_STATUS (dep
);
4099 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4101 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4103 gcc_assert (ds
== -1);
4107 /* Check that dependence type contains the same bits as the status. */
4108 if (dt
== REG_DEP_TRUE
)
4109 gcc_assert (ds
& DEP_TRUE
);
4110 else if (dt
== REG_DEP_OUTPUT
)
4111 gcc_assert ((ds
& DEP_OUTPUT
)
4112 && !(ds
& DEP_TRUE
));
4114 gcc_assert ((dt
== REG_DEP_ANTI
)
4116 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4118 /* HARD_DEP can not appear in dep_status of a link. */
4119 gcc_assert (!(ds
& HARD_DEP
));
4121 /* Check that dependence status is set correctly when speculation is not
4123 if (!sched_deps_info
->generate_spec_deps
)
4124 gcc_assert (!(ds
& SPECULATIVE
));
4125 else if (ds
& SPECULATIVE
)
4129 ds_t type
= FIRST_SPEC_TYPE
;
4131 /* Check that dependence weakness is in proper range. */
4135 get_dep_weak (ds
, type
);
4137 if (type
== LAST_SPEC_TYPE
)
4139 type
<<= SPEC_TYPE_SHIFT
;
4144 if (ds
& BEGIN_SPEC
)
4146 /* Only true dependence can be data speculative. */
4147 if (ds
& BEGIN_DATA
)
4148 gcc_assert (ds
& DEP_TRUE
);
4150 /* Control dependencies in the insn scheduler are represented by
4151 anti-dependencies, therefore only anti dependence can be
4152 control speculative. */
4153 if (ds
& BEGIN_CONTROL
)
4154 gcc_assert (ds
& DEP_ANTI
);
4158 /* Subsequent speculations should resolve true dependencies. */
4159 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4162 /* Check that true and anti dependencies can't have other speculative
4165 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4166 /* An output dependence can't be speculative at all. */
4167 gcc_assert (!(ds
& DEP_OUTPUT
));
4169 gcc_assert (ds
& BEGIN_CONTROL
);
4172 #endif /* ENABLE_CHECKING */
4174 #endif /* INSN_SCHEDULING */