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"
46 #ifdef INSN_SCHEDULING
48 #ifdef ENABLE_CHECKING
54 /* Holds current parameters for the dependency analyzer. */
55 struct sched_deps_info_def
*sched_deps_info
;
57 /* The data is specific to the Haifa scheduler. */
58 VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
= NULL
;
60 /* Return the major type present in the DS. */
68 return REG_DEP_OUTPUT
;
70 gcc_assert (ds
& DEP_ANTI
);
75 /* Return equivalent dep_status. */
77 dk_to_ds (enum reg_note dk
)
88 gcc_assert (dk
== REG_DEP_ANTI
);
93 /* Functions to operate with dependence information container - dep_t. */
95 /* Init DEP with the arguments. */
97 init_dep_1 (dep_t dep
, rtx pro
, rtx con
, enum reg_note type
, ds_t ds
)
101 DEP_TYPE (dep
) = type
;
102 DEP_STATUS (dep
) = ds
;
105 /* Init DEP with the arguments.
106 While most of the scheduler (including targets) only need the major type
107 of the dependency, it is convenient to hide full dep_status from them. */
109 init_dep (dep_t dep
, rtx pro
, rtx con
, enum reg_note kind
)
113 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
114 ds
= dk_to_ds (kind
);
118 init_dep_1 (dep
, pro
, con
, kind
, ds
);
121 /* Make a copy of FROM in TO. */
123 copy_dep (dep_t to
, dep_t from
)
125 memcpy (to
, from
, sizeof (*to
));
128 static void dump_ds (FILE *, ds_t
);
130 /* Define flags for dump_dep (). */
132 /* Dump producer of the dependence. */
133 #define DUMP_DEP_PRO (2)
135 /* Dump consumer of the dependence. */
136 #define DUMP_DEP_CON (4)
138 /* Dump type of the dependence. */
139 #define DUMP_DEP_TYPE (8)
141 /* Dump status of the dependence. */
142 #define DUMP_DEP_STATUS (16)
144 /* Dump all information about the dependence. */
145 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
149 FLAGS is a bit mask specifying what information about DEP needs
151 If FLAGS has the very first bit set, then dump all information about DEP
152 and propagate this bit into the callee dump functions. */
154 dump_dep (FILE *dump
, dep_t dep
, int flags
)
157 flags
|= DUMP_DEP_ALL
;
161 if (flags
& DUMP_DEP_PRO
)
162 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
164 if (flags
& DUMP_DEP_CON
)
165 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
167 if (flags
& DUMP_DEP_TYPE
)
170 enum reg_note type
= DEP_TYPE (dep
);
191 fprintf (dump
, "%c; ", t
);
194 if (flags
& DUMP_DEP_STATUS
)
196 if (current_sched_info
->flags
& USE_DEPS_LIST
)
197 dump_ds (dump
, DEP_STATUS (dep
));
203 /* Default flags for dump_dep (). */
204 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
206 /* Dump all fields of DEP to STDERR. */
208 sd_debug_dep (dep_t dep
)
210 dump_dep (stderr
, dep
, 1);
211 fprintf (stderr
, "\n");
214 /* Determine whether DEP is a dependency link of a non-debug insn on a
218 depl_on_debug_p (dep_link_t dep
)
220 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
221 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
224 /* Functions to operate with a single link from the dependencies lists -
227 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
230 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
232 dep_link_t next
= *prev_nextp
;
234 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
235 && DEP_LINK_NEXT (l
) == NULL
);
237 /* Init node being inserted. */
238 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
239 DEP_LINK_NEXT (l
) = next
;
244 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
246 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
253 /* Add dep_link LINK to deps_list L. */
255 add_to_deps_list (dep_link_t link
, deps_list_t l
)
257 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
259 /* Don't count debug deps. */
260 if (!depl_on_debug_p (link
))
261 ++DEPS_LIST_N_LINKS (l
);
264 /* Detach dep_link L from the list. */
266 detach_dep_link (dep_link_t l
)
268 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
269 dep_link_t next
= DEP_LINK_NEXT (l
);
274 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
276 DEP_LINK_PREV_NEXTP (l
) = NULL
;
277 DEP_LINK_NEXT (l
) = NULL
;
280 /* Remove link LINK from list LIST. */
282 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
284 detach_dep_link (link
);
286 /* Don't count debug deps. */
287 if (!depl_on_debug_p (link
))
288 --DEPS_LIST_N_LINKS (list
);
291 /* Move link LINK from list FROM to list TO. */
293 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
295 remove_from_deps_list (link
, from
);
296 add_to_deps_list (link
, to
);
299 /* Return true of LINK is not attached to any list. */
301 dep_link_is_detached_p (dep_link_t link
)
303 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
306 /* Pool to hold all dependency nodes (dep_node_t). */
307 static alloc_pool dn_pool
;
309 /* Number of dep_nodes out there. */
310 static int dn_pool_diff
= 0;
312 /* Create a dep_node. */
314 create_dep_node (void)
316 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
317 dep_link_t back
= DEP_NODE_BACK (n
);
318 dep_link_t forw
= DEP_NODE_FORW (n
);
320 DEP_LINK_NODE (back
) = n
;
321 DEP_LINK_NEXT (back
) = NULL
;
322 DEP_LINK_PREV_NEXTP (back
) = NULL
;
324 DEP_LINK_NODE (forw
) = n
;
325 DEP_LINK_NEXT (forw
) = NULL
;
326 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
333 /* Delete dep_node N. N must not be connected to any deps_list. */
335 delete_dep_node (dep_node_t n
)
337 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
338 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
342 pool_free (dn_pool
, n
);
345 /* Pool to hold dependencies lists (deps_list_t). */
346 static alloc_pool dl_pool
;
348 /* Number of deps_lists out there. */
349 static int dl_pool_diff
= 0;
351 /* Functions to operate with dependences lists - deps_list_t. */
353 /* Return true if list L is empty. */
355 deps_list_empty_p (deps_list_t l
)
357 return DEPS_LIST_N_LINKS (l
) == 0;
360 /* Create a new deps_list. */
362 create_deps_list (void)
364 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
366 DEPS_LIST_FIRST (l
) = NULL
;
367 DEPS_LIST_N_LINKS (l
) = 0;
373 /* Free deps_list L. */
375 free_deps_list (deps_list_t l
)
377 gcc_assert (deps_list_empty_p (l
));
381 pool_free (dl_pool
, l
);
384 /* Return true if there is no dep_nodes and deps_lists out there.
385 After the region is scheduled all the dependency nodes and lists
386 should [generally] be returned to pool. */
388 deps_pools_are_empty_p (void)
390 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
393 /* Remove all elements from L. */
395 clear_deps_list (deps_list_t l
)
399 dep_link_t link
= DEPS_LIST_FIRST (l
);
404 remove_from_deps_list (link
, l
);
409 static regset reg_pending_sets
;
410 static regset reg_pending_clobbers
;
411 static regset reg_pending_uses
;
412 static enum reg_pending_barrier_mode reg_pending_barrier
;
414 /* Hard registers implicitly clobbered or used (or may be implicitly
415 clobbered or used) by the currently analyzed insn. For example,
416 insn in its constraint has one register class. Even if there is
417 currently no hard register in the insn, the particular hard
418 register will be in the insn after reload pass because the
419 constraint requires it. */
420 static HARD_REG_SET implicit_reg_pending_clobbers
;
421 static HARD_REG_SET implicit_reg_pending_uses
;
423 /* To speed up the test for duplicate dependency links we keep a
424 record of dependencies created by add_dependence when the average
425 number of instructions in a basic block is very large.
427 Studies have shown that there is typically around 5 instructions between
428 branches for typical C code. So we can make a guess that the average
429 basic block is approximately 5 instructions long; we will choose 100X
430 the average size as a very large basic block.
432 Each insn has associated bitmaps for its dependencies. Each bitmap
433 has enough entries to represent a dependency on any other insn in
434 the insn chain. All bitmap for true dependencies cache is
435 allocated then the rest two ones are also allocated. */
436 static bitmap_head
*true_dependency_cache
= NULL
;
437 static bitmap_head
*output_dependency_cache
= NULL
;
438 static bitmap_head
*anti_dependency_cache
= NULL
;
439 static bitmap_head
*spec_dependency_cache
= NULL
;
440 static int cache_size
;
442 static int deps_may_trap_p (const_rtx
);
443 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
);
444 static void add_dependence_list_and_free (struct deps
*, rtx
,
445 rtx
*, int, enum reg_note
);
446 static void delete_all_dependences (rtx
);
447 static void fixup_sched_groups (rtx
);
449 static void flush_pending_lists (struct deps
*, rtx
, int, int);
450 static void sched_analyze_1 (struct deps
*, rtx
, rtx
);
451 static void sched_analyze_2 (struct deps
*, rtx
, rtx
);
452 static void sched_analyze_insn (struct deps
*, rtx
, rtx
);
454 static bool sched_has_condition_p (const_rtx
);
455 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
457 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
459 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
461 #ifdef ENABLE_CHECKING
462 static void check_dep (dep_t
, bool);
465 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
468 deps_may_trap_p (const_rtx mem
)
470 const_rtx addr
= XEXP (mem
, 0);
472 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
474 const_rtx t
= get_reg_known_value (REGNO (addr
));
478 return rtx_addr_can_trap_p (addr
);
482 /* Find the condition under which INSN is executed. If REV is not NULL,
483 it is set to TRUE when the returned comparison should be reversed
484 to get the actual condition. */
486 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
488 rtx pat
= PATTERN (insn
);
497 if (GET_CODE (pat
) == COND_EXEC
)
498 return COND_EXEC_TEST (pat
);
500 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
503 src
= SET_SRC (pc_set (insn
));
505 if (XEXP (src
, 2) == pc_rtx
)
506 return XEXP (src
, 0);
507 else if (XEXP (src
, 1) == pc_rtx
)
509 rtx cond
= XEXP (src
, 0);
510 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
512 if (revcode
== UNKNOWN
)
523 /* True when we can find a condition under which INSN is executed. */
525 sched_has_condition_p (const_rtx insn
)
527 return !! sched_get_condition_with_rev (insn
, NULL
);
532 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
534 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
536 if (COMPARISON_P (cond1
)
537 && COMPARISON_P (cond2
)
538 && GET_CODE (cond1
) ==
540 ? reversed_comparison_code (cond2
, NULL
)
542 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
543 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
548 /* Return true if insn1 and insn2 can never depend on one another because
549 the conditions under which they are executed are mutually exclusive. */
551 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
554 bool rev1
= false, rev2
= false;
556 /* df doesn't handle conditional lifetimes entirely correctly;
557 calls mess up the conditional lifetimes. */
558 if (!CALL_P (insn1
) && !CALL_P (insn2
))
560 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
561 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
563 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
564 /* Make sure first instruction doesn't affect condition of second
565 instruction if switched. */
566 && !modified_in_p (cond1
, insn2
)
567 /* Make sure second instruction doesn't affect condition of first
568 instruction if switched. */
569 && !modified_in_p (cond2
, insn1
))
576 /* Return true if INSN can potentially be speculated with type DS. */
578 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
580 if (HAS_INTERNAL_DEP (insn
))
583 if (!NONJUMP_INSN_P (insn
))
586 if (SCHED_GROUP_P (insn
))
589 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
592 if (side_effects_p (PATTERN (insn
)))
596 /* The following instructions, which depend on a speculatively scheduled
597 instruction, cannot be speculatively scheduled along. */
599 if (may_trap_p (PATTERN (insn
)))
600 /* If instruction might trap, it cannot be speculatively scheduled.
601 For control speculation it's obvious why and for data speculation
602 it's because the insn might get wrong input if speculation
603 wasn't successful. */
606 if ((ds
& BE_IN_DATA
)
607 && sched_has_condition_p (insn
))
608 /* If this is a predicated instruction, then it cannot be
609 speculatively scheduled. See PR35659. */
616 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
617 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
618 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
619 This function is used to switch sd_iterator to the next list.
620 !!! For internal use only. Might consider moving it to sched-int.h. */
622 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
623 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
625 sd_list_types_def types
= *types_ptr
;
627 if (types
& SD_LIST_HARD_BACK
)
629 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
630 *resolved_p_ptr
= false;
631 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
633 else if (types
& SD_LIST_SPEC_BACK
)
635 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
636 *resolved_p_ptr
= false;
637 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
639 else if (types
& SD_LIST_FORW
)
641 *list_ptr
= INSN_FORW_DEPS (insn
);
642 *resolved_p_ptr
= false;
643 *types_ptr
= types
& ~SD_LIST_FORW
;
645 else if (types
& SD_LIST_RES_BACK
)
647 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
648 *resolved_p_ptr
= true;
649 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
651 else if (types
& SD_LIST_RES_FORW
)
653 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
654 *resolved_p_ptr
= true;
655 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
660 *resolved_p_ptr
= false;
661 *types_ptr
= SD_LIST_NONE
;
665 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
667 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
671 while (list_types
!= SD_LIST_NONE
)
676 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
678 size
+= DEPS_LIST_N_LINKS (list
);
684 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
687 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
689 while (list_types
!= SD_LIST_NONE
)
694 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
695 if (!deps_list_empty_p (list
))
702 /* Initialize data for INSN. */
704 sd_init_insn (rtx insn
)
706 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
707 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
708 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
709 INSN_FORW_DEPS (insn
) = create_deps_list ();
710 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
712 if (DEBUG_INSN_P (insn
))
713 DEBUG_INSN_SCHED_P (insn
) = TRUE
;
715 /* ??? It would be nice to allocate dependency caches here. */
718 /* Free data for INSN. */
720 sd_finish_insn (rtx insn
)
722 /* ??? It would be nice to deallocate dependency caches here. */
724 if (DEBUG_INSN_P (insn
))
726 gcc_assert (DEBUG_INSN_SCHED_P (insn
));
727 DEBUG_INSN_SCHED_P (insn
) = FALSE
;
730 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
731 INSN_HARD_BACK_DEPS (insn
) = NULL
;
733 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
734 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
736 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
737 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
739 free_deps_list (INSN_FORW_DEPS (insn
));
740 INSN_FORW_DEPS (insn
) = NULL
;
742 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
743 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
746 /* Find a dependency between producer PRO and consumer CON.
747 Search through resolved dependency lists if RESOLVED_P is true.
748 If no such dependency is found return NULL,
749 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
750 with an iterator pointing to it. */
752 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
753 sd_iterator_def
*sd_it_ptr
)
755 sd_list_types_def pro_list_type
;
756 sd_list_types_def con_list_type
;
757 sd_iterator_def sd_it
;
759 bool found_p
= false;
763 pro_list_type
= SD_LIST_RES_FORW
;
764 con_list_type
= SD_LIST_RES_BACK
;
768 pro_list_type
= SD_LIST_FORW
;
769 con_list_type
= SD_LIST_BACK
;
772 /* Walk through either back list of INSN or forw list of ELEM
773 depending on which one is shorter. */
774 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
776 /* Find the dep_link with producer PRO in consumer's back_deps. */
777 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
778 if (DEP_PRO (dep
) == pro
)
786 /* Find the dep_link with consumer CON in producer's forw_deps. */
787 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
788 if (DEP_CON (dep
) == con
)
797 if (sd_it_ptr
!= NULL
)
806 /* Find a dependency between producer PRO and consumer CON.
807 Use dependency [if available] to check if dependency is present at all.
808 Search through resolved dependency lists if RESOLVED_P is true.
809 If the dependency or NULL if none found. */
811 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
813 if (true_dependency_cache
!= NULL
)
814 /* Avoiding the list walk below can cut compile times dramatically
817 int elem_luid
= INSN_LUID (pro
);
818 int insn_luid
= INSN_LUID (con
);
820 gcc_assert (output_dependency_cache
!= NULL
821 && anti_dependency_cache
!= NULL
);
823 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
824 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
825 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
829 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
832 /* Add or update a dependence described by DEP.
833 MEM1 and MEM2, if non-null, correspond to memory locations in case of
836 The function returns a value indicating if an old entry has been changed
837 or a new entry has been added to insn's backward deps.
839 This function merely checks if producer and consumer is the same insn
840 and doesn't create a dep in this case. Actual manipulation of
841 dependence data structures is performed in add_or_update_dep_1. */
842 static enum DEPS_ADJUST_RESULT
843 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
845 rtx elem
= DEP_PRO (dep
);
846 rtx insn
= DEP_CON (dep
);
848 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
850 /* Don't depend an insn on itself. */
853 if (sched_deps_info
->generate_spec_deps
)
854 /* INSN has an internal dependence, which we can't overcome. */
855 HAS_INTERNAL_DEP (insn
) = 1;
860 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
863 /* Ask dependency caches what needs to be done for dependence DEP.
864 Return DEP_CREATED if new dependence should be created and there is no
865 need to try to find one searching the dependencies lists.
866 Return DEP_PRESENT if there already is a dependence described by DEP and
867 hence nothing is to be done.
868 Return DEP_CHANGED if there already is a dependence, but it should be
869 updated to incorporate additional information from DEP. */
870 static enum DEPS_ADJUST_RESULT
871 ask_dependency_caches (dep_t dep
)
873 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
874 int insn_luid
= INSN_LUID (DEP_CON (dep
));
876 gcc_assert (true_dependency_cache
!= NULL
877 && output_dependency_cache
!= NULL
878 && anti_dependency_cache
!= NULL
);
880 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
882 enum reg_note present_dep_type
;
884 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
885 present_dep_type
= REG_DEP_TRUE
;
886 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
887 present_dep_type
= REG_DEP_OUTPUT
;
888 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
889 present_dep_type
= REG_DEP_ANTI
;
891 /* There is no existing dep so it should be created. */
894 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
895 /* DEP does not add anything to the existing dependence. */
900 ds_t present_dep_types
= 0;
902 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
903 present_dep_types
|= DEP_TRUE
;
904 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
905 present_dep_types
|= DEP_OUTPUT
;
906 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
907 present_dep_types
|= DEP_ANTI
;
909 if (present_dep_types
== 0)
910 /* There is no existing dep so it should be created. */
913 if (!(current_sched_info
->flags
& DO_SPECULATION
)
914 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
916 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
917 == present_dep_types
)
918 /* DEP does not add anything to the existing dependence. */
923 /* Only true dependencies can be data speculative and
924 only anti dependencies can be control speculative. */
925 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
926 == present_dep_types
);
928 /* if (DEP is SPECULATIVE) then
929 ..we should update DEP_STATUS
931 ..we should reset existing dep to non-speculative. */
938 /* Set dependency caches according to DEP. */
940 set_dependency_caches (dep_t dep
)
942 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
943 int insn_luid
= INSN_LUID (DEP_CON (dep
));
945 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
947 switch (DEP_TYPE (dep
))
950 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
954 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
958 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
967 ds_t ds
= DEP_STATUS (dep
);
970 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
972 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
974 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
976 if (ds
& SPECULATIVE
)
978 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
979 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
984 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
985 caches accordingly. */
987 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
989 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
990 int insn_luid
= INSN_LUID (DEP_CON (dep
));
992 /* Clear corresponding cache entry because type of the link
993 may have changed. Keep them if we use_deps_list. */
994 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
999 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1003 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1011 set_dependency_caches (dep
);
1014 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1016 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1018 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1019 dep_link_t link
= DEP_NODE_BACK (node
);
1020 dep_t dep
= DEP_NODE_DEP (node
);
1021 rtx elem
= DEP_PRO (dep
);
1022 rtx insn
= DEP_CON (dep
);
1024 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1026 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1028 if (true_dependency_cache
!= NULL
)
1029 /* Clear the cache entry. */
1030 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1034 /* Update DEP to incorporate information from NEW_DEP.
1035 SD_IT points to DEP in case it should be moved to another list.
1036 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1037 data-speculative dependence should be updated. */
1038 static enum DEPS_ADJUST_RESULT
1039 update_dep (dep_t dep
, dep_t new_dep
,
1040 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1041 rtx mem1 ATTRIBUTE_UNUSED
,
1042 rtx mem2 ATTRIBUTE_UNUSED
)
1044 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1045 enum reg_note old_type
= DEP_TYPE (dep
);
1047 /* If this is a more restrictive type of dependence than the
1048 existing one, then change the existing dependence to this
1050 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1052 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1056 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1057 /* Update DEP_STATUS. */
1059 ds_t dep_status
= DEP_STATUS (dep
);
1060 ds_t ds
= DEP_STATUS (new_dep
);
1061 ds_t new_status
= ds
| dep_status
;
1063 if (new_status
& SPECULATIVE
)
1064 /* Either existing dep or a dep we're adding or both are
1067 if (!(ds
& SPECULATIVE
)
1068 || !(dep_status
& SPECULATIVE
))
1069 /* The new dep can't be speculative. */
1071 new_status
&= ~SPECULATIVE
;
1073 if (dep_status
& SPECULATIVE
)
1074 /* The old dep was speculative, but now it
1076 change_spec_dep_to_hard (sd_it
);
1080 /* Both are speculative. Merge probabilities. */
1085 dw
= estimate_dep_weak (mem1
, mem2
);
1086 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1089 new_status
= ds_merge (dep_status
, ds
);
1095 if (dep_status
!= ds
)
1097 DEP_STATUS (dep
) = ds
;
1102 if (true_dependency_cache
!= NULL
1103 && res
== DEP_CHANGED
)
1104 update_dependency_caches (dep
, old_type
);
1109 /* Add or update a dependence described by DEP.
1110 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1113 The function returns a value indicating if an old entry has been changed
1114 or a new entry has been added to insn's backward deps or nothing has
1115 been updated at all. */
1116 static enum DEPS_ADJUST_RESULT
1117 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1118 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1120 bool maybe_present_p
= true;
1121 bool present_p
= false;
1123 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1124 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1126 #ifdef ENABLE_CHECKING
1127 check_dep (new_dep
, mem1
!= NULL
);
1130 if (true_dependency_cache
!= NULL
)
1132 switch (ask_dependency_caches (new_dep
))
1138 maybe_present_p
= true;
1143 maybe_present_p
= false;
1153 /* Check that we don't already have this dependence. */
1154 if (maybe_present_p
)
1157 sd_iterator_def sd_it
;
1159 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1161 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1163 resolved_p
, &sd_it
);
1165 if (present_dep
!= NULL
)
1166 /* We found an existing dependency between ELEM and INSN. */
1167 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1169 /* We didn't find a dep, it shouldn't present in the cache. */
1170 gcc_assert (!present_p
);
1173 /* Might want to check one level of transitivity to save conses.
1174 This check should be done in maybe_add_or_update_dep_1.
1175 Since we made it to add_or_update_dep_1, we must create
1176 (or update) a link. */
1178 if (mem1
!= NULL_RTX
)
1180 gcc_assert (sched_deps_info
->generate_spec_deps
);
1181 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1182 estimate_dep_weak (mem1
, mem2
));
1185 sd_add_dep (new_dep
, resolved_p
);
1190 /* Initialize BACK_LIST_PTR with consumer's backward list and
1191 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1192 initialize with lists that hold resolved deps. */
1194 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1195 deps_list_t
*back_list_ptr
,
1196 deps_list_t
*forw_list_ptr
)
1198 rtx con
= DEP_CON (dep
);
1202 if ((current_sched_info
->flags
& DO_SPECULATION
)
1203 && (DEP_STATUS (dep
) & SPECULATIVE
))
1204 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1206 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1208 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1212 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1213 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1217 /* Add dependence described by DEP.
1218 If RESOLVED_P is true treat the dependence as a resolved one. */
1220 sd_add_dep (dep_t dep
, bool resolved_p
)
1222 dep_node_t n
= create_dep_node ();
1223 deps_list_t con_back_deps
;
1224 deps_list_t pro_forw_deps
;
1225 rtx elem
= DEP_PRO (dep
);
1226 rtx insn
= DEP_CON (dep
);
1228 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1230 if ((current_sched_info
->flags
& DO_SPECULATION
)
1231 && !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1232 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1234 copy_dep (DEP_NODE_DEP (n
), dep
);
1236 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1238 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1240 #ifdef ENABLE_CHECKING
1241 check_dep (dep
, false);
1244 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1246 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1247 in the bitmap caches of dependency information. */
1248 if (true_dependency_cache
!= NULL
)
1249 set_dependency_caches (dep
);
1252 /* Add or update backward dependence between INSN and ELEM
1253 with given type DEP_TYPE and dep_status DS.
1254 This function is a convenience wrapper. */
1255 enum DEPS_ADJUST_RESULT
1256 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1258 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1261 /* Resolved dependence pointed to by SD_IT.
1262 SD_IT will advance to the next element. */
1264 sd_resolve_dep (sd_iterator_def sd_it
)
1266 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1267 dep_t dep
= DEP_NODE_DEP (node
);
1268 rtx pro
= DEP_PRO (dep
);
1269 rtx con
= DEP_CON (dep
);
1271 if ((current_sched_info
->flags
& DO_SPECULATION
)
1272 && (DEP_STATUS (dep
) & SPECULATIVE
))
1273 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1274 INSN_RESOLVED_BACK_DEPS (con
));
1276 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1277 INSN_RESOLVED_BACK_DEPS (con
));
1279 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1280 INSN_RESOLVED_FORW_DEPS (pro
));
1283 /* Make TO depend on all the FROM's producers.
1284 If RESOLVED_P is true add dependencies to the resolved lists. */
1286 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1288 sd_list_types_def list_type
;
1289 sd_iterator_def sd_it
;
1292 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1294 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1296 dep_def _new_dep
, *new_dep
= &_new_dep
;
1298 copy_dep (new_dep
, dep
);
1299 DEP_CON (new_dep
) = to
;
1300 sd_add_dep (new_dep
, resolved_p
);
1304 /* Remove a dependency referred to by SD_IT.
1305 SD_IT will point to the next dependence after removal. */
1307 sd_delete_dep (sd_iterator_def sd_it
)
1309 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1310 dep_t dep
= DEP_NODE_DEP (n
);
1311 rtx pro
= DEP_PRO (dep
);
1312 rtx con
= DEP_CON (dep
);
1313 deps_list_t con_back_deps
;
1314 deps_list_t pro_forw_deps
;
1316 if (true_dependency_cache
!= NULL
)
1318 int elem_luid
= INSN_LUID (pro
);
1319 int insn_luid
= INSN_LUID (con
);
1321 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1322 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1323 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1325 if (current_sched_info
->flags
& DO_SPECULATION
)
1326 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1329 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1330 &con_back_deps
, &pro_forw_deps
);
1332 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1333 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1335 delete_dep_node (n
);
1338 /* Dump size of the lists. */
1339 #define DUMP_LISTS_SIZE (2)
1341 /* Dump dependencies of the lists. */
1342 #define DUMP_LISTS_DEPS (4)
1344 /* Dump all information about the lists. */
1345 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1347 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1348 FLAGS is a bit mask specifying what information about the lists needs
1350 If FLAGS has the very first bit set, then dump all information about
1351 the lists and propagate this bit into the callee dump functions. */
1353 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1355 sd_iterator_def sd_it
;
1362 flags
|= DUMP_LISTS_ALL
;
1364 fprintf (dump
, "[");
1366 if (flags
& DUMP_LISTS_SIZE
)
1367 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1369 if (flags
& DUMP_LISTS_DEPS
)
1371 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1373 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1374 fprintf (dump
, " ");
1379 /* Dump all information about deps_lists of INSN specified by TYPES
1382 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1384 dump_lists (stderr
, insn
, types
, 1);
1385 fprintf (stderr
, "\n");
1388 /* A convenience wrapper to operate on an entire list. */
1391 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
)
1393 for (; list
; list
= XEXP (list
, 1))
1395 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1396 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1400 /* Similar, but free *LISTP at the same time, when the context
1404 add_dependence_list_and_free (struct deps
*deps
, rtx insn
, rtx
*listp
,
1405 int uncond
, enum reg_note dep_type
)
1411 add_dependence_list (insn
, *listp
, uncond
, dep_type
);
1415 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
1417 next
= XEXP (list
, 1);
1418 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1419 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1420 free_INSN_LIST_node (list
);
1424 /* Remove all occurences of INSN from LIST. Return the number of
1425 occurences removed. */
1428 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1434 if (XEXP (*listp
, 0) == insn
)
1436 remove_free_INSN_LIST_node (listp
);
1441 listp
= &XEXP (*listp
, 1);
1447 /* Same as above, but process two lists at once. */
1449 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1455 if (XEXP (*listp
, 0) == insn
)
1457 remove_free_INSN_LIST_node (listp
);
1458 remove_free_EXPR_LIST_node (exprp
);
1463 listp
= &XEXP (*listp
, 1);
1464 exprp
= &XEXP (*exprp
, 1);
1470 /* Clear all dependencies for an insn. */
1472 delete_all_dependences (rtx insn
)
1474 sd_iterator_def sd_it
;
1477 /* The below cycle can be optimized to clear the caches and back_deps
1478 in one call but that would provoke duplication of code from
1481 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1482 sd_iterator_cond (&sd_it
, &dep
);)
1483 sd_delete_dep (sd_it
);
1486 /* All insns in a scheduling group except the first should only have
1487 dependencies on the previous insn in the group. So we find the
1488 first instruction in the scheduling group by walking the dependence
1489 chains backwards. Then we add the dependencies for the group to
1490 the previous nonnote insn. */
1493 fixup_sched_groups (rtx insn
)
1495 sd_iterator_def sd_it
;
1499 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1502 rtx pro
= DEP_PRO (dep
);
1506 i
= prev_nonnote_insn (i
);
1510 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1512 if (! sched_insns_conditions_mutex_p (i
, pro
))
1513 add_dependence (i
, pro
, DEP_TYPE (dep
));
1517 delete_all_dependences (insn
);
1519 prev_nonnote
= prev_nonnote_insn (insn
);
1520 while (DEBUG_INSN_P (prev_nonnote
))
1521 prev_nonnote
= prev_nonnote_insn (prev_nonnote
);
1522 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1523 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1524 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1527 /* Process an insn's memory dependencies. There are four kinds of
1530 (0) read dependence: read follows read
1531 (1) true dependence: read follows write
1532 (2) output dependence: write follows write
1533 (3) anti dependence: write follows read
1535 We are careful to build only dependencies which actually exist, and
1536 use transitivity to avoid building too many links. */
1538 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1539 The MEM is a memory reference contained within INSN, which we are saving
1540 so that we can do memory aliasing on it. */
1543 add_insn_mem_dependence (struct deps
*deps
, bool read_p
,
1550 gcc_assert (!deps
->readonly
);
1553 insn_list
= &deps
->pending_read_insns
;
1554 mem_list
= &deps
->pending_read_mems
;
1555 if (!DEBUG_INSN_P (insn
))
1556 deps
->pending_read_list_length
++;
1560 insn_list
= &deps
->pending_write_insns
;
1561 mem_list
= &deps
->pending_write_mems
;
1562 deps
->pending_write_list_length
++;
1565 link
= alloc_INSN_LIST (insn
, *insn_list
);
1568 if (sched_deps_info
->use_cselib
)
1570 mem
= shallow_copy_rtx (mem
);
1571 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
1573 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1577 /* Make a dependency between every memory reference on the pending lists
1578 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1579 dependencies for a read operation, similarly with FOR_WRITE. */
1582 flush_pending_lists (struct deps
*deps
, rtx insn
, int for_read
,
1587 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1589 if (!deps
->readonly
)
1591 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1592 deps
->pending_read_list_length
= 0;
1596 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1597 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1599 add_dependence_list_and_free (deps
, insn
,
1600 &deps
->last_pending_memory_flush
, 1,
1601 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1602 if (!deps
->readonly
)
1604 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1605 deps
->pending_write_list_length
= 0;
1607 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1608 deps
->pending_flush_length
= 1;
1612 /* Instruction which dependencies we are analyzing. */
1613 static rtx cur_insn
= NULL_RTX
;
1615 /* Implement hooks for haifa scheduler. */
1618 haifa_start_insn (rtx insn
)
1620 gcc_assert (insn
&& !cur_insn
);
1626 haifa_finish_insn (void)
1632 haifa_note_reg_set (int regno
)
1634 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1638 haifa_note_reg_clobber (int regno
)
1640 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1644 haifa_note_reg_use (int regno
)
1646 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1650 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1652 if (!(ds
& SPECULATIVE
))
1655 pending_mem
= NULL_RTX
;
1658 gcc_assert (ds
& BEGIN_DATA
);
1661 dep_def _dep
, *dep
= &_dep
;
1663 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1664 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: -1);
1665 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1671 haifa_note_dep (rtx elem
, ds_t ds
)
1676 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1677 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1681 note_reg_use (int r
)
1683 if (sched_deps_info
->note_reg_use
)
1684 sched_deps_info
->note_reg_use (r
);
1688 note_reg_set (int r
)
1690 if (sched_deps_info
->note_reg_set
)
1691 sched_deps_info
->note_reg_set (r
);
1695 note_reg_clobber (int r
)
1697 if (sched_deps_info
->note_reg_clobber
)
1698 sched_deps_info
->note_reg_clobber (r
);
1702 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1704 if (sched_deps_info
->note_mem_dep
)
1705 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1709 note_dep (rtx e
, ds_t ds
)
1711 if (sched_deps_info
->note_dep
)
1712 sched_deps_info
->note_dep (e
, ds
);
1715 /* Return corresponding to DS reg_note. */
1720 return REG_DEP_TRUE
;
1721 else if (ds
& DEP_OUTPUT
)
1722 return REG_DEP_OUTPUT
;
1725 gcc_assert (ds
& DEP_ANTI
);
1726 return REG_DEP_ANTI
;
1732 /* Functions for computation of info needed for register pressure
1733 sensitive insn scheduling. */
1736 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1737 static struct reg_use_data
*
1738 create_insn_reg_use (int regno
, rtx insn
)
1740 struct reg_use_data
*use
;
1742 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1745 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1746 INSN_REG_USE_LIST (insn
) = use
;
1750 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1751 static struct reg_set_data
*
1752 create_insn_reg_set (int regno
, rtx insn
)
1754 struct reg_set_data
*set
;
1756 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1759 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1760 INSN_REG_SET_LIST (insn
) = set
;
1764 /* Set up insn register uses for INSN and dependency context DEPS. */
1766 setup_insn_reg_uses (struct deps
*deps
, rtx insn
)
1769 reg_set_iterator rsi
;
1771 struct reg_use_data
*use
, *use2
, *next
;
1772 struct deps_reg
*reg_last
;
1774 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1776 if (i
< FIRST_PSEUDO_REGISTER
1777 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1780 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1781 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1782 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1783 /* Ignore use which is not dying. */
1786 use
= create_insn_reg_use (i
, insn
);
1787 use
->next_regno_use
= use
;
1788 reg_last
= &deps
->reg_last
[i
];
1790 /* Create the cycle list of uses. */
1791 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1793 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1794 next
= use
->next_regno_use
;
1795 use
->next_regno_use
= use2
;
1796 use2
->next_regno_use
= next
;
1801 /* Register pressure info for the currently processed insn. */
1802 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1804 /* Return TRUE if INSN has the use structure for REGNO. */
1806 insn_use_p (rtx insn
, int regno
)
1808 struct reg_use_data
*use
;
1810 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1811 if (use
->regno
== regno
)
1816 /* Update the register pressure info after birth of pseudo register REGNO
1817 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
1818 the register is in clobber or unused after the insn. */
1820 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
1825 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1826 cl
= sched_regno_cover_class
[regno
];
1829 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1832 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
1833 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1837 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
1838 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1842 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
1843 reg_pressure_info
[cl
].set_increase
= new_incr
;
1844 if (! insn_use_p (insn
, regno
))
1845 reg_pressure_info
[cl
].change
+= incr
;
1846 create_insn_reg_set (regno
, insn
);
1848 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1852 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
1853 hard registers involved in the birth. */
1855 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
1856 bool clobber_p
, bool unused_p
)
1859 int new_incr
, last
= regno
+ nregs
;
1861 while (regno
< last
)
1863 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1864 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1866 cl
= sched_regno_cover_class
[regno
];
1871 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
1872 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1876 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
1877 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1881 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
1882 reg_pressure_info
[cl
].set_increase
= new_incr
;
1883 if (! insn_use_p (insn
, regno
))
1884 reg_pressure_info
[cl
].change
+= 1;
1885 create_insn_reg_set (regno
, insn
);
1887 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1894 /* Update the register pressure info after birth of pseudo or hard
1895 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
1896 correspondingly that the register is in clobber or unused after the
1899 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
1903 if (GET_CODE (reg
) == SUBREG
)
1904 reg
= SUBREG_REG (reg
);
1909 regno
= REGNO (reg
);
1910 if (regno
< FIRST_PSEUDO_REGISTER
)
1911 mark_insn_hard_regno_birth (insn
, regno
,
1912 hard_regno_nregs
[regno
][GET_MODE (reg
)],
1913 clobber_p
, unused_p
);
1915 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
1918 /* Update the register pressure info after death of pseudo register
1921 mark_pseudo_death (int regno
)
1926 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1927 cl
= sched_regno_cover_class
[regno
];
1930 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1931 reg_pressure_info
[cl
].change
-= incr
;
1935 /* Like mark_pseudo_death except that NREGS saying how many hard
1936 registers involved in the death. */
1938 mark_hard_regno_death (int regno
, int nregs
)
1941 int last
= regno
+ nregs
;
1943 while (regno
< last
)
1945 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1946 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1948 cl
= sched_regno_cover_class
[regno
];
1950 reg_pressure_info
[cl
].change
-= 1;
1956 /* Update the register pressure info after death of pseudo or hard
1959 mark_reg_death (rtx reg
)
1963 if (GET_CODE (reg
) == SUBREG
)
1964 reg
= SUBREG_REG (reg
);
1969 regno
= REGNO (reg
);
1970 if (regno
< FIRST_PSEUDO_REGISTER
)
1971 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1973 mark_pseudo_death (regno
);
1976 /* Process SETTER of REG. DATA is an insn containing the setter. */
1978 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
1980 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
1983 ((rtx
) data
, reg
, false,
1984 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
1987 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
1989 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1991 if (GET_CODE (setter
) == CLOBBER
)
1992 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
1995 /* Set up reg pressure info related to INSN. */
1997 setup_insn_reg_pressure_info (rtx insn
)
2001 static struct reg_pressure_data
*pressure_info
;
2004 gcc_assert (sched_pressure_p
);
2006 if (! INSN_P (insn
))
2009 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2011 cl
= ira_reg_class_cover
[i
];
2012 reg_pressure_info
[cl
].clobber_increase
= 0;
2013 reg_pressure_info
[cl
].set_increase
= 0;
2014 reg_pressure_info
[cl
].unused_set_increase
= 0;
2015 reg_pressure_info
[cl
].change
= 0;
2018 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2020 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2023 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2024 if (REG_NOTE_KIND (link
) == REG_INC
)
2025 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2028 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2029 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2030 mark_reg_death (XEXP (link
, 0));
2032 len
= sizeof (struct reg_pressure_data
) * ira_reg_class_cover_size
;
2034 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2035 INSN_MAX_REG_PRESSURE (insn
) = (int *) xmalloc (ira_reg_class_cover_size
2037 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2039 cl
= ira_reg_class_cover
[i
];
2040 pressure_info
[i
].clobber_increase
2041 = reg_pressure_info
[cl
].clobber_increase
;
2042 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2043 pressure_info
[i
].unused_set_increase
2044 = reg_pressure_info
[cl
].unused_set_increase
;
2045 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2052 /* Internal variable for sched_analyze_[12] () functions.
2053 If it is nonzero, this means that sched_analyze_[12] looks
2054 at the most toplevel SET. */
2055 static bool can_start_lhs_rhs_p
;
2057 /* Extend reg info for the deps context DEPS given that
2058 we have just generated a register numbered REGNO. */
2060 extend_deps_reg_info (struct deps
*deps
, int regno
)
2062 int max_regno
= regno
+ 1;
2064 gcc_assert (!reload_completed
);
2066 /* In a readonly context, it would not hurt to extend info,
2067 but it should not be needed. */
2068 if (reload_completed
&& deps
->readonly
)
2070 deps
->max_reg
= max_regno
;
2074 if (max_regno
> deps
->max_reg
)
2076 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2078 memset (&deps
->reg_last
[deps
->max_reg
],
2079 0, (max_regno
- deps
->max_reg
)
2080 * sizeof (struct deps_reg
));
2081 deps
->max_reg
= max_regno
;
2085 /* Extends REG_INFO_P if needed. */
2087 maybe_extend_reg_info_p (void)
2089 /* Extend REG_INFO_P, if needed. */
2090 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2092 size_t new_reg_info_p_size
= max_regno
+ 128;
2094 gcc_assert (!reload_completed
&& sel_sched_p ());
2096 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2097 new_reg_info_p_size
,
2099 sizeof (*reg_info_p
));
2100 reg_info_p_size
= new_reg_info_p_size
;
2104 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2105 The type of the reference is specified by REF and can be SET,
2106 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2109 sched_analyze_reg (struct deps
*deps
, int regno
, enum machine_mode mode
,
2110 enum rtx_code ref
, rtx insn
)
2112 /* We could emit new pseudos in renaming. Extend the reg structures. */
2113 if (!reload_completed
&& sel_sched_p ()
2114 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2115 extend_deps_reg_info (deps
, regno
);
2117 maybe_extend_reg_info_p ();
2119 /* A hard reg in a wide mode may really be multiple registers.
2120 If so, mark all of them just like the first. */
2121 if (regno
< FIRST_PSEUDO_REGISTER
)
2123 int i
= hard_regno_nregs
[regno
][mode
];
2127 note_reg_set (regno
+ i
);
2129 else if (ref
== USE
)
2132 note_reg_use (regno
+ i
);
2137 note_reg_clobber (regno
+ i
);
2141 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2142 it does not reload. Ignore these as they have served their
2144 else if (regno
>= deps
->max_reg
)
2146 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2147 gcc_assert (code
== USE
|| code
== CLOBBER
);
2153 note_reg_set (regno
);
2154 else if (ref
== USE
)
2155 note_reg_use (regno
);
2157 note_reg_clobber (regno
);
2159 /* Pseudos that are REG_EQUIV to something may be replaced
2160 by that during reloading. We need only add dependencies for
2161 the address in the REG_EQUIV note. */
2162 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2164 rtx t
= get_reg_known_value (regno
);
2166 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2169 /* Don't let it cross a call after scheduling if it doesn't
2170 already cross one. */
2171 if (REG_N_CALLS_CROSSED (regno
) == 0)
2173 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2174 deps
->sched_before_next_call
2175 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2177 add_dependence_list (insn
, deps
->last_function_call
, 1,
2183 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2184 rtx, X, creating all dependencies generated by the write to the
2185 destination of X, and reads of everything mentioned. */
2188 sched_analyze_1 (struct deps
*deps
, rtx x
, rtx insn
)
2190 rtx dest
= XEXP (x
, 0);
2191 enum rtx_code code
= GET_CODE (x
);
2192 bool cslr_p
= can_start_lhs_rhs_p
;
2194 can_start_lhs_rhs_p
= false;
2200 if (cslr_p
&& sched_deps_info
->start_lhs
)
2201 sched_deps_info
->start_lhs (dest
);
2203 if (GET_CODE (dest
) == PARALLEL
)
2207 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2208 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2209 sched_analyze_1 (deps
,
2210 gen_rtx_CLOBBER (VOIDmode
,
2211 XEXP (XVECEXP (dest
, 0, i
), 0)),
2214 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2215 sched_deps_info
->finish_lhs ();
2219 can_start_lhs_rhs_p
= cslr_p
;
2221 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2223 can_start_lhs_rhs_p
= false;
2229 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2230 || GET_CODE (dest
) == ZERO_EXTRACT
)
2232 if (GET_CODE (dest
) == STRICT_LOW_PART
2233 || GET_CODE (dest
) == ZERO_EXTRACT
2234 || df_read_modify_subreg_p (dest
))
2236 /* These both read and modify the result. We must handle
2237 them as writes to get proper dependencies for following
2238 instructions. We must handle them as reads to get proper
2239 dependencies from this to previous instructions.
2240 Thus we need to call sched_analyze_2. */
2242 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2244 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2246 /* The second and third arguments are values read by this insn. */
2247 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2248 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2250 dest
= XEXP (dest
, 0);
2255 int regno
= REGNO (dest
);
2256 enum machine_mode mode
= GET_MODE (dest
);
2258 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2261 /* Treat all writes to a stack register as modifying the TOS. */
2262 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2266 /* Avoid analyzing the same register twice. */
2267 if (regno
!= FIRST_STACK_REG
)
2268 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2270 nregs
= hard_regno_nregs
[FIRST_STACK_REG
][mode
];
2271 while (--nregs
>= 0)
2272 SET_HARD_REG_BIT (implicit_reg_pending_uses
,
2273 FIRST_STACK_REG
+ nregs
);
2277 else if (MEM_P (dest
))
2279 /* Writing memory. */
2282 if (sched_deps_info
->use_cselib
)
2284 t
= shallow_copy_rtx (dest
);
2285 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
2286 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2290 /* Pending lists can't get larger with a readonly context. */
2292 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2293 > MAX_PENDING_LIST_LENGTH
))
2295 /* Flush all pending reads and writes to prevent the pending lists
2296 from getting any larger. Insn scheduling runs too slowly when
2297 these lists get long. When compiling GCC with itself,
2298 this flush occurs 8 times for sparc, and 10 times for m88k using
2299 the default value of 32. */
2300 flush_pending_lists (deps
, insn
, false, true);
2304 rtx pending
, pending_mem
;
2306 pending
= deps
->pending_read_insns
;
2307 pending_mem
= deps
->pending_read_mems
;
2310 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2311 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2312 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2315 pending
= XEXP (pending
, 1);
2316 pending_mem
= XEXP (pending_mem
, 1);
2319 pending
= deps
->pending_write_insns
;
2320 pending_mem
= deps
->pending_write_mems
;
2323 if (output_dependence (XEXP (pending_mem
, 0), t
)
2324 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2325 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2328 pending
= XEXP (pending
, 1);
2329 pending_mem
= XEXP (pending_mem
, 1);
2332 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2335 if (!deps
->readonly
)
2336 add_insn_mem_dependence (deps
, false, insn
, dest
);
2338 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2341 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2342 sched_deps_info
->finish_lhs ();
2344 /* Analyze reads. */
2345 if (GET_CODE (x
) == SET
)
2347 can_start_lhs_rhs_p
= cslr_p
;
2349 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2351 can_start_lhs_rhs_p
= false;
2355 /* Analyze the uses of memory and registers in rtx X in INSN. */
2357 sched_analyze_2 (struct deps
*deps
, rtx x
, rtx insn
)
2363 bool cslr_p
= can_start_lhs_rhs_p
;
2365 can_start_lhs_rhs_p
= false;
2371 if (cslr_p
&& sched_deps_info
->start_rhs
)
2372 sched_deps_info
->start_rhs (x
);
2374 code
= GET_CODE (x
);
2385 /* Ignore constants. */
2386 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2387 sched_deps_info
->finish_rhs ();
2393 /* User of CC0 depends on immediately preceding insn. */
2394 SCHED_GROUP_P (insn
) = 1;
2395 /* Don't move CC0 setter to another block (it can set up the
2396 same flag for previous CC0 users which is safe). */
2397 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2399 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2400 sched_deps_info
->finish_rhs ();
2407 int regno
= REGNO (x
);
2408 enum machine_mode mode
= GET_MODE (x
);
2410 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2413 /* Treat all reads of a stack register as modifying the TOS. */
2414 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2416 /* Avoid analyzing the same register twice. */
2417 if (regno
!= FIRST_STACK_REG
)
2418 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2419 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2423 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2424 sched_deps_info
->finish_rhs ();
2431 /* Reading memory. */
2433 rtx pending
, pending_mem
;
2436 if (sched_deps_info
->use_cselib
)
2438 t
= shallow_copy_rtx (t
);
2439 cselib_lookup (XEXP (t
, 0), Pmode
, 1);
2440 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2443 if (!DEBUG_INSN_P (insn
))
2446 pending
= deps
->pending_read_insns
;
2447 pending_mem
= deps
->pending_read_mems
;
2450 if (read_dependence (XEXP (pending_mem
, 0), t
)
2451 && ! sched_insns_conditions_mutex_p (insn
,
2453 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2456 pending
= XEXP (pending
, 1);
2457 pending_mem
= XEXP (pending_mem
, 1);
2460 pending
= deps
->pending_write_insns
;
2461 pending_mem
= deps
->pending_write_mems
;
2464 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
2466 && ! sched_insns_conditions_mutex_p (insn
,
2468 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2469 sched_deps_info
->generate_spec_deps
2470 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2472 pending
= XEXP (pending
, 1);
2473 pending_mem
= XEXP (pending_mem
, 1);
2476 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2478 if (! JUMP_P (XEXP (u
, 0)))
2479 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2480 else if (deps_may_trap_p (x
))
2482 if ((sched_deps_info
->generate_spec_deps
)
2483 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2485 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2488 note_dep (XEXP (u
, 0), ds
);
2491 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2496 /* Always add these dependencies to pending_reads, since
2497 this insn may be followed by a write. */
2498 if (!deps
->readonly
)
2499 add_insn_mem_dependence (deps
, true, insn
, x
);
2501 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2503 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2504 sched_deps_info
->finish_rhs ();
2509 /* Force pending stores to memory in case a trap handler needs them. */
2511 flush_pending_lists (deps
, insn
, true, false);
2515 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2516 reg_pending_barrier
= TRUE_BARRIER
;
2519 case UNSPEC_VOLATILE
:
2520 flush_pending_lists (deps
, insn
, true, true);
2526 /* Traditional and volatile asm instructions must be considered to use
2527 and clobber all hard registers, all pseudo-registers and all of
2528 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2530 Consider for instance a volatile asm that changes the fpu rounding
2531 mode. An insn should not be moved across this even if it only uses
2532 pseudo-regs because it might give an incorrectly rounded result. */
2533 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2534 reg_pending_barrier
= TRUE_BARRIER
;
2536 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2537 We can not just fall through here since then we would be confused
2538 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2539 traditional asms unlike their normal usage. */
2541 if (code
== ASM_OPERANDS
)
2543 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2544 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2546 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2547 sched_deps_info
->finish_rhs ();
2558 /* These both read and modify the result. We must handle them as writes
2559 to get proper dependencies for following instructions. We must handle
2560 them as reads to get proper dependencies from this to previous
2561 instructions. Thus we need to pass them to both sched_analyze_1
2562 and sched_analyze_2. We must call sched_analyze_2 first in order
2563 to get the proper antecedent for the read. */
2564 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2565 sched_analyze_1 (deps
, x
, insn
);
2567 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2568 sched_deps_info
->finish_rhs ();
2574 /* op0 = op0 + op1 */
2575 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2576 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2577 sched_analyze_1 (deps
, x
, insn
);
2579 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2580 sched_deps_info
->finish_rhs ();
2588 /* Other cases: walk the insn. */
2589 fmt
= GET_RTX_FORMAT (code
);
2590 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2593 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2594 else if (fmt
[i
] == 'E')
2595 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2596 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2599 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2600 sched_deps_info
->finish_rhs ();
2603 /* Analyze an INSN with pattern X to find all dependencies. */
2605 sched_analyze_insn (struct deps
*deps
, rtx x
, rtx insn
)
2607 RTX_CODE code
= GET_CODE (x
);
2610 reg_set_iterator rsi
;
2612 if (! reload_completed
)
2616 extract_insn (insn
);
2617 preprocess_constraints ();
2618 ira_implicitly_set_insn_hard_regs (&temp
);
2619 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2622 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2626 /* Avoid moving trapping instructions accross function calls that might
2627 not always return. */
2628 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2631 if (code
== COND_EXEC
)
2633 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2635 /* ??? Should be recording conditions so we reduce the number of
2636 false dependencies. */
2637 x
= COND_EXEC_CODE (x
);
2638 code
= GET_CODE (x
);
2640 if (code
== SET
|| code
== CLOBBER
)
2642 sched_analyze_1 (deps
, x
, insn
);
2644 /* Bare clobber insns are used for letting life analysis, reg-stack
2645 and others know that a value is dead. Depend on the last call
2646 instruction so that reg-stack won't get confused. */
2647 if (code
== CLOBBER
)
2648 add_dependence_list (insn
, deps
->last_function_call
, 1,
2651 else if (code
== PARALLEL
)
2653 for (i
= XVECLEN (x
, 0); i
--;)
2655 rtx sub
= XVECEXP (x
, 0, i
);
2656 code
= GET_CODE (sub
);
2658 if (code
== COND_EXEC
)
2660 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2661 sub
= COND_EXEC_CODE (sub
);
2662 code
= GET_CODE (sub
);
2664 if (code
== SET
|| code
== CLOBBER
)
2665 sched_analyze_1 (deps
, sub
, insn
);
2667 sched_analyze_2 (deps
, sub
, insn
);
2671 sched_analyze_2 (deps
, x
, insn
);
2673 /* Mark registers CLOBBERED or used by called function. */
2676 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2678 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2679 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2681 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2683 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2684 reg_pending_barrier
= MOVE_BARRIER
;
2690 next
= next_nonnote_insn (insn
);
2691 while (next
&& DEBUG_INSN_P (next
))
2692 next
= next_nonnote_insn (next
);
2693 if (next
&& BARRIER_P (next
))
2694 reg_pending_barrier
= MOVE_BARRIER
;
2697 rtx pending
, pending_mem
;
2699 if (sched_deps_info
->compute_jump_reg_dependencies
)
2701 regset_head tmp_uses
, tmp_sets
;
2702 INIT_REG_SET (&tmp_uses
);
2703 INIT_REG_SET (&tmp_sets
);
2705 (*sched_deps_info
->compute_jump_reg_dependencies
)
2706 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
2707 /* Make latency of jump equal to 0 by using anti-dependence. */
2708 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
, rsi
)
2710 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2711 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2712 add_dependence_list (insn
, reg_last
->implicit_sets
,
2714 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2717 if (!deps
->readonly
)
2719 reg_last
->uses_length
++;
2720 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2723 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
2725 CLEAR_REG_SET (&tmp_uses
);
2726 CLEAR_REG_SET (&tmp_sets
);
2729 /* All memory writes and volatile reads must happen before the
2730 jump. Non-volatile reads must happen before the jump iff
2731 the result is needed by the above register used mask. */
2733 pending
= deps
->pending_write_insns
;
2734 pending_mem
= deps
->pending_write_mems
;
2737 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2738 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2739 pending
= XEXP (pending
, 1);
2740 pending_mem
= XEXP (pending_mem
, 1);
2743 pending
= deps
->pending_read_insns
;
2744 pending_mem
= deps
->pending_read_mems
;
2747 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2748 && ! 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 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2759 /* If this instruction can throw an exception, then moving it changes
2760 where block boundaries fall. This is mighty confusing elsewhere.
2761 Therefore, prevent such an instruction from being moved. Same for
2762 non-jump instructions that define block boundaries.
2763 ??? Unclear whether this is still necessary in EBB mode. If not,
2764 add_branch_dependences should be adjusted for RGN mode instead. */
2765 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2766 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2767 reg_pending_barrier
= MOVE_BARRIER
;
2769 if (sched_pressure_p
)
2771 setup_insn_reg_uses (deps
, insn
);
2772 setup_insn_reg_pressure_info (insn
);
2775 /* Add register dependencies for insn. */
2776 if (DEBUG_INSN_P (insn
))
2778 rtx prev
= deps
->last_debug_insn
;
2781 if (!deps
->readonly
)
2782 deps
->last_debug_insn
= insn
;
2785 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2787 add_dependence_list (insn
, deps
->last_function_call
, 1,
2790 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2791 if (! JUMP_P (XEXP (u
, 0))
2793 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2795 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2797 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2798 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
);
2799 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
);
2801 if (!deps
->readonly
)
2802 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2804 CLEAR_REG_SET (reg_pending_uses
);
2806 /* Quite often, a debug insn will refer to stuff in the
2807 previous instruction, but the reason we want this
2808 dependency here is to make sure the scheduler doesn't
2809 gratuitously move a debug insn ahead. This could dirty
2810 DF flags and cause additional analysis that wouldn't have
2811 occurred in compilation without debug insns, and such
2812 additional analysis can modify the generated code. */
2813 prev
= PREV_INSN (insn
);
2815 if (prev
&& NONDEBUG_INSN_P (prev
))
2816 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2820 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2822 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2823 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2824 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
);
2825 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2827 if (!deps
->readonly
)
2829 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2830 reg_last
->uses_length
++;
2834 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2835 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
2837 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2838 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2839 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2841 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2843 if (!deps
->readonly
)
2845 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2846 reg_last
->uses_length
++;
2850 /* If the current insn is conditional, we can't free any
2852 if (sched_has_condition_p (insn
))
2854 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2856 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2857 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2858 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2860 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2862 if (!deps
->readonly
)
2865 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2866 reg_last
->clobbers_length
++;
2869 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2871 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2872 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2873 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2875 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2876 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2878 if (!deps
->readonly
)
2880 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2881 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2887 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2889 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2890 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
2891 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
2893 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2895 add_dependence_list_and_free (deps
, insn
,
2896 ®_last
->implicit_sets
, 0,
2898 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2900 add_dependence_list_and_free
2901 (deps
, insn
, ®_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2903 if (!deps
->readonly
)
2905 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2906 reg_last
->clobbers_length
= 0;
2907 reg_last
->uses_length
= 0;
2912 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2913 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2915 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2918 if (!deps
->readonly
)
2920 reg_last
->clobbers_length
++;
2922 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2925 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2927 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2929 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2931 add_dependence_list_and_free (deps
, insn
,
2932 ®_last
->implicit_sets
,
2934 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
2936 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2939 if (!deps
->readonly
)
2941 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2942 reg_last
->uses_length
= 0;
2943 reg_last
->clobbers_length
= 0;
2944 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2950 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2951 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2953 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2954 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2955 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
);
2956 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2958 if (!deps
->readonly
)
2959 reg_last
->implicit_sets
2960 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
2963 if (!deps
->readonly
)
2965 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
2966 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
2967 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
2968 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2969 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
2970 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2971 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
2973 /* Set up the pending barrier found. */
2974 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
2977 CLEAR_REG_SET (reg_pending_uses
);
2978 CLEAR_REG_SET (reg_pending_clobbers
);
2979 CLEAR_REG_SET (reg_pending_sets
);
2980 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
2981 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
2983 /* Add dependencies if a scheduling barrier was found. */
2984 if (reg_pending_barrier
)
2986 /* In the case of barrier the most added dependencies are not
2987 real, so we use anti-dependence here. */
2988 if (sched_has_condition_p (insn
))
2990 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
2992 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2993 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2994 add_dependence_list (insn
, reg_last
->sets
, 0,
2995 reg_pending_barrier
== TRUE_BARRIER
2996 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
2997 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2999 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3000 reg_pending_barrier
== TRUE_BARRIER
3001 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3006 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3008 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3009 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3011 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3012 reg_pending_barrier
== TRUE_BARRIER
3013 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3014 add_dependence_list_and_free (deps
, insn
,
3015 ®_last
->implicit_sets
, 0,
3017 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3018 reg_pending_barrier
== TRUE_BARRIER
3019 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3021 if (!deps
->readonly
)
3023 reg_last
->uses_length
= 0;
3024 reg_last
->clobbers_length
= 0;
3029 if (!deps
->readonly
)
3030 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3032 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3033 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3034 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3037 /* Flush pending lists on jumps, but not on speculative checks. */
3038 if (JUMP_P (insn
) && !(sel_sched_p ()
3039 && sel_insn_is_speculation_check (insn
)))
3040 flush_pending_lists (deps
, insn
, true, true);
3042 if (!deps
->readonly
)
3043 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3044 reg_pending_barrier
= NOT_A_BARRIER
;
3047 /* If a post-call group is still open, see if it should remain so.
3048 This insn must be a simple move of a hard reg to a pseudo or
3051 We must avoid moving these insns for correctness on
3052 SMALL_REGISTER_CLASS machines, and for special registers like
3053 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3054 hard regs for all targets. */
3056 if (deps
->in_post_call_group_p
)
3058 rtx tmp
, set
= single_set (insn
);
3059 int src_regno
, dest_regno
;
3063 if (DEBUG_INSN_P (insn
))
3064 /* We don't want to mark debug insns as part of the same
3065 sched group. We know they really aren't, but if we use
3066 debug insns to tell that a call group is over, we'll
3067 get different code if debug insns are not there and
3068 instructions that follow seem like they should be part
3071 Also, if we did, fixup_sched_groups() would move the
3072 deps of the debug insn to the call insn, modifying
3073 non-debug post-dependency counts of the debug insn
3074 dependencies and otherwise messing with the scheduling
3077 Instead, let such debug insns be scheduled freely, but
3078 keep the call group open in case there are insns that
3079 should be part of it afterwards. Since we grant debug
3080 insns higher priority than even sched group insns, it
3081 will all turn out all right. */
3082 goto debug_dont_end_call_group
;
3084 goto end_call_group
;
3087 tmp
= SET_DEST (set
);
3088 if (GET_CODE (tmp
) == SUBREG
)
3089 tmp
= SUBREG_REG (tmp
);
3091 dest_regno
= REGNO (tmp
);
3093 goto end_call_group
;
3095 tmp
= SET_SRC (set
);
3096 if (GET_CODE (tmp
) == SUBREG
)
3097 tmp
= SUBREG_REG (tmp
);
3098 if ((GET_CODE (tmp
) == PLUS
3099 || GET_CODE (tmp
) == MINUS
)
3100 && REG_P (XEXP (tmp
, 0))
3101 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3102 && dest_regno
== STACK_POINTER_REGNUM
)
3103 src_regno
= STACK_POINTER_REGNUM
;
3104 else if (REG_P (tmp
))
3105 src_regno
= REGNO (tmp
);
3107 goto end_call_group
;
3109 if (src_regno
< FIRST_PSEUDO_REGISTER
3110 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3113 && deps
->in_post_call_group_p
== post_call_initial
)
3114 deps
->in_post_call_group_p
= post_call
;
3116 if (!sel_sched_p () || sched_emulate_haifa_p
)
3118 SCHED_GROUP_P (insn
) = 1;
3119 CANT_MOVE (insn
) = 1;
3125 if (!deps
->readonly
)
3126 deps
->in_post_call_group_p
= not_post_call
;
3130 debug_dont_end_call_group
:
3131 if ((current_sched_info
->flags
& DO_SPECULATION
)
3132 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3133 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3137 sel_mark_hard_insn (insn
);
3140 sd_iterator_def sd_it
;
3143 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3144 sd_iterator_cond (&sd_it
, &dep
);)
3145 change_spec_dep_to_hard (sd_it
);
3150 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3151 longjmp, loop forever, ...). */
3153 call_may_noreturn_p (rtx insn
)
3157 /* const or pure calls that aren't looping will always return. */
3158 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3159 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3162 call
= PATTERN (insn
);
3163 if (GET_CODE (call
) == PARALLEL
)
3164 call
= XVECEXP (call
, 0, 0);
3165 if (GET_CODE (call
) == SET
)
3166 call
= SET_SRC (call
);
3167 if (GET_CODE (call
) == CALL
3168 && MEM_P (XEXP (call
, 0))
3169 && GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3171 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3172 if (SYMBOL_REF_DECL (symbol
)
3173 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3175 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3177 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3180 case BUILT_IN_BCOPY
:
3181 case BUILT_IN_BZERO
:
3182 case BUILT_IN_INDEX
:
3183 case BUILT_IN_MEMCHR
:
3184 case BUILT_IN_MEMCMP
:
3185 case BUILT_IN_MEMCPY
:
3186 case BUILT_IN_MEMMOVE
:
3187 case BUILT_IN_MEMPCPY
:
3188 case BUILT_IN_MEMSET
:
3189 case BUILT_IN_RINDEX
:
3190 case BUILT_IN_STPCPY
:
3191 case BUILT_IN_STPNCPY
:
3192 case BUILT_IN_STRCAT
:
3193 case BUILT_IN_STRCHR
:
3194 case BUILT_IN_STRCMP
:
3195 case BUILT_IN_STRCPY
:
3196 case BUILT_IN_STRCSPN
:
3197 case BUILT_IN_STRLEN
:
3198 case BUILT_IN_STRNCAT
:
3199 case BUILT_IN_STRNCMP
:
3200 case BUILT_IN_STRNCPY
:
3201 case BUILT_IN_STRPBRK
:
3202 case BUILT_IN_STRRCHR
:
3203 case BUILT_IN_STRSPN
:
3204 case BUILT_IN_STRSTR
:
3205 /* Assume certain string/memory builtins always return. */
3213 /* For all other calls assume that they might not always return. */
3217 /* Analyze INSN with DEPS as a context. */
3219 deps_analyze_insn (struct deps
*deps
, rtx insn
)
3221 if (sched_deps_info
->start_insn
)
3222 sched_deps_info
->start_insn (insn
);
3224 if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
) || JUMP_P (insn
))
3226 /* Make each JUMP_INSN (but not a speculative check)
3227 a scheduling barrier for memory references. */
3231 && sel_insn_is_speculation_check (insn
)))
3233 /* Keep the list a reasonable size. */
3234 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3235 flush_pending_lists (deps
, insn
, true, true);
3237 deps
->last_pending_memory_flush
3238 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
3241 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3243 else if (CALL_P (insn
))
3247 CANT_MOVE (insn
) = 1;
3249 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3251 /* This is setjmp. Assume that all registers, not just
3252 hard registers, may be clobbered by this call. */
3253 reg_pending_barrier
= MOVE_BARRIER
;
3257 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3258 /* A call may read and modify global register variables. */
3261 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3262 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3264 /* Other call-clobbered hard regs may be clobbered.
3265 Since we only have a choice between 'might be clobbered'
3266 and 'definitely not clobbered', we must include all
3267 partly call-clobbered registers here. */
3268 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3269 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3270 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3271 /* We don't know what set of fixed registers might be used
3272 by the function, but it is certain that the stack pointer
3273 is among them, but be conservative. */
3274 else if (fixed_regs
[i
])
3275 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3276 /* The frame pointer is normally not used by the function
3277 itself, but by the debugger. */
3278 /* ??? MIPS o32 is an exception. It uses the frame pointer
3279 in the macro expansion of jal but does not represent this
3280 fact in the call_insn rtl. */
3281 else if (i
== FRAME_POINTER_REGNUM
3282 || (i
== HARD_FRAME_POINTER_REGNUM
3283 && (! reload_completed
|| frame_pointer_needed
)))
3284 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3287 /* For each insn which shouldn't cross a call, add a dependence
3288 between that insn and this call insn. */
3289 add_dependence_list_and_free (deps
, insn
,
3290 &deps
->sched_before_next_call
, 1,
3293 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3295 /* If CALL would be in a sched group, then this will violate
3296 convention that sched group insns have dependencies only on the
3297 previous instruction.
3299 Of course one can say: "Hey! What about head of the sched group?"
3300 And I will answer: "Basic principles (one dep per insn) are always
3302 gcc_assert (!SCHED_GROUP_P (insn
));
3304 /* In the absence of interprocedural alias analysis, we must flush
3305 all pending reads and writes, and start new dependencies starting
3306 from here. But only flush writes for constant calls (which may
3307 be passed a pointer to something we haven't written yet). */
3308 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3310 if (!deps
->readonly
)
3312 /* Remember the last function call for limiting lifetimes. */
3313 free_INSN_LIST_list (&deps
->last_function_call
);
3314 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3316 if (call_may_noreturn_p (insn
))
3318 /* Remember the last function call that might not always return
3319 normally for limiting moves of trapping insns. */
3320 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3321 deps
->last_function_call_may_noreturn
3322 = alloc_INSN_LIST (insn
, NULL_RTX
);
3325 /* Before reload, begin a post-call group, so as to keep the
3326 lifetimes of hard registers correct. */
3327 if (! reload_completed
)
3328 deps
->in_post_call_group_p
= post_call
;
3332 if (sched_deps_info
->use_cselib
)
3333 cselib_process_insn (insn
);
3335 /* EH_REGION insn notes can not appear until well after we complete
3338 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3339 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3341 if (sched_deps_info
->finish_insn
)
3342 sched_deps_info
->finish_insn ();
3344 /* Fixup the dependencies in the sched group. */
3345 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3346 && SCHED_GROUP_P (insn
) && !sel_sched_p ())
3347 fixup_sched_groups (insn
);
3350 /* Initialize DEPS for the new block beginning with HEAD. */
3352 deps_start_bb (struct deps
*deps
, rtx head
)
3354 gcc_assert (!deps
->readonly
);
3356 /* Before reload, if the previous block ended in a call, show that
3357 we are inside a post-call group, so as to keep the lifetimes of
3358 hard registers correct. */
3359 if (! reload_completed
&& !LABEL_P (head
))
3361 rtx insn
= prev_nonnote_insn (head
);
3363 while (insn
&& DEBUG_INSN_P (insn
))
3364 insn
= prev_nonnote_insn (insn
);
3365 if (insn
&& CALL_P (insn
))
3366 deps
->in_post_call_group_p
= post_call_initial
;
3370 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3371 dependencies for each insn. */
3373 sched_analyze (struct deps
*deps
, rtx head
, rtx tail
)
3377 if (sched_deps_info
->use_cselib
)
3380 deps_start_bb (deps
, head
);
3382 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3387 /* And initialize deps_lists. */
3388 sd_init_insn (insn
);
3391 deps_analyze_insn (deps
, insn
);
3395 if (sched_deps_info
->use_cselib
)
3403 /* Helper for sched_free_deps ().
3404 Delete INSN's (RESOLVED_P) backward dependencies. */
3406 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3408 sd_iterator_def sd_it
;
3410 sd_list_types_def types
;
3413 types
= SD_LIST_RES_BACK
;
3415 types
= SD_LIST_BACK
;
3417 for (sd_it
= sd_iterator_start (insn
, types
);
3418 sd_iterator_cond (&sd_it
, &dep
);)
3420 dep_link_t link
= *sd_it
.linkp
;
3421 dep_node_t node
= DEP_LINK_NODE (link
);
3422 deps_list_t back_list
;
3423 deps_list_t forw_list
;
3425 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3426 remove_from_deps_list (link
, back_list
);
3427 delete_dep_node (node
);
3431 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3434 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3437 rtx next_tail
= NEXT_INSN (tail
);
3439 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3440 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3442 /* Clear resolved back deps together with its dep_nodes. */
3443 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3445 /* Clear forward deps and leave the dep_nodes to the
3446 corresponding back_deps list. */
3448 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3450 clear_deps_list (INSN_FORW_DEPS (insn
));
3452 sd_finish_insn (insn
);
3456 /* Initialize variables for region data dependence analysis.
3457 n_bbs is the number of region blocks. */
3460 init_deps (struct deps
*deps
)
3462 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3464 deps
->max_reg
= max_reg
;
3465 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3466 INIT_REG_SET (&deps
->reg_last_in_use
);
3467 INIT_REG_SET (&deps
->reg_conditional_sets
);
3469 deps
->pending_read_insns
= 0;
3470 deps
->pending_read_mems
= 0;
3471 deps
->pending_write_insns
= 0;
3472 deps
->pending_write_mems
= 0;
3473 deps
->pending_read_list_length
= 0;
3474 deps
->pending_write_list_length
= 0;
3475 deps
->pending_flush_length
= 0;
3476 deps
->last_pending_memory_flush
= 0;
3477 deps
->last_function_call
= 0;
3478 deps
->last_function_call_may_noreturn
= 0;
3479 deps
->sched_before_next_call
= 0;
3480 deps
->in_post_call_group_p
= not_post_call
;
3481 deps
->last_debug_insn
= 0;
3482 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3486 /* Free insn lists found in DEPS. */
3489 free_deps (struct deps
*deps
)
3492 reg_set_iterator rsi
;
3494 free_INSN_LIST_list (&deps
->pending_read_insns
);
3495 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3496 free_INSN_LIST_list (&deps
->pending_write_insns
);
3497 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3498 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3500 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3501 times. For a testcase with 42000 regs and 8000 small basic blocks,
3502 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3503 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3505 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3507 free_INSN_LIST_list (®_last
->uses
);
3509 free_INSN_LIST_list (®_last
->sets
);
3510 if (reg_last
->implicit_sets
)
3511 free_INSN_LIST_list (®_last
->implicit_sets
);
3512 if (reg_last
->clobbers
)
3513 free_INSN_LIST_list (®_last
->clobbers
);
3515 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3516 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3518 free (deps
->reg_last
);
3519 deps
->reg_last
= NULL
;
3524 /* Remove INSN from dependence contexts DEPS. Caution: reg_conditional_sets
3527 remove_from_deps (struct deps
*deps
, rtx insn
)
3531 reg_set_iterator rsi
;
3533 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3534 &deps
->pending_read_mems
);
3535 if (!DEBUG_INSN_P (insn
))
3536 deps
->pending_read_list_length
-= removed
;
3537 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3538 &deps
->pending_write_mems
);
3539 deps
->pending_write_list_length
-= removed
;
3540 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3541 deps
->pending_flush_length
-= removed
;
3543 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3545 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3547 remove_from_dependence_list (insn
, ®_last
->uses
);
3549 remove_from_dependence_list (insn
, ®_last
->sets
);
3550 if (reg_last
->implicit_sets
)
3551 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3552 if (reg_last
->clobbers
)
3553 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3554 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3555 && !reg_last
->clobbers
)
3556 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3561 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3562 remove_from_dependence_list (insn
,
3563 &deps
->last_function_call_may_noreturn
);
3565 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3568 /* Init deps data vector. */
3570 init_deps_data_vector (void)
3572 int reserve
= (sched_max_luid
+ 1
3573 - VEC_length (haifa_deps_insn_data_def
, h_d_i_d
));
3575 && ! VEC_space (haifa_deps_insn_data_def
, h_d_i_d
, reserve
))
3576 VEC_safe_grow_cleared (haifa_deps_insn_data_def
, heap
, h_d_i_d
,
3577 3 * sched_max_luid
/ 2);
3580 /* If it is profitable to use them, initialize or extend (depending on
3581 GLOBAL_P) dependency data. */
3583 sched_deps_init (bool global_p
)
3585 /* Average number of insns in the basic block.
3586 '+ 1' is used to make it nonzero. */
3587 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3589 init_deps_data_vector ();
3591 /* We use another caching mechanism for selective scheduling, so
3592 we don't use this one. */
3593 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3595 /* ?!? We could save some memory by computing a per-region luid mapping
3596 which could reduce both the number of vectors in the cache and the
3597 size of each vector. Instead we just avoid the cache entirely unless
3598 the average number of instructions in a basic block is very high. See
3599 the comment before the declaration of true_dependency_cache for
3600 what we consider "very high". */
3602 extend_dependency_caches (sched_max_luid
, true);
3607 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3608 /* Allocate lists for one block at a time. */
3610 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3611 /* Allocate nodes for one block at a time.
3612 We assume that average insn has
3614 5 * insns_in_block
);
3619 /* Create or extend (depending on CREATE_P) dependency caches to
3622 extend_dependency_caches (int n
, bool create_p
)
3624 if (create_p
|| true_dependency_cache
)
3626 int i
, luid
= cache_size
+ n
;
3628 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
3630 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
3631 output_dependency_cache
, luid
);
3632 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
3635 if (current_sched_info
->flags
& DO_SPECULATION
)
3636 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
3639 for (i
= cache_size
; i
< luid
; i
++)
3641 bitmap_initialize (&true_dependency_cache
[i
], 0);
3642 bitmap_initialize (&output_dependency_cache
[i
], 0);
3643 bitmap_initialize (&anti_dependency_cache
[i
], 0);
3645 if (current_sched_info
->flags
& DO_SPECULATION
)
3646 bitmap_initialize (&spec_dependency_cache
[i
], 0);
3652 /* Finalize dependency information for the whole function. */
3654 sched_deps_finish (void)
3656 gcc_assert (deps_pools_are_empty_p ());
3657 free_alloc_pool_if_empty (&dn_pool
);
3658 free_alloc_pool_if_empty (&dl_pool
);
3659 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
3661 VEC_free (haifa_deps_insn_data_def
, heap
, h_d_i_d
);
3664 if (true_dependency_cache
)
3668 for (i
= 0; i
< cache_size
; i
++)
3670 bitmap_clear (&true_dependency_cache
[i
]);
3671 bitmap_clear (&output_dependency_cache
[i
]);
3672 bitmap_clear (&anti_dependency_cache
[i
]);
3674 if (sched_deps_info
->generate_spec_deps
)
3675 bitmap_clear (&spec_dependency_cache
[i
]);
3677 free (true_dependency_cache
);
3678 true_dependency_cache
= NULL
;
3679 free (output_dependency_cache
);
3680 output_dependency_cache
= NULL
;
3681 free (anti_dependency_cache
);
3682 anti_dependency_cache
= NULL
;
3684 if (sched_deps_info
->generate_spec_deps
)
3686 free (spec_dependency_cache
);
3687 spec_dependency_cache
= NULL
;
3693 /* Initialize some global variables needed by the dependency analysis
3697 init_deps_global (void)
3699 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3700 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3701 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
3702 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
3703 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
3704 reg_pending_barrier
= NOT_A_BARRIER
;
3706 if (!sel_sched_p () || sched_emulate_haifa_p
)
3708 sched_deps_info
->start_insn
= haifa_start_insn
;
3709 sched_deps_info
->finish_insn
= haifa_finish_insn
;
3711 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
3712 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
3713 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
3715 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
3716 sched_deps_info
->note_dep
= haifa_note_dep
;
3720 /* Free everything used by the dependency analysis code. */
3723 finish_deps_global (void)
3725 FREE_REG_SET (reg_pending_sets
);
3726 FREE_REG_SET (reg_pending_clobbers
);
3727 FREE_REG_SET (reg_pending_uses
);
3730 /* Estimate the weakness of dependence between MEM1 and MEM2. */
3732 estimate_dep_weak (rtx mem1
, rtx mem2
)
3737 /* MEMs are the same - don't speculate. */
3738 return MIN_DEP_WEAK
;
3740 r1
= XEXP (mem1
, 0);
3741 r2
= XEXP (mem2
, 0);
3744 || (REG_P (r1
) && REG_P (r2
)
3745 && REGNO (r1
) == REGNO (r2
)))
3746 /* Again, MEMs are the same. */
3747 return MIN_DEP_WEAK
;
3748 else if ((REG_P (r1
) && !REG_P (r2
))
3749 || (!REG_P (r1
) && REG_P (r2
)))
3750 /* Different addressing modes - reason to be more speculative,
3752 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
3754 /* We can't say anything about the dependence. */
3755 return UNCERTAIN_DEP_WEAK
;
3758 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3759 This function can handle same INSN and ELEM (INSN == ELEM).
3760 It is a convenience wrapper. */
3762 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
3767 if (dep_type
== REG_DEP_TRUE
)
3769 else if (dep_type
== REG_DEP_OUTPUT
)
3773 gcc_assert (dep_type
== REG_DEP_ANTI
);
3777 /* When add_dependence is called from inside sched-deps.c, we expect
3778 cur_insn to be non-null. */
3779 internal
= cur_insn
!= NULL
;
3781 gcc_assert (insn
== cur_insn
);
3785 note_dep (elem
, ds
);
3790 /* Return weakness of speculative type TYPE in the dep_status DS. */
3792 get_dep_weak_1 (ds_t ds
, ds_t type
)
3798 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
3799 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
3800 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
3801 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
3802 default: gcc_unreachable ();
3809 get_dep_weak (ds_t ds
, ds_t type
)
3811 dw_t dw
= get_dep_weak_1 (ds
, type
);
3813 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3817 /* Return the dep_status, which has the same parameters as DS, except for
3818 speculative type TYPE, that will have weakness DW. */
3820 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
3822 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3827 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
3828 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
3829 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
3830 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
3831 default: gcc_unreachable ();
3836 /* Return the join of two dep_statuses DS1 and DS2.
3837 If MAX_P is true then choose the greater probability,
3838 otherwise multiply probabilities.
3839 This function assumes that both DS1 and DS2 contain speculative bits. */
3841 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
3845 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
3847 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
3849 t
= FIRST_SPEC_TYPE
;
3852 if ((ds1
& t
) && !(ds2
& t
))
3854 else if (!(ds1
& t
) && (ds2
& t
))
3856 else if ((ds1
& t
) && (ds2
& t
))
3858 dw_t dw1
= get_dep_weak (ds1
, t
);
3859 dw_t dw2
= get_dep_weak (ds2
, t
);
3864 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
3866 if (dw
< MIN_DEP_WEAK
)
3877 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
3880 if (t
== LAST_SPEC_TYPE
)
3882 t
<<= SPEC_TYPE_SHIFT
;
3889 /* Return the join of two dep_statuses DS1 and DS2.
3890 This function assumes that both DS1 and DS2 contain speculative bits. */
3892 ds_merge (ds_t ds1
, ds_t ds2
)
3894 return ds_merge_1 (ds1
, ds2
, false);
3897 /* Return the join of two dep_statuses DS1 and DS2. */
3899 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
3901 ds_t new_status
= ds
| ds2
;
3903 if (new_status
& SPECULATIVE
)
3905 if ((ds
&& !(ds
& SPECULATIVE
))
3906 || (ds2
&& !(ds2
& SPECULATIVE
)))
3907 /* Then this dep can't be speculative. */
3908 new_status
&= ~SPECULATIVE
;
3911 /* Both are speculative. Merging probabilities. */
3916 dw
= estimate_dep_weak (mem1
, mem2
);
3917 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
3925 new_status
= ds_merge (ds2
, ds
);
3932 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
3935 ds_max_merge (ds_t ds1
, ds_t ds2
)
3937 if (ds1
== 0 && ds2
== 0)
3940 if (ds1
== 0 && ds2
!= 0)
3943 if (ds1
!= 0 && ds2
== 0)
3946 return ds_merge_1 (ds1
, ds2
, true);
3949 /* Return the probability of speculation success for the speculation
3957 dt
= FIRST_SPEC_TYPE
;
3962 res
*= (ds_t
) get_dep_weak (ds
, dt
);
3966 if (dt
== LAST_SPEC_TYPE
)
3968 dt
<<= SPEC_TYPE_SHIFT
;
3974 res
/= MAX_DEP_WEAK
;
3976 if (res
< MIN_DEP_WEAK
)
3979 gcc_assert (res
<= MAX_DEP_WEAK
);
3984 /* Return a dep status that contains all speculation types of DS. */
3986 ds_get_speculation_types (ds_t ds
)
3988 if (ds
& BEGIN_DATA
)
3990 if (ds
& BE_IN_DATA
)
3992 if (ds
& BEGIN_CONTROL
)
3993 ds
|= BEGIN_CONTROL
;
3994 if (ds
& BE_IN_CONTROL
)
3995 ds
|= BE_IN_CONTROL
;
3997 return ds
& SPECULATIVE
;
4000 /* Return a dep status that contains maximal weakness for each speculation
4001 type present in DS. */
4003 ds_get_max_dep_weak (ds_t ds
)
4005 if (ds
& BEGIN_DATA
)
4006 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4007 if (ds
& BE_IN_DATA
)
4008 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4009 if (ds
& BEGIN_CONTROL
)
4010 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4011 if (ds
& BE_IN_CONTROL
)
4012 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4017 /* Dump information about the dependence status S. */
4019 dump_ds (FILE *f
, ds_t s
)
4024 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4026 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4027 if (s
& BEGIN_CONTROL
)
4028 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4029 if (s
& BE_IN_CONTROL
)
4030 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4033 fprintf (f
, "HARD_DEP; ");
4036 fprintf (f
, "DEP_TRUE; ");
4038 fprintf (f
, "DEP_ANTI; ");
4040 fprintf (f
, "DEP_OUTPUT; ");
4048 dump_ds (stderr
, s
);
4049 fprintf (stderr
, "\n");
4052 #ifdef ENABLE_CHECKING
4053 /* Verify that dependence type and status are consistent.
4054 If RELAXED_P is true, then skip dep_weakness checks. */
4056 check_dep (dep_t dep
, bool relaxed_p
)
4058 enum reg_note dt
= DEP_TYPE (dep
);
4059 ds_t ds
= DEP_STATUS (dep
);
4061 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4063 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4065 gcc_assert (ds
== -1);
4069 /* Check that dependence type contains the same bits as the status. */
4070 if (dt
== REG_DEP_TRUE
)
4071 gcc_assert (ds
& DEP_TRUE
);
4072 else if (dt
== REG_DEP_OUTPUT
)
4073 gcc_assert ((ds
& DEP_OUTPUT
)
4074 && !(ds
& DEP_TRUE
));
4076 gcc_assert ((dt
== REG_DEP_ANTI
)
4078 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4080 /* HARD_DEP can not appear in dep_status of a link. */
4081 gcc_assert (!(ds
& HARD_DEP
));
4083 /* Check that dependence status is set correctly when speculation is not
4085 if (!sched_deps_info
->generate_spec_deps
)
4086 gcc_assert (!(ds
& SPECULATIVE
));
4087 else if (ds
& SPECULATIVE
)
4091 ds_t type
= FIRST_SPEC_TYPE
;
4093 /* Check that dependence weakness is in proper range. */
4097 get_dep_weak (ds
, type
);
4099 if (type
== LAST_SPEC_TYPE
)
4101 type
<<= SPEC_TYPE_SHIFT
;
4106 if (ds
& BEGIN_SPEC
)
4108 /* Only true dependence can be data speculative. */
4109 if (ds
& BEGIN_DATA
)
4110 gcc_assert (ds
& DEP_TRUE
);
4112 /* Control dependencies in the insn scheduler are represented by
4113 anti-dependencies, therefore only anti dependence can be
4114 control speculative. */
4115 if (ds
& BEGIN_CONTROL
)
4116 gcc_assert (ds
& DEP_ANTI
);
4120 /* Subsequent speculations should resolve true dependencies. */
4121 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4124 /* Check that true and anti dependencies can't have other speculative
4127 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4128 /* An output dependence can't be speculative at all. */
4129 gcc_assert (!(ds
& DEP_OUTPUT
));
4131 gcc_assert (ds
& BEGIN_CONTROL
);
4134 #endif /* ENABLE_CHECKING */
4136 #endif /* INSN_SCHEDULING */