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
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"
45 #ifdef INSN_SCHEDULING
47 #ifdef ENABLE_CHECKING
53 /* Holds current parameters for the dependency analyzer. */
54 struct sched_deps_info_def
*sched_deps_info
;
56 /* The data is specific to the Haifa scheduler. */
57 VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
= NULL
;
59 /* Return the major type present in the DS. */
67 return REG_DEP_OUTPUT
;
69 gcc_assert (ds
& DEP_ANTI
);
74 /* Return equivalent dep_status. */
76 dk_to_ds (enum reg_note dk
)
87 gcc_assert (dk
== REG_DEP_ANTI
);
92 /* Functions to operate with dependence information container - dep_t. */
94 /* Init DEP with the arguments. */
96 init_dep_1 (dep_t dep
, rtx pro
, rtx con
, enum reg_note type
, ds_t ds
)
100 DEP_TYPE (dep
) = type
;
101 DEP_STATUS (dep
) = ds
;
104 /* Init DEP with the arguments.
105 While most of the scheduler (including targets) only need the major type
106 of the dependency, it is convenient to hide full dep_status from them. */
108 init_dep (dep_t dep
, rtx pro
, rtx con
, enum reg_note kind
)
112 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
113 ds
= dk_to_ds (kind
);
117 init_dep_1 (dep
, pro
, con
, kind
, ds
);
120 /* Make a copy of FROM in TO. */
122 copy_dep (dep_t to
, dep_t from
)
124 memcpy (to
, from
, sizeof (*to
));
127 static void dump_ds (FILE *, ds_t
);
129 /* Define flags for dump_dep (). */
131 /* Dump producer of the dependence. */
132 #define DUMP_DEP_PRO (2)
134 /* Dump consumer of the dependence. */
135 #define DUMP_DEP_CON (4)
137 /* Dump type of the dependence. */
138 #define DUMP_DEP_TYPE (8)
140 /* Dump status of the dependence. */
141 #define DUMP_DEP_STATUS (16)
143 /* Dump all information about the dependence. */
144 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
148 FLAGS is a bit mask specifying what information about DEP needs
150 If FLAGS has the very first bit set, then dump all information about DEP
151 and propagate this bit into the callee dump functions. */
153 dump_dep (FILE *dump
, dep_t dep
, int flags
)
156 flags
|= DUMP_DEP_ALL
;
160 if (flags
& DUMP_DEP_PRO
)
161 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
163 if (flags
& DUMP_DEP_CON
)
164 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
166 if (flags
& DUMP_DEP_TYPE
)
169 enum reg_note type
= DEP_TYPE (dep
);
190 fprintf (dump
, "%c; ", t
);
193 if (flags
& DUMP_DEP_STATUS
)
195 if (current_sched_info
->flags
& USE_DEPS_LIST
)
196 dump_ds (dump
, DEP_STATUS (dep
));
202 /* Default flags for dump_dep (). */
203 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
205 /* Dump all fields of DEP to STDERR. */
207 sd_debug_dep (dep_t dep
)
209 dump_dep (stderr
, dep
, 1);
210 fprintf (stderr
, "\n");
213 /* Functions to operate with a single link from the dependencies lists -
216 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
219 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
221 dep_link_t next
= *prev_nextp
;
223 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
224 && DEP_LINK_NEXT (l
) == NULL
);
226 /* Init node being inserted. */
227 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
228 DEP_LINK_NEXT (l
) = next
;
233 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
235 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
242 /* Add dep_link LINK to deps_list L. */
244 add_to_deps_list (dep_link_t link
, deps_list_t l
)
246 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
248 ++DEPS_LIST_N_LINKS (l
);
251 /* Detach dep_link L from the list. */
253 detach_dep_link (dep_link_t l
)
255 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
256 dep_link_t next
= DEP_LINK_NEXT (l
);
261 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
263 DEP_LINK_PREV_NEXTP (l
) = NULL
;
264 DEP_LINK_NEXT (l
) = NULL
;
267 /* Remove link LINK from list LIST. */
269 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
271 detach_dep_link (link
);
273 --DEPS_LIST_N_LINKS (list
);
276 /* Move link LINK from list FROM to list TO. */
278 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
280 remove_from_deps_list (link
, from
);
281 add_to_deps_list (link
, to
);
284 /* Return true of LINK is not attached to any list. */
286 dep_link_is_detached_p (dep_link_t link
)
288 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
291 /* Pool to hold all dependency nodes (dep_node_t). */
292 static alloc_pool dn_pool
;
294 /* Number of dep_nodes out there. */
295 static int dn_pool_diff
= 0;
297 /* Create a dep_node. */
299 create_dep_node (void)
301 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
302 dep_link_t back
= DEP_NODE_BACK (n
);
303 dep_link_t forw
= DEP_NODE_FORW (n
);
305 DEP_LINK_NODE (back
) = n
;
306 DEP_LINK_NEXT (back
) = NULL
;
307 DEP_LINK_PREV_NEXTP (back
) = NULL
;
309 DEP_LINK_NODE (forw
) = n
;
310 DEP_LINK_NEXT (forw
) = NULL
;
311 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
318 /* Delete dep_node N. N must not be connected to any deps_list. */
320 delete_dep_node (dep_node_t n
)
322 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
323 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
327 pool_free (dn_pool
, n
);
330 /* Pool to hold dependencies lists (deps_list_t). */
331 static alloc_pool dl_pool
;
333 /* Number of deps_lists out there. */
334 static int dl_pool_diff
= 0;
336 /* Functions to operate with dependences lists - deps_list_t. */
338 /* Return true if list L is empty. */
340 deps_list_empty_p (deps_list_t l
)
342 return DEPS_LIST_N_LINKS (l
) == 0;
345 /* Create a new deps_list. */
347 create_deps_list (void)
349 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
351 DEPS_LIST_FIRST (l
) = NULL
;
352 DEPS_LIST_N_LINKS (l
) = 0;
358 /* Free deps_list L. */
360 free_deps_list (deps_list_t l
)
362 gcc_assert (deps_list_empty_p (l
));
366 pool_free (dl_pool
, l
);
369 /* Return true if there is no dep_nodes and deps_lists out there.
370 After the region is scheduled all the dependency nodes and lists
371 should [generally] be returned to pool. */
373 deps_pools_are_empty_p (void)
375 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
378 /* Remove all elements from L. */
380 clear_deps_list (deps_list_t l
)
384 dep_link_t link
= DEPS_LIST_FIRST (l
);
389 remove_from_deps_list (link
, l
);
394 static regset reg_pending_sets
;
395 static regset reg_pending_clobbers
;
396 static regset reg_pending_uses
;
397 static enum reg_pending_barrier_mode reg_pending_barrier
;
399 /* To speed up the test for duplicate dependency links we keep a
400 record of dependencies created by add_dependence when the average
401 number of instructions in a basic block is very large.
403 Studies have shown that there is typically around 5 instructions between
404 branches for typical C code. So we can make a guess that the average
405 basic block is approximately 5 instructions long; we will choose 100X
406 the average size as a very large basic block.
408 Each insn has associated bitmaps for its dependencies. Each bitmap
409 has enough entries to represent a dependency on any other insn in
410 the insn chain. All bitmap for true dependencies cache is
411 allocated then the rest two ones are also allocated. */
412 static bitmap_head
*true_dependency_cache
= NULL
;
413 static bitmap_head
*output_dependency_cache
= NULL
;
414 static bitmap_head
*anti_dependency_cache
= NULL
;
415 static bitmap_head
*spec_dependency_cache
= NULL
;
416 static int cache_size
;
418 static int deps_may_trap_p (const_rtx
);
419 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
);
420 static void add_dependence_list_and_free (struct deps
*, rtx
,
421 rtx
*, int, enum reg_note
);
422 static void delete_all_dependences (rtx
);
423 static void fixup_sched_groups (rtx
);
425 static void flush_pending_lists (struct deps
*, rtx
, int, int);
426 static void sched_analyze_1 (struct deps
*, rtx
, rtx
);
427 static void sched_analyze_2 (struct deps
*, rtx
, rtx
);
428 static void sched_analyze_insn (struct deps
*, rtx
, rtx
);
430 static bool sched_has_condition_p (const_rtx
);
431 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
433 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
435 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
437 #ifdef ENABLE_CHECKING
438 static void check_dep (dep_t
, bool);
441 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
444 deps_may_trap_p (const_rtx mem
)
446 const_rtx addr
= XEXP (mem
, 0);
448 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
450 const_rtx t
= get_reg_known_value (REGNO (addr
));
454 return rtx_addr_can_trap_p (addr
);
458 /* Find the condition under which INSN is executed. If REV is not NULL,
459 it is set to TRUE when the returned comparison should be reversed
460 to get the actual condition. */
462 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
464 rtx pat
= PATTERN (insn
);
473 if (GET_CODE (pat
) == COND_EXEC
)
474 return COND_EXEC_TEST (pat
);
476 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
479 src
= SET_SRC (pc_set (insn
));
481 if (XEXP (src
, 2) == pc_rtx
)
482 return XEXP (src
, 0);
483 else if (XEXP (src
, 1) == pc_rtx
)
485 rtx cond
= XEXP (src
, 0);
486 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
488 if (revcode
== UNKNOWN
)
499 /* True when we can find a condition under which INSN is executed. */
501 sched_has_condition_p (const_rtx insn
)
503 return !! sched_get_condition_with_rev (insn
, NULL
);
508 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
510 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
512 if (COMPARISON_P (cond1
)
513 && COMPARISON_P (cond2
)
514 && GET_CODE (cond1
) ==
516 ? reversed_comparison_code (cond2
, NULL
)
518 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
519 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
524 /* Return true if insn1 and insn2 can never depend on one another because
525 the conditions under which they are executed are mutually exclusive. */
527 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
530 bool rev1
= false, rev2
= false;
532 /* df doesn't handle conditional lifetimes entirely correctly;
533 calls mess up the conditional lifetimes. */
534 if (!CALL_P (insn1
) && !CALL_P (insn2
))
536 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
537 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
539 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
540 /* Make sure first instruction doesn't affect condition of second
541 instruction if switched. */
542 && !modified_in_p (cond1
, insn2
)
543 /* Make sure second instruction doesn't affect condition of first
544 instruction if switched. */
545 && !modified_in_p (cond2
, insn1
))
552 /* Return true if INSN can potentially be speculated with type DS. */
554 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
556 if (HAS_INTERNAL_DEP (insn
))
559 if (!NONJUMP_INSN_P (insn
))
562 if (SCHED_GROUP_P (insn
))
565 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
568 if (side_effects_p (PATTERN (insn
)))
572 /* The following instructions, which depend on a speculatively scheduled
573 instruction, cannot be speculatively scheduled along. */
575 if (may_trap_p (PATTERN (insn
)))
576 /* If instruction might trap, it cannot be speculatively scheduled.
577 For control speculation it's obvious why and for data speculation
578 it's because the insn might get wrong input if speculation
579 wasn't successful. */
582 if ((ds
& BE_IN_DATA
)
583 && sched_has_condition_p (insn
))
584 /* If this is a predicated instruction, then it cannot be
585 speculatively scheduled. See PR35659. */
592 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
593 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
594 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
595 This function is used to switch sd_iterator to the next list.
596 !!! For internal use only. Might consider moving it to sched-int.h. */
598 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
599 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
601 sd_list_types_def types
= *types_ptr
;
603 if (types
& SD_LIST_HARD_BACK
)
605 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
606 *resolved_p_ptr
= false;
607 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
609 else if (types
& SD_LIST_SPEC_BACK
)
611 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
612 *resolved_p_ptr
= false;
613 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
615 else if (types
& SD_LIST_FORW
)
617 *list_ptr
= INSN_FORW_DEPS (insn
);
618 *resolved_p_ptr
= false;
619 *types_ptr
= types
& ~SD_LIST_FORW
;
621 else if (types
& SD_LIST_RES_BACK
)
623 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
624 *resolved_p_ptr
= true;
625 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
627 else if (types
& SD_LIST_RES_FORW
)
629 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
630 *resolved_p_ptr
= true;
631 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
636 *resolved_p_ptr
= false;
637 *types_ptr
= SD_LIST_NONE
;
641 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
643 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
647 while (list_types
!= SD_LIST_NONE
)
652 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
654 size
+= DEPS_LIST_N_LINKS (list
);
660 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
662 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
664 return sd_lists_size (insn
, list_types
) == 0;
667 /* Initialize data for INSN. */
669 sd_init_insn (rtx insn
)
671 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
672 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
673 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
674 INSN_FORW_DEPS (insn
) = create_deps_list ();
675 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
677 if (DEBUG_INSN_P (insn
))
678 DEBUG_INSN_SCHED_P (insn
) = TRUE
;
680 /* ??? It would be nice to allocate dependency caches here. */
683 /* Free data for INSN. */
685 sd_finish_insn (rtx insn
)
687 /* ??? It would be nice to deallocate dependency caches here. */
689 if (DEBUG_INSN_P (insn
))
691 gcc_assert (DEBUG_INSN_SCHED_P (insn
));
692 DEBUG_INSN_SCHED_P (insn
) = FALSE
;
695 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
696 INSN_HARD_BACK_DEPS (insn
) = NULL
;
698 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
699 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
701 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
702 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
704 free_deps_list (INSN_FORW_DEPS (insn
));
705 INSN_FORW_DEPS (insn
) = NULL
;
707 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
708 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
711 /* Find a dependency between producer PRO and consumer CON.
712 Search through resolved dependency lists if RESOLVED_P is true.
713 If no such dependency is found return NULL,
714 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
715 with an iterator pointing to it. */
717 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
718 sd_iterator_def
*sd_it_ptr
)
720 sd_list_types_def pro_list_type
;
721 sd_list_types_def con_list_type
;
722 sd_iterator_def sd_it
;
724 bool found_p
= false;
728 pro_list_type
= SD_LIST_RES_FORW
;
729 con_list_type
= SD_LIST_RES_BACK
;
733 pro_list_type
= SD_LIST_FORW
;
734 con_list_type
= SD_LIST_BACK
;
737 /* Walk through either back list of INSN or forw list of ELEM
738 depending on which one is shorter. */
739 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
741 /* Find the dep_link with producer PRO in consumer's back_deps. */
742 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
743 if (DEP_PRO (dep
) == pro
)
751 /* Find the dep_link with consumer CON in producer's forw_deps. */
752 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
753 if (DEP_CON (dep
) == con
)
762 if (sd_it_ptr
!= NULL
)
771 /* Find a dependency between producer PRO and consumer CON.
772 Use dependency [if available] to check if dependency is present at all.
773 Search through resolved dependency lists if RESOLVED_P is true.
774 If the dependency or NULL if none found. */
776 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
778 if (true_dependency_cache
!= NULL
)
779 /* Avoiding the list walk below can cut compile times dramatically
782 int elem_luid
= INSN_LUID (pro
);
783 int insn_luid
= INSN_LUID (con
);
785 gcc_assert (output_dependency_cache
!= NULL
786 && anti_dependency_cache
!= NULL
);
788 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
789 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
790 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
794 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
797 /* Add or update a dependence described by DEP.
798 MEM1 and MEM2, if non-null, correspond to memory locations in case of
801 The function returns a value indicating if an old entry has been changed
802 or a new entry has been added to insn's backward deps.
804 This function merely checks if producer and consumer is the same insn
805 and doesn't create a dep in this case. Actual manipulation of
806 dependence data structures is performed in add_or_update_dep_1. */
807 static enum DEPS_ADJUST_RESULT
808 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
810 rtx elem
= DEP_PRO (dep
);
811 rtx insn
= DEP_CON (dep
);
813 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
815 /* Don't depend an insn on itself. */
818 if (sched_deps_info
->generate_spec_deps
)
819 /* INSN has an internal dependence, which we can't overcome. */
820 HAS_INTERNAL_DEP (insn
) = 1;
825 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
828 /* Ask dependency caches what needs to be done for dependence DEP.
829 Return DEP_CREATED if new dependence should be created and there is no
830 need to try to find one searching the dependencies lists.
831 Return DEP_PRESENT if there already is a dependence described by DEP and
832 hence nothing is to be done.
833 Return DEP_CHANGED if there already is a dependence, but it should be
834 updated to incorporate additional information from DEP. */
835 static enum DEPS_ADJUST_RESULT
836 ask_dependency_caches (dep_t dep
)
838 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
839 int insn_luid
= INSN_LUID (DEP_CON (dep
));
841 gcc_assert (true_dependency_cache
!= NULL
842 && output_dependency_cache
!= NULL
843 && anti_dependency_cache
!= NULL
);
845 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
847 enum reg_note present_dep_type
;
849 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
850 present_dep_type
= REG_DEP_TRUE
;
851 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
852 present_dep_type
= REG_DEP_OUTPUT
;
853 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
854 present_dep_type
= REG_DEP_ANTI
;
856 /* There is no existing dep so it should be created. */
859 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
860 /* DEP does not add anything to the existing dependence. */
865 ds_t present_dep_types
= 0;
867 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
868 present_dep_types
|= DEP_TRUE
;
869 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
870 present_dep_types
|= DEP_OUTPUT
;
871 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
872 present_dep_types
|= DEP_ANTI
;
874 if (present_dep_types
== 0)
875 /* There is no existing dep so it should be created. */
878 if (!(current_sched_info
->flags
& DO_SPECULATION
)
879 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
881 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
882 == present_dep_types
)
883 /* DEP does not add anything to the existing dependence. */
888 /* Only true dependencies can be data speculative and
889 only anti dependencies can be control speculative. */
890 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
891 == present_dep_types
);
893 /* if (DEP is SPECULATIVE) then
894 ..we should update DEP_STATUS
896 ..we should reset existing dep to non-speculative. */
903 /* Set dependency caches according to DEP. */
905 set_dependency_caches (dep_t dep
)
907 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
908 int insn_luid
= INSN_LUID (DEP_CON (dep
));
910 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
912 switch (DEP_TYPE (dep
))
915 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
919 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
923 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
932 ds_t ds
= DEP_STATUS (dep
);
935 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
937 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
939 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
941 if (ds
& SPECULATIVE
)
943 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
944 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
949 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
950 caches accordingly. */
952 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
954 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
955 int insn_luid
= INSN_LUID (DEP_CON (dep
));
957 /* Clear corresponding cache entry because type of the link
958 may have changed. Keep them if we use_deps_list. */
959 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
964 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
968 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
976 set_dependency_caches (dep
);
979 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
981 change_spec_dep_to_hard (sd_iterator_def sd_it
)
983 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
984 dep_link_t link
= DEP_NODE_BACK (node
);
985 dep_t dep
= DEP_NODE_DEP (node
);
986 rtx elem
= DEP_PRO (dep
);
987 rtx insn
= DEP_CON (dep
);
989 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
991 DEP_STATUS (dep
) &= ~SPECULATIVE
;
993 if (true_dependency_cache
!= NULL
)
994 /* Clear the cache entry. */
995 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
999 /* Update DEP to incorporate information from NEW_DEP.
1000 SD_IT points to DEP in case it should be moved to another list.
1001 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1002 data-speculative dependence should be updated. */
1003 static enum DEPS_ADJUST_RESULT
1004 update_dep (dep_t dep
, dep_t new_dep
,
1005 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1006 rtx mem1 ATTRIBUTE_UNUSED
,
1007 rtx mem2 ATTRIBUTE_UNUSED
)
1009 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1010 enum reg_note old_type
= DEP_TYPE (dep
);
1012 /* If this is a more restrictive type of dependence than the
1013 existing one, then change the existing dependence to this
1015 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1017 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1021 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1022 /* Update DEP_STATUS. */
1024 ds_t dep_status
= DEP_STATUS (dep
);
1025 ds_t ds
= DEP_STATUS (new_dep
);
1026 ds_t new_status
= ds
| dep_status
;
1028 if (new_status
& SPECULATIVE
)
1029 /* Either existing dep or a dep we're adding or both are
1032 if (!(ds
& SPECULATIVE
)
1033 || !(dep_status
& SPECULATIVE
))
1034 /* The new dep can't be speculative. */
1036 new_status
&= ~SPECULATIVE
;
1038 if (dep_status
& SPECULATIVE
)
1039 /* The old dep was speculative, but now it
1041 change_spec_dep_to_hard (sd_it
);
1045 /* Both are speculative. Merge probabilities. */
1050 dw
= estimate_dep_weak (mem1
, mem2
);
1051 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1054 new_status
= ds_merge (dep_status
, ds
);
1060 if (dep_status
!= ds
)
1062 DEP_STATUS (dep
) = ds
;
1067 if (true_dependency_cache
!= NULL
1068 && res
== DEP_CHANGED
)
1069 update_dependency_caches (dep
, old_type
);
1074 /* Add or update a dependence described by DEP.
1075 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1078 The function returns a value indicating if an old entry has been changed
1079 or a new entry has been added to insn's backward deps or nothing has
1080 been updated at all. */
1081 static enum DEPS_ADJUST_RESULT
1082 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1083 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1085 bool maybe_present_p
= true;
1086 bool present_p
= false;
1088 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1089 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1091 #ifdef ENABLE_CHECKING
1092 check_dep (new_dep
, mem1
!= NULL
);
1095 if (true_dependency_cache
!= NULL
)
1097 switch (ask_dependency_caches (new_dep
))
1103 maybe_present_p
= true;
1108 maybe_present_p
= false;
1118 /* Check that we don't already have this dependence. */
1119 if (maybe_present_p
)
1122 sd_iterator_def sd_it
;
1124 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1126 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1128 resolved_p
, &sd_it
);
1130 if (present_dep
!= NULL
)
1131 /* We found an existing dependency between ELEM and INSN. */
1132 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1134 /* We didn't find a dep, it shouldn't present in the cache. */
1135 gcc_assert (!present_p
);
1138 /* Might want to check one level of transitivity to save conses.
1139 This check should be done in maybe_add_or_update_dep_1.
1140 Since we made it to add_or_update_dep_1, we must create
1141 (or update) a link. */
1143 if (mem1
!= NULL_RTX
)
1145 gcc_assert (sched_deps_info
->generate_spec_deps
);
1146 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1147 estimate_dep_weak (mem1
, mem2
));
1150 sd_add_dep (new_dep
, resolved_p
);
1155 /* Initialize BACK_LIST_PTR with consumer's backward list and
1156 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1157 initialize with lists that hold resolved deps. */
1159 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1160 deps_list_t
*back_list_ptr
,
1161 deps_list_t
*forw_list_ptr
)
1163 rtx con
= DEP_CON (dep
);
1167 if ((current_sched_info
->flags
& DO_SPECULATION
)
1168 && (DEP_STATUS (dep
) & SPECULATIVE
))
1169 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1171 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1173 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1177 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1178 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1182 /* Add dependence described by DEP.
1183 If RESOLVED_P is true treat the dependence as a resolved one. */
1185 sd_add_dep (dep_t dep
, bool resolved_p
)
1187 dep_node_t n
= create_dep_node ();
1188 deps_list_t con_back_deps
;
1189 deps_list_t pro_forw_deps
;
1190 rtx elem
= DEP_PRO (dep
);
1191 rtx insn
= DEP_CON (dep
);
1193 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1194 gcc_assert (!DEBUG_INSN_P (elem
) || DEBUG_INSN_P (insn
));
1196 if ((current_sched_info
->flags
& DO_SPECULATION
)
1197 && !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1198 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1200 copy_dep (DEP_NODE_DEP (n
), dep
);
1202 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1204 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1206 #ifdef ENABLE_CHECKING
1207 check_dep (dep
, false);
1210 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1212 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1213 in the bitmap caches of dependency information. */
1214 if (true_dependency_cache
!= NULL
)
1215 set_dependency_caches (dep
);
1218 /* Add or update backward dependence between INSN and ELEM
1219 with given type DEP_TYPE and dep_status DS.
1220 This function is a convenience wrapper. */
1221 enum DEPS_ADJUST_RESULT
1222 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1224 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1227 /* Resolved dependence pointed to by SD_IT.
1228 SD_IT will advance to the next element. */
1230 sd_resolve_dep (sd_iterator_def sd_it
)
1232 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1233 dep_t dep
= DEP_NODE_DEP (node
);
1234 rtx pro
= DEP_PRO (dep
);
1235 rtx con
= DEP_CON (dep
);
1237 if ((current_sched_info
->flags
& DO_SPECULATION
)
1238 && (DEP_STATUS (dep
) & SPECULATIVE
))
1239 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1240 INSN_RESOLVED_BACK_DEPS (con
));
1242 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1243 INSN_RESOLVED_BACK_DEPS (con
));
1245 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1246 INSN_RESOLVED_FORW_DEPS (pro
));
1249 /* Make TO depend on all the FROM's producers.
1250 If RESOLVED_P is true add dependencies to the resolved lists. */
1252 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1254 sd_list_types_def list_type
;
1255 sd_iterator_def sd_it
;
1258 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1260 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1262 dep_def _new_dep
, *new_dep
= &_new_dep
;
1264 copy_dep (new_dep
, dep
);
1265 DEP_CON (new_dep
) = to
;
1266 sd_add_dep (new_dep
, resolved_p
);
1270 /* Remove a dependency referred to by SD_IT.
1271 SD_IT will point to the next dependence after removal. */
1273 sd_delete_dep (sd_iterator_def sd_it
)
1275 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1276 dep_t dep
= DEP_NODE_DEP (n
);
1277 rtx pro
= DEP_PRO (dep
);
1278 rtx con
= DEP_CON (dep
);
1279 deps_list_t con_back_deps
;
1280 deps_list_t pro_forw_deps
;
1282 if (true_dependency_cache
!= NULL
)
1284 int elem_luid
= INSN_LUID (pro
);
1285 int insn_luid
= INSN_LUID (con
);
1287 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1288 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1289 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1291 if (current_sched_info
->flags
& DO_SPECULATION
)
1292 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1295 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1296 &con_back_deps
, &pro_forw_deps
);
1298 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1299 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1301 delete_dep_node (n
);
1304 /* Dump size of the lists. */
1305 #define DUMP_LISTS_SIZE (2)
1307 /* Dump dependencies of the lists. */
1308 #define DUMP_LISTS_DEPS (4)
1310 /* Dump all information about the lists. */
1311 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1313 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1314 FLAGS is a bit mask specifying what information about the lists needs
1316 If FLAGS has the very first bit set, then dump all information about
1317 the lists and propagate this bit into the callee dump functions. */
1319 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1321 sd_iterator_def sd_it
;
1328 flags
|= DUMP_LISTS_ALL
;
1330 fprintf (dump
, "[");
1332 if (flags
& DUMP_LISTS_SIZE
)
1333 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1335 if (flags
& DUMP_LISTS_DEPS
)
1337 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1339 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1340 fprintf (dump
, " ");
1345 /* Dump all information about deps_lists of INSN specified by TYPES
1348 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1350 dump_lists (stderr
, insn
, types
, 1);
1351 fprintf (stderr
, "\n");
1354 /* A convenience wrapper to operate on an entire list. */
1357 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
)
1359 for (; list
; list
= XEXP (list
, 1))
1361 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1362 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1366 /* Similar, but free *LISTP at the same time, when the context
1370 add_dependence_list_and_free (struct deps
*deps
, rtx insn
, rtx
*listp
,
1371 int uncond
, enum reg_note dep_type
)
1377 add_dependence_list (insn
, *listp
, uncond
, dep_type
);
1381 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
1383 next
= XEXP (list
, 1);
1384 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1385 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1386 free_INSN_LIST_node (list
);
1390 /* Remove all occurences of INSN from LIST. Return the number of
1391 occurences removed. */
1394 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1400 if (XEXP (*listp
, 0) == insn
)
1402 remove_free_INSN_LIST_node (listp
);
1407 listp
= &XEXP (*listp
, 1);
1413 /* Same as above, but process two lists at once. */
1415 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1421 if (XEXP (*listp
, 0) == insn
)
1423 remove_free_INSN_LIST_node (listp
);
1424 remove_free_EXPR_LIST_node (exprp
);
1429 listp
= &XEXP (*listp
, 1);
1430 exprp
= &XEXP (*exprp
, 1);
1436 /* Clear all dependencies for an insn. */
1438 delete_all_dependences (rtx insn
)
1440 sd_iterator_def sd_it
;
1443 /* The below cycle can be optimized to clear the caches and back_deps
1444 in one call but that would provoke duplication of code from
1447 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1448 sd_iterator_cond (&sd_it
, &dep
);)
1449 sd_delete_dep (sd_it
);
1452 /* All insns in a scheduling group except the first should only have
1453 dependencies on the previous insn in the group. So we find the
1454 first instruction in the scheduling group by walking the dependence
1455 chains backwards. Then we add the dependencies for the group to
1456 the previous nonnote insn. */
1459 fixup_sched_groups (rtx insn
)
1461 sd_iterator_def sd_it
;
1465 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1468 rtx pro
= DEP_PRO (dep
);
1472 i
= prev_nonnote_insn (i
);
1476 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1478 if (! sched_insns_conditions_mutex_p (i
, pro
))
1479 add_dependence (i
, pro
, DEP_TYPE (dep
));
1483 delete_all_dependences (insn
);
1485 prev_nonnote
= prev_nonnote_insn (insn
);
1486 while (DEBUG_INSN_P (prev_nonnote
))
1487 prev_nonnote
= prev_nonnote_insn (prev_nonnote
);
1488 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1489 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1490 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1493 /* Process an insn's memory dependencies. There are four kinds of
1496 (0) read dependence: read follows read
1497 (1) true dependence: read follows write
1498 (2) output dependence: write follows write
1499 (3) anti dependence: write follows read
1501 We are careful to build only dependencies which actually exist, and
1502 use transitivity to avoid building too many links. */
1504 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1505 The MEM is a memory reference contained within INSN, which we are saving
1506 so that we can do memory aliasing on it. */
1509 add_insn_mem_dependence (struct deps
*deps
, bool read_p
,
1516 gcc_assert (!deps
->readonly
);
1519 insn_list
= &deps
->pending_read_insns
;
1520 mem_list
= &deps
->pending_read_mems
;
1521 deps
->pending_read_list_length
++;
1525 insn_list
= &deps
->pending_write_insns
;
1526 mem_list
= &deps
->pending_write_mems
;
1527 deps
->pending_write_list_length
++;
1530 link
= alloc_INSN_LIST (insn
, *insn_list
);
1533 if (sched_deps_info
->use_cselib
)
1535 mem
= shallow_copy_rtx (mem
);
1536 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
1538 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1542 /* Make a dependency between every memory reference on the pending lists
1543 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1544 dependencies for a read operation, similarly with FOR_WRITE. */
1547 flush_pending_lists (struct deps
*deps
, rtx insn
, int for_read
,
1552 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1554 if (!deps
->readonly
)
1556 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1557 deps
->pending_read_list_length
= 0;
1561 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1562 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1564 add_dependence_list_and_free (deps
, insn
,
1565 &deps
->last_pending_memory_flush
, 1,
1566 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1567 if (!deps
->readonly
)
1569 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1570 deps
->pending_write_list_length
= 0;
1572 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1573 deps
->pending_flush_length
= 1;
1577 /* Instruction which dependencies we are analyzing. */
1578 static rtx cur_insn
= NULL_RTX
;
1580 /* Implement hooks for haifa scheduler. */
1583 haifa_start_insn (rtx insn
)
1585 gcc_assert (insn
&& !cur_insn
);
1591 haifa_finish_insn (void)
1597 haifa_note_reg_set (int regno
)
1599 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1603 haifa_note_reg_clobber (int regno
)
1605 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1609 haifa_note_reg_use (int regno
)
1611 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1615 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1617 if (!(ds
& SPECULATIVE
))
1620 pending_mem
= NULL_RTX
;
1623 gcc_assert (ds
& BEGIN_DATA
);
1626 dep_def _dep
, *dep
= &_dep
;
1628 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1629 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: -1);
1630 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1636 haifa_note_dep (rtx elem
, ds_t ds
)
1641 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1642 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1646 note_reg_use (int r
)
1648 if (sched_deps_info
->note_reg_use
)
1649 sched_deps_info
->note_reg_use (r
);
1653 note_reg_set (int r
)
1655 if (sched_deps_info
->note_reg_set
)
1656 sched_deps_info
->note_reg_set (r
);
1660 note_reg_clobber (int r
)
1662 if (sched_deps_info
->note_reg_clobber
)
1663 sched_deps_info
->note_reg_clobber (r
);
1667 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1669 if (sched_deps_info
->note_mem_dep
)
1670 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1674 note_dep (rtx e
, ds_t ds
)
1676 if (sched_deps_info
->note_dep
)
1677 sched_deps_info
->note_dep (e
, ds
);
1680 /* Return corresponding to DS reg_note. */
1685 return REG_DEP_TRUE
;
1686 else if (ds
& DEP_OUTPUT
)
1687 return REG_DEP_OUTPUT
;
1690 gcc_assert (ds
& DEP_ANTI
);
1691 return REG_DEP_ANTI
;
1696 /* Internal variable for sched_analyze_[12] () functions.
1697 If it is nonzero, this means that sched_analyze_[12] looks
1698 at the most toplevel SET. */
1699 static bool can_start_lhs_rhs_p
;
1701 /* Extend reg info for the deps context DEPS given that
1702 we have just generated a register numbered REGNO. */
1704 extend_deps_reg_info (struct deps
*deps
, int regno
)
1706 int max_regno
= regno
+ 1;
1708 gcc_assert (!reload_completed
);
1710 /* In a readonly context, it would not hurt to extend info,
1711 but it should not be needed. */
1712 if (reload_completed
&& deps
->readonly
)
1714 deps
->max_reg
= max_regno
;
1718 if (max_regno
> deps
->max_reg
)
1720 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
1722 memset (&deps
->reg_last
[deps
->max_reg
],
1723 0, (max_regno
- deps
->max_reg
)
1724 * sizeof (struct deps_reg
));
1725 deps
->max_reg
= max_regno
;
1729 /* Extends REG_INFO_P if needed. */
1731 maybe_extend_reg_info_p (void)
1733 /* Extend REG_INFO_P, if needed. */
1734 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
1736 size_t new_reg_info_p_size
= max_regno
+ 128;
1738 gcc_assert (!reload_completed
&& sel_sched_p ());
1740 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
1741 new_reg_info_p_size
,
1743 sizeof (*reg_info_p
));
1744 reg_info_p_size
= new_reg_info_p_size
;
1748 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
1749 The type of the reference is specified by REF and can be SET,
1750 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
1753 sched_analyze_reg (struct deps
*deps
, int regno
, enum machine_mode mode
,
1754 enum rtx_code ref
, rtx insn
)
1756 /* We could emit new pseudos in renaming. Extend the reg structures. */
1757 if (!reload_completed
&& sel_sched_p ()
1758 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
1759 extend_deps_reg_info (deps
, regno
);
1761 maybe_extend_reg_info_p ();
1763 /* A hard reg in a wide mode may really be multiple registers.
1764 If so, mark all of them just like the first. */
1765 if (regno
< FIRST_PSEUDO_REGISTER
)
1767 int i
= hard_regno_nregs
[regno
][mode
];
1771 note_reg_set (regno
+ i
);
1773 else if (ref
== USE
)
1776 note_reg_use (regno
+ i
);
1781 note_reg_clobber (regno
+ i
);
1785 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
1786 it does not reload. Ignore these as they have served their
1788 else if (regno
>= deps
->max_reg
)
1790 enum rtx_code code
= GET_CODE (PATTERN (insn
));
1791 gcc_assert (code
== USE
|| code
== CLOBBER
);
1797 note_reg_set (regno
);
1798 else if (ref
== USE
)
1799 note_reg_use (regno
);
1801 note_reg_clobber (regno
);
1803 /* Pseudos that are REG_EQUIV to something may be replaced
1804 by that during reloading. We need only add dependencies for
1805 the address in the REG_EQUIV note. */
1806 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
1808 rtx t
= get_reg_known_value (regno
);
1810 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
1813 /* Don't let it cross a call after scheduling if it doesn't
1814 already cross one. */
1815 if (REG_N_CALLS_CROSSED (regno
) == 0)
1817 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
1818 deps
->sched_before_next_call
1819 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
1821 add_dependence_list (insn
, deps
->last_function_call
, 1,
1827 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
1828 rtx, X, creating all dependencies generated by the write to the
1829 destination of X, and reads of everything mentioned. */
1832 sched_analyze_1 (struct deps
*deps
, rtx x
, rtx insn
)
1834 rtx dest
= XEXP (x
, 0);
1835 enum rtx_code code
= GET_CODE (x
);
1836 bool cslr_p
= can_start_lhs_rhs_p
;
1838 can_start_lhs_rhs_p
= false;
1844 if (cslr_p
&& sched_deps_info
->start_lhs
)
1845 sched_deps_info
->start_lhs (dest
);
1847 if (GET_CODE (dest
) == PARALLEL
)
1851 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
1852 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
1853 sched_analyze_1 (deps
,
1854 gen_rtx_CLOBBER (VOIDmode
,
1855 XEXP (XVECEXP (dest
, 0, i
), 0)),
1858 if (cslr_p
&& sched_deps_info
->finish_lhs
)
1859 sched_deps_info
->finish_lhs ();
1863 can_start_lhs_rhs_p
= cslr_p
;
1865 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
1867 can_start_lhs_rhs_p
= false;
1873 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
1874 || GET_CODE (dest
) == ZERO_EXTRACT
)
1876 if (GET_CODE (dest
) == STRICT_LOW_PART
1877 || GET_CODE (dest
) == ZERO_EXTRACT
1878 || df_read_modify_subreg_p (dest
))
1880 /* These both read and modify the result. We must handle
1881 them as writes to get proper dependencies for following
1882 instructions. We must handle them as reads to get proper
1883 dependencies from this to previous instructions.
1884 Thus we need to call sched_analyze_2. */
1886 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
1888 if (GET_CODE (dest
) == ZERO_EXTRACT
)
1890 /* The second and third arguments are values read by this insn. */
1891 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
1892 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
1894 dest
= XEXP (dest
, 0);
1899 int regno
= REGNO (dest
);
1900 enum machine_mode mode
= GET_MODE (dest
);
1902 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
1905 /* Treat all writes to a stack register as modifying the TOS. */
1906 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
1908 /* Avoid analyzing the same register twice. */
1909 if (regno
!= FIRST_STACK_REG
)
1910 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
1911 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
1915 else if (MEM_P (dest
))
1917 /* Writing memory. */
1920 if (sched_deps_info
->use_cselib
)
1922 t
= shallow_copy_rtx (dest
);
1923 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
1924 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
1928 /* Pending lists can't get larger with a readonly context. */
1930 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
1931 > MAX_PENDING_LIST_LENGTH
))
1933 /* Flush all pending reads and writes to prevent the pending lists
1934 from getting any larger. Insn scheduling runs too slowly when
1935 these lists get long. When compiling GCC with itself,
1936 this flush occurs 8 times for sparc, and 10 times for m88k using
1937 the default value of 32. */
1938 flush_pending_lists (deps
, insn
, false, true);
1942 rtx pending
, pending_mem
;
1944 pending
= deps
->pending_read_insns
;
1945 pending_mem
= deps
->pending_read_mems
;
1948 if (anti_dependence (XEXP (pending_mem
, 0), t
)
1949 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
1950 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
1953 pending
= XEXP (pending
, 1);
1954 pending_mem
= XEXP (pending_mem
, 1);
1957 pending
= deps
->pending_write_insns
;
1958 pending_mem
= deps
->pending_write_mems
;
1961 if (output_dependence (XEXP (pending_mem
, 0), t
)
1962 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
1963 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
1966 pending
= XEXP (pending
, 1);
1967 pending_mem
= XEXP (pending_mem
, 1);
1970 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
1973 if (!deps
->readonly
)
1974 add_insn_mem_dependence (deps
, false, insn
, dest
);
1976 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
1979 if (cslr_p
&& sched_deps_info
->finish_lhs
)
1980 sched_deps_info
->finish_lhs ();
1982 /* Analyze reads. */
1983 if (GET_CODE (x
) == SET
)
1985 can_start_lhs_rhs_p
= cslr_p
;
1987 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
1989 can_start_lhs_rhs_p
= false;
1993 /* Analyze the uses of memory and registers in rtx X in INSN. */
1995 sched_analyze_2 (struct deps
*deps
, rtx x
, rtx insn
)
2001 bool cslr_p
= can_start_lhs_rhs_p
;
2003 can_start_lhs_rhs_p
= false;
2009 if (cslr_p
&& sched_deps_info
->start_rhs
)
2010 sched_deps_info
->start_rhs (x
);
2012 code
= GET_CODE (x
);
2023 /* Ignore constants. */
2024 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2025 sched_deps_info
->finish_rhs ();
2031 /* User of CC0 depends on immediately preceding insn. */
2032 SCHED_GROUP_P (insn
) = 1;
2033 /* Don't move CC0 setter to another block (it can set up the
2034 same flag for previous CC0 users which is safe). */
2035 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2037 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2038 sched_deps_info
->finish_rhs ();
2045 int regno
= REGNO (x
);
2046 enum machine_mode mode
= GET_MODE (x
);
2048 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2051 /* Treat all reads of a stack register as modifying the TOS. */
2052 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2054 /* Avoid analyzing the same register twice. */
2055 if (regno
!= FIRST_STACK_REG
)
2056 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2057 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2061 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2062 sched_deps_info
->finish_rhs ();
2069 /* Reading memory. */
2071 rtx pending
, pending_mem
;
2074 if (DEBUG_INSN_P (insn
))
2076 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2080 if (sched_deps_info
->use_cselib
)
2082 t
= shallow_copy_rtx (t
);
2083 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
2084 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2087 pending
= deps
->pending_read_insns
;
2088 pending_mem
= deps
->pending_read_mems
;
2091 if (read_dependence (XEXP (pending_mem
, 0), t
)
2092 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2093 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2096 pending
= XEXP (pending
, 1);
2097 pending_mem
= XEXP (pending_mem
, 1);
2100 pending
= deps
->pending_write_insns
;
2101 pending_mem
= deps
->pending_write_mems
;
2104 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
2106 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2107 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2108 sched_deps_info
->generate_spec_deps
2109 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2111 pending
= XEXP (pending
, 1);
2112 pending_mem
= XEXP (pending_mem
, 1);
2115 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2117 if (! JUMP_P (XEXP (u
, 0)))
2118 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2119 else if (deps_may_trap_p (x
))
2121 if ((sched_deps_info
->generate_spec_deps
)
2122 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2124 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2127 note_dep (XEXP (u
, 0), ds
);
2130 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2134 /* Always add these dependencies to pending_reads, since
2135 this insn may be followed by a write. */
2136 if (!deps
->readonly
)
2137 add_insn_mem_dependence (deps
, true, insn
, x
);
2139 /* Take advantage of tail recursion here. */
2140 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2142 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2143 sched_deps_info
->finish_rhs ();
2148 /* Force pending stores to memory in case a trap handler needs them. */
2150 flush_pending_lists (deps
, insn
, true, false);
2153 case UNSPEC_VOLATILE
:
2154 flush_pending_lists (deps
, insn
, true, true);
2160 /* Traditional and volatile asm instructions must be considered to use
2161 and clobber all hard registers, all pseudo-registers and all of
2162 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2164 Consider for instance a volatile asm that changes the fpu rounding
2165 mode. An insn should not be moved across this even if it only uses
2166 pseudo-regs because it might give an incorrectly rounded result. */
2167 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2168 reg_pending_barrier
= TRUE_BARRIER
;
2170 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2171 We can not just fall through here since then we would be confused
2172 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2173 traditional asms unlike their normal usage. */
2175 if (code
== ASM_OPERANDS
)
2177 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2178 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2180 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2181 sched_deps_info
->finish_rhs ();
2192 /* These both read and modify the result. We must handle them as writes
2193 to get proper dependencies for following instructions. We must handle
2194 them as reads to get proper dependencies from this to previous
2195 instructions. Thus we need to pass them to both sched_analyze_1
2196 and sched_analyze_2. We must call sched_analyze_2 first in order
2197 to get the proper antecedent for the read. */
2198 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2199 sched_analyze_1 (deps
, x
, insn
);
2201 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2202 sched_deps_info
->finish_rhs ();
2208 /* op0 = op0 + op1 */
2209 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2210 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2211 sched_analyze_1 (deps
, x
, insn
);
2213 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2214 sched_deps_info
->finish_rhs ();
2222 /* Other cases: walk the insn. */
2223 fmt
= GET_RTX_FORMAT (code
);
2224 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2227 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2228 else if (fmt
[i
] == 'E')
2229 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2230 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2233 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2234 sched_deps_info
->finish_rhs ();
2237 /* Analyze an INSN with pattern X to find all dependencies. */
2239 sched_analyze_insn (struct deps
*deps
, rtx x
, rtx insn
)
2241 RTX_CODE code
= GET_CODE (x
);
2244 reg_set_iterator rsi
;
2246 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2249 if (code
== COND_EXEC
)
2251 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2253 /* ??? Should be recording conditions so we reduce the number of
2254 false dependencies. */
2255 x
= COND_EXEC_CODE (x
);
2256 code
= GET_CODE (x
);
2258 if (code
== SET
|| code
== CLOBBER
)
2260 sched_analyze_1 (deps
, x
, insn
);
2262 /* Bare clobber insns are used for letting life analysis, reg-stack
2263 and others know that a value is dead. Depend on the last call
2264 instruction so that reg-stack won't get confused. */
2265 if (code
== CLOBBER
)
2266 add_dependence_list (insn
, deps
->last_function_call
, 1, REG_DEP_OUTPUT
);
2268 else if (code
== PARALLEL
)
2270 for (i
= XVECLEN (x
, 0); i
--;)
2272 rtx sub
= XVECEXP (x
, 0, i
);
2273 code
= GET_CODE (sub
);
2275 if (code
== COND_EXEC
)
2277 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2278 sub
= COND_EXEC_CODE (sub
);
2279 code
= GET_CODE (sub
);
2281 if (code
== SET
|| code
== CLOBBER
)
2282 sched_analyze_1 (deps
, sub
, insn
);
2284 sched_analyze_2 (deps
, sub
, insn
);
2288 sched_analyze_2 (deps
, x
, insn
);
2290 /* Mark registers CLOBBERED or used by called function. */
2293 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2295 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2296 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2298 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2300 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2301 reg_pending_barrier
= MOVE_BARRIER
;
2307 next
= next_nonnote_insn (insn
);
2308 while (next
&& DEBUG_INSN_P (next
))
2309 next
= next_nonnote_insn (next
);
2310 if (next
&& BARRIER_P (next
))
2311 reg_pending_barrier
= MOVE_BARRIER
;
2314 rtx pending
, pending_mem
;
2316 if (sched_deps_info
->compute_jump_reg_dependencies
)
2318 regset_head tmp_uses
, tmp_sets
;
2319 INIT_REG_SET (&tmp_uses
);
2320 INIT_REG_SET (&tmp_sets
);
2322 (*sched_deps_info
->compute_jump_reg_dependencies
)
2323 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
2324 /* Make latency of jump equal to 0 by using anti-dependence. */
2325 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
, rsi
)
2327 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2328 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2329 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2332 if (!deps
->readonly
)
2334 reg_last
->uses_length
++;
2335 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2338 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
2340 CLEAR_REG_SET (&tmp_uses
);
2341 CLEAR_REG_SET (&tmp_sets
);
2344 /* All memory writes and volatile reads must happen before the
2345 jump. Non-volatile reads must happen before the jump iff
2346 the result is needed by the above register used mask. */
2348 pending
= deps
->pending_write_insns
;
2349 pending_mem
= deps
->pending_write_mems
;
2352 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2353 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2354 pending
= XEXP (pending
, 1);
2355 pending_mem
= XEXP (pending_mem
, 1);
2358 pending
= deps
->pending_read_insns
;
2359 pending_mem
= deps
->pending_read_mems
;
2362 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2363 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2364 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2365 pending
= XEXP (pending
, 1);
2366 pending_mem
= XEXP (pending_mem
, 1);
2369 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2374 /* If this instruction can throw an exception, then moving it changes
2375 where block boundaries fall. This is mighty confusing elsewhere.
2376 Therefore, prevent such an instruction from being moved. Same for
2377 non-jump instructions that define block boundaries.
2378 ??? Unclear whether this is still necessary in EBB mode. If not,
2379 add_branch_dependences should be adjusted for RGN mode instead. */
2380 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2381 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2382 reg_pending_barrier
= MOVE_BARRIER
;
2384 /* Add register dependencies for insn. */
2385 if (DEBUG_INSN_P (insn
))
2387 rtx prev
= deps
->last_debug_insn
;
2390 if (!deps
->readonly
)
2391 deps
->last_debug_insn
= insn
;
2394 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2396 add_dependence_list (insn
, deps
->last_function_call
, 1,
2399 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2400 if (! JUMP_P (XEXP (u
, 0))
2402 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2404 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2406 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2407 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
);
2408 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
);
2410 CLEAR_REG_SET (reg_pending_uses
);
2412 /* Quite often, a debug insn will refer to stuff in the
2413 previous instruction, but the reason we want this
2414 dependency here is to make sure the scheduler doesn't
2415 gratuitously move a debug insn ahead. This could dirty
2416 DF flags and cause additional analysis that wouldn't have
2417 occurred in compilation without debug insns, and such
2418 additional analysis can modify the generated code. */
2419 prev
= PREV_INSN (insn
);
2421 if (prev
&& NONDEBUG_INSN_P (prev
))
2422 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2424 /* If the current insn is conditional, we can't free any
2426 else if (sched_has_condition_p (insn
))
2428 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2430 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2431 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2432 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2434 if (!deps
->readonly
)
2436 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2437 reg_last
->uses_length
++;
2440 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2442 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2443 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2444 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2446 if (!deps
->readonly
)
2448 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2449 reg_last
->clobbers_length
++;
2452 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2454 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2455 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2456 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2457 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2459 if (!deps
->readonly
)
2461 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2462 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2468 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2470 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2471 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2472 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2474 if (!deps
->readonly
)
2476 reg_last
->uses_length
++;
2477 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2480 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2482 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2483 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
2484 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
2486 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2488 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2490 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
2493 if (!deps
->readonly
)
2495 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2496 reg_last
->clobbers_length
= 0;
2497 reg_last
->uses_length
= 0;
2502 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2503 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2506 if (!deps
->readonly
)
2508 reg_last
->clobbers_length
++;
2509 reg_last
->clobbers
= alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2512 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2514 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2515 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2517 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
2519 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2522 if (!deps
->readonly
)
2524 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2525 reg_last
->uses_length
= 0;
2526 reg_last
->clobbers_length
= 0;
2527 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2532 if (!deps
->readonly
)
2534 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
2535 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
2536 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
2538 /* Set up the pending barrier found. */
2539 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
2542 CLEAR_REG_SET (reg_pending_uses
);
2543 CLEAR_REG_SET (reg_pending_clobbers
);
2544 CLEAR_REG_SET (reg_pending_sets
);
2546 /* Add dependencies if a scheduling barrier was found. */
2547 if (reg_pending_barrier
)
2549 /* In the case of barrier the most added dependencies are not
2550 real, so we use anti-dependence here. */
2551 if (sched_has_condition_p (insn
))
2553 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
2555 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2556 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2558 (insn
, reg_last
->sets
, 0,
2559 reg_pending_barrier
== TRUE_BARRIER
? REG_DEP_TRUE
: REG_DEP_ANTI
);
2561 (insn
, reg_last
->clobbers
, 0,
2562 reg_pending_barrier
== TRUE_BARRIER
? REG_DEP_TRUE
: REG_DEP_ANTI
);
2567 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
2569 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2570 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2572 add_dependence_list_and_free
2573 (deps
, insn
, ®_last
->sets
, 0,
2574 reg_pending_barrier
== TRUE_BARRIER
? REG_DEP_TRUE
: REG_DEP_ANTI
);
2575 add_dependence_list_and_free
2576 (deps
, insn
, ®_last
->clobbers
, 0,
2577 reg_pending_barrier
== TRUE_BARRIER
? REG_DEP_TRUE
: REG_DEP_ANTI
);
2579 if (!deps
->readonly
)
2581 reg_last
->uses_length
= 0;
2582 reg_last
->clobbers_length
= 0;
2587 if (!deps
->readonly
)
2588 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
2590 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2591 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2592 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
2595 /* Flush pending lists on jumps, but not on speculative checks. */
2596 if (JUMP_P (insn
) && !(sel_sched_p ()
2597 && sel_insn_is_speculation_check (insn
)))
2598 flush_pending_lists (deps
, insn
, true, true);
2600 if (!deps
->readonly
)
2601 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
2602 reg_pending_barrier
= NOT_A_BARRIER
;
2605 /* If a post-call group is still open, see if it should remain so.
2606 This insn must be a simple move of a hard reg to a pseudo or
2609 We must avoid moving these insns for correctness on
2610 SMALL_REGISTER_CLASS machines, and for special registers like
2611 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
2612 hard regs for all targets. */
2614 if (deps
->in_post_call_group_p
)
2616 rtx tmp
, set
= single_set (insn
);
2617 int src_regno
, dest_regno
;
2621 if (DEBUG_INSN_P (insn
))
2622 /* We don't want to mark debug insns as part of the same
2623 sched group. We know they really aren't, but if we use
2624 debug insns to tell that a call group is over, we'll
2625 get different code if debug insns are not there and
2626 instructions that follow seem like they should be part
2629 Also, if we did, fixup_sched_groups() would move the
2630 deps of the debug insn to the call insn, modifying
2631 non-debug post-dependency counts of the debug insn
2632 dependencies and otherwise messing with the scheduling
2635 Instead, let such debug insns be scheduled freely, but
2636 keep the call group open in case there are insns that
2637 should be part of it afterwards. Since we grant debug
2638 insns higher priority than even sched group insns, it
2639 will all turn out all right. */
2640 goto debug_dont_end_call_group
;
2642 goto end_call_group
;
2645 tmp
= SET_DEST (set
);
2646 if (GET_CODE (tmp
) == SUBREG
)
2647 tmp
= SUBREG_REG (tmp
);
2649 dest_regno
= REGNO (tmp
);
2651 goto end_call_group
;
2653 tmp
= SET_SRC (set
);
2654 if (GET_CODE (tmp
) == SUBREG
)
2655 tmp
= SUBREG_REG (tmp
);
2656 if ((GET_CODE (tmp
) == PLUS
2657 || GET_CODE (tmp
) == MINUS
)
2658 && REG_P (XEXP (tmp
, 0))
2659 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
2660 && dest_regno
== STACK_POINTER_REGNUM
)
2661 src_regno
= STACK_POINTER_REGNUM
;
2662 else if (REG_P (tmp
))
2663 src_regno
= REGNO (tmp
);
2665 goto end_call_group
;
2667 if (src_regno
< FIRST_PSEUDO_REGISTER
2668 || dest_regno
< FIRST_PSEUDO_REGISTER
)
2671 && deps
->in_post_call_group_p
== post_call_initial
)
2672 deps
->in_post_call_group_p
= post_call
;
2674 if (!sel_sched_p () || sched_emulate_haifa_p
)
2676 SCHED_GROUP_P (insn
) = 1;
2677 CANT_MOVE (insn
) = 1;
2683 if (!deps
->readonly
)
2684 deps
->in_post_call_group_p
= not_post_call
;
2688 debug_dont_end_call_group
:
2689 if ((current_sched_info
->flags
& DO_SPECULATION
)
2690 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
2691 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
2695 sel_mark_hard_insn (insn
);
2698 sd_iterator_def sd_it
;
2701 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
2702 sd_iterator_cond (&sd_it
, &dep
);)
2703 change_spec_dep_to_hard (sd_it
);
2708 /* Analyze INSN with DEPS as a context. */
2710 deps_analyze_insn (struct deps
*deps
, rtx insn
)
2712 if (sched_deps_info
->start_insn
)
2713 sched_deps_info
->start_insn (insn
);
2715 if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
) || JUMP_P (insn
))
2717 /* Make each JUMP_INSN (but not a speculative check)
2718 a scheduling barrier for memory references. */
2722 && sel_insn_is_speculation_check (insn
)))
2724 /* Keep the list a reasonable size. */
2725 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
2726 flush_pending_lists (deps
, insn
, true, true);
2728 deps
->last_pending_memory_flush
2729 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
2732 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
2734 else if (CALL_P (insn
))
2738 CANT_MOVE (insn
) = 1;
2740 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2742 /* This is setjmp. Assume that all registers, not just
2743 hard registers, may be clobbered by this call. */
2744 reg_pending_barrier
= MOVE_BARRIER
;
2748 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2749 /* A call may read and modify global register variables. */
2752 SET_REGNO_REG_SET (reg_pending_sets
, i
);
2753 SET_REGNO_REG_SET (reg_pending_uses
, i
);
2755 /* Other call-clobbered hard regs may be clobbered.
2756 Since we only have a choice between 'might be clobbered'
2757 and 'definitely not clobbered', we must include all
2758 partly call-clobbered registers here. */
2759 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
2760 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
2761 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
2762 /* We don't know what set of fixed registers might be used
2763 by the function, but it is certain that the stack pointer
2764 is among them, but be conservative. */
2765 else if (fixed_regs
[i
])
2766 SET_REGNO_REG_SET (reg_pending_uses
, i
);
2767 /* The frame pointer is normally not used by the function
2768 itself, but by the debugger. */
2769 /* ??? MIPS o32 is an exception. It uses the frame pointer
2770 in the macro expansion of jal but does not represent this
2771 fact in the call_insn rtl. */
2772 else if (i
== FRAME_POINTER_REGNUM
2773 || (i
== HARD_FRAME_POINTER_REGNUM
2774 && (! reload_completed
|| frame_pointer_needed
)))
2775 SET_REGNO_REG_SET (reg_pending_uses
, i
);
2778 /* For each insn which shouldn't cross a call, add a dependence
2779 between that insn and this call insn. */
2780 add_dependence_list_and_free (deps
, insn
,
2781 &deps
->sched_before_next_call
, 1,
2784 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
2786 /* If CALL would be in a sched group, then this will violate
2787 convention that sched group insns have dependencies only on the
2788 previous instruction.
2790 Of course one can say: "Hey! What about head of the sched group?"
2791 And I will answer: "Basic principles (one dep per insn) are always
2793 gcc_assert (!SCHED_GROUP_P (insn
));
2795 /* In the absence of interprocedural alias analysis, we must flush
2796 all pending reads and writes, and start new dependencies starting
2797 from here. But only flush writes for constant calls (which may
2798 be passed a pointer to something we haven't written yet). */
2799 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
2801 if (!deps
->readonly
)
2803 /* Remember the last function call for limiting lifetimes. */
2804 free_INSN_LIST_list (&deps
->last_function_call
);
2805 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
2807 /* Before reload, begin a post-call group, so as to keep the
2808 lifetimes of hard registers correct. */
2809 if (! reload_completed
)
2810 deps
->in_post_call_group_p
= post_call
;
2814 if (sched_deps_info
->use_cselib
)
2815 cselib_process_insn (insn
);
2817 /* EH_REGION insn notes can not appear until well after we complete
2820 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
2821 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
2823 if (sched_deps_info
->finish_insn
)
2824 sched_deps_info
->finish_insn ();
2826 /* Fixup the dependencies in the sched group. */
2827 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
2828 && SCHED_GROUP_P (insn
) && !sel_sched_p ())
2829 fixup_sched_groups (insn
);
2832 /* Initialize DEPS for the new block beginning with HEAD. */
2834 deps_start_bb (struct deps
*deps
, rtx head
)
2836 gcc_assert (!deps
->readonly
);
2838 /* Before reload, if the previous block ended in a call, show that
2839 we are inside a post-call group, so as to keep the lifetimes of
2840 hard registers correct. */
2841 if (! reload_completed
&& !LABEL_P (head
))
2843 rtx insn
= prev_nonnote_insn (head
);
2845 while (insn
&& DEBUG_INSN_P (insn
))
2846 insn
= prev_nonnote_insn (insn
);
2847 if (insn
&& CALL_P (insn
))
2848 deps
->in_post_call_group_p
= post_call_initial
;
2852 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
2853 dependencies for each insn. */
2855 sched_analyze (struct deps
*deps
, rtx head
, rtx tail
)
2859 if (sched_deps_info
->use_cselib
)
2862 deps_start_bb (deps
, head
);
2864 for (insn
= head
;; insn
= NEXT_INSN (insn
))
2869 /* And initialize deps_lists. */
2870 sd_init_insn (insn
);
2873 deps_analyze_insn (deps
, insn
);
2877 if (sched_deps_info
->use_cselib
)
2885 /* Helper for sched_free_deps ().
2886 Delete INSN's (RESOLVED_P) backward dependencies. */
2888 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
2890 sd_iterator_def sd_it
;
2892 sd_list_types_def types
;
2895 types
= SD_LIST_RES_BACK
;
2897 types
= SD_LIST_BACK
;
2899 for (sd_it
= sd_iterator_start (insn
, types
);
2900 sd_iterator_cond (&sd_it
, &dep
);)
2902 dep_link_t link
= *sd_it
.linkp
;
2903 dep_node_t node
= DEP_LINK_NODE (link
);
2904 deps_list_t back_list
;
2905 deps_list_t forw_list
;
2907 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
2908 remove_from_deps_list (link
, back_list
);
2909 delete_dep_node (node
);
2913 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
2916 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
2919 rtx next_tail
= NEXT_INSN (tail
);
2921 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
2922 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
2924 /* Clear resolved back deps together with its dep_nodes. */
2925 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
2927 /* Clear forward deps and leave the dep_nodes to the
2928 corresponding back_deps list. */
2930 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
2932 clear_deps_list (INSN_FORW_DEPS (insn
));
2934 sd_finish_insn (insn
);
2938 /* Initialize variables for region data dependence analysis.
2939 n_bbs is the number of region blocks. */
2942 init_deps (struct deps
*deps
)
2944 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
2946 deps
->max_reg
= max_reg
;
2947 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
2948 INIT_REG_SET (&deps
->reg_last_in_use
);
2949 INIT_REG_SET (&deps
->reg_conditional_sets
);
2951 deps
->pending_read_insns
= 0;
2952 deps
->pending_read_mems
= 0;
2953 deps
->pending_write_insns
= 0;
2954 deps
->pending_write_mems
= 0;
2955 deps
->pending_read_list_length
= 0;
2956 deps
->pending_write_list_length
= 0;
2957 deps
->pending_flush_length
= 0;
2958 deps
->last_pending_memory_flush
= 0;
2959 deps
->last_function_call
= 0;
2960 deps
->sched_before_next_call
= 0;
2961 deps
->in_post_call_group_p
= not_post_call
;
2962 deps
->last_debug_insn
= 0;
2963 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
2967 /* Free insn lists found in DEPS. */
2970 free_deps (struct deps
*deps
)
2973 reg_set_iterator rsi
;
2975 free_INSN_LIST_list (&deps
->pending_read_insns
);
2976 free_EXPR_LIST_list (&deps
->pending_read_mems
);
2977 free_INSN_LIST_list (&deps
->pending_write_insns
);
2978 free_EXPR_LIST_list (&deps
->pending_write_mems
);
2979 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
2981 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
2982 times. For a testcase with 42000 regs and 8000 small basic blocks,
2983 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
2984 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
2986 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2988 free_INSN_LIST_list (®_last
->uses
);
2990 free_INSN_LIST_list (®_last
->sets
);
2991 if (reg_last
->clobbers
)
2992 free_INSN_LIST_list (®_last
->clobbers
);
2994 CLEAR_REG_SET (&deps
->reg_last_in_use
);
2995 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
2997 free (deps
->reg_last
);
2998 deps
->reg_last
= NULL
;
3003 /* Remove INSN from dependence contexts DEPS. Caution: reg_conditional_sets
3006 remove_from_deps (struct deps
*deps
, rtx insn
)
3010 reg_set_iterator rsi
;
3012 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3013 &deps
->pending_read_mems
);
3014 deps
->pending_read_list_length
-= removed
;
3015 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3016 &deps
->pending_write_mems
);
3017 deps
->pending_write_list_length
-= removed
;
3018 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3019 deps
->pending_flush_length
-= removed
;
3021 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3023 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3025 remove_from_dependence_list (insn
, ®_last
->uses
);
3027 remove_from_dependence_list (insn
, ®_last
->sets
);
3028 if (reg_last
->clobbers
)
3029 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3030 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->clobbers
)
3031 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3035 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3036 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3039 /* Init deps data vector. */
3041 init_deps_data_vector (void)
3043 int reserve
= (sched_max_luid
+ 1
3044 - VEC_length (haifa_deps_insn_data_def
, h_d_i_d
));
3046 && ! VEC_space (haifa_deps_insn_data_def
, h_d_i_d
, reserve
))
3047 VEC_safe_grow_cleared (haifa_deps_insn_data_def
, heap
, h_d_i_d
,
3048 3 * sched_max_luid
/ 2);
3051 /* If it is profitable to use them, initialize or extend (depending on
3052 GLOBAL_P) dependency data. */
3054 sched_deps_init (bool global_p
)
3056 /* Average number of insns in the basic block.
3057 '+ 1' is used to make it nonzero. */
3058 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3060 init_deps_data_vector ();
3062 /* We use another caching mechanism for selective scheduling, so
3063 we don't use this one. */
3064 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3066 /* ?!? We could save some memory by computing a per-region luid mapping
3067 which could reduce both the number of vectors in the cache and the
3068 size of each vector. Instead we just avoid the cache entirely unless
3069 the average number of instructions in a basic block is very high. See
3070 the comment before the declaration of true_dependency_cache for
3071 what we consider "very high". */
3073 extend_dependency_caches (sched_max_luid
, true);
3078 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3079 /* Allocate lists for one block at a time. */
3081 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3082 /* Allocate nodes for one block at a time.
3083 We assume that average insn has
3085 5 * insns_in_block
);
3090 /* Create or extend (depending on CREATE_P) dependency caches to
3093 extend_dependency_caches (int n
, bool create_p
)
3095 if (create_p
|| true_dependency_cache
)
3097 int i
, luid
= cache_size
+ n
;
3099 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
3101 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
3102 output_dependency_cache
, luid
);
3103 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
3106 if (current_sched_info
->flags
& DO_SPECULATION
)
3107 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
3110 for (i
= cache_size
; i
< luid
; i
++)
3112 bitmap_initialize (&true_dependency_cache
[i
], 0);
3113 bitmap_initialize (&output_dependency_cache
[i
], 0);
3114 bitmap_initialize (&anti_dependency_cache
[i
], 0);
3116 if (current_sched_info
->flags
& DO_SPECULATION
)
3117 bitmap_initialize (&spec_dependency_cache
[i
], 0);
3123 /* Finalize dependency information for the whole function. */
3125 sched_deps_finish (void)
3127 gcc_assert (deps_pools_are_empty_p ());
3128 free_alloc_pool_if_empty (&dn_pool
);
3129 free_alloc_pool_if_empty (&dl_pool
);
3130 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
3132 VEC_free (haifa_deps_insn_data_def
, heap
, h_d_i_d
);
3135 if (true_dependency_cache
)
3139 for (i
= 0; i
< cache_size
; i
++)
3141 bitmap_clear (&true_dependency_cache
[i
]);
3142 bitmap_clear (&output_dependency_cache
[i
]);
3143 bitmap_clear (&anti_dependency_cache
[i
]);
3145 if (sched_deps_info
->generate_spec_deps
)
3146 bitmap_clear (&spec_dependency_cache
[i
]);
3148 free (true_dependency_cache
);
3149 true_dependency_cache
= NULL
;
3150 free (output_dependency_cache
);
3151 output_dependency_cache
= NULL
;
3152 free (anti_dependency_cache
);
3153 anti_dependency_cache
= NULL
;
3155 if (sched_deps_info
->generate_spec_deps
)
3157 free (spec_dependency_cache
);
3158 spec_dependency_cache
= NULL
;
3164 /* Initialize some global variables needed by the dependency analysis
3168 init_deps_global (void)
3170 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
3171 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
3172 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
3173 reg_pending_barrier
= NOT_A_BARRIER
;
3175 if (!sel_sched_p () || sched_emulate_haifa_p
)
3177 sched_deps_info
->start_insn
= haifa_start_insn
;
3178 sched_deps_info
->finish_insn
= haifa_finish_insn
;
3180 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
3181 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
3182 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
3184 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
3185 sched_deps_info
->note_dep
= haifa_note_dep
;
3189 /* Free everything used by the dependency analysis code. */
3192 finish_deps_global (void)
3194 FREE_REG_SET (reg_pending_sets
);
3195 FREE_REG_SET (reg_pending_clobbers
);
3196 FREE_REG_SET (reg_pending_uses
);
3199 /* Estimate the weakness of dependence between MEM1 and MEM2. */
3201 estimate_dep_weak (rtx mem1
, rtx mem2
)
3206 /* MEMs are the same - don't speculate. */
3207 return MIN_DEP_WEAK
;
3209 r1
= XEXP (mem1
, 0);
3210 r2
= XEXP (mem2
, 0);
3213 || (REG_P (r1
) && REG_P (r2
)
3214 && REGNO (r1
) == REGNO (r2
)))
3215 /* Again, MEMs are the same. */
3216 return MIN_DEP_WEAK
;
3217 else if ((REG_P (r1
) && !REG_P (r2
))
3218 || (!REG_P (r1
) && REG_P (r2
)))
3219 /* Different addressing modes - reason to be more speculative,
3221 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
3223 /* We can't say anything about the dependence. */
3224 return UNCERTAIN_DEP_WEAK
;
3227 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3228 This function can handle same INSN and ELEM (INSN == ELEM).
3229 It is a convenience wrapper. */
3231 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
3236 if (dep_type
== REG_DEP_TRUE
)
3238 else if (dep_type
== REG_DEP_OUTPUT
)
3242 gcc_assert (dep_type
== REG_DEP_ANTI
);
3246 /* When add_dependence is called from inside sched-deps.c, we expect
3247 cur_insn to be non-null. */
3248 internal
= cur_insn
!= NULL
;
3250 gcc_assert (insn
== cur_insn
);
3254 note_dep (elem
, ds
);
3259 /* Return weakness of speculative type TYPE in the dep_status DS. */
3261 get_dep_weak_1 (ds_t ds
, ds_t type
)
3267 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
3268 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
3269 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
3270 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
3271 default: gcc_unreachable ();
3278 get_dep_weak (ds_t ds
, ds_t type
)
3280 dw_t dw
= get_dep_weak_1 (ds
, type
);
3282 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3286 /* Return the dep_status, which has the same parameters as DS, except for
3287 speculative type TYPE, that will have weakness DW. */
3289 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
3291 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3296 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
3297 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
3298 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
3299 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
3300 default: gcc_unreachable ();
3305 /* Return the join of two dep_statuses DS1 and DS2.
3306 If MAX_P is true then choose the greater probability,
3307 otherwise multiply probabilities.
3308 This function assumes that both DS1 and DS2 contain speculative bits. */
3310 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
3314 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
3316 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
3318 t
= FIRST_SPEC_TYPE
;
3321 if ((ds1
& t
) && !(ds2
& t
))
3323 else if (!(ds1
& t
) && (ds2
& t
))
3325 else if ((ds1
& t
) && (ds2
& t
))
3327 dw_t dw1
= get_dep_weak (ds1
, t
);
3328 dw_t dw2
= get_dep_weak (ds2
, t
);
3333 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
3335 if (dw
< MIN_DEP_WEAK
)
3346 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
3349 if (t
== LAST_SPEC_TYPE
)
3351 t
<<= SPEC_TYPE_SHIFT
;
3358 /* Return the join of two dep_statuses DS1 and DS2.
3359 This function assumes that both DS1 and DS2 contain speculative bits. */
3361 ds_merge (ds_t ds1
, ds_t ds2
)
3363 return ds_merge_1 (ds1
, ds2
, false);
3366 /* Return the join of two dep_statuses DS1 and DS2. */
3368 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
3370 ds_t new_status
= ds
| ds2
;
3372 if (new_status
& SPECULATIVE
)
3374 if ((ds
&& !(ds
& SPECULATIVE
))
3375 || (ds2
&& !(ds2
& SPECULATIVE
)))
3376 /* Then this dep can't be speculative. */
3377 new_status
&= ~SPECULATIVE
;
3380 /* Both are speculative. Merging probabilities. */
3385 dw
= estimate_dep_weak (mem1
, mem2
);
3386 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
3394 new_status
= ds_merge (ds2
, ds
);
3401 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
3404 ds_max_merge (ds_t ds1
, ds_t ds2
)
3406 if (ds1
== 0 && ds2
== 0)
3409 if (ds1
== 0 && ds2
!= 0)
3412 if (ds1
!= 0 && ds2
== 0)
3415 return ds_merge_1 (ds1
, ds2
, true);
3418 /* Return the probability of speculation success for the speculation
3426 dt
= FIRST_SPEC_TYPE
;
3431 res
*= (ds_t
) get_dep_weak (ds
, dt
);
3435 if (dt
== LAST_SPEC_TYPE
)
3437 dt
<<= SPEC_TYPE_SHIFT
;
3443 res
/= MAX_DEP_WEAK
;
3445 if (res
< MIN_DEP_WEAK
)
3448 gcc_assert (res
<= MAX_DEP_WEAK
);
3453 /* Return a dep status that contains all speculation types of DS. */
3455 ds_get_speculation_types (ds_t ds
)
3457 if (ds
& BEGIN_DATA
)
3459 if (ds
& BE_IN_DATA
)
3461 if (ds
& BEGIN_CONTROL
)
3462 ds
|= BEGIN_CONTROL
;
3463 if (ds
& BE_IN_CONTROL
)
3464 ds
|= BE_IN_CONTROL
;
3466 return ds
& SPECULATIVE
;
3469 /* Return a dep status that contains maximal weakness for each speculation
3470 type present in DS. */
3472 ds_get_max_dep_weak (ds_t ds
)
3474 if (ds
& BEGIN_DATA
)
3475 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
3476 if (ds
& BE_IN_DATA
)
3477 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
3478 if (ds
& BEGIN_CONTROL
)
3479 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
3480 if (ds
& BE_IN_CONTROL
)
3481 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
3486 /* Dump information about the dependence status S. */
3488 dump_ds (FILE *f
, ds_t s
)
3493 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
3495 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
3496 if (s
& BEGIN_CONTROL
)
3497 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
3498 if (s
& BE_IN_CONTROL
)
3499 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
3502 fprintf (f
, "HARD_DEP; ");
3505 fprintf (f
, "DEP_TRUE; ");
3507 fprintf (f
, "DEP_ANTI; ");
3509 fprintf (f
, "DEP_OUTPUT; ");
3517 dump_ds (stderr
, s
);
3518 fprintf (stderr
, "\n");
3521 #ifdef ENABLE_CHECKING
3522 /* Verify that dependence type and status are consistent.
3523 If RELAXED_P is true, then skip dep_weakness checks. */
3525 check_dep (dep_t dep
, bool relaxed_p
)
3527 enum reg_note dt
= DEP_TYPE (dep
);
3528 ds_t ds
= DEP_STATUS (dep
);
3530 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
3532 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
3534 gcc_assert (ds
== -1);
3538 /* Check that dependence type contains the same bits as the status. */
3539 if (dt
== REG_DEP_TRUE
)
3540 gcc_assert (ds
& DEP_TRUE
);
3541 else if (dt
== REG_DEP_OUTPUT
)
3542 gcc_assert ((ds
& DEP_OUTPUT
)
3543 && !(ds
& DEP_TRUE
));
3545 gcc_assert ((dt
== REG_DEP_ANTI
)
3547 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
3549 /* HARD_DEP can not appear in dep_status of a link. */
3550 gcc_assert (!(ds
& HARD_DEP
));
3552 /* Check that dependence status is set correctly when speculation is not
3554 if (!sched_deps_info
->generate_spec_deps
)
3555 gcc_assert (!(ds
& SPECULATIVE
));
3556 else if (ds
& SPECULATIVE
)
3560 ds_t type
= FIRST_SPEC_TYPE
;
3562 /* Check that dependence weakness is in proper range. */
3566 get_dep_weak (ds
, type
);
3568 if (type
== LAST_SPEC_TYPE
)
3570 type
<<= SPEC_TYPE_SHIFT
;
3575 if (ds
& BEGIN_SPEC
)
3577 /* Only true dependence can be data speculative. */
3578 if (ds
& BEGIN_DATA
)
3579 gcc_assert (ds
& DEP_TRUE
);
3581 /* Control dependencies in the insn scheduler are represented by
3582 anti-dependencies, therefore only anti dependence can be
3583 control speculative. */
3584 if (ds
& BEGIN_CONTROL
)
3585 gcc_assert (ds
& DEP_ANTI
);
3589 /* Subsequent speculations should resolve true dependencies. */
3590 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
3593 /* Check that true and anti dependencies can't have other speculative
3596 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
3597 /* An output dependence can't be speculative at all. */
3598 gcc_assert (!(ds
& DEP_OUTPUT
));
3600 gcc_assert (ds
& BEGIN_CONTROL
);
3603 #endif /* ENABLE_CHECKING */
3605 #endif /* INSN_SCHEDULING */