1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992-2019 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "insn-attr.h"
38 #include "sched-int.h"
41 #include "function-abi.h"
43 #ifdef INSN_SCHEDULING
45 /* Holds current parameters for the dependency analyzer. */
46 struct sched_deps_info_def
*sched_deps_info
;
48 /* The data is specific to the Haifa scheduler. */
49 vec
<haifa_deps_insn_data_def
>
52 /* Return the major type present in the DS. */
60 return REG_DEP_OUTPUT
;
63 return REG_DEP_CONTROL
;
65 gcc_assert (ds
& DEP_ANTI
);
70 /* Return equivalent dep_status. */
72 dk_to_ds (enum reg_note dk
)
86 gcc_assert (dk
== REG_DEP_ANTI
);
91 /* Functions to operate with dependence information container - dep_t. */
93 /* Init DEP with the arguments. */
95 init_dep_1 (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note type
, ds_t ds
)
99 DEP_TYPE (dep
) = type
;
100 DEP_STATUS (dep
) = ds
;
101 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
102 DEP_NONREG (dep
) = 0;
103 DEP_MULTIPLE (dep
) = 0;
104 DEP_REPLACE (dep
) = NULL
;
107 /* Init DEP with the arguments.
108 While most of the scheduler (including targets) only need the major type
109 of the dependency, it is convenient to hide full dep_status from them. */
111 init_dep (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note kind
)
115 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
116 ds
= dk_to_ds (kind
);
120 init_dep_1 (dep
, pro
, con
, kind
, ds
);
123 /* Make a copy of FROM in TO. */
125 copy_dep (dep_t to
, dep_t from
)
127 memcpy (to
, from
, sizeof (*to
));
130 static void dump_ds (FILE *, ds_t
);
132 /* Define flags for dump_dep (). */
134 /* Dump producer of the dependence. */
135 #define DUMP_DEP_PRO (2)
137 /* Dump consumer of the dependence. */
138 #define DUMP_DEP_CON (4)
140 /* Dump type of the dependence. */
141 #define DUMP_DEP_TYPE (8)
143 /* Dump status of the dependence. */
144 #define DUMP_DEP_STATUS (16)
146 /* Dump all information about the dependence. */
147 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
151 FLAGS is a bit mask specifying what information about DEP needs
153 If FLAGS has the very first bit set, then dump all information about DEP
154 and propagate this bit into the callee dump functions. */
156 dump_dep (FILE *dump
, dep_t dep
, int flags
)
159 flags
|= DUMP_DEP_ALL
;
163 if (flags
& DUMP_DEP_PRO
)
164 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
166 if (flags
& DUMP_DEP_CON
)
167 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
169 if (flags
& DUMP_DEP_TYPE
)
172 enum reg_note type
= DEP_TYPE (dep
);
184 case REG_DEP_CONTROL
:
197 fprintf (dump
, "%c; ", t
);
200 if (flags
& DUMP_DEP_STATUS
)
202 if (current_sched_info
->flags
& USE_DEPS_LIST
)
203 dump_ds (dump
, DEP_STATUS (dep
));
209 /* Default flags for dump_dep (). */
210 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
212 /* Dump all fields of DEP to STDERR. */
214 sd_debug_dep (dep_t dep
)
216 dump_dep (stderr
, dep
, 1);
217 fprintf (stderr
, "\n");
220 /* Determine whether DEP is a dependency link of a non-debug insn on a
224 depl_on_debug_p (dep_link_t dep
)
226 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
227 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
230 /* Functions to operate with a single link from the dependencies lists -
233 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
236 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
238 dep_link_t next
= *prev_nextp
;
240 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
241 && DEP_LINK_NEXT (l
) == NULL
);
243 /* Init node being inserted. */
244 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
245 DEP_LINK_NEXT (l
) = next
;
250 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
252 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
259 /* Add dep_link LINK to deps_list L. */
261 add_to_deps_list (dep_link_t link
, deps_list_t l
)
263 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
265 /* Don't count debug deps. */
266 if (!depl_on_debug_p (link
))
267 ++DEPS_LIST_N_LINKS (l
);
270 /* Detach dep_link L from the list. */
272 detach_dep_link (dep_link_t l
)
274 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
275 dep_link_t next
= DEP_LINK_NEXT (l
);
280 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
282 DEP_LINK_PREV_NEXTP (l
) = NULL
;
283 DEP_LINK_NEXT (l
) = NULL
;
286 /* Remove link LINK from list LIST. */
288 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
290 detach_dep_link (link
);
292 /* Don't count debug deps. */
293 if (!depl_on_debug_p (link
))
294 --DEPS_LIST_N_LINKS (list
);
297 /* Move link LINK from list FROM to list TO. */
299 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
301 remove_from_deps_list (link
, from
);
302 add_to_deps_list (link
, to
);
305 /* Return true of LINK is not attached to any list. */
307 dep_link_is_detached_p (dep_link_t link
)
309 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
312 /* Pool to hold all dependency nodes (dep_node_t). */
313 static object_allocator
<_dep_node
> *dn_pool
;
315 /* Number of dep_nodes out there. */
316 static int dn_pool_diff
= 0;
318 /* Create a dep_node. */
320 create_dep_node (void)
322 dep_node_t n
= dn_pool
->allocate ();
323 dep_link_t back
= DEP_NODE_BACK (n
);
324 dep_link_t forw
= DEP_NODE_FORW (n
);
326 DEP_LINK_NODE (back
) = n
;
327 DEP_LINK_NEXT (back
) = NULL
;
328 DEP_LINK_PREV_NEXTP (back
) = NULL
;
330 DEP_LINK_NODE (forw
) = n
;
331 DEP_LINK_NEXT (forw
) = NULL
;
332 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
339 /* Delete dep_node N. N must not be connected to any deps_list. */
341 delete_dep_node (dep_node_t n
)
343 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
344 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
346 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n
)));
353 /* Pool to hold dependencies lists (deps_list_t). */
354 static object_allocator
<_deps_list
> *dl_pool
;
356 /* Number of deps_lists out there. */
357 static int dl_pool_diff
= 0;
359 /* Functions to operate with dependences lists - deps_list_t. */
361 /* Return true if list L is empty. */
363 deps_list_empty_p (deps_list_t l
)
365 return DEPS_LIST_N_LINKS (l
) == 0;
368 /* Create a new deps_list. */
370 create_deps_list (void)
372 deps_list_t l
= dl_pool
->allocate ();
374 DEPS_LIST_FIRST (l
) = NULL
;
375 DEPS_LIST_N_LINKS (l
) = 0;
381 /* Free deps_list L. */
383 free_deps_list (deps_list_t l
)
385 gcc_assert (deps_list_empty_p (l
));
392 /* Return true if there is no dep_nodes and deps_lists out there.
393 After the region is scheduled all the dependency nodes and lists
394 should [generally] be returned to pool. */
396 deps_pools_are_empty_p (void)
398 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
401 /* Remove all elements from L. */
403 clear_deps_list (deps_list_t l
)
407 dep_link_t link
= DEPS_LIST_FIRST (l
);
412 remove_from_deps_list (link
, l
);
417 /* Decide whether a dependency should be treated as a hard or a speculative
420 dep_spec_p (dep_t dep
)
422 if (current_sched_info
->flags
& DO_SPECULATION
)
424 if (DEP_STATUS (dep
) & SPECULATIVE
)
427 if (current_sched_info
->flags
& DO_PREDICATION
)
429 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
432 if (DEP_REPLACE (dep
) != NULL
)
437 static regset reg_pending_sets
;
438 static regset reg_pending_clobbers
;
439 static regset reg_pending_uses
;
440 static regset reg_pending_control_uses
;
441 static enum reg_pending_barrier_mode reg_pending_barrier
;
443 /* Hard registers implicitly clobbered or used (or may be implicitly
444 clobbered or used) by the currently analyzed insn. For example,
445 insn in its constraint has one register class. Even if there is
446 currently no hard register in the insn, the particular hard
447 register will be in the insn after reload pass because the
448 constraint requires it. */
449 static HARD_REG_SET implicit_reg_pending_clobbers
;
450 static HARD_REG_SET implicit_reg_pending_uses
;
452 /* To speed up the test for duplicate dependency links we keep a
453 record of dependencies created by add_dependence when the average
454 number of instructions in a basic block is very large.
456 Studies have shown that there is typically around 5 instructions between
457 branches for typical C code. So we can make a guess that the average
458 basic block is approximately 5 instructions long; we will choose 100X
459 the average size as a very large basic block.
461 Each insn has associated bitmaps for its dependencies. Each bitmap
462 has enough entries to represent a dependency on any other insn in
463 the insn chain. All bitmap for true dependencies cache is
464 allocated then the rest two ones are also allocated. */
465 static bitmap true_dependency_cache
= NULL
;
466 static bitmap output_dependency_cache
= NULL
;
467 static bitmap anti_dependency_cache
= NULL
;
468 static bitmap control_dependency_cache
= NULL
;
469 static bitmap spec_dependency_cache
= NULL
;
470 static int cache_size
;
472 /* True if we should mark added dependencies as a non-register deps. */
473 static bool mark_as_hard
;
475 static int deps_may_trap_p (const_rtx
);
476 static void add_dependence_1 (rtx_insn
*, rtx_insn
*, enum reg_note
);
477 static void add_dependence_list (rtx_insn
*, rtx_insn_list
*, int,
478 enum reg_note
, bool);
479 static void add_dependence_list_and_free (class deps_desc
*, rtx_insn
*,
480 rtx_insn_list
**, int, enum reg_note
,
482 static void delete_all_dependences (rtx_insn
*);
483 static void chain_to_prev_insn (rtx_insn
*);
485 static void flush_pending_lists (class deps_desc
*, rtx_insn
*, int, int);
486 static void sched_analyze_1 (class deps_desc
*, rtx
, rtx_insn
*);
487 static void sched_analyze_2 (class deps_desc
*, rtx
, rtx_insn
*);
488 static void sched_analyze_insn (class deps_desc
*, rtx
, rtx_insn
*);
490 static bool sched_has_condition_p (const rtx_insn
*);
491 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
493 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
495 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
497 static void check_dep (dep_t
, bool);
500 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
503 deps_may_trap_p (const_rtx mem
)
505 const_rtx addr
= XEXP (mem
, 0);
507 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
509 const_rtx t
= get_reg_known_value (REGNO (addr
));
513 return rtx_addr_can_trap_p (addr
);
517 /* Find the condition under which INSN is executed. If REV is not NULL,
518 it is set to TRUE when the returned comparison should be reversed
519 to get the actual condition. */
521 sched_get_condition_with_rev_uncached (const rtx_insn
*insn
, bool *rev
)
523 rtx pat
= PATTERN (insn
);
529 if (GET_CODE (pat
) == COND_EXEC
)
530 return COND_EXEC_TEST (pat
);
532 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
535 src
= SET_SRC (pc_set (insn
));
537 if (XEXP (src
, 2) == pc_rtx
)
538 return XEXP (src
, 0);
539 else if (XEXP (src
, 1) == pc_rtx
)
541 rtx cond
= XEXP (src
, 0);
542 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
544 if (revcode
== UNKNOWN
)
555 /* Return the condition under which INSN does not execute (i.e. the
556 not-taken condition for a conditional branch), or NULL if we cannot
557 find such a condition. The caller should make a copy of the condition
560 sched_get_reverse_condition_uncached (const rtx_insn
*insn
)
563 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
564 if (cond
== NULL_RTX
)
568 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
569 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
576 /* Caching variant of sched_get_condition_with_rev_uncached.
577 We only do actual work the first time we come here for an insn; the
578 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
580 sched_get_condition_with_rev (const rtx_insn
*insn
, bool *rev
)
584 if (INSN_LUID (insn
) == 0)
585 return sched_get_condition_with_rev_uncached (insn
, rev
);
587 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
590 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
593 *rev
= INSN_REVERSE_COND (insn
);
594 return INSN_CACHED_COND (insn
);
597 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
598 INSN_REVERSE_COND (insn
) = tmp
;
600 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
602 INSN_CACHED_COND (insn
) = const_true_rtx
;
607 *rev
= INSN_REVERSE_COND (insn
);
608 return INSN_CACHED_COND (insn
);
611 /* True when we can find a condition under which INSN is executed. */
613 sched_has_condition_p (const rtx_insn
*insn
)
615 return !! sched_get_condition_with_rev (insn
, NULL
);
620 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
622 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
624 if (COMPARISON_P (cond1
)
625 && COMPARISON_P (cond2
)
626 && GET_CODE (cond1
) ==
628 ? reversed_comparison_code (cond2
, NULL
)
630 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
631 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
636 /* Return true if insn1 and insn2 can never depend on one another because
637 the conditions under which they are executed are mutually exclusive. */
639 sched_insns_conditions_mutex_p (const rtx_insn
*insn1
, const rtx_insn
*insn2
)
642 bool rev1
= false, rev2
= false;
644 /* df doesn't handle conditional lifetimes entirely correctly;
645 calls mess up the conditional lifetimes. */
646 if (!CALL_P (insn1
) && !CALL_P (insn2
))
648 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
649 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
651 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
652 /* Make sure first instruction doesn't affect condition of second
653 instruction if switched. */
654 && !modified_in_p (cond1
, insn2
)
655 /* Make sure second instruction doesn't affect condition of first
656 instruction if switched. */
657 && !modified_in_p (cond2
, insn1
))
664 /* Return true if INSN can potentially be speculated with type DS. */
666 sched_insn_is_legitimate_for_speculation_p (const rtx_insn
*insn
, ds_t ds
)
668 if (HAS_INTERNAL_DEP (insn
))
671 if (!NONJUMP_INSN_P (insn
))
674 if (SCHED_GROUP_P (insn
))
677 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn
)))
680 if (side_effects_p (PATTERN (insn
)))
684 /* The following instructions, which depend on a speculatively scheduled
685 instruction, cannot be speculatively scheduled along. */
687 if (may_trap_or_fault_p (PATTERN (insn
)))
688 /* If instruction might fault, it cannot be speculatively scheduled.
689 For control speculation it's obvious why and for data speculation
690 it's because the insn might get wrong input if speculation
691 wasn't successful. */
694 if ((ds
& BE_IN_DATA
)
695 && sched_has_condition_p (insn
))
696 /* If this is a predicated instruction, then it cannot be
697 speculatively scheduled. See PR35659. */
704 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
705 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
706 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
707 This function is used to switch sd_iterator to the next list.
708 !!! For internal use only. Might consider moving it to sched-int.h. */
710 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
711 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
713 sd_list_types_def types
= *types_ptr
;
715 if (types
& SD_LIST_HARD_BACK
)
717 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
718 *resolved_p_ptr
= false;
719 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
721 else if (types
& SD_LIST_SPEC_BACK
)
723 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
724 *resolved_p_ptr
= false;
725 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
727 else if (types
& SD_LIST_FORW
)
729 *list_ptr
= INSN_FORW_DEPS (insn
);
730 *resolved_p_ptr
= false;
731 *types_ptr
= types
& ~SD_LIST_FORW
;
733 else if (types
& SD_LIST_RES_BACK
)
735 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
736 *resolved_p_ptr
= true;
737 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
739 else if (types
& SD_LIST_RES_FORW
)
741 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
742 *resolved_p_ptr
= true;
743 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
748 *resolved_p_ptr
= false;
749 *types_ptr
= SD_LIST_NONE
;
753 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
755 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
759 while (list_types
!= SD_LIST_NONE
)
764 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
766 size
+= DEPS_LIST_N_LINKS (list
);
772 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
775 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
777 while (list_types
!= SD_LIST_NONE
)
782 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
783 if (!deps_list_empty_p (list
))
790 /* Initialize data for INSN. */
792 sd_init_insn (rtx_insn
*insn
)
794 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
795 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
796 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
797 INSN_FORW_DEPS (insn
) = create_deps_list ();
798 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
800 /* ??? It would be nice to allocate dependency caches here. */
803 /* Free data for INSN. */
805 sd_finish_insn (rtx_insn
*insn
)
807 /* ??? It would be nice to deallocate dependency caches here. */
809 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
810 INSN_HARD_BACK_DEPS (insn
) = NULL
;
812 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
813 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
815 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
816 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
818 free_deps_list (INSN_FORW_DEPS (insn
));
819 INSN_FORW_DEPS (insn
) = NULL
;
821 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
822 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
825 /* Find a dependency between producer PRO and consumer CON.
826 Search through resolved dependency lists if RESOLVED_P is true.
827 If no such dependency is found return NULL,
828 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
829 with an iterator pointing to it. */
831 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
832 sd_iterator_def
*sd_it_ptr
)
834 sd_list_types_def pro_list_type
;
835 sd_list_types_def con_list_type
;
836 sd_iterator_def sd_it
;
838 bool found_p
= false;
842 pro_list_type
= SD_LIST_RES_FORW
;
843 con_list_type
= SD_LIST_RES_BACK
;
847 pro_list_type
= SD_LIST_FORW
;
848 con_list_type
= SD_LIST_BACK
;
851 /* Walk through either back list of INSN or forw list of ELEM
852 depending on which one is shorter. */
853 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
855 /* Find the dep_link with producer PRO in consumer's back_deps. */
856 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
857 if (DEP_PRO (dep
) == pro
)
865 /* Find the dep_link with consumer CON in producer's forw_deps. */
866 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
867 if (DEP_CON (dep
) == con
)
876 if (sd_it_ptr
!= NULL
)
885 /* Find a dependency between producer PRO and consumer CON.
886 Use dependency [if available] to check if dependency is present at all.
887 Search through resolved dependency lists if RESOLVED_P is true.
888 If the dependency or NULL if none found. */
890 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
892 if (true_dependency_cache
!= NULL
)
893 /* Avoiding the list walk below can cut compile times dramatically
896 int elem_luid
= INSN_LUID (pro
);
897 int insn_luid
= INSN_LUID (con
);
899 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
900 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
901 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
902 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
906 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
909 /* Add or update a dependence described by DEP.
910 MEM1 and MEM2, if non-null, correspond to memory locations in case of
913 The function returns a value indicating if an old entry has been changed
914 or a new entry has been added to insn's backward deps.
916 This function merely checks if producer and consumer is the same insn
917 and doesn't create a dep in this case. Actual manipulation of
918 dependence data structures is performed in add_or_update_dep_1. */
919 static enum DEPS_ADJUST_RESULT
920 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
922 rtx_insn
*elem
= DEP_PRO (dep
);
923 rtx_insn
*insn
= DEP_CON (dep
);
925 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
927 /* Don't depend an insn on itself. */
930 if (sched_deps_info
->generate_spec_deps
)
931 /* INSN has an internal dependence, which we can't overcome. */
932 HAS_INTERNAL_DEP (insn
) = 1;
937 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
940 /* Ask dependency caches what needs to be done for dependence DEP.
941 Return DEP_CREATED if new dependence should be created and there is no
942 need to try to find one searching the dependencies lists.
943 Return DEP_PRESENT if there already is a dependence described by DEP and
944 hence nothing is to be done.
945 Return DEP_CHANGED if there already is a dependence, but it should be
946 updated to incorporate additional information from DEP. */
947 static enum DEPS_ADJUST_RESULT
948 ask_dependency_caches (dep_t dep
)
950 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
951 int insn_luid
= INSN_LUID (DEP_CON (dep
));
953 gcc_assert (true_dependency_cache
!= NULL
954 && output_dependency_cache
!= NULL
955 && anti_dependency_cache
!= NULL
956 && control_dependency_cache
!= NULL
);
958 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
960 enum reg_note present_dep_type
;
962 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
963 present_dep_type
= REG_DEP_TRUE
;
964 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
965 present_dep_type
= REG_DEP_OUTPUT
;
966 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
967 present_dep_type
= REG_DEP_ANTI
;
968 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
969 present_dep_type
= REG_DEP_CONTROL
;
971 /* There is no existing dep so it should be created. */
974 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
975 /* DEP does not add anything to the existing dependence. */
980 ds_t present_dep_types
= 0;
982 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
983 present_dep_types
|= DEP_TRUE
;
984 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
985 present_dep_types
|= DEP_OUTPUT
;
986 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
987 present_dep_types
|= DEP_ANTI
;
988 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
989 present_dep_types
|= DEP_CONTROL
;
991 if (present_dep_types
== 0)
992 /* There is no existing dep so it should be created. */
995 if (!(current_sched_info
->flags
& DO_SPECULATION
)
996 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
998 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
999 == present_dep_types
)
1000 /* DEP does not add anything to the existing dependence. */
1005 /* Only true dependencies can be data speculative and
1006 only anti dependencies can be control speculative. */
1007 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1008 == present_dep_types
);
1010 /* if (DEP is SPECULATIVE) then
1011 ..we should update DEP_STATUS
1013 ..we should reset existing dep to non-speculative. */
1020 /* Set dependency caches according to DEP. */
1022 set_dependency_caches (dep_t dep
)
1024 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1025 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1027 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1029 switch (DEP_TYPE (dep
))
1032 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1035 case REG_DEP_OUTPUT
:
1036 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1040 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1043 case REG_DEP_CONTROL
:
1044 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1053 ds_t ds
= DEP_STATUS (dep
);
1056 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1057 if (ds
& DEP_OUTPUT
)
1058 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1060 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1061 if (ds
& DEP_CONTROL
)
1062 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1064 if (ds
& SPECULATIVE
)
1066 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1067 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1072 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1073 caches accordingly. */
1075 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1077 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1078 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1080 /* Clear corresponding cache entry because type of the link
1081 may have changed. Keep them if we use_deps_list. */
1082 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1086 case REG_DEP_OUTPUT
:
1087 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1091 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1094 case REG_DEP_CONTROL
:
1095 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1103 set_dependency_caches (dep
);
1106 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1108 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1110 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1111 dep_link_t link
= DEP_NODE_BACK (node
);
1112 dep_t dep
= DEP_NODE_DEP (node
);
1113 rtx_insn
*elem
= DEP_PRO (dep
);
1114 rtx_insn
*insn
= DEP_CON (dep
);
1116 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1118 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1120 if (true_dependency_cache
!= NULL
)
1121 /* Clear the cache entry. */
1122 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1126 /* Update DEP to incorporate information from NEW_DEP.
1127 SD_IT points to DEP in case it should be moved to another list.
1128 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1129 data-speculative dependence should be updated. */
1130 static enum DEPS_ADJUST_RESULT
1131 update_dep (dep_t dep
, dep_t new_dep
,
1132 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1133 rtx mem1 ATTRIBUTE_UNUSED
,
1134 rtx mem2 ATTRIBUTE_UNUSED
)
1136 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1137 enum reg_note old_type
= DEP_TYPE (dep
);
1138 bool was_spec
= dep_spec_p (dep
);
1140 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1141 DEP_MULTIPLE (dep
) = 1;
1143 /* If this is a more restrictive type of dependence than the
1144 existing one, then change the existing dependence to this
1146 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1148 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1152 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1153 /* Update DEP_STATUS. */
1155 ds_t dep_status
= DEP_STATUS (dep
);
1156 ds_t ds
= DEP_STATUS (new_dep
);
1157 ds_t new_status
= ds
| dep_status
;
1159 if (new_status
& SPECULATIVE
)
1161 /* Either existing dep or a dep we're adding or both are
1163 if (!(ds
& SPECULATIVE
)
1164 || !(dep_status
& SPECULATIVE
))
1165 /* The new dep can't be speculative. */
1166 new_status
&= ~SPECULATIVE
;
1169 /* Both are speculative. Merge probabilities. */
1174 dw
= estimate_dep_weak (mem1
, mem2
);
1175 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1178 new_status
= ds_merge (dep_status
, ds
);
1184 if (dep_status
!= ds
)
1186 DEP_STATUS (dep
) = ds
;
1191 if (was_spec
&& !dep_spec_p (dep
))
1192 /* The old dep was speculative, but now it isn't. */
1193 change_spec_dep_to_hard (sd_it
);
1195 if (true_dependency_cache
!= NULL
1196 && res
== DEP_CHANGED
)
1197 update_dependency_caches (dep
, old_type
);
1202 /* Add or update a dependence described by DEP.
1203 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1206 The function returns a value indicating if an old entry has been changed
1207 or a new entry has been added to insn's backward deps or nothing has
1208 been updated at all. */
1209 static enum DEPS_ADJUST_RESULT
1210 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1211 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1213 bool maybe_present_p
= true;
1214 bool present_p
= false;
1216 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1217 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1220 check_dep (new_dep
, mem1
!= NULL
);
1222 if (true_dependency_cache
!= NULL
)
1224 switch (ask_dependency_caches (new_dep
))
1228 sd_iterator_def sd_it
;
1230 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1232 resolved_p
, &sd_it
);
1233 DEP_MULTIPLE (present_dep
) = 1;
1237 maybe_present_p
= true;
1242 maybe_present_p
= false;
1252 /* Check that we don't already have this dependence. */
1253 if (maybe_present_p
)
1256 sd_iterator_def sd_it
;
1258 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1260 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1262 resolved_p
, &sd_it
);
1264 if (present_dep
!= NULL
)
1265 /* We found an existing dependency between ELEM and INSN. */
1266 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1268 /* We didn't find a dep, it shouldn't present in the cache. */
1269 gcc_assert (!present_p
);
1272 /* Might want to check one level of transitivity to save conses.
1273 This check should be done in maybe_add_or_update_dep_1.
1274 Since we made it to add_or_update_dep_1, we must create
1275 (or update) a link. */
1277 if (mem1
!= NULL_RTX
)
1279 gcc_assert (sched_deps_info
->generate_spec_deps
);
1280 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1281 estimate_dep_weak (mem1
, mem2
));
1284 sd_add_dep (new_dep
, resolved_p
);
1289 /* Initialize BACK_LIST_PTR with consumer's backward list and
1290 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1291 initialize with lists that hold resolved deps. */
1293 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1294 deps_list_t
*back_list_ptr
,
1295 deps_list_t
*forw_list_ptr
)
1297 rtx_insn
*con
= DEP_CON (dep
);
1301 if (dep_spec_p (dep
))
1302 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1304 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1306 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1310 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1311 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1315 /* Add dependence described by DEP.
1316 If RESOLVED_P is true treat the dependence as a resolved one. */
1318 sd_add_dep (dep_t dep
, bool resolved_p
)
1320 dep_node_t n
= create_dep_node ();
1321 deps_list_t con_back_deps
;
1322 deps_list_t pro_forw_deps
;
1323 rtx_insn
*elem
= DEP_PRO (dep
);
1324 rtx_insn
*insn
= DEP_CON (dep
);
1326 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1328 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1329 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1330 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1332 copy_dep (DEP_NODE_DEP (n
), dep
);
1334 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1336 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1339 check_dep (dep
, false);
1341 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1343 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1344 in the bitmap caches of dependency information. */
1345 if (true_dependency_cache
!= NULL
)
1346 set_dependency_caches (dep
);
1349 /* Add or update backward dependence between INSN and ELEM
1350 with given type DEP_TYPE and dep_status DS.
1351 This function is a convenience wrapper. */
1352 enum DEPS_ADJUST_RESULT
1353 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1355 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1358 /* Resolved dependence pointed to by SD_IT.
1359 SD_IT will advance to the next element. */
1361 sd_resolve_dep (sd_iterator_def sd_it
)
1363 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1364 dep_t dep
= DEP_NODE_DEP (node
);
1365 rtx_insn
*pro
= DEP_PRO (dep
);
1366 rtx_insn
*con
= DEP_CON (dep
);
1368 if (dep_spec_p (dep
))
1369 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1370 INSN_RESOLVED_BACK_DEPS (con
));
1372 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1373 INSN_RESOLVED_BACK_DEPS (con
));
1375 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1376 INSN_RESOLVED_FORW_DEPS (pro
));
1379 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1380 pointed to by SD_IT to unresolved state. */
1382 sd_unresolve_dep (sd_iterator_def sd_it
)
1384 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1385 dep_t dep
= DEP_NODE_DEP (node
);
1386 rtx_insn
*pro
= DEP_PRO (dep
);
1387 rtx_insn
*con
= DEP_CON (dep
);
1389 if (dep_spec_p (dep
))
1390 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1391 INSN_SPEC_BACK_DEPS (con
));
1393 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1394 INSN_HARD_BACK_DEPS (con
));
1396 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1397 INSN_FORW_DEPS (pro
));
1400 /* Make TO depend on all the FROM's producers.
1401 If RESOLVED_P is true add dependencies to the resolved lists. */
1403 sd_copy_back_deps (rtx_insn
*to
, rtx_insn
*from
, bool resolved_p
)
1405 sd_list_types_def list_type
;
1406 sd_iterator_def sd_it
;
1409 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1411 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1413 dep_def _new_dep
, *new_dep
= &_new_dep
;
1415 copy_dep (new_dep
, dep
);
1416 DEP_CON (new_dep
) = to
;
1417 sd_add_dep (new_dep
, resolved_p
);
1421 /* Remove a dependency referred to by SD_IT.
1422 SD_IT will point to the next dependence after removal. */
1424 sd_delete_dep (sd_iterator_def sd_it
)
1426 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1427 dep_t dep
= DEP_NODE_DEP (n
);
1428 rtx_insn
*pro
= DEP_PRO (dep
);
1429 rtx_insn
*con
= DEP_CON (dep
);
1430 deps_list_t con_back_deps
;
1431 deps_list_t pro_forw_deps
;
1433 if (true_dependency_cache
!= NULL
)
1435 int elem_luid
= INSN_LUID (pro
);
1436 int insn_luid
= INSN_LUID (con
);
1438 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1439 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1440 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1441 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1443 if (current_sched_info
->flags
& DO_SPECULATION
)
1444 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1447 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1448 &con_back_deps
, &pro_forw_deps
);
1450 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1451 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1453 delete_dep_node (n
);
1456 /* Dump size of the lists. */
1457 #define DUMP_LISTS_SIZE (2)
1459 /* Dump dependencies of the lists. */
1460 #define DUMP_LISTS_DEPS (4)
1462 /* Dump all information about the lists. */
1463 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1465 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1466 FLAGS is a bit mask specifying what information about the lists needs
1468 If FLAGS has the very first bit set, then dump all information about
1469 the lists and propagate this bit into the callee dump functions. */
1471 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1473 sd_iterator_def sd_it
;
1480 flags
|= DUMP_LISTS_ALL
;
1482 fprintf (dump
, "[");
1484 if (flags
& DUMP_LISTS_SIZE
)
1485 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1487 if (flags
& DUMP_LISTS_DEPS
)
1489 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1491 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1492 fprintf (dump
, " ");
1497 /* Dump all information about deps_lists of INSN specified by TYPES
1500 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1502 dump_lists (stderr
, insn
, types
, 1);
1503 fprintf (stderr
, "\n");
1506 /* A wrapper around add_dependence_1, to add a dependence of CON on
1507 PRO, with type DEP_TYPE. This function implements special handling
1508 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1509 the type to REG_DEP_ANTI if we can determine that predication is
1510 impossible; otherwise we add additional true dependencies on the
1511 INSN_COND_DEPS list of the jump (which PRO must be). */
1513 add_dependence (rtx_insn
*con
, rtx_insn
*pro
, enum reg_note dep_type
)
1515 if (dep_type
== REG_DEP_CONTROL
1516 && !(current_sched_info
->flags
& DO_PREDICATION
))
1517 dep_type
= REG_DEP_ANTI
;
1519 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1520 so we must also make the insn dependent on the setter of the
1522 if (dep_type
== REG_DEP_CONTROL
)
1524 rtx_insn
*real_pro
= pro
;
1525 rtx_insn
*other
= real_insn_for_shadow (real_pro
);
1528 if (other
!= NULL_RTX
)
1530 cond
= sched_get_reverse_condition_uncached (real_pro
);
1531 /* Verify that the insn does not use a different value in
1532 the condition register than the one that was present at
1534 if (cond
== NULL_RTX
)
1535 dep_type
= REG_DEP_ANTI
;
1536 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1539 CLEAR_HARD_REG_SET (uses
);
1540 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1541 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1542 dep_type
= REG_DEP_ANTI
;
1544 if (dep_type
== REG_DEP_CONTROL
)
1546 if (sched_verbose
>= 5)
1547 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1548 INSN_UID (real_pro
));
1549 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1550 REG_DEP_TRUE
, false);
1554 add_dependence_1 (con
, pro
, dep_type
);
1557 /* A convenience wrapper to operate on an entire list. HARD should be
1558 true if DEP_NONREG should be set on newly created dependencies. */
1561 add_dependence_list (rtx_insn
*insn
, rtx_insn_list
*list
, int uncond
,
1562 enum reg_note dep_type
, bool hard
)
1564 mark_as_hard
= hard
;
1565 for (; list
; list
= list
->next ())
1567 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, list
->insn ()))
1568 add_dependence (insn
, list
->insn (), dep_type
);
1570 mark_as_hard
= false;
1573 /* Similar, but free *LISTP at the same time, when the context
1574 is not readonly. HARD should be true if DEP_NONREG should be set on
1575 newly created dependencies. */
1578 add_dependence_list_and_free (class deps_desc
*deps
, rtx_insn
*insn
,
1579 rtx_insn_list
**listp
,
1580 int uncond
, enum reg_note dep_type
, bool hard
)
1582 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1584 /* We don't want to short-circuit dependencies involving debug
1585 insns, because they may cause actual dependencies to be
1587 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1590 free_INSN_LIST_list (listp
);
1593 /* Remove all occurrences of INSN from LIST. Return the number of
1594 occurrences removed. */
1597 remove_from_dependence_list (rtx_insn
*insn
, rtx_insn_list
**listp
)
1603 if ((*listp
)->insn () == insn
)
1605 remove_free_INSN_LIST_node (listp
);
1610 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1616 /* Same as above, but process two lists at once. */
1618 remove_from_both_dependence_lists (rtx_insn
*insn
,
1619 rtx_insn_list
**listp
,
1620 rtx_expr_list
**exprp
)
1626 if (XEXP (*listp
, 0) == insn
)
1628 remove_free_INSN_LIST_node (listp
);
1629 remove_free_EXPR_LIST_node (exprp
);
1634 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1635 exprp
= (rtx_expr_list
**)&XEXP (*exprp
, 1);
1641 /* Clear all dependencies for an insn. */
1643 delete_all_dependences (rtx_insn
*insn
)
1645 sd_iterator_def sd_it
;
1648 /* The below cycle can be optimized to clear the caches and back_deps
1649 in one call but that would provoke duplication of code from
1652 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1653 sd_iterator_cond (&sd_it
, &dep
);)
1654 sd_delete_dep (sd_it
);
1657 /* All insns in a scheduling group except the first should only have
1658 dependencies on the previous insn in the group. So we find the
1659 first instruction in the scheduling group by walking the dependence
1660 chains backwards. Then we add the dependencies for the group to
1661 the previous nonnote insn. */
1664 chain_to_prev_insn (rtx_insn
*insn
)
1666 sd_iterator_def sd_it
;
1668 rtx_insn
*prev_nonnote
;
1670 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1673 rtx_insn
*pro
= DEP_PRO (dep
);
1677 i
= prev_nonnote_insn (i
);
1681 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1683 if (! sched_insns_conditions_mutex_p (i
, pro
))
1684 add_dependence (i
, pro
, DEP_TYPE (dep
));
1688 delete_all_dependences (insn
);
1690 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1691 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1692 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1693 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1696 /* Process an insn's memory dependencies. There are four kinds of
1699 (0) read dependence: read follows read
1700 (1) true dependence: read follows write
1701 (2) output dependence: write follows write
1702 (3) anti dependence: write follows read
1704 We are careful to build only dependencies which actually exist, and
1705 use transitivity to avoid building too many links. */
1707 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1708 The MEM is a memory reference contained within INSN, which we are saving
1709 so that we can do memory aliasing on it. */
1712 add_insn_mem_dependence (class deps_desc
*deps
, bool read_p
,
1713 rtx_insn
*insn
, rtx mem
)
1715 rtx_insn_list
**insn_list
;
1716 rtx_insn_list
*insn_node
;
1717 rtx_expr_list
**mem_list
;
1718 rtx_expr_list
*mem_node
;
1720 gcc_assert (!deps
->readonly
);
1723 insn_list
= &deps
->pending_read_insns
;
1724 mem_list
= &deps
->pending_read_mems
;
1725 if (!DEBUG_INSN_P (insn
))
1726 deps
->pending_read_list_length
++;
1730 insn_list
= &deps
->pending_write_insns
;
1731 mem_list
= &deps
->pending_write_mems
;
1732 deps
->pending_write_list_length
++;
1735 insn_node
= alloc_INSN_LIST (insn
, *insn_list
);
1736 *insn_list
= insn_node
;
1738 if (sched_deps_info
->use_cselib
)
1740 mem
= shallow_copy_rtx (mem
);
1741 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1742 GET_MODE (mem
), insn
);
1744 mem_node
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1745 *mem_list
= mem_node
;
1748 /* Make a dependency between every memory reference on the pending lists
1749 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1750 dependencies for a read operation, similarly with FOR_WRITE. */
1753 flush_pending_lists (class deps_desc
*deps
, rtx_insn
*insn
, int for_read
,
1758 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1759 1, REG_DEP_ANTI
, true);
1760 if (!deps
->readonly
)
1762 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1763 deps
->pending_read_list_length
= 0;
1767 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1768 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1771 add_dependence_list_and_free (deps
, insn
,
1772 &deps
->last_pending_memory_flush
, 1,
1773 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1776 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1777 REG_DEP_ANTI
, true);
1779 if (DEBUG_INSN_P (insn
))
1782 free_INSN_LIST_list (&deps
->pending_read_insns
);
1783 free_INSN_LIST_list (&deps
->pending_write_insns
);
1784 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1785 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1788 if (!deps
->readonly
)
1790 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1791 deps
->pending_write_list_length
= 0;
1793 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1794 deps
->pending_flush_length
= 1;
1796 mark_as_hard
= false;
1799 /* Instruction which dependencies we are analyzing. */
1800 static rtx_insn
*cur_insn
= NULL
;
1802 /* Implement hooks for haifa scheduler. */
1805 haifa_start_insn (rtx_insn
*insn
)
1807 gcc_assert (insn
&& !cur_insn
);
1813 haifa_finish_insn (void)
1819 haifa_note_reg_set (int regno
)
1821 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1825 haifa_note_reg_clobber (int regno
)
1827 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1831 haifa_note_reg_use (int regno
)
1833 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1837 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx_insn
*pending_insn
, ds_t ds
)
1839 if (!(ds
& SPECULATIVE
))
1842 pending_mem
= NULL_RTX
;
1845 gcc_assert (ds
& BEGIN_DATA
);
1848 dep_def _dep
, *dep
= &_dep
;
1850 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1851 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1852 DEP_NONREG (dep
) = 1;
1853 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1859 haifa_note_dep (rtx_insn
*elem
, ds_t ds
)
1864 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1866 DEP_NONREG (dep
) = 1;
1867 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1871 note_reg_use (int r
)
1873 if (sched_deps_info
->note_reg_use
)
1874 sched_deps_info
->note_reg_use (r
);
1878 note_reg_set (int r
)
1880 if (sched_deps_info
->note_reg_set
)
1881 sched_deps_info
->note_reg_set (r
);
1885 note_reg_clobber (int r
)
1887 if (sched_deps_info
->note_reg_clobber
)
1888 sched_deps_info
->note_reg_clobber (r
);
1892 note_mem_dep (rtx m1
, rtx m2
, rtx_insn
*e
, ds_t ds
)
1894 if (sched_deps_info
->note_mem_dep
)
1895 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1899 note_dep (rtx_insn
*e
, ds_t ds
)
1901 if (sched_deps_info
->note_dep
)
1902 sched_deps_info
->note_dep (e
, ds
);
1905 /* Return corresponding to DS reg_note. */
1910 return REG_DEP_TRUE
;
1911 else if (ds
& DEP_OUTPUT
)
1912 return REG_DEP_OUTPUT
;
1913 else if (ds
& DEP_ANTI
)
1914 return REG_DEP_ANTI
;
1917 gcc_assert (ds
& DEP_CONTROL
);
1918 return REG_DEP_CONTROL
;
1924 /* Functions for computation of info needed for register pressure
1925 sensitive insn scheduling. */
1928 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1929 static struct reg_use_data
*
1930 create_insn_reg_use (int regno
, rtx_insn
*insn
)
1932 struct reg_use_data
*use
;
1934 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1937 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1938 INSN_REG_USE_LIST (insn
) = use
;
1942 /* Allocate reg_set_data structure for REGNO and INSN. */
1944 create_insn_reg_set (int regno
, rtx insn
)
1946 struct reg_set_data
*set
;
1948 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1951 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1952 INSN_REG_SET_LIST (insn
) = set
;
1955 /* Set up insn register uses for INSN and dependency context DEPS. */
1957 setup_insn_reg_uses (class deps_desc
*deps
, rtx_insn
*insn
)
1960 reg_set_iterator rsi
;
1961 struct reg_use_data
*use
, *use2
, *next
;
1962 struct deps_reg
*reg_last
;
1964 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1966 if (i
< FIRST_PSEUDO_REGISTER
1967 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1970 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1971 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1972 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1973 /* Ignore use which is not dying. */
1976 use
= create_insn_reg_use (i
, insn
);
1977 use
->next_regno_use
= use
;
1978 reg_last
= &deps
->reg_last
[i
];
1980 /* Create the cycle list of uses. */
1981 for (rtx_insn_list
*list
= reg_last
->uses
; list
; list
= list
->next ())
1983 use2
= create_insn_reg_use (i
, list
->insn ());
1984 next
= use
->next_regno_use
;
1985 use
->next_regno_use
= use2
;
1986 use2
->next_regno_use
= next
;
1991 /* Register pressure info for the currently processed insn. */
1992 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1994 /* Return TRUE if INSN has the use structure for REGNO. */
1996 insn_use_p (rtx insn
, int regno
)
1998 struct reg_use_data
*use
;
2000 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2001 if (use
->regno
== regno
)
2006 /* Update the register pressure info after birth of pseudo register REGNO
2007 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2008 the register is in clobber or unused after the insn. */
2010 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2015 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2016 cl
= sched_regno_pressure_class
[regno
];
2019 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2022 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2023 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2027 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2028 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2032 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2033 reg_pressure_info
[cl
].set_increase
= new_incr
;
2034 if (! insn_use_p (insn
, regno
))
2035 reg_pressure_info
[cl
].change
+= incr
;
2036 create_insn_reg_set (regno
, insn
);
2038 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2042 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2043 hard registers involved in the birth. */
2045 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2046 bool clobber_p
, bool unused_p
)
2049 int new_incr
, last
= regno
+ nregs
;
2051 while (regno
< last
)
2053 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2054 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2056 cl
= sched_regno_pressure_class
[regno
];
2061 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2062 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2066 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2067 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2071 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2072 reg_pressure_info
[cl
].set_increase
= new_incr
;
2073 if (! insn_use_p (insn
, regno
))
2074 reg_pressure_info
[cl
].change
+= 1;
2075 create_insn_reg_set (regno
, insn
);
2077 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2084 /* Update the register pressure info after birth of pseudo or hard
2085 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2086 correspondingly that the register is in clobber or unused after the
2089 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2093 if (GET_CODE (reg
) == SUBREG
)
2094 reg
= SUBREG_REG (reg
);
2099 regno
= REGNO (reg
);
2100 if (regno
< FIRST_PSEUDO_REGISTER
)
2101 mark_insn_hard_regno_birth (insn
, regno
, REG_NREGS (reg
),
2102 clobber_p
, unused_p
);
2104 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2107 /* Update the register pressure info after death of pseudo register
2110 mark_pseudo_death (int regno
)
2115 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2116 cl
= sched_regno_pressure_class
[regno
];
2119 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2120 reg_pressure_info
[cl
].change
-= incr
;
2124 /* Like mark_pseudo_death except that NREGS saying how many hard
2125 registers involved in the death. */
2127 mark_hard_regno_death (int regno
, int nregs
)
2130 int last
= regno
+ nregs
;
2132 while (regno
< last
)
2134 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2135 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2137 cl
= sched_regno_pressure_class
[regno
];
2139 reg_pressure_info
[cl
].change
-= 1;
2145 /* Update the register pressure info after death of pseudo or hard
2148 mark_reg_death (rtx reg
)
2152 if (GET_CODE (reg
) == SUBREG
)
2153 reg
= SUBREG_REG (reg
);
2158 regno
= REGNO (reg
);
2159 if (regno
< FIRST_PSEUDO_REGISTER
)
2160 mark_hard_regno_death (regno
, REG_NREGS (reg
));
2162 mark_pseudo_death (regno
);
2165 /* Process SETTER of REG. DATA is an insn containing the setter. */
2167 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2169 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2172 ((rtx
) data
, reg
, false,
2173 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2176 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2178 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2180 if (GET_CODE (setter
) == CLOBBER
)
2181 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2184 /* Set up reg pressure info related to INSN. */
2186 init_insn_reg_pressure_info (rtx_insn
*insn
)
2190 static struct reg_pressure_data
*pressure_info
;
2193 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2195 if (! INSN_P (insn
))
2198 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2200 cl
= ira_pressure_classes
[i
];
2201 reg_pressure_info
[cl
].clobber_increase
= 0;
2202 reg_pressure_info
[cl
].set_increase
= 0;
2203 reg_pressure_info
[cl
].unused_set_increase
= 0;
2204 reg_pressure_info
[cl
].change
= 0;
2207 note_stores (insn
, mark_insn_reg_clobber
, insn
);
2209 note_stores (insn
, mark_insn_reg_store
, insn
);
2212 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2213 if (REG_NOTE_KIND (link
) == REG_INC
)
2214 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2216 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2217 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2218 mark_reg_death (XEXP (link
, 0));
2220 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2222 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2223 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2224 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2226 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2228 cl
= ira_pressure_classes
[i
];
2229 pressure_info
[i
].clobber_increase
2230 = reg_pressure_info
[cl
].clobber_increase
;
2231 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2232 pressure_info
[i
].unused_set_increase
2233 = reg_pressure_info
[cl
].unused_set_increase
;
2234 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2241 /* Internal variable for sched_analyze_[12] () functions.
2242 If it is nonzero, this means that sched_analyze_[12] looks
2243 at the most toplevel SET. */
2244 static bool can_start_lhs_rhs_p
;
2246 /* Extend reg info for the deps context DEPS given that
2247 we have just generated a register numbered REGNO. */
2249 extend_deps_reg_info (class deps_desc
*deps
, int regno
)
2251 int max_regno
= regno
+ 1;
2253 gcc_assert (!reload_completed
);
2255 /* In a readonly context, it would not hurt to extend info,
2256 but it should not be needed. */
2257 if (reload_completed
&& deps
->readonly
)
2259 deps
->max_reg
= max_regno
;
2263 if (max_regno
> deps
->max_reg
)
2265 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2267 memset (&deps
->reg_last
[deps
->max_reg
],
2268 0, (max_regno
- deps
->max_reg
)
2269 * sizeof (struct deps_reg
));
2270 deps
->max_reg
= max_regno
;
2274 /* Extends REG_INFO_P if needed. */
2276 maybe_extend_reg_info_p (void)
2278 /* Extend REG_INFO_P, if needed. */
2279 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2281 size_t new_reg_info_p_size
= max_regno
+ 128;
2283 gcc_assert (!reload_completed
&& sel_sched_p ());
2285 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2286 new_reg_info_p_size
,
2288 sizeof (*reg_info_p
));
2289 reg_info_p_size
= new_reg_info_p_size
;
2293 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2294 The type of the reference is specified by REF and can be SET,
2295 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2298 sched_analyze_reg (class deps_desc
*deps
, int regno
, machine_mode mode
,
2299 enum rtx_code ref
, rtx_insn
*insn
)
2301 /* We could emit new pseudos in renaming. Extend the reg structures. */
2302 if (!reload_completed
&& sel_sched_p ()
2303 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2304 extend_deps_reg_info (deps
, regno
);
2306 maybe_extend_reg_info_p ();
2308 /* A hard reg in a wide mode may really be multiple registers.
2309 If so, mark all of them just like the first. */
2310 if (regno
< FIRST_PSEUDO_REGISTER
)
2312 int i
= hard_regno_nregs (regno
, mode
);
2316 note_reg_set (regno
+ i
);
2318 else if (ref
== USE
)
2321 note_reg_use (regno
+ i
);
2323 else if (ref
== CLOBBER_HIGH
)
2325 gcc_assert (i
== 1);
2326 /* We don't know the current state of the register, so have to treat
2327 the clobber high as a full clobber. */
2328 note_reg_clobber (regno
);
2333 note_reg_clobber (regno
+ i
);
2337 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2338 it does not reload. Ignore these as they have served their
2340 else if (regno
>= deps
->max_reg
)
2342 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2343 gcc_assert (code
== USE
|| code
== CLOBBER
);
2349 note_reg_set (regno
);
2350 else if (ref
== USE
)
2351 note_reg_use (regno
);
2353 /* For CLOBBER_HIGH, we don't know the current state of the register,
2354 so have to treat it as a full clobber. */
2355 note_reg_clobber (regno
);
2357 /* Pseudos that are REG_EQUIV to something may be replaced
2358 by that during reloading. We need only add dependencies for
2359 the address in the REG_EQUIV note. */
2360 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2362 rtx t
= get_reg_known_value (regno
);
2364 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2367 /* Don't let it cross a call after scheduling if it doesn't
2368 already cross one. */
2369 if (REG_N_CALLS_CROSSED (regno
) == 0)
2371 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2372 deps
->sched_before_next_call
2373 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2375 add_dependence_list (insn
, deps
->last_function_call
, 1,
2376 REG_DEP_ANTI
, false);
2381 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2382 rtx, X, creating all dependencies generated by the write to the
2383 destination of X, and reads of everything mentioned. */
2386 sched_analyze_1 (class deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2388 rtx dest
= XEXP (x
, 0);
2389 enum rtx_code code
= GET_CODE (x
);
2390 bool cslr_p
= can_start_lhs_rhs_p
;
2392 can_start_lhs_rhs_p
= false;
2398 if (cslr_p
&& sched_deps_info
->start_lhs
)
2399 sched_deps_info
->start_lhs (dest
);
2401 if (GET_CODE (dest
) == PARALLEL
)
2405 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2406 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2407 sched_analyze_1 (deps
,
2408 gen_rtx_CLOBBER (VOIDmode
,
2409 XEXP (XVECEXP (dest
, 0, i
), 0)),
2412 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2413 sched_deps_info
->finish_lhs ();
2417 can_start_lhs_rhs_p
= cslr_p
;
2419 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2421 can_start_lhs_rhs_p
= false;
2427 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2428 || GET_CODE (dest
) == ZERO_EXTRACT
)
2430 if (GET_CODE (dest
) == STRICT_LOW_PART
2431 || GET_CODE (dest
) == ZERO_EXTRACT
2432 || read_modify_subreg_p (dest
))
2434 /* These both read and modify the result. We must handle
2435 them as writes to get proper dependencies for following
2436 instructions. We must handle them as reads to get proper
2437 dependencies from this to previous instructions.
2438 Thus we need to call sched_analyze_2. */
2440 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2442 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2444 /* The second and third arguments are values read by this insn. */
2445 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2446 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2448 dest
= XEXP (dest
, 0);
2453 int regno
= REGNO (dest
);
2454 machine_mode mode
= GET_MODE (dest
);
2456 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2459 /* Treat all writes to a stack register as modifying the TOS. */
2460 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2462 /* Avoid analyzing the same register twice. */
2463 if (regno
!= FIRST_STACK_REG
)
2464 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2466 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2471 else if (MEM_P (dest
))
2473 /* Writing memory. */
2476 if (sched_deps_info
->use_cselib
)
2478 machine_mode address_mode
= get_address_mode (dest
);
2480 t
= shallow_copy_rtx (dest
);
2481 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2482 GET_MODE (t
), insn
);
2484 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2489 /* Pending lists can't get larger with a readonly context. */
2491 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2492 >= MAX_PENDING_LIST_LENGTH
))
2494 /* Flush all pending reads and writes to prevent the pending lists
2495 from getting any larger. Insn scheduling runs too slowly when
2496 these lists get long. When compiling GCC with itself,
2497 this flush occurs 8 times for sparc, and 10 times for m88k using
2498 the default value of 32. */
2499 flush_pending_lists (deps
, insn
, false, true);
2503 rtx_insn_list
*pending
;
2504 rtx_expr_list
*pending_mem
;
2506 pending
= deps
->pending_read_insns
;
2507 pending_mem
= deps
->pending_read_mems
;
2510 if (anti_dependence (pending_mem
->element (), t
)
2511 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2512 note_mem_dep (t
, pending_mem
->element (), pending
->insn (),
2515 pending
= pending
->next ();
2516 pending_mem
= pending_mem
->next ();
2519 pending
= deps
->pending_write_insns
;
2520 pending_mem
= deps
->pending_write_mems
;
2523 if (output_dependence (pending_mem
->element (), t
)
2524 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2525 note_mem_dep (t
, pending_mem
->element (),
2529 pending
= pending
->next ();
2530 pending_mem
= pending_mem
-> next ();
2533 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2534 REG_DEP_ANTI
, true);
2535 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2536 REG_DEP_CONTROL
, true);
2538 if (!deps
->readonly
)
2539 add_insn_mem_dependence (deps
, false, insn
, dest
);
2541 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2544 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2545 sched_deps_info
->finish_lhs ();
2547 /* Analyze reads. */
2548 if (GET_CODE (x
) == SET
)
2550 can_start_lhs_rhs_p
= cslr_p
;
2552 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2554 can_start_lhs_rhs_p
= false;
2558 /* Analyze the uses of memory and registers in rtx X in INSN. */
2560 sched_analyze_2 (class deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2566 bool cslr_p
= can_start_lhs_rhs_p
;
2568 can_start_lhs_rhs_p
= false;
2574 if (cslr_p
&& sched_deps_info
->start_rhs
)
2575 sched_deps_info
->start_rhs (x
);
2577 code
= GET_CODE (x
);
2585 /* Ignore constants. */
2586 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2587 sched_deps_info
->finish_rhs ();
2595 /* User of CC0 depends on immediately preceding insn. */
2596 SCHED_GROUP_P (insn
) = 1;
2597 /* Don't move CC0 setter to another block (it can set up the
2598 same flag for previous CC0 users which is safe). */
2599 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2601 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2602 sched_deps_info
->finish_rhs ();
2608 int regno
= REGNO (x
);
2609 machine_mode mode
= GET_MODE (x
);
2611 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2614 /* Treat all reads of a stack register as modifying the TOS. */
2615 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2617 /* Avoid analyzing the same register twice. */
2618 if (regno
!= FIRST_STACK_REG
)
2619 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2620 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2624 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2625 sched_deps_info
->finish_rhs ();
2632 /* Reading memory. */
2634 rtx_insn_list
*pending
;
2635 rtx_expr_list
*pending_mem
;
2638 if (sched_deps_info
->use_cselib
)
2640 machine_mode address_mode
= get_address_mode (t
);
2642 t
= shallow_copy_rtx (t
);
2643 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2644 GET_MODE (t
), insn
);
2646 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2650 if (!DEBUG_INSN_P (insn
))
2653 pending
= deps
->pending_read_insns
;
2654 pending_mem
= deps
->pending_read_mems
;
2657 if (read_dependence (pending_mem
->element (), t
)
2658 && ! sched_insns_conditions_mutex_p (insn
,
2660 note_mem_dep (t
, pending_mem
->element (),
2664 pending
= pending
->next ();
2665 pending_mem
= pending_mem
->next ();
2668 pending
= deps
->pending_write_insns
;
2669 pending_mem
= deps
->pending_write_mems
;
2672 if (true_dependence (pending_mem
->element (), VOIDmode
, t
)
2673 && ! sched_insns_conditions_mutex_p (insn
,
2675 note_mem_dep (t
, pending_mem
->element (),
2677 sched_deps_info
->generate_spec_deps
2678 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2680 pending
= pending
->next ();
2681 pending_mem
= pending_mem
->next ();
2684 for (u
= deps
->last_pending_memory_flush
; u
; u
= u
->next ())
2685 add_dependence (insn
, u
->insn (), REG_DEP_ANTI
);
2687 for (u
= deps
->pending_jump_insns
; u
; u
= u
->next ())
2688 if (deps_may_trap_p (x
))
2690 if ((sched_deps_info
->generate_spec_deps
)
2691 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2693 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2696 note_dep (u
->insn (), ds
);
2699 add_dependence (insn
, u
->insn (), REG_DEP_CONTROL
);
2703 /* Always add these dependencies to pending_reads, since
2704 this insn may be followed by a write. */
2705 if (!deps
->readonly
)
2707 if ((deps
->pending_read_list_length
2708 + deps
->pending_write_list_length
)
2709 >= MAX_PENDING_LIST_LENGTH
2710 && !DEBUG_INSN_P (insn
))
2711 flush_pending_lists (deps
, insn
, true, true);
2712 add_insn_mem_dependence (deps
, true, insn
, x
);
2715 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2717 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2718 sched_deps_info
->finish_rhs ();
2723 /* Force pending stores to memory in case a trap handler needs them.
2724 Also force pending loads from memory; loads and stores can segfault
2725 and the signal handler won't be triggered if the trap insn was moved
2726 above load or store insn. */
2728 flush_pending_lists (deps
, insn
, true, true);
2732 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2733 reg_pending_barrier
= TRUE_BARRIER
;
2734 /* Prefetch insn contains addresses only. So if the prefetch
2735 address has no registers, there will be no dependencies on
2736 the prefetch insn. This is wrong with result code
2737 correctness point of view as such prefetch can be moved below
2738 a jump insn which usually generates MOVE_BARRIER preventing
2739 to move insns containing registers or memories through the
2740 barrier. It is also wrong with generated code performance
2741 point of view as prefetch withouth dependecies will have a
2742 tendency to be issued later instead of earlier. It is hard
2743 to generate accurate dependencies for prefetch insns as
2744 prefetch has only the start address but it is better to have
2745 something than nothing. */
2746 if (!deps
->readonly
)
2748 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2749 if (sched_deps_info
->use_cselib
)
2750 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2751 add_insn_mem_dependence (deps
, true, insn
, x
);
2755 case UNSPEC_VOLATILE
:
2756 flush_pending_lists (deps
, insn
, true, true);
2762 /* Traditional and volatile asm instructions must be considered to use
2763 and clobber all hard registers, all pseudo-registers and all of
2764 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2766 Consider for instance a volatile asm that changes the fpu rounding
2767 mode. An insn should not be moved across this even if it only uses
2768 pseudo-regs because it might give an incorrectly rounded result. */
2769 if ((code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2770 && !DEBUG_INSN_P (insn
))
2771 reg_pending_barrier
= TRUE_BARRIER
;
2773 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2774 We cannot just fall through here since then we would be confused
2775 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2776 traditional asms unlike their normal usage. */
2778 if (code
== ASM_OPERANDS
)
2780 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2781 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2783 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2784 sched_deps_info
->finish_rhs ();
2795 /* These both read and modify the result. We must handle them as writes
2796 to get proper dependencies for following instructions. We must handle
2797 them as reads to get proper dependencies from this to previous
2798 instructions. Thus we need to pass them to both sched_analyze_1
2799 and sched_analyze_2. We must call sched_analyze_2 first in order
2800 to get the proper antecedent for the read. */
2801 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2802 sched_analyze_1 (deps
, x
, insn
);
2804 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2805 sched_deps_info
->finish_rhs ();
2811 /* op0 = op0 + op1 */
2812 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2813 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2814 sched_analyze_1 (deps
, x
, insn
);
2816 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2817 sched_deps_info
->finish_rhs ();
2825 /* Other cases: walk the insn. */
2826 fmt
= GET_RTX_FORMAT (code
);
2827 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2830 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2831 else if (fmt
[i
] == 'E')
2832 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2833 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2836 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2837 sched_deps_info
->finish_rhs ();
2840 /* Try to group two fusible insns together to prevent scheduler
2841 from scheduling them apart. */
2844 sched_macro_fuse_insns (rtx_insn
*insn
)
2847 /* No target hook would return true for debug insn as any of the
2848 hook operand, and with very large sequences of only debug insns
2849 where on each we call sched_macro_fuse_insns it has quadratic
2850 compile time complexity. */
2851 if (DEBUG_INSN_P (insn
))
2853 prev
= prev_nonnote_nondebug_insn (insn
);
2857 if (any_condjump_p (insn
))
2859 unsigned int condreg1
, condreg2
;
2861 if (targetm
.fixed_condition_code_regs (&condreg1
, &condreg2
))
2863 cc_reg_1
= gen_rtx_REG (CCmode
, condreg1
);
2864 if (reg_referenced_p (cc_reg_1
, PATTERN (insn
))
2865 && modified_in_p (cc_reg_1
, prev
))
2867 if (targetm
.sched
.macro_fusion_pair_p (prev
, insn
))
2868 SCHED_GROUP_P (insn
) = 1;
2874 if (single_set (insn
) && single_set (prev
))
2876 if (targetm
.sched
.macro_fusion_pair_p (prev
, insn
))
2877 SCHED_GROUP_P (insn
) = 1;
2881 /* Get the implicit reg pending clobbers for INSN and save them in TEMP. */
2883 get_implicit_reg_pending_clobbers (HARD_REG_SET
*temp
, rtx_insn
*insn
)
2885 extract_insn (insn
);
2886 preprocess_constraints (insn
);
2887 alternative_mask preferred
= get_preferred_alternatives (insn
);
2888 ira_implicitly_set_insn_hard_regs (temp
, preferred
);
2889 *temp
&= ~ira_no_alloc_regs
;
2892 /* Analyze an INSN with pattern X to find all dependencies. */
2894 sched_analyze_insn (class deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2896 RTX_CODE code
= GET_CODE (x
);
2899 reg_set_iterator rsi
;
2901 if (! reload_completed
)
2904 get_implicit_reg_pending_clobbers (&temp
, insn
);
2905 implicit_reg_pending_clobbers
|= temp
;
2908 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2911 /* Group compare and branch insns for macro-fusion. */
2913 && targetm
.sched
.macro_fusion_p
2914 && targetm
.sched
.macro_fusion_p ())
2915 sched_macro_fuse_insns (insn
);
2918 /* Avoid moving trapping instructions across function calls that might
2919 not always return. */
2920 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2921 1, REG_DEP_ANTI
, true);
2923 /* We must avoid creating a situation in which two successors of the
2924 current block have different unwind info after scheduling. If at any
2925 point the two paths re-join this leads to incorrect unwind info. */
2926 /* ??? There are certain situations involving a forced frame pointer in
2927 which, with extra effort, we could fix up the unwind info at a later
2928 CFG join. However, it seems better to notice these cases earlier
2929 during prologue generation and avoid marking the frame pointer setup
2930 as frame-related at all. */
2931 if (RTX_FRAME_RELATED_P (insn
))
2933 /* Make sure prologue insn is scheduled before next jump. */
2934 deps
->sched_before_next_jump
2935 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2937 /* Make sure epilogue insn is scheduled after preceding jumps. */
2938 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2939 REG_DEP_ANTI
, true);
2940 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2944 if (code
== COND_EXEC
)
2946 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2948 /* ??? Should be recording conditions so we reduce the number of
2949 false dependencies. */
2950 x
= COND_EXEC_CODE (x
);
2951 code
= GET_CODE (x
);
2953 if (code
== SET
|| code
== CLOBBER
)
2955 sched_analyze_1 (deps
, x
, insn
);
2957 /* Bare clobber insns are used for letting life analysis, reg-stack
2958 and others know that a value is dead. Depend on the last call
2959 instruction so that reg-stack won't get confused. */
2960 if (code
== CLOBBER
)
2961 add_dependence_list (insn
, deps
->last_function_call
, 1,
2962 REG_DEP_OUTPUT
, true);
2964 else if (code
== PARALLEL
)
2966 for (i
= XVECLEN (x
, 0); i
--;)
2968 rtx sub
= XVECEXP (x
, 0, i
);
2969 code
= GET_CODE (sub
);
2971 if (code
== COND_EXEC
)
2973 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2974 sub
= COND_EXEC_CODE (sub
);
2975 code
= GET_CODE (sub
);
2977 else if (code
== SET
|| code
== CLOBBER
|| code
== CLOBBER_HIGH
)
2978 sched_analyze_1 (deps
, sub
, insn
);
2980 sched_analyze_2 (deps
, sub
, insn
);
2984 sched_analyze_2 (deps
, x
, insn
);
2986 /* Mark registers CLOBBERED or used by called function. */
2989 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2991 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2992 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2993 else if (GET_CODE (XEXP (link
, 0)) == CLOBBER_HIGH
)
2994 /* We could support CLOBBER_HIGH and treat it in the same way as
2995 HARD_REGNO_CALL_PART_CLOBBERED, but no port needs that yet. */
2997 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2998 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
3000 /* Don't schedule anything after a tail call, tail call needs
3001 to use at least all call-saved registers. */
3002 if (SIBLING_CALL_P (insn
))
3003 reg_pending_barrier
= TRUE_BARRIER
;
3004 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3005 reg_pending_barrier
= MOVE_BARRIER
;
3010 rtx_insn
*next
= next_nonnote_nondebug_insn (insn
);
3011 /* ??? For tablejumps, the barrier may appear not immediately after
3012 the jump, but after a label and a jump_table_data insn. */
3013 if (next
&& LABEL_P (next
) && NEXT_INSN (next
)
3014 && JUMP_TABLE_DATA_P (NEXT_INSN (next
)))
3015 next
= NEXT_INSN (NEXT_INSN (next
));
3016 if (next
&& BARRIER_P (next
))
3017 reg_pending_barrier
= MOVE_BARRIER
;
3020 rtx_insn_list
*pending
;
3021 rtx_expr_list
*pending_mem
;
3023 if (sched_deps_info
->compute_jump_reg_dependencies
)
3025 (*sched_deps_info
->compute_jump_reg_dependencies
)
3026 (insn
, reg_pending_control_uses
);
3028 /* Make latency of jump equal to 0 by using anti-dependence. */
3029 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3031 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3032 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
3034 add_dependence_list (insn
, reg_last
->implicit_sets
,
3035 0, REG_DEP_ANTI
, false);
3036 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3037 REG_DEP_ANTI
, false);
3041 /* All memory writes and volatile reads must happen before the
3042 jump. Non-volatile reads must happen before the jump iff
3043 the result is needed by the above register used mask. */
3045 pending
= deps
->pending_write_insns
;
3046 pending_mem
= deps
->pending_write_mems
;
3049 if (! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3050 add_dependence (insn
, pending
->insn (),
3052 pending
= pending
->next ();
3053 pending_mem
= pending_mem
->next ();
3056 pending
= deps
->pending_read_insns
;
3057 pending_mem
= deps
->pending_read_mems
;
3060 if (MEM_VOLATILE_P (pending_mem
->element ())
3061 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3062 add_dependence (insn
, pending
->insn (),
3064 pending
= pending
->next ();
3065 pending_mem
= pending_mem
->next ();
3068 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
3069 REG_DEP_ANTI
, true);
3070 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
3071 REG_DEP_ANTI
, true);
3075 /* If this instruction can throw an exception, then moving it changes
3076 where block boundaries fall. This is mighty confusing elsewhere.
3077 Therefore, prevent such an instruction from being moved. Same for
3078 non-jump instructions that define block boundaries.
3079 ??? Unclear whether this is still necessary in EBB mode. If not,
3080 add_branch_dependences should be adjusted for RGN mode instead. */
3081 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
3082 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
3083 reg_pending_barrier
= MOVE_BARRIER
;
3085 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
3087 setup_insn_reg_uses (deps
, insn
);
3088 init_insn_reg_pressure_info (insn
);
3091 /* Add register dependencies for insn. */
3092 if (DEBUG_INSN_P (insn
))
3094 rtx_insn
*prev
= deps
->last_debug_insn
;
3097 if (!deps
->readonly
)
3098 deps
->last_debug_insn
= insn
;
3101 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3103 add_dependence_list (insn
, deps
->last_function_call
, 1,
3104 REG_DEP_ANTI
, false);
3106 if (!sel_sched_p ())
3107 for (u
= deps
->last_pending_memory_flush
; u
; u
= u
->next ())
3108 add_dependence (insn
, u
->insn (), REG_DEP_ANTI
);
3110 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3112 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3113 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3114 /* There's no point in making REG_DEP_CONTROL dependencies for
3116 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3119 if (!deps
->readonly
)
3120 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3122 CLEAR_REG_SET (reg_pending_uses
);
3124 /* Quite often, a debug insn will refer to stuff in the
3125 previous instruction, but the reason we want this
3126 dependency here is to make sure the scheduler doesn't
3127 gratuitously move a debug insn ahead. This could dirty
3128 DF flags and cause additional analysis that wouldn't have
3129 occurred in compilation without debug insns, and such
3130 additional analysis can modify the generated code. */
3131 prev
= PREV_INSN (insn
);
3133 if (prev
&& NONDEBUG_INSN_P (prev
))
3134 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3138 regset_head set_or_clobbered
;
3140 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3142 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3143 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3144 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3146 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3149 if (!deps
->readonly
)
3151 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3152 reg_last
->uses_length
++;
3156 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3157 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3159 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3160 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3161 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3162 REG_DEP_ANTI
, false);
3163 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3166 if (!deps
->readonly
)
3168 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3169 reg_last
->uses_length
++;
3173 if (targetm
.sched
.exposed_pipeline
)
3175 INIT_REG_SET (&set_or_clobbered
);
3176 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3178 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3180 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3182 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3184 rtx other
= XEXP (list
, 0);
3185 if (INSN_CACHED_COND (other
) != const_true_rtx
3186 && refers_to_regno_p (i
, INSN_CACHED_COND (other
)))
3187 INSN_CACHED_COND (other
) = const_true_rtx
;
3192 /* If the current insn is conditional, we can't free any
3194 if (sched_has_condition_p (insn
))
3196 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3198 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3199 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3201 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3202 REG_DEP_ANTI
, false);
3203 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3205 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3206 REG_DEP_CONTROL
, false);
3208 if (!deps
->readonly
)
3211 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3212 reg_last
->clobbers_length
++;
3215 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3217 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3218 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3220 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3221 REG_DEP_ANTI
, false);
3222 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3224 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3226 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3227 REG_DEP_CONTROL
, false);
3229 if (!deps
->readonly
)
3230 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3235 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3237 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3238 if (reg_last
->uses_length
>= MAX_PENDING_LIST_LENGTH
3239 || reg_last
->clobbers_length
>= MAX_PENDING_LIST_LENGTH
)
3241 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3242 REG_DEP_OUTPUT
, false);
3243 add_dependence_list_and_free (deps
, insn
,
3244 ®_last
->implicit_sets
, 0,
3245 REG_DEP_ANTI
, false);
3246 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3247 REG_DEP_ANTI
, false);
3248 add_dependence_list_and_free (deps
, insn
,
3249 ®_last
->control_uses
, 0,
3250 REG_DEP_ANTI
, false);
3251 add_dependence_list_and_free (deps
, insn
,
3252 ®_last
->clobbers
, 0,
3253 REG_DEP_OUTPUT
, false);
3255 if (!deps
->readonly
)
3257 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3258 reg_last
->clobbers_length
= 0;
3259 reg_last
->uses_length
= 0;
3264 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3266 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3267 REG_DEP_ANTI
, false);
3268 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3270 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3271 REG_DEP_CONTROL
, false);
3274 if (!deps
->readonly
)
3276 reg_last
->clobbers_length
++;
3278 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3281 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3283 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3285 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3286 REG_DEP_OUTPUT
, false);
3287 add_dependence_list_and_free (deps
, insn
,
3288 ®_last
->implicit_sets
,
3289 0, REG_DEP_ANTI
, false);
3290 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3291 REG_DEP_OUTPUT
, false);
3292 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3293 REG_DEP_ANTI
, false);
3294 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3295 REG_DEP_CONTROL
, false);
3297 if (!deps
->readonly
)
3299 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3300 reg_last
->uses_length
= 0;
3301 reg_last
->clobbers_length
= 0;
3305 if (!deps
->readonly
)
3307 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3309 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3310 reg_last
->control_uses
3311 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3316 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3317 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3319 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3320 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3321 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3322 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3323 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3326 if (!deps
->readonly
)
3327 reg_last
->implicit_sets
3328 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3331 if (!deps
->readonly
)
3333 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3334 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3335 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3336 IOR_REG_SET_HRS (&deps
->reg_last_in_use
,
3337 implicit_reg_pending_uses
3338 | implicit_reg_pending_clobbers
);
3340 /* Set up the pending barrier found. */
3341 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3344 CLEAR_REG_SET (reg_pending_uses
);
3345 CLEAR_REG_SET (reg_pending_clobbers
);
3346 CLEAR_REG_SET (reg_pending_sets
);
3347 CLEAR_REG_SET (reg_pending_control_uses
);
3348 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3349 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3351 /* Add dependencies if a scheduling barrier was found. */
3352 if (reg_pending_barrier
)
3354 /* In the case of barrier the most added dependencies are not
3355 real, so we use anti-dependence here. */
3356 if (sched_has_condition_p (insn
))
3358 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3360 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3361 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3363 add_dependence_list (insn
, reg_last
->sets
, 0,
3364 reg_pending_barrier
== TRUE_BARRIER
3365 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3366 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3367 REG_DEP_ANTI
, true);
3368 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3369 reg_pending_barrier
== TRUE_BARRIER
3370 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3375 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3377 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3378 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3379 REG_DEP_ANTI
, true);
3380 add_dependence_list_and_free (deps
, insn
,
3381 ®_last
->control_uses
, 0,
3382 REG_DEP_CONTROL
, true);
3383 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3384 reg_pending_barrier
== TRUE_BARRIER
3385 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3387 add_dependence_list_and_free (deps
, insn
,
3388 ®_last
->implicit_sets
, 0,
3389 REG_DEP_ANTI
, true);
3390 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3391 reg_pending_barrier
== TRUE_BARRIER
3392 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3395 if (!deps
->readonly
)
3397 reg_last
->uses_length
= 0;
3398 reg_last
->clobbers_length
= 0;
3403 if (!deps
->readonly
)
3404 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3406 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3407 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3408 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3411 /* Don't flush pending lists on speculative checks for
3412 selective scheduling. */
3413 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn
))
3414 flush_pending_lists (deps
, insn
, true, true);
3416 reg_pending_barrier
= NOT_A_BARRIER
;
3419 /* If a post-call group is still open, see if it should remain so.
3420 This insn must be a simple move of a hard reg to a pseudo or
3423 We must avoid moving these insns for correctness on targets
3424 with small register classes, and for special registers like
3425 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3426 hard regs for all targets. */
3428 if (deps
->in_post_call_group_p
)
3430 rtx tmp
, set
= single_set (insn
);
3431 int src_regno
, dest_regno
;
3435 if (DEBUG_INSN_P (insn
))
3436 /* We don't want to mark debug insns as part of the same
3437 sched group. We know they really aren't, but if we use
3438 debug insns to tell that a call group is over, we'll
3439 get different code if debug insns are not there and
3440 instructions that follow seem like they should be part
3443 Also, if we did, chain_to_prev_insn would move the
3444 deps of the debug insn to the call insn, modifying
3445 non-debug post-dependency counts of the debug insn
3446 dependencies and otherwise messing with the scheduling
3449 Instead, let such debug insns be scheduled freely, but
3450 keep the call group open in case there are insns that
3451 should be part of it afterwards. Since we grant debug
3452 insns higher priority than even sched group insns, it
3453 will all turn out all right. */
3454 goto debug_dont_end_call_group
;
3456 goto end_call_group
;
3459 tmp
= SET_DEST (set
);
3460 if (GET_CODE (tmp
) == SUBREG
)
3461 tmp
= SUBREG_REG (tmp
);
3463 dest_regno
= REGNO (tmp
);
3465 goto end_call_group
;
3467 tmp
= SET_SRC (set
);
3468 if (GET_CODE (tmp
) == SUBREG
)
3469 tmp
= SUBREG_REG (tmp
);
3470 if ((GET_CODE (tmp
) == PLUS
3471 || GET_CODE (tmp
) == MINUS
)
3472 && REG_P (XEXP (tmp
, 0))
3473 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3474 && dest_regno
== STACK_POINTER_REGNUM
)
3475 src_regno
= STACK_POINTER_REGNUM
;
3476 else if (REG_P (tmp
))
3477 src_regno
= REGNO (tmp
);
3479 goto end_call_group
;
3481 if (src_regno
< FIRST_PSEUDO_REGISTER
3482 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3485 && deps
->in_post_call_group_p
== post_call_initial
)
3486 deps
->in_post_call_group_p
= post_call
;
3488 if (!sel_sched_p () || sched_emulate_haifa_p
)
3490 SCHED_GROUP_P (insn
) = 1;
3491 CANT_MOVE (insn
) = 1;
3497 if (!deps
->readonly
)
3498 deps
->in_post_call_group_p
= not_post_call
;
3502 debug_dont_end_call_group
:
3503 if ((current_sched_info
->flags
& DO_SPECULATION
)
3504 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3505 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3509 sel_mark_hard_insn (insn
);
3512 sd_iterator_def sd_it
;
3515 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3516 sd_iterator_cond (&sd_it
, &dep
);)
3517 change_spec_dep_to_hard (sd_it
);
3521 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3522 honor their original ordering. */
3523 if (find_reg_note (insn
, REG_ARGS_SIZE
, NULL
))
3525 if (deps
->last_args_size
)
3526 add_dependence (insn
, deps
->last_args_size
, REG_DEP_OUTPUT
);
3527 if (!deps
->readonly
)
3528 deps
->last_args_size
= insn
;
3531 /* We must not mix prologue and epilogue insns. See PR78029. */
3532 if (prologue_contains (insn
))
3534 add_dependence_list (insn
, deps
->last_epilogue
, true, REG_DEP_ANTI
, true);
3535 if (!deps
->readonly
)
3537 if (deps
->last_logue_was_epilogue
)
3538 free_INSN_LIST_list (&deps
->last_prologue
);
3539 deps
->last_prologue
= alloc_INSN_LIST (insn
, deps
->last_prologue
);
3540 deps
->last_logue_was_epilogue
= false;
3544 if (epilogue_contains (insn
))
3546 add_dependence_list (insn
, deps
->last_prologue
, true, REG_DEP_ANTI
, true);
3547 if (!deps
->readonly
)
3549 if (!deps
->last_logue_was_epilogue
)
3550 free_INSN_LIST_list (&deps
->last_epilogue
);
3551 deps
->last_epilogue
= alloc_INSN_LIST (insn
, deps
->last_epilogue
);
3552 deps
->last_logue_was_epilogue
= true;
3557 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3558 longjmp, loop forever, ...). */
3559 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3560 test for ECF_NORETURN? */
3562 call_may_noreturn_p (rtx_insn
*insn
)
3566 /* const or pure calls that aren't looping will always return. */
3567 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3568 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3571 call
= get_call_rtx_from (insn
);
3572 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3574 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3575 if (SYMBOL_REF_DECL (symbol
)
3576 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3578 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3580 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3583 case BUILT_IN_BCOPY
:
3584 case BUILT_IN_BZERO
:
3585 case BUILT_IN_INDEX
:
3586 case BUILT_IN_MEMCHR
:
3587 case BUILT_IN_MEMCMP
:
3588 case BUILT_IN_MEMCPY
:
3589 case BUILT_IN_MEMMOVE
:
3590 case BUILT_IN_MEMPCPY
:
3591 case BUILT_IN_MEMSET
:
3592 case BUILT_IN_RINDEX
:
3593 case BUILT_IN_STPCPY
:
3594 case BUILT_IN_STPNCPY
:
3595 case BUILT_IN_STRCAT
:
3596 case BUILT_IN_STRCHR
:
3597 case BUILT_IN_STRCMP
:
3598 case BUILT_IN_STRCPY
:
3599 case BUILT_IN_STRCSPN
:
3600 case BUILT_IN_STRLEN
:
3601 case BUILT_IN_STRNCAT
:
3602 case BUILT_IN_STRNCMP
:
3603 case BUILT_IN_STRNCPY
:
3604 case BUILT_IN_STRPBRK
:
3605 case BUILT_IN_STRRCHR
:
3606 case BUILT_IN_STRSPN
:
3607 case BUILT_IN_STRSTR
:
3608 /* Assume certain string/memory builtins always return. */
3616 /* For all other calls assume that they might not always return. */
3620 /* Return true if INSN should be made dependent on the previous instruction
3621 group, and if all INSN's dependencies should be moved to the first
3622 instruction of that group. */
3625 chain_to_prev_insn_p (rtx_insn
*insn
)
3627 /* INSN forms a group with the previous instruction. */
3628 if (SCHED_GROUP_P (insn
))
3631 /* If the previous instruction clobbers a register R and this one sets
3632 part of R, the clobber was added specifically to help us track the
3633 liveness of R. There's no point scheduling the clobber and leaving
3634 INSN behind, especially if we move the clobber to another block. */
3635 rtx_insn
*prev
= prev_nonnote_nondebug_insn (insn
);
3638 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3639 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3641 rtx x
= XEXP (PATTERN (prev
), 0);
3642 if (set_of (x
, insn
))
3649 /* Analyze INSN with DEPS as a context. */
3651 deps_analyze_insn (class deps_desc
*deps
, rtx_insn
*insn
)
3653 if (sched_deps_info
->start_insn
)
3654 sched_deps_info
->start_insn (insn
);
3656 /* Record the condition for this insn. */
3657 if (NONDEBUG_INSN_P (insn
))
3660 sched_get_condition_with_rev (insn
, NULL
);
3661 t
= INSN_CACHED_COND (insn
);
3662 INSN_COND_DEPS (insn
) = NULL
;
3663 if (reload_completed
3664 && (current_sched_info
->flags
& DO_PREDICATION
)
3666 && REG_P (XEXP (t
, 0))
3667 && CONSTANT_P (XEXP (t
, 1)))
3671 rtx_insn_list
*cond_deps
= NULL
;
3674 nregs
= REG_NREGS (t
);
3677 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3678 cond_deps
= concat_INSN_LIST (reg_last
->sets
, cond_deps
);
3679 cond_deps
= concat_INSN_LIST (reg_last
->clobbers
, cond_deps
);
3680 cond_deps
= concat_INSN_LIST (reg_last
->implicit_sets
, cond_deps
);
3682 INSN_COND_DEPS (insn
) = cond_deps
;
3688 /* Make each JUMP_INSN (but not a speculative check)
3689 a scheduling barrier for memory references. */
3692 && sel_insn_is_speculation_check (insn
)))
3694 /* Keep the list a reasonable size. */
3695 if (deps
->pending_flush_length
++ >= MAX_PENDING_LIST_LENGTH
)
3696 flush_pending_lists (deps
, insn
, true, true);
3698 deps
->pending_jump_insns
3699 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3702 /* For each insn which shouldn't cross a jump, add a dependence. */
3703 add_dependence_list_and_free (deps
, insn
,
3704 &deps
->sched_before_next_jump
, 1,
3705 REG_DEP_ANTI
, true);
3707 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3709 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3711 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3713 else if (CALL_P (insn
))
3717 CANT_MOVE (insn
) = 1;
3719 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3721 /* This is setjmp. Assume that all registers, not just
3722 hard registers, may be clobbered by this call. */
3723 reg_pending_barrier
= MOVE_BARRIER
;
3727 function_abi callee_abi
= insn_callee_abi (insn
);
3728 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3729 /* A call may read and modify global register variables. */
3732 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3733 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3735 /* Other call-clobbered hard regs may be clobbered.
3736 Since we only have a choice between 'might be clobbered'
3737 and 'definitely not clobbered', we must include all
3738 partly call-clobbered registers here. */
3739 else if (callee_abi
.clobbers_at_least_part_of_reg_p (i
))
3740 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3741 /* We don't know what set of fixed registers might be used
3742 by the function, but it is certain that the stack pointer
3743 is among them, but be conservative. */
3744 else if (fixed_regs
[i
])
3745 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3746 /* The frame pointer is normally not used by the function
3747 itself, but by the debugger. */
3748 /* ??? MIPS o32 is an exception. It uses the frame pointer
3749 in the macro expansion of jal but does not represent this
3750 fact in the call_insn rtl. */
3751 else if (i
== FRAME_POINTER_REGNUM
3752 || (i
== HARD_FRAME_POINTER_REGNUM
3753 && (! reload_completed
|| frame_pointer_needed
)))
3754 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3757 /* For each insn which shouldn't cross a call, add a dependence
3758 between that insn and this call insn. */
3759 add_dependence_list_and_free (deps
, insn
,
3760 &deps
->sched_before_next_call
, 1,
3761 REG_DEP_ANTI
, true);
3763 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3765 /* If CALL would be in a sched group, then this will violate
3766 convention that sched group insns have dependencies only on the
3767 previous instruction.
3769 Of course one can say: "Hey! What about head of the sched group?"
3770 And I will answer: "Basic principles (one dep per insn) are always
3772 gcc_assert (!SCHED_GROUP_P (insn
));
3774 /* In the absence of interprocedural alias analysis, we must flush
3775 all pending reads and writes, and start new dependencies starting
3776 from here. But only flush writes for constant calls (which may
3777 be passed a pointer to something we haven't written yet). */
3778 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3780 if (!deps
->readonly
)
3782 /* Remember the last function call for limiting lifetimes. */
3783 free_INSN_LIST_list (&deps
->last_function_call
);
3784 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3786 if (call_may_noreturn_p (insn
))
3788 /* Remember the last function call that might not always return
3789 normally for limiting moves of trapping insns. */
3790 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3791 deps
->last_function_call_may_noreturn
3792 = alloc_INSN_LIST (insn
, NULL_RTX
);
3795 /* Before reload, begin a post-call group, so as to keep the
3796 lifetimes of hard registers correct. */
3797 if (! reload_completed
)
3798 deps
->in_post_call_group_p
= post_call
;
3802 if (sched_deps_info
->use_cselib
)
3803 cselib_process_insn (insn
);
3805 if (sched_deps_info
->finish_insn
)
3806 sched_deps_info
->finish_insn ();
3808 /* Fixup the dependencies in the sched group. */
3809 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3810 && chain_to_prev_insn_p (insn
)
3812 chain_to_prev_insn (insn
);
3815 /* Initialize DEPS for the new block beginning with HEAD. */
3817 deps_start_bb (class deps_desc
*deps
, rtx_insn
*head
)
3819 gcc_assert (!deps
->readonly
);
3821 /* Before reload, if the previous block ended in a call, show that
3822 we are inside a post-call group, so as to keep the lifetimes of
3823 hard registers correct. */
3824 if (! reload_completed
&& !LABEL_P (head
))
3826 rtx_insn
*insn
= prev_nonnote_nondebug_insn (head
);
3828 if (insn
&& CALL_P (insn
))
3829 deps
->in_post_call_group_p
= post_call_initial
;
3833 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3834 dependencies for each insn. */
3836 sched_analyze (class deps_desc
*deps
, rtx_insn
*head
, rtx_insn
*tail
)
3840 if (sched_deps_info
->use_cselib
)
3841 cselib_init (CSELIB_RECORD_MEMORY
);
3843 deps_start_bb (deps
, head
);
3845 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3850 /* And initialize deps_lists. */
3851 sd_init_insn (insn
);
3852 /* Clean up SCHED_GROUP_P which may be set by last
3854 if (SCHED_GROUP_P (insn
))
3855 SCHED_GROUP_P (insn
) = 0;
3858 deps_analyze_insn (deps
, insn
);
3862 if (sched_deps_info
->use_cselib
)
3870 /* Helper for sched_free_deps ().
3871 Delete INSN's (RESOLVED_P) backward dependencies. */
3873 delete_dep_nodes_in_back_deps (rtx_insn
*insn
, bool resolved_p
)
3875 sd_iterator_def sd_it
;
3877 sd_list_types_def types
;
3880 types
= SD_LIST_RES_BACK
;
3882 types
= SD_LIST_BACK
;
3884 for (sd_it
= sd_iterator_start (insn
, types
);
3885 sd_iterator_cond (&sd_it
, &dep
);)
3887 dep_link_t link
= *sd_it
.linkp
;
3888 dep_node_t node
= DEP_LINK_NODE (link
);
3889 deps_list_t back_list
;
3890 deps_list_t forw_list
;
3892 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3893 remove_from_deps_list (link
, back_list
);
3894 delete_dep_node (node
);
3898 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3901 sched_free_deps (rtx_insn
*head
, rtx_insn
*tail
, bool resolved_p
)
3904 rtx_insn
*next_tail
= NEXT_INSN (tail
);
3906 /* We make two passes since some insns may be scheduled before their
3907 dependencies are resolved. */
3908 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3909 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3911 /* Clear forward deps and leave the dep_nodes to the
3912 corresponding back_deps list. */
3914 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3916 clear_deps_list (INSN_FORW_DEPS (insn
));
3918 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3919 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3921 /* Clear resolved back deps together with its dep_nodes. */
3922 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3924 sd_finish_insn (insn
);
3928 /* Initialize variables for region data dependence analysis.
3929 When LAZY_REG_LAST is true, do not allocate reg_last array
3930 of class deps_desc immediately. */
3933 init_deps (class deps_desc
*deps
, bool lazy_reg_last
)
3935 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3937 deps
->max_reg
= max_reg
;
3939 deps
->reg_last
= NULL
;
3941 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3942 INIT_REG_SET (&deps
->reg_last_in_use
);
3944 deps
->pending_read_insns
= 0;
3945 deps
->pending_read_mems
= 0;
3946 deps
->pending_write_insns
= 0;
3947 deps
->pending_write_mems
= 0;
3948 deps
->pending_jump_insns
= 0;
3949 deps
->pending_read_list_length
= 0;
3950 deps
->pending_write_list_length
= 0;
3951 deps
->pending_flush_length
= 0;
3952 deps
->last_pending_memory_flush
= 0;
3953 deps
->last_function_call
= 0;
3954 deps
->last_function_call_may_noreturn
= 0;
3955 deps
->sched_before_next_call
= 0;
3956 deps
->sched_before_next_jump
= 0;
3957 deps
->in_post_call_group_p
= not_post_call
;
3958 deps
->last_debug_insn
= 0;
3959 deps
->last_args_size
= 0;
3960 deps
->last_prologue
= 0;
3961 deps
->last_epilogue
= 0;
3962 deps
->last_logue_was_epilogue
= false;
3963 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3967 /* Init only reg_last field of DEPS, which was not allocated before as
3968 we inited DEPS lazily. */
3970 init_deps_reg_last (class deps_desc
*deps
)
3972 gcc_assert (deps
&& deps
->max_reg
> 0);
3973 gcc_assert (deps
->reg_last
== NULL
);
3975 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3979 /* Free insn lists found in DEPS. */
3982 free_deps (class deps_desc
*deps
)
3985 reg_set_iterator rsi
;
3987 /* We set max_reg to 0 when this context was already freed. */
3988 if (deps
->max_reg
== 0)
3990 gcc_assert (deps
->reg_last
== NULL
);
3995 free_INSN_LIST_list (&deps
->pending_read_insns
);
3996 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3997 free_INSN_LIST_list (&deps
->pending_write_insns
);
3998 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3999 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
4001 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
4002 times. For a testcase with 42000 regs and 8000 small basic blocks,
4003 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
4004 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
4006 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
4008 free_INSN_LIST_list (®_last
->uses
);
4010 free_INSN_LIST_list (®_last
->sets
);
4011 if (reg_last
->implicit_sets
)
4012 free_INSN_LIST_list (®_last
->implicit_sets
);
4013 if (reg_last
->control_uses
)
4014 free_INSN_LIST_list (®_last
->control_uses
);
4015 if (reg_last
->clobbers
)
4016 free_INSN_LIST_list (®_last
->clobbers
);
4018 CLEAR_REG_SET (&deps
->reg_last_in_use
);
4020 /* As we initialize reg_last lazily, it is possible that we didn't allocate
4022 free (deps
->reg_last
);
4023 deps
->reg_last
= NULL
;
4028 /* Remove INSN from dependence contexts DEPS. */
4030 remove_from_deps (class deps_desc
*deps
, rtx_insn
*insn
)
4034 reg_set_iterator rsi
;
4036 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
4037 &deps
->pending_read_mems
);
4038 if (!DEBUG_INSN_P (insn
))
4039 deps
->pending_read_list_length
-= removed
;
4040 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
4041 &deps
->pending_write_mems
);
4042 deps
->pending_write_list_length
-= removed
;
4044 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
4045 deps
->pending_flush_length
-= removed
;
4046 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
4047 deps
->pending_flush_length
-= removed
;
4049 unsigned to_clear
= -1U;
4050 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
4052 if (to_clear
!= -1U)
4054 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, to_clear
);
4057 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
4059 remove_from_dependence_list (insn
, ®_last
->uses
);
4061 remove_from_dependence_list (insn
, ®_last
->sets
);
4062 if (reg_last
->implicit_sets
)
4063 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
4064 if (reg_last
->clobbers
)
4065 remove_from_dependence_list (insn
, ®_last
->clobbers
);
4066 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
4067 && !reg_last
->clobbers
)
4070 if (to_clear
!= -1U)
4071 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, to_clear
);
4075 remove_from_dependence_list (insn
, &deps
->last_function_call
);
4076 remove_from_dependence_list (insn
,
4077 &deps
->last_function_call_may_noreturn
);
4079 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
4082 /* Init deps data vector. */
4084 init_deps_data_vector (void)
4086 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
4087 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
4088 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
4091 /* If it is profitable to use them, initialize or extend (depending on
4092 GLOBAL_P) dependency data. */
4094 sched_deps_init (bool global_p
)
4096 /* Average number of insns in the basic block.
4097 '+ 1' is used to make it nonzero. */
4098 int insns_in_block
= sched_max_luid
/ n_basic_blocks_for_fn (cfun
) + 1;
4100 init_deps_data_vector ();
4102 /* We use another caching mechanism for selective scheduling, so
4103 we don't use this one. */
4104 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
4106 /* ?!? We could save some memory by computing a per-region luid mapping
4107 which could reduce both the number of vectors in the cache and the
4108 size of each vector. Instead we just avoid the cache entirely unless
4109 the average number of instructions in a basic block is very high. See
4110 the comment before the declaration of true_dependency_cache for
4111 what we consider "very high". */
4113 extend_dependency_caches (sched_max_luid
, true);
4118 dl_pool
= new object_allocator
<_deps_list
> ("deps_list");
4119 /* Allocate lists for one block at a time. */
4120 dn_pool
= new object_allocator
<_dep_node
> ("dep_node");
4121 /* Allocate nodes for one block at a time. */
4126 /* Create or extend (depending on CREATE_P) dependency caches to
4129 extend_dependency_caches (int n
, bool create_p
)
4131 if (create_p
|| true_dependency_cache
)
4133 int i
, luid
= cache_size
+ n
;
4135 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4137 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4138 output_dependency_cache
, luid
);
4139 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4141 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4144 if (current_sched_info
->flags
& DO_SPECULATION
)
4145 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4148 for (i
= cache_size
; i
< luid
; i
++)
4150 bitmap_initialize (&true_dependency_cache
[i
], 0);
4151 bitmap_initialize (&output_dependency_cache
[i
], 0);
4152 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4153 bitmap_initialize (&control_dependency_cache
[i
], 0);
4155 if (current_sched_info
->flags
& DO_SPECULATION
)
4156 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4162 /* Finalize dependency information for the whole function. */
4164 sched_deps_finish (void)
4166 gcc_assert (deps_pools_are_empty_p ());
4175 if (true_dependency_cache
)
4179 for (i
= 0; i
< cache_size
; i
++)
4181 bitmap_clear (&true_dependency_cache
[i
]);
4182 bitmap_clear (&output_dependency_cache
[i
]);
4183 bitmap_clear (&anti_dependency_cache
[i
]);
4184 bitmap_clear (&control_dependency_cache
[i
]);
4186 if (sched_deps_info
->generate_spec_deps
)
4187 bitmap_clear (&spec_dependency_cache
[i
]);
4189 free (true_dependency_cache
);
4190 true_dependency_cache
= NULL
;
4191 free (output_dependency_cache
);
4192 output_dependency_cache
= NULL
;
4193 free (anti_dependency_cache
);
4194 anti_dependency_cache
= NULL
;
4195 free (control_dependency_cache
);
4196 control_dependency_cache
= NULL
;
4198 if (sched_deps_info
->generate_spec_deps
)
4200 free (spec_dependency_cache
);
4201 spec_dependency_cache
= NULL
;
4207 /* Initialize some global variables needed by the dependency analysis
4211 init_deps_global (void)
4213 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4214 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4215 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4216 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4217 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4218 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4219 reg_pending_barrier
= NOT_A_BARRIER
;
4221 if (!sel_sched_p () || sched_emulate_haifa_p
)
4223 sched_deps_info
->start_insn
= haifa_start_insn
;
4224 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4226 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4227 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4228 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4230 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4231 sched_deps_info
->note_dep
= haifa_note_dep
;
4235 /* Free everything used by the dependency analysis code. */
4238 finish_deps_global (void)
4240 FREE_REG_SET (reg_pending_sets
);
4241 FREE_REG_SET (reg_pending_clobbers
);
4242 FREE_REG_SET (reg_pending_uses
);
4243 FREE_REG_SET (reg_pending_control_uses
);
4246 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4248 estimate_dep_weak (rtx mem1
, rtx mem2
)
4251 /* MEMs are the same - don't speculate. */
4252 return MIN_DEP_WEAK
;
4254 rtx r1
= XEXP (mem1
, 0);
4255 rtx r2
= XEXP (mem2
, 0);
4257 if (sched_deps_info
->use_cselib
)
4259 /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be
4260 dangling at this point, since we never preserve them. Instead we
4261 canonicalize manually to get stable VALUEs out of hashing. */
4262 if (GET_CODE (r1
) == VALUE
&& CSELIB_VAL_PTR (r1
))
4263 r1
= canonical_cselib_val (CSELIB_VAL_PTR (r1
))->val_rtx
;
4264 if (GET_CODE (r2
) == VALUE
&& CSELIB_VAL_PTR (r2
))
4265 r2
= canonical_cselib_val (CSELIB_VAL_PTR (r2
))->val_rtx
;
4269 || (REG_P (r1
) && REG_P (r2
) && REGNO (r1
) == REGNO (r2
)))
4270 /* Again, MEMs are the same. */
4271 return MIN_DEP_WEAK
;
4272 else if ((REG_P (r1
) && !REG_P (r2
)) || (!REG_P (r1
) && REG_P (r2
)))
4273 /* Different addressing modes - reason to be more speculative,
4275 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4277 /* We can't say anything about the dependence. */
4278 return UNCERTAIN_DEP_WEAK
;
4281 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4282 This function can handle same INSN and ELEM (INSN == ELEM).
4283 It is a convenience wrapper. */
4285 add_dependence_1 (rtx_insn
*insn
, rtx_insn
*elem
, enum reg_note dep_type
)
4290 if (dep_type
== REG_DEP_TRUE
)
4292 else if (dep_type
== REG_DEP_OUTPUT
)
4294 else if (dep_type
== REG_DEP_CONTROL
)
4298 gcc_assert (dep_type
== REG_DEP_ANTI
);
4302 /* When add_dependence is called from inside sched-deps.c, we expect
4303 cur_insn to be non-null. */
4304 internal
= cur_insn
!= NULL
;
4306 gcc_assert (insn
== cur_insn
);
4310 note_dep (elem
, ds
);
4315 /* Return weakness of speculative type TYPE in the dep_status DS,
4316 without checking to prevent ICEs on malformed input. */
4318 get_dep_weak_1 (ds_t ds
, ds_t type
)
4324 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4325 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4326 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4327 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4328 default: gcc_unreachable ();
4334 /* Return weakness of speculative type TYPE in the dep_status DS. */
4336 get_dep_weak (ds_t ds
, ds_t type
)
4338 dw_t dw
= get_dep_weak_1 (ds
, type
);
4340 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4344 /* Return the dep_status, which has the same parameters as DS, except for
4345 speculative type TYPE, that will have weakness DW. */
4347 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4349 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4354 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4355 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4356 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4357 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4358 default: gcc_unreachable ();
4363 /* Return the join of two dep_statuses DS1 and DS2.
4364 If MAX_P is true then choose the greater probability,
4365 otherwise multiply probabilities.
4366 This function assumes that both DS1 and DS2 contain speculative bits. */
4368 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4372 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4374 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4376 t
= FIRST_SPEC_TYPE
;
4379 if ((ds1
& t
) && !(ds2
& t
))
4381 else if (!(ds1
& t
) && (ds2
& t
))
4383 else if ((ds1
& t
) && (ds2
& t
))
4385 dw_t dw1
= get_dep_weak (ds1
, t
);
4386 dw_t dw2
= get_dep_weak (ds2
, t
);
4391 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4393 if (dw
< MIN_DEP_WEAK
)
4404 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4407 if (t
== LAST_SPEC_TYPE
)
4409 t
<<= SPEC_TYPE_SHIFT
;
4416 /* Return the join of two dep_statuses DS1 and DS2.
4417 This function assumes that both DS1 and DS2 contain speculative bits. */
4419 ds_merge (ds_t ds1
, ds_t ds2
)
4421 return ds_merge_1 (ds1
, ds2
, false);
4424 /* Return the join of two dep_statuses DS1 and DS2. */
4426 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4428 ds_t new_status
= ds
| ds2
;
4430 if (new_status
& SPECULATIVE
)
4432 if ((ds
&& !(ds
& SPECULATIVE
))
4433 || (ds2
&& !(ds2
& SPECULATIVE
)))
4434 /* Then this dep can't be speculative. */
4435 new_status
&= ~SPECULATIVE
;
4438 /* Both are speculative. Merging probabilities. */
4443 dw
= estimate_dep_weak (mem1
, mem2
);
4444 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4452 new_status
= ds_merge (ds2
, ds
);
4459 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4462 ds_max_merge (ds_t ds1
, ds_t ds2
)
4464 if (ds1
== 0 && ds2
== 0)
4467 if (ds1
== 0 && ds2
!= 0)
4470 if (ds1
!= 0 && ds2
== 0)
4473 return ds_merge_1 (ds1
, ds2
, true);
4476 /* Return the probability of speculation success for the speculation
4484 dt
= FIRST_SPEC_TYPE
;
4489 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4493 if (dt
== LAST_SPEC_TYPE
)
4495 dt
<<= SPEC_TYPE_SHIFT
;
4501 res
/= MAX_DEP_WEAK
;
4503 if (res
< MIN_DEP_WEAK
)
4506 gcc_assert (res
<= MAX_DEP_WEAK
);
4511 /* Return a dep status that contains all speculation types of DS. */
4513 ds_get_speculation_types (ds_t ds
)
4515 if (ds
& BEGIN_DATA
)
4517 if (ds
& BE_IN_DATA
)
4519 if (ds
& BEGIN_CONTROL
)
4520 ds
|= BEGIN_CONTROL
;
4521 if (ds
& BE_IN_CONTROL
)
4522 ds
|= BE_IN_CONTROL
;
4524 return ds
& SPECULATIVE
;
4527 /* Return a dep status that contains maximal weakness for each speculation
4528 type present in DS. */
4530 ds_get_max_dep_weak (ds_t ds
)
4532 if (ds
& BEGIN_DATA
)
4533 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4534 if (ds
& BE_IN_DATA
)
4535 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4536 if (ds
& BEGIN_CONTROL
)
4537 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4538 if (ds
& BE_IN_CONTROL
)
4539 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4544 /* Dump information about the dependence status S. */
4546 dump_ds (FILE *f
, ds_t s
)
4551 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4553 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4554 if (s
& BEGIN_CONTROL
)
4555 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4556 if (s
& BE_IN_CONTROL
)
4557 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4560 fprintf (f
, "HARD_DEP; ");
4563 fprintf (f
, "DEP_TRUE; ");
4565 fprintf (f
, "DEP_OUTPUT; ");
4567 fprintf (f
, "DEP_ANTI; ");
4568 if (s
& DEP_CONTROL
)
4569 fprintf (f
, "DEP_CONTROL; ");
4577 dump_ds (stderr
, s
);
4578 fprintf (stderr
, "\n");
4581 /* Verify that dependence type and status are consistent.
4582 If RELAXED_P is true, then skip dep_weakness checks. */
4584 check_dep (dep_t dep
, bool relaxed_p
)
4586 enum reg_note dt
= DEP_TYPE (dep
);
4587 ds_t ds
= DEP_STATUS (dep
);
4589 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4591 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4593 gcc_assert (ds
== 0);
4597 /* Check that dependence type contains the same bits as the status. */
4598 if (dt
== REG_DEP_TRUE
)
4599 gcc_assert (ds
& DEP_TRUE
);
4600 else if (dt
== REG_DEP_OUTPUT
)
4601 gcc_assert ((ds
& DEP_OUTPUT
)
4602 && !(ds
& DEP_TRUE
));
4603 else if (dt
== REG_DEP_ANTI
)
4604 gcc_assert ((ds
& DEP_ANTI
)
4605 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4607 gcc_assert (dt
== REG_DEP_CONTROL
4608 && (ds
& DEP_CONTROL
)
4609 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4611 /* HARD_DEP cannot appear in dep_status of a link. */
4612 gcc_assert (!(ds
& HARD_DEP
));
4614 /* Check that dependence status is set correctly when speculation is not
4616 if (!sched_deps_info
->generate_spec_deps
)
4617 gcc_assert (!(ds
& SPECULATIVE
));
4618 else if (ds
& SPECULATIVE
)
4622 ds_t type
= FIRST_SPEC_TYPE
;
4624 /* Check that dependence weakness is in proper range. */
4628 get_dep_weak (ds
, type
);
4630 if (type
== LAST_SPEC_TYPE
)
4632 type
<<= SPEC_TYPE_SHIFT
;
4637 if (ds
& BEGIN_SPEC
)
4639 /* Only true dependence can be data speculative. */
4640 if (ds
& BEGIN_DATA
)
4641 gcc_assert (ds
& DEP_TRUE
);
4643 /* Control dependencies in the insn scheduler are represented by
4644 anti-dependencies, therefore only anti dependence can be
4645 control speculative. */
4646 if (ds
& BEGIN_CONTROL
)
4647 gcc_assert (ds
& DEP_ANTI
);
4651 /* Subsequent speculations should resolve true dependencies. */
4652 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4655 /* Check that true and anti dependencies can't have other speculative
4658 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4659 /* An output dependence can't be speculative at all. */
4660 gcc_assert (!(ds
& DEP_OUTPUT
));
4662 gcc_assert (ds
& BEGIN_CONTROL
);
4666 /* The following code discovers opportunities to switch a memory reference
4667 and an increment by modifying the address. We ensure that this is done
4668 only for dependencies that are only used to show a single register
4669 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4670 instruction involved is subject to only one dep that can cause a pattern
4673 When we discover a suitable dependency, we fill in the dep_replacement
4674 structure to show how to modify the memory reference. */
4676 /* Holds information about a pair of memory reference and register increment
4677 insns which depend on each other, but could possibly be interchanged. */
4684 /* A register occurring in the memory address for which we wish to break
4685 the dependence. This must be identical to the destination register of
4688 /* Any kind of index that is added to that register. */
4690 /* The constant offset used in the memory address. */
4691 HOST_WIDE_INT mem_constant
;
4692 /* The constant added in the increment insn. Negated if the increment is
4693 after the memory address. */
4694 HOST_WIDE_INT inc_constant
;
4695 /* The source register used in the increment. May be different from mem_reg0
4696 if the increment occurs before the memory address. */
4700 /* Verify that the memory location described in MII can be replaced with
4701 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4702 insn remains unchanged by this function. */
4705 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4707 rtx mem
= *mii
->mem_loc
;
4710 /* Jump through a lot of hoops to keep the attributes up to date. We
4711 do not want to call one of the change address variants that take
4712 an offset even though we know the offset in many cases. These
4713 assume you are changing where the address is pointing by the
4715 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4716 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4718 if (sched_verbose
>= 5)
4719 fprintf (sched_dump
, "validation failure\n");
4723 /* Put back the old one. */
4724 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4729 /* Return true if INSN is of a form "a = b op c" where a and b are
4730 regs. op is + if c is a reg and +|- if c is a const. Fill in
4731 informantion in MII about what is found.
4732 BEFORE_MEM indicates whether the increment is found before or after
4733 a corresponding memory reference. */
4736 parse_add_or_inc (struct mem_inc_info
*mii
, rtx_insn
*insn
, bool before_mem
)
4738 rtx pat
= single_set (insn
);
4742 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4745 /* Do not allow breaking data dependencies for insns that are marked
4746 with REG_STACK_CHECK. */
4747 if (find_reg_note (insn
, REG_STACK_CHECK
, NULL
))
4750 /* Result must be single reg. */
4751 if (!REG_P (SET_DEST (pat
)))
4754 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4757 mii
->inc_insn
= insn
;
4758 src
= SET_SRC (pat
);
4759 mii
->inc_input
= XEXP (src
, 0);
4761 if (!REG_P (XEXP (src
, 0)))
4764 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4767 cst
= XEXP (src
, 1);
4768 if (!CONST_INT_P (cst
))
4770 mii
->inc_constant
= INTVAL (cst
);
4772 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4776 mii
->inc_constant
= -mii
->inc_constant
;
4781 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4783 /* Note that the sign has already been reversed for !before_mem. */
4784 if (STACK_GROWS_DOWNWARD
)
4785 return mii
->inc_constant
> 0;
4787 return mii
->inc_constant
< 0;
4792 /* Once a suitable mem reference has been found and the corresponding data
4793 in MII has been filled in, this function is called to find a suitable
4794 add or inc insn involving the register we found in the memory
4798 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4800 sd_iterator_def sd_it
;
4803 sd_it
= sd_iterator_start (mii
->mem_insn
,
4804 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4805 while (sd_iterator_cond (&sd_it
, &dep
))
4807 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4808 rtx_insn
*pro
= DEP_PRO (dep
);
4809 rtx_insn
*con
= DEP_CON (dep
);
4810 rtx_insn
*inc_cand
= backwards
? pro
: con
;
4811 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4813 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4815 struct dep_replacement
*desc
;
4817 rtx newaddr
, newmem
;
4819 if (sched_verbose
>= 5)
4820 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4821 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4823 /* Need to assure that none of the operands of the inc
4824 instruction are assigned to by the mem insn. */
4825 FOR_EACH_INSN_DEF (def
, mii
->mem_insn
)
4826 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4827 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4829 if (sched_verbose
>= 5)
4830 fprintf (sched_dump
,
4831 "inc conflicts with store failure.\n");
4835 newaddr
= mii
->inc_input
;
4836 if (mii
->mem_index
!= NULL_RTX
)
4837 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4839 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4840 mii
->mem_constant
+ mii
->inc_constant
);
4841 newmem
= attempt_change (mii
, newaddr
);
4842 if (newmem
== NULL_RTX
)
4844 if (sched_verbose
>= 5)
4845 fprintf (sched_dump
, "successful address replacement\n");
4846 desc
= XCNEW (struct dep_replacement
);
4847 DEP_REPLACE (dep
) = desc
;
4848 desc
->loc
= mii
->mem_loc
;
4849 desc
->newval
= newmem
;
4850 desc
->orig
= *desc
->loc
;
4851 desc
->insn
= mii
->mem_insn
;
4852 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4853 INSN_SPEC_BACK_DEPS (con
));
4856 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4857 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4862 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4863 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4869 sd_iterator_next (&sd_it
);
4874 /* A recursive function that walks ADDRESS_OF_X to find memory references
4875 which could be modified during scheduling. We call find_inc for each
4876 one we find that has a recognizable form. MII holds information about
4877 the pair of memory/increment instructions.
4878 We ensure that every instruction with a memory reference (which will be
4879 the location of the replacement) is assigned at most one breakable
4883 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4885 rtx x
= *address_of_x
;
4886 enum rtx_code code
= GET_CODE (x
);
4887 const char *const fmt
= GET_RTX_FORMAT (code
);
4892 rtx reg0
= XEXP (x
, 0);
4894 mii
->mem_loc
= address_of_x
;
4895 mii
->mem_index
= NULL_RTX
;
4896 mii
->mem_constant
= 0;
4897 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4899 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4900 reg0
= XEXP (reg0
, 0);
4902 if (GET_CODE (reg0
) == PLUS
)
4904 mii
->mem_index
= XEXP (reg0
, 1);
4905 reg0
= XEXP (reg0
, 0);
4910 int occurrences
= 0;
4912 /* Make sure this reg appears only once in this insn. Can't use
4913 count_occurrences since that only works for pseudos. */
4914 FOR_EACH_INSN_USE (use
, mii
->mem_insn
)
4915 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (use
)))
4916 if (++occurrences
> 1)
4918 if (sched_verbose
>= 5)
4919 fprintf (sched_dump
, "mem count failure\n");
4923 mii
->mem_reg0
= reg0
;
4924 return find_inc (mii
, true) || find_inc (mii
, false);
4929 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4931 /* If REG occurs inside a MEM used in a bit-field reference,
4932 that is unacceptable. */
4936 /* Time for some deep diving. */
4937 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4941 if (find_mem (mii
, &XEXP (x
, i
)))
4944 else if (fmt
[i
] == 'E')
4947 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4948 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4956 /* Examine the instructions between HEAD and TAIL and try to find
4957 dependencies that can be broken by modifying one of the patterns. */
4960 find_modifiable_mems (rtx_insn
*head
, rtx_insn
*tail
)
4962 rtx_insn
*insn
, *next_tail
= NEXT_INSN (tail
);
4963 int success_in_block
= 0;
4965 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4967 struct mem_inc_info mii
;
4969 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4972 mii
.mem_insn
= insn
;
4973 if (find_mem (&mii
, &PATTERN (insn
)))
4976 if (success_in_block
&& sched_verbose
>= 5)
4977 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4981 #endif /* INSN_SCHEDULING */