1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992-2014 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"
27 #include "diagnostic-core.h"
29 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
46 #ifdef INSN_SCHEDULING
48 #ifdef ENABLE_CHECKING
54 /* Holds current parameters for the dependency analyzer. */
55 struct sched_deps_info_def
*sched_deps_info
;
57 /* The data is specific to the Haifa scheduler. */
58 vec
<haifa_deps_insn_data_def
>
61 /* Return the major type present in the DS. */
69 return REG_DEP_OUTPUT
;
72 return REG_DEP_CONTROL
;
74 gcc_assert (ds
& DEP_ANTI
);
79 /* Return equivalent dep_status. */
81 dk_to_ds (enum reg_note dk
)
95 gcc_assert (dk
== REG_DEP_ANTI
);
100 /* Functions to operate with dependence information container - dep_t. */
102 /* Init DEP with the arguments. */
104 init_dep_1 (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note type
, ds_t ds
)
108 DEP_TYPE (dep
) = type
;
109 DEP_STATUS (dep
) = ds
;
110 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
111 DEP_NONREG (dep
) = 0;
112 DEP_MULTIPLE (dep
) = 0;
113 DEP_REPLACE (dep
) = NULL
;
116 /* Init DEP with the arguments.
117 While most of the scheduler (including targets) only need the major type
118 of the dependency, it is convenient to hide full dep_status from them. */
120 init_dep (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note kind
)
124 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
125 ds
= dk_to_ds (kind
);
129 init_dep_1 (dep
, pro
, con
, kind
, ds
);
132 /* Make a copy of FROM in TO. */
134 copy_dep (dep_t to
, dep_t from
)
136 memcpy (to
, from
, sizeof (*to
));
139 static void dump_ds (FILE *, ds_t
);
141 /* Define flags for dump_dep (). */
143 /* Dump producer of the dependence. */
144 #define DUMP_DEP_PRO (2)
146 /* Dump consumer of the dependence. */
147 #define DUMP_DEP_CON (4)
149 /* Dump type of the dependence. */
150 #define DUMP_DEP_TYPE (8)
152 /* Dump status of the dependence. */
153 #define DUMP_DEP_STATUS (16)
155 /* Dump all information about the dependence. */
156 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
160 FLAGS is a bit mask specifying what information about DEP needs
162 If FLAGS has the very first bit set, then dump all information about DEP
163 and propagate this bit into the callee dump functions. */
165 dump_dep (FILE *dump
, dep_t dep
, int flags
)
168 flags
|= DUMP_DEP_ALL
;
172 if (flags
& DUMP_DEP_PRO
)
173 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
175 if (flags
& DUMP_DEP_CON
)
176 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
178 if (flags
& DUMP_DEP_TYPE
)
181 enum reg_note type
= DEP_TYPE (dep
);
193 case REG_DEP_CONTROL
:
206 fprintf (dump
, "%c; ", t
);
209 if (flags
& DUMP_DEP_STATUS
)
211 if (current_sched_info
->flags
& USE_DEPS_LIST
)
212 dump_ds (dump
, DEP_STATUS (dep
));
218 /* Default flags for dump_dep (). */
219 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
221 /* Dump all fields of DEP to STDERR. */
223 sd_debug_dep (dep_t dep
)
225 dump_dep (stderr
, dep
, 1);
226 fprintf (stderr
, "\n");
229 /* Determine whether DEP is a dependency link of a non-debug insn on a
233 depl_on_debug_p (dep_link_t dep
)
235 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
236 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
239 /* Functions to operate with a single link from the dependencies lists -
242 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
245 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
247 dep_link_t next
= *prev_nextp
;
249 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
250 && DEP_LINK_NEXT (l
) == NULL
);
252 /* Init node being inserted. */
253 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
254 DEP_LINK_NEXT (l
) = next
;
259 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
261 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
268 /* Add dep_link LINK to deps_list L. */
270 add_to_deps_list (dep_link_t link
, deps_list_t l
)
272 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
274 /* Don't count debug deps. */
275 if (!depl_on_debug_p (link
))
276 ++DEPS_LIST_N_LINKS (l
);
279 /* Detach dep_link L from the list. */
281 detach_dep_link (dep_link_t l
)
283 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
284 dep_link_t next
= DEP_LINK_NEXT (l
);
289 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
291 DEP_LINK_PREV_NEXTP (l
) = NULL
;
292 DEP_LINK_NEXT (l
) = NULL
;
295 /* Remove link LINK from list LIST. */
297 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
299 detach_dep_link (link
);
301 /* Don't count debug deps. */
302 if (!depl_on_debug_p (link
))
303 --DEPS_LIST_N_LINKS (list
);
306 /* Move link LINK from list FROM to list TO. */
308 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
310 remove_from_deps_list (link
, from
);
311 add_to_deps_list (link
, to
);
314 /* Return true of LINK is not attached to any list. */
316 dep_link_is_detached_p (dep_link_t link
)
318 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
321 /* Pool to hold all dependency nodes (dep_node_t). */
322 static alloc_pool dn_pool
;
324 /* Number of dep_nodes out there. */
325 static int dn_pool_diff
= 0;
327 /* Create a dep_node. */
329 create_dep_node (void)
331 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
332 dep_link_t back
= DEP_NODE_BACK (n
);
333 dep_link_t forw
= DEP_NODE_FORW (n
);
335 DEP_LINK_NODE (back
) = n
;
336 DEP_LINK_NEXT (back
) = NULL
;
337 DEP_LINK_PREV_NEXTP (back
) = NULL
;
339 DEP_LINK_NODE (forw
) = n
;
340 DEP_LINK_NEXT (forw
) = NULL
;
341 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
348 /* Delete dep_node N. N must not be connected to any deps_list. */
350 delete_dep_node (dep_node_t n
)
352 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
353 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
355 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n
)));
359 pool_free (dn_pool
, n
);
362 /* Pool to hold dependencies lists (deps_list_t). */
363 static alloc_pool dl_pool
;
365 /* Number of deps_lists out there. */
366 static int dl_pool_diff
= 0;
368 /* Functions to operate with dependences lists - deps_list_t. */
370 /* Return true if list L is empty. */
372 deps_list_empty_p (deps_list_t l
)
374 return DEPS_LIST_N_LINKS (l
) == 0;
377 /* Create a new deps_list. */
379 create_deps_list (void)
381 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
383 DEPS_LIST_FIRST (l
) = NULL
;
384 DEPS_LIST_N_LINKS (l
) = 0;
390 /* Free deps_list L. */
392 free_deps_list (deps_list_t l
)
394 gcc_assert (deps_list_empty_p (l
));
398 pool_free (dl_pool
, l
);
401 /* Return true if there is no dep_nodes and deps_lists out there.
402 After the region is scheduled all the dependency nodes and lists
403 should [generally] be returned to pool. */
405 deps_pools_are_empty_p (void)
407 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
410 /* Remove all elements from L. */
412 clear_deps_list (deps_list_t l
)
416 dep_link_t link
= DEPS_LIST_FIRST (l
);
421 remove_from_deps_list (link
, l
);
426 /* Decide whether a dependency should be treated as a hard or a speculative
429 dep_spec_p (dep_t dep
)
431 if (current_sched_info
->flags
& DO_SPECULATION
)
433 if (DEP_STATUS (dep
) & SPECULATIVE
)
436 if (current_sched_info
->flags
& DO_PREDICATION
)
438 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
441 if (DEP_REPLACE (dep
) != NULL
)
446 static regset reg_pending_sets
;
447 static regset reg_pending_clobbers
;
448 static regset reg_pending_uses
;
449 static regset reg_pending_control_uses
;
450 static enum reg_pending_barrier_mode reg_pending_barrier
;
452 /* Hard registers implicitly clobbered or used (or may be implicitly
453 clobbered or used) by the currently analyzed insn. For example,
454 insn in its constraint has one register class. Even if there is
455 currently no hard register in the insn, the particular hard
456 register will be in the insn after reload pass because the
457 constraint requires it. */
458 static HARD_REG_SET implicit_reg_pending_clobbers
;
459 static HARD_REG_SET implicit_reg_pending_uses
;
461 /* To speed up the test for duplicate dependency links we keep a
462 record of dependencies created by add_dependence when the average
463 number of instructions in a basic block is very large.
465 Studies have shown that there is typically around 5 instructions between
466 branches for typical C code. So we can make a guess that the average
467 basic block is approximately 5 instructions long; we will choose 100X
468 the average size as a very large basic block.
470 Each insn has associated bitmaps for its dependencies. Each bitmap
471 has enough entries to represent a dependency on any other insn in
472 the insn chain. All bitmap for true dependencies cache is
473 allocated then the rest two ones are also allocated. */
474 static bitmap_head
*true_dependency_cache
= NULL
;
475 static bitmap_head
*output_dependency_cache
= NULL
;
476 static bitmap_head
*anti_dependency_cache
= NULL
;
477 static bitmap_head
*control_dependency_cache
= NULL
;
478 static bitmap_head
*spec_dependency_cache
= NULL
;
479 static int cache_size
;
481 /* True if we should mark added dependencies as a non-register deps. */
482 static bool mark_as_hard
;
484 static int deps_may_trap_p (const_rtx
);
485 static void add_dependence_1 (rtx_insn
*, rtx_insn
*, enum reg_note
);
486 static void add_dependence_list (rtx_insn
*, rtx_insn_list
*, int,
487 enum reg_note
, bool);
488 static void add_dependence_list_and_free (struct deps_desc
*, rtx_insn
*,
489 rtx_insn_list
**, int, enum reg_note
,
491 static void delete_all_dependences (rtx
);
492 static void chain_to_prev_insn (rtx_insn
*);
494 static void flush_pending_lists (struct deps_desc
*, rtx_insn
*, int, int);
495 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx_insn
*);
496 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx_insn
*);
497 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx_insn
*);
499 static bool sched_has_condition_p (const_rtx
);
500 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
502 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
504 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
506 #ifdef ENABLE_CHECKING
507 static void check_dep (dep_t
, bool);
510 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
513 deps_may_trap_p (const_rtx mem
)
515 const_rtx addr
= XEXP (mem
, 0);
517 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
519 const_rtx t
= get_reg_known_value (REGNO (addr
));
523 return rtx_addr_can_trap_p (addr
);
527 /* Find the condition under which INSN is executed. If REV is not NULL,
528 it is set to TRUE when the returned comparison should be reversed
529 to get the actual condition. */
531 sched_get_condition_with_rev_uncached (const_rtx insn
, bool *rev
)
533 rtx pat
= PATTERN (insn
);
539 if (GET_CODE (pat
) == COND_EXEC
)
540 return COND_EXEC_TEST (pat
);
542 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
545 src
= SET_SRC (pc_set (insn
));
547 if (XEXP (src
, 2) == pc_rtx
)
548 return XEXP (src
, 0);
549 else if (XEXP (src
, 1) == pc_rtx
)
551 rtx cond
= XEXP (src
, 0);
552 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
554 if (revcode
== UNKNOWN
)
565 /* Return the condition under which INSN does not execute (i.e. the
566 not-taken condition for a conditional branch), or NULL if we cannot
567 find such a condition. The caller should make a copy of the condition
570 sched_get_reverse_condition_uncached (const_rtx insn
)
573 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
574 if (cond
== NULL_RTX
)
578 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
579 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
586 /* Caching variant of sched_get_condition_with_rev_uncached.
587 We only do actual work the first time we come here for an insn; the
588 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
590 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
594 if (INSN_LUID (insn
) == 0)
595 return sched_get_condition_with_rev_uncached (insn
, rev
);
597 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
600 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
603 *rev
= INSN_REVERSE_COND (insn
);
604 return INSN_CACHED_COND (insn
);
607 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
608 INSN_REVERSE_COND (insn
) = tmp
;
610 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
612 INSN_CACHED_COND (insn
) = const_true_rtx
;
617 *rev
= INSN_REVERSE_COND (insn
);
618 return INSN_CACHED_COND (insn
);
621 /* True when we can find a condition under which INSN is executed. */
623 sched_has_condition_p (const_rtx insn
)
625 return !! sched_get_condition_with_rev (insn
, NULL
);
630 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
632 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
634 if (COMPARISON_P (cond1
)
635 && COMPARISON_P (cond2
)
636 && GET_CODE (cond1
) ==
638 ? reversed_comparison_code (cond2
, NULL
)
640 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
641 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
646 /* Return true if insn1 and insn2 can never depend on one another because
647 the conditions under which they are executed are mutually exclusive. */
649 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
652 bool rev1
= false, rev2
= false;
654 /* df doesn't handle conditional lifetimes entirely correctly;
655 calls mess up the conditional lifetimes. */
656 if (!CALL_P (insn1
) && !CALL_P (insn2
))
658 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
659 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
661 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
662 /* Make sure first instruction doesn't affect condition of second
663 instruction if switched. */
664 && !modified_in_p (cond1
, insn2
)
665 /* Make sure second instruction doesn't affect condition of first
666 instruction if switched. */
667 && !modified_in_p (cond2
, insn1
))
674 /* Return true if INSN can potentially be speculated with type DS. */
676 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
678 if (HAS_INTERNAL_DEP (insn
))
681 if (!NONJUMP_INSN_P (insn
))
684 if (SCHED_GROUP_P (insn
))
687 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
690 if (side_effects_p (PATTERN (insn
)))
694 /* The following instructions, which depend on a speculatively scheduled
695 instruction, cannot be speculatively scheduled along. */
697 if (may_trap_or_fault_p (PATTERN (insn
)))
698 /* If instruction might fault, it cannot be speculatively scheduled.
699 For control speculation it's obvious why and for data speculation
700 it's because the insn might get wrong input if speculation
701 wasn't successful. */
704 if ((ds
& BE_IN_DATA
)
705 && sched_has_condition_p (insn
))
706 /* If this is a predicated instruction, then it cannot be
707 speculatively scheduled. See PR35659. */
714 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
715 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
716 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
717 This function is used to switch sd_iterator to the next list.
718 !!! For internal use only. Might consider moving it to sched-int.h. */
720 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
721 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
723 sd_list_types_def types
= *types_ptr
;
725 if (types
& SD_LIST_HARD_BACK
)
727 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
728 *resolved_p_ptr
= false;
729 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
731 else if (types
& SD_LIST_SPEC_BACK
)
733 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
734 *resolved_p_ptr
= false;
735 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
737 else if (types
& SD_LIST_FORW
)
739 *list_ptr
= INSN_FORW_DEPS (insn
);
740 *resolved_p_ptr
= false;
741 *types_ptr
= types
& ~SD_LIST_FORW
;
743 else if (types
& SD_LIST_RES_BACK
)
745 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
746 *resolved_p_ptr
= true;
747 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
749 else if (types
& SD_LIST_RES_FORW
)
751 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
752 *resolved_p_ptr
= true;
753 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
758 *resolved_p_ptr
= false;
759 *types_ptr
= SD_LIST_NONE
;
763 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
765 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
769 while (list_types
!= SD_LIST_NONE
)
774 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
776 size
+= DEPS_LIST_N_LINKS (list
);
782 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
785 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
787 while (list_types
!= SD_LIST_NONE
)
792 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
793 if (!deps_list_empty_p (list
))
800 /* Initialize data for INSN. */
802 sd_init_insn (rtx insn
)
804 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
805 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
806 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
807 INSN_FORW_DEPS (insn
) = create_deps_list ();
808 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
810 /* ??? It would be nice to allocate dependency caches here. */
813 /* Free data for INSN. */
815 sd_finish_insn (rtx insn
)
817 /* ??? It would be nice to deallocate dependency caches here. */
819 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
820 INSN_HARD_BACK_DEPS (insn
) = NULL
;
822 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
823 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
825 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
826 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
828 free_deps_list (INSN_FORW_DEPS (insn
));
829 INSN_FORW_DEPS (insn
) = NULL
;
831 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
832 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
835 /* Find a dependency between producer PRO and consumer CON.
836 Search through resolved dependency lists if RESOLVED_P is true.
837 If no such dependency is found return NULL,
838 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
839 with an iterator pointing to it. */
841 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
842 sd_iterator_def
*sd_it_ptr
)
844 sd_list_types_def pro_list_type
;
845 sd_list_types_def con_list_type
;
846 sd_iterator_def sd_it
;
848 bool found_p
= false;
852 pro_list_type
= SD_LIST_RES_FORW
;
853 con_list_type
= SD_LIST_RES_BACK
;
857 pro_list_type
= SD_LIST_FORW
;
858 con_list_type
= SD_LIST_BACK
;
861 /* Walk through either back list of INSN or forw list of ELEM
862 depending on which one is shorter. */
863 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
865 /* Find the dep_link with producer PRO in consumer's back_deps. */
866 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
867 if (DEP_PRO (dep
) == pro
)
875 /* Find the dep_link with consumer CON in producer's forw_deps. */
876 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
877 if (DEP_CON (dep
) == con
)
886 if (sd_it_ptr
!= NULL
)
895 /* Find a dependency between producer PRO and consumer CON.
896 Use dependency [if available] to check if dependency is present at all.
897 Search through resolved dependency lists if RESOLVED_P is true.
898 If the dependency or NULL if none found. */
900 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
902 if (true_dependency_cache
!= NULL
)
903 /* Avoiding the list walk below can cut compile times dramatically
906 int elem_luid
= INSN_LUID (pro
);
907 int insn_luid
= INSN_LUID (con
);
909 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
910 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
911 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
912 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
916 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
919 /* Add or update a dependence described by DEP.
920 MEM1 and MEM2, if non-null, correspond to memory locations in case of
923 The function returns a value indicating if an old entry has been changed
924 or a new entry has been added to insn's backward deps.
926 This function merely checks if producer and consumer is the same insn
927 and doesn't create a dep in this case. Actual manipulation of
928 dependence data structures is performed in add_or_update_dep_1. */
929 static enum DEPS_ADJUST_RESULT
930 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
932 rtx_insn
*elem
= DEP_PRO (dep
);
933 rtx_insn
*insn
= DEP_CON (dep
);
935 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
937 /* Don't depend an insn on itself. */
940 if (sched_deps_info
->generate_spec_deps
)
941 /* INSN has an internal dependence, which we can't overcome. */
942 HAS_INTERNAL_DEP (insn
) = 1;
947 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
950 /* Ask dependency caches what needs to be done for dependence DEP.
951 Return DEP_CREATED if new dependence should be created and there is no
952 need to try to find one searching the dependencies lists.
953 Return DEP_PRESENT if there already is a dependence described by DEP and
954 hence nothing is to be done.
955 Return DEP_CHANGED if there already is a dependence, but it should be
956 updated to incorporate additional information from DEP. */
957 static enum DEPS_ADJUST_RESULT
958 ask_dependency_caches (dep_t dep
)
960 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
961 int insn_luid
= INSN_LUID (DEP_CON (dep
));
963 gcc_assert (true_dependency_cache
!= NULL
964 && output_dependency_cache
!= NULL
965 && anti_dependency_cache
!= NULL
966 && control_dependency_cache
!= NULL
);
968 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
970 enum reg_note present_dep_type
;
972 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
973 present_dep_type
= REG_DEP_TRUE
;
974 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
975 present_dep_type
= REG_DEP_OUTPUT
;
976 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
977 present_dep_type
= REG_DEP_ANTI
;
978 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
979 present_dep_type
= REG_DEP_CONTROL
;
981 /* There is no existing dep so it should be created. */
984 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
985 /* DEP does not add anything to the existing dependence. */
990 ds_t present_dep_types
= 0;
992 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
993 present_dep_types
|= DEP_TRUE
;
994 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
995 present_dep_types
|= DEP_OUTPUT
;
996 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
997 present_dep_types
|= DEP_ANTI
;
998 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
999 present_dep_types
|= DEP_CONTROL
;
1001 if (present_dep_types
== 0)
1002 /* There is no existing dep so it should be created. */
1005 if (!(current_sched_info
->flags
& DO_SPECULATION
)
1006 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
1008 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
1009 == present_dep_types
)
1010 /* DEP does not add anything to the existing dependence. */
1015 /* Only true dependencies can be data speculative and
1016 only anti dependencies can be control speculative. */
1017 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1018 == present_dep_types
);
1020 /* if (DEP is SPECULATIVE) then
1021 ..we should update DEP_STATUS
1023 ..we should reset existing dep to non-speculative. */
1030 /* Set dependency caches according to DEP. */
1032 set_dependency_caches (dep_t dep
)
1034 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1035 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1037 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1039 switch (DEP_TYPE (dep
))
1042 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1045 case REG_DEP_OUTPUT
:
1046 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1050 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1053 case REG_DEP_CONTROL
:
1054 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1063 ds_t ds
= DEP_STATUS (dep
);
1066 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1067 if (ds
& DEP_OUTPUT
)
1068 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1070 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1071 if (ds
& DEP_CONTROL
)
1072 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1074 if (ds
& SPECULATIVE
)
1076 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1077 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1082 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1083 caches accordingly. */
1085 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1087 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1088 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1090 /* Clear corresponding cache entry because type of the link
1091 may have changed. Keep them if we use_deps_list. */
1092 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1096 case REG_DEP_OUTPUT
:
1097 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1101 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1104 case REG_DEP_CONTROL
:
1105 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1113 set_dependency_caches (dep
);
1116 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1118 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1120 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1121 dep_link_t link
= DEP_NODE_BACK (node
);
1122 dep_t dep
= DEP_NODE_DEP (node
);
1123 rtx_insn
*elem
= DEP_PRO (dep
);
1124 rtx_insn
*insn
= DEP_CON (dep
);
1126 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1128 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1130 if (true_dependency_cache
!= NULL
)
1131 /* Clear the cache entry. */
1132 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1136 /* Update DEP to incorporate information from NEW_DEP.
1137 SD_IT points to DEP in case it should be moved to another list.
1138 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1139 data-speculative dependence should be updated. */
1140 static enum DEPS_ADJUST_RESULT
1141 update_dep (dep_t dep
, dep_t new_dep
,
1142 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1143 rtx mem1 ATTRIBUTE_UNUSED
,
1144 rtx mem2 ATTRIBUTE_UNUSED
)
1146 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1147 enum reg_note old_type
= DEP_TYPE (dep
);
1148 bool was_spec
= dep_spec_p (dep
);
1150 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1151 DEP_MULTIPLE (dep
) = 1;
1153 /* If this is a more restrictive type of dependence than the
1154 existing one, then change the existing dependence to this
1156 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1158 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1162 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1163 /* Update DEP_STATUS. */
1165 ds_t dep_status
= DEP_STATUS (dep
);
1166 ds_t ds
= DEP_STATUS (new_dep
);
1167 ds_t new_status
= ds
| dep_status
;
1169 if (new_status
& SPECULATIVE
)
1171 /* Either existing dep or a dep we're adding or both are
1173 if (!(ds
& SPECULATIVE
)
1174 || !(dep_status
& SPECULATIVE
))
1175 /* The new dep can't be speculative. */
1176 new_status
&= ~SPECULATIVE
;
1179 /* Both are speculative. Merge probabilities. */
1184 dw
= estimate_dep_weak (mem1
, mem2
);
1185 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1188 new_status
= ds_merge (dep_status
, ds
);
1194 if (dep_status
!= ds
)
1196 DEP_STATUS (dep
) = ds
;
1201 if (was_spec
&& !dep_spec_p (dep
))
1202 /* The old dep was speculative, but now it isn't. */
1203 change_spec_dep_to_hard (sd_it
);
1205 if (true_dependency_cache
!= NULL
1206 && res
== DEP_CHANGED
)
1207 update_dependency_caches (dep
, old_type
);
1212 /* Add or update a dependence described by DEP.
1213 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1216 The function returns a value indicating if an old entry has been changed
1217 or a new entry has been added to insn's backward deps or nothing has
1218 been updated at all. */
1219 static enum DEPS_ADJUST_RESULT
1220 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1221 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1223 bool maybe_present_p
= true;
1224 bool present_p
= false;
1226 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1227 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1229 #ifdef ENABLE_CHECKING
1230 check_dep (new_dep
, mem1
!= NULL
);
1233 if (true_dependency_cache
!= NULL
)
1235 switch (ask_dependency_caches (new_dep
))
1241 maybe_present_p
= true;
1246 maybe_present_p
= false;
1256 /* Check that we don't already have this dependence. */
1257 if (maybe_present_p
)
1260 sd_iterator_def sd_it
;
1262 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1264 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1266 resolved_p
, &sd_it
);
1268 if (present_dep
!= NULL
)
1269 /* We found an existing dependency between ELEM and INSN. */
1270 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1272 /* We didn't find a dep, it shouldn't present in the cache. */
1273 gcc_assert (!present_p
);
1276 /* Might want to check one level of transitivity to save conses.
1277 This check should be done in maybe_add_or_update_dep_1.
1278 Since we made it to add_or_update_dep_1, we must create
1279 (or update) a link. */
1281 if (mem1
!= NULL_RTX
)
1283 gcc_assert (sched_deps_info
->generate_spec_deps
);
1284 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1285 estimate_dep_weak (mem1
, mem2
));
1288 sd_add_dep (new_dep
, resolved_p
);
1293 /* Initialize BACK_LIST_PTR with consumer's backward list and
1294 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1295 initialize with lists that hold resolved deps. */
1297 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1298 deps_list_t
*back_list_ptr
,
1299 deps_list_t
*forw_list_ptr
)
1301 rtx_insn
*con
= DEP_CON (dep
);
1305 if (dep_spec_p (dep
))
1306 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1308 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1310 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1314 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1315 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1319 /* Add dependence described by DEP.
1320 If RESOLVED_P is true treat the dependence as a resolved one. */
1322 sd_add_dep (dep_t dep
, bool resolved_p
)
1324 dep_node_t n
= create_dep_node ();
1325 deps_list_t con_back_deps
;
1326 deps_list_t pro_forw_deps
;
1327 rtx_insn
*elem
= DEP_PRO (dep
);
1328 rtx_insn
*insn
= DEP_CON (dep
);
1330 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1332 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1333 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1334 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1336 copy_dep (DEP_NODE_DEP (n
), dep
);
1338 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1340 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1342 #ifdef ENABLE_CHECKING
1343 check_dep (dep
, false);
1346 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1348 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1349 in the bitmap caches of dependency information. */
1350 if (true_dependency_cache
!= NULL
)
1351 set_dependency_caches (dep
);
1354 /* Add or update backward dependence between INSN and ELEM
1355 with given type DEP_TYPE and dep_status DS.
1356 This function is a convenience wrapper. */
1357 enum DEPS_ADJUST_RESULT
1358 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1360 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1363 /* Resolved dependence pointed to by SD_IT.
1364 SD_IT will advance to the next element. */
1366 sd_resolve_dep (sd_iterator_def sd_it
)
1368 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1369 dep_t dep
= DEP_NODE_DEP (node
);
1370 rtx_insn
*pro
= DEP_PRO (dep
);
1371 rtx_insn
*con
= DEP_CON (dep
);
1373 if (dep_spec_p (dep
))
1374 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1375 INSN_RESOLVED_BACK_DEPS (con
));
1377 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1378 INSN_RESOLVED_BACK_DEPS (con
));
1380 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1381 INSN_RESOLVED_FORW_DEPS (pro
));
1384 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1385 pointed to by SD_IT to unresolved state. */
1387 sd_unresolve_dep (sd_iterator_def sd_it
)
1389 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1390 dep_t dep
= DEP_NODE_DEP (node
);
1391 rtx_insn
*pro
= DEP_PRO (dep
);
1392 rtx_insn
*con
= DEP_CON (dep
);
1394 if (dep_spec_p (dep
))
1395 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1396 INSN_SPEC_BACK_DEPS (con
));
1398 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1399 INSN_HARD_BACK_DEPS (con
));
1401 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1402 INSN_FORW_DEPS (pro
));
1405 /* Make TO depend on all the FROM's producers.
1406 If RESOLVED_P is true add dependencies to the resolved lists. */
1408 sd_copy_back_deps (rtx_insn
*to
, rtx_insn
*from
, bool resolved_p
)
1410 sd_list_types_def list_type
;
1411 sd_iterator_def sd_it
;
1414 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1416 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1418 dep_def _new_dep
, *new_dep
= &_new_dep
;
1420 copy_dep (new_dep
, dep
);
1421 DEP_CON (new_dep
) = to
;
1422 sd_add_dep (new_dep
, resolved_p
);
1426 /* Remove a dependency referred to by SD_IT.
1427 SD_IT will point to the next dependence after removal. */
1429 sd_delete_dep (sd_iterator_def sd_it
)
1431 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1432 dep_t dep
= DEP_NODE_DEP (n
);
1433 rtx_insn
*pro
= DEP_PRO (dep
);
1434 rtx_insn
*con
= DEP_CON (dep
);
1435 deps_list_t con_back_deps
;
1436 deps_list_t pro_forw_deps
;
1438 if (true_dependency_cache
!= NULL
)
1440 int elem_luid
= INSN_LUID (pro
);
1441 int insn_luid
= INSN_LUID (con
);
1443 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1444 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1445 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1446 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1448 if (current_sched_info
->flags
& DO_SPECULATION
)
1449 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1452 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1453 &con_back_deps
, &pro_forw_deps
);
1455 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1456 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1458 delete_dep_node (n
);
1461 /* Dump size of the lists. */
1462 #define DUMP_LISTS_SIZE (2)
1464 /* Dump dependencies of the lists. */
1465 #define DUMP_LISTS_DEPS (4)
1467 /* Dump all information about the lists. */
1468 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1470 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1471 FLAGS is a bit mask specifying what information about the lists needs
1473 If FLAGS has the very first bit set, then dump all information about
1474 the lists and propagate this bit into the callee dump functions. */
1476 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1478 sd_iterator_def sd_it
;
1485 flags
|= DUMP_LISTS_ALL
;
1487 fprintf (dump
, "[");
1489 if (flags
& DUMP_LISTS_SIZE
)
1490 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1492 if (flags
& DUMP_LISTS_DEPS
)
1494 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1496 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1497 fprintf (dump
, " ");
1502 /* Dump all information about deps_lists of INSN specified by TYPES
1505 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1507 dump_lists (stderr
, insn
, types
, 1);
1508 fprintf (stderr
, "\n");
1511 /* A wrapper around add_dependence_1, to add a dependence of CON on
1512 PRO, with type DEP_TYPE. This function implements special handling
1513 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1514 the type to REG_DEP_ANTI if we can determine that predication is
1515 impossible; otherwise we add additional true dependencies on the
1516 INSN_COND_DEPS list of the jump (which PRO must be). */
1518 add_dependence (rtx_insn
*con
, rtx_insn
*pro
, enum reg_note dep_type
)
1520 if (dep_type
== REG_DEP_CONTROL
1521 && !(current_sched_info
->flags
& DO_PREDICATION
))
1522 dep_type
= REG_DEP_ANTI
;
1524 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1525 so we must also make the insn dependent on the setter of the
1527 if (dep_type
== REG_DEP_CONTROL
)
1529 rtx_insn
*real_pro
= pro
;
1530 rtx_insn
*other
= real_insn_for_shadow (real_pro
);
1533 if (other
!= NULL_RTX
)
1535 cond
= sched_get_reverse_condition_uncached (real_pro
);
1536 /* Verify that the insn does not use a different value in
1537 the condition register than the one that was present at
1539 if (cond
== NULL_RTX
)
1540 dep_type
= REG_DEP_ANTI
;
1541 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1544 CLEAR_HARD_REG_SET (uses
);
1545 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1546 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1547 dep_type
= REG_DEP_ANTI
;
1549 if (dep_type
== REG_DEP_CONTROL
)
1551 if (sched_verbose
>= 5)
1552 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1553 INSN_UID (real_pro
));
1554 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1555 REG_DEP_TRUE
, false);
1559 add_dependence_1 (con
, pro
, dep_type
);
1562 /* A convenience wrapper to operate on an entire list. HARD should be
1563 true if DEP_NONREG should be set on newly created dependencies. */
1566 add_dependence_list (rtx_insn
*insn
, rtx_insn_list
*list
, int uncond
,
1567 enum reg_note dep_type
, bool hard
)
1569 mark_as_hard
= hard
;
1570 for (; list
; list
= list
->next ())
1572 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, list
->insn ()))
1573 add_dependence (insn
, list
->insn (), dep_type
);
1575 mark_as_hard
= false;
1578 /* Similar, but free *LISTP at the same time, when the context
1579 is not readonly. HARD should be true if DEP_NONREG should be set on
1580 newly created dependencies. */
1583 add_dependence_list_and_free (struct deps_desc
*deps
, rtx_insn
*insn
,
1584 rtx_insn_list
**listp
,
1585 int uncond
, enum reg_note dep_type
, bool hard
)
1587 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1589 /* We don't want to short-circuit dependencies involving debug
1590 insns, because they may cause actual dependencies to be
1592 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1595 free_INSN_LIST_list (listp
);
1598 /* Remove all occurrences of INSN from LIST. Return the number of
1599 occurrences removed. */
1602 remove_from_dependence_list (rtx insn
, rtx_insn_list
**listp
)
1608 if ((*listp
)->insn () == insn
)
1610 remove_free_INSN_LIST_node (listp
);
1615 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1621 /* Same as above, but process two lists at once. */
1623 remove_from_both_dependence_lists (rtx insn
,
1624 rtx_insn_list
**listp
,
1625 rtx_expr_list
**exprp
)
1631 if (XEXP (*listp
, 0) == insn
)
1633 remove_free_INSN_LIST_node (listp
);
1634 remove_free_EXPR_LIST_node (exprp
);
1639 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1640 exprp
= (rtx_expr_list
**)&XEXP (*exprp
, 1);
1646 /* Clear all dependencies for an insn. */
1648 delete_all_dependences (rtx insn
)
1650 sd_iterator_def sd_it
;
1653 /* The below cycle can be optimized to clear the caches and back_deps
1654 in one call but that would provoke duplication of code from
1657 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1658 sd_iterator_cond (&sd_it
, &dep
);)
1659 sd_delete_dep (sd_it
);
1662 /* All insns in a scheduling group except the first should only have
1663 dependencies on the previous insn in the group. So we find the
1664 first instruction in the scheduling group by walking the dependence
1665 chains backwards. Then we add the dependencies for the group to
1666 the previous nonnote insn. */
1669 chain_to_prev_insn (rtx_insn
*insn
)
1671 sd_iterator_def sd_it
;
1673 rtx_insn
*prev_nonnote
;
1675 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1678 rtx_insn
*pro
= DEP_PRO (dep
);
1682 i
= prev_nonnote_insn (i
);
1686 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1688 if (! sched_insns_conditions_mutex_p (i
, pro
))
1689 add_dependence (i
, pro
, DEP_TYPE (dep
));
1693 delete_all_dependences (insn
);
1695 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1696 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1697 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1698 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1701 /* Process an insn's memory dependencies. There are four kinds of
1704 (0) read dependence: read follows read
1705 (1) true dependence: read follows write
1706 (2) output dependence: write follows write
1707 (3) anti dependence: write follows read
1709 We are careful to build only dependencies which actually exist, and
1710 use transitivity to avoid building too many links. */
1712 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1713 The MEM is a memory reference contained within INSN, which we are saving
1714 so that we can do memory aliasing on it. */
1717 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1718 rtx_insn
*insn
, rtx mem
)
1720 rtx_insn_list
**insn_list
;
1721 rtx_insn_list
*insn_node
;
1722 rtx_expr_list
**mem_list
;
1723 rtx_expr_list
*mem_node
;
1725 gcc_assert (!deps
->readonly
);
1728 insn_list
= &deps
->pending_read_insns
;
1729 mem_list
= &deps
->pending_read_mems
;
1730 if (!DEBUG_INSN_P (insn
))
1731 deps
->pending_read_list_length
++;
1735 insn_list
= &deps
->pending_write_insns
;
1736 mem_list
= &deps
->pending_write_mems
;
1737 deps
->pending_write_list_length
++;
1740 insn_node
= alloc_INSN_LIST (insn
, *insn_list
);
1741 *insn_list
= insn_node
;
1743 if (sched_deps_info
->use_cselib
)
1745 mem
= shallow_copy_rtx (mem
);
1746 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1747 GET_MODE (mem
), insn
);
1749 mem_node
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1750 *mem_list
= mem_node
;
1753 /* Make a dependency between every memory reference on the pending lists
1754 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1755 dependencies for a read operation, similarly with FOR_WRITE. */
1758 flush_pending_lists (struct deps_desc
*deps
, rtx_insn
*insn
, int for_read
,
1763 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1764 1, REG_DEP_ANTI
, true);
1765 if (!deps
->readonly
)
1767 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1768 deps
->pending_read_list_length
= 0;
1772 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1773 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1776 add_dependence_list_and_free (deps
, insn
,
1777 &deps
->last_pending_memory_flush
, 1,
1778 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1781 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1782 REG_DEP_ANTI
, true);
1784 if (DEBUG_INSN_P (insn
))
1787 free_INSN_LIST_list (&deps
->pending_read_insns
);
1788 free_INSN_LIST_list (&deps
->pending_write_insns
);
1789 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1790 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1793 if (!deps
->readonly
)
1795 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1796 deps
->pending_write_list_length
= 0;
1798 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1799 deps
->pending_flush_length
= 1;
1801 mark_as_hard
= false;
1804 /* Instruction which dependencies we are analyzing. */
1805 static rtx_insn
*cur_insn
= NULL
;
1807 /* Implement hooks for haifa scheduler. */
1810 haifa_start_insn (rtx_insn
*insn
)
1812 gcc_assert (insn
&& !cur_insn
);
1818 haifa_finish_insn (void)
1824 haifa_note_reg_set (int regno
)
1826 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1830 haifa_note_reg_clobber (int regno
)
1832 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1836 haifa_note_reg_use (int regno
)
1838 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1842 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx_insn
*pending_insn
, ds_t ds
)
1844 if (!(ds
& SPECULATIVE
))
1847 pending_mem
= NULL_RTX
;
1850 gcc_assert (ds
& BEGIN_DATA
);
1853 dep_def _dep
, *dep
= &_dep
;
1855 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1856 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1857 DEP_NONREG (dep
) = 1;
1858 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1864 haifa_note_dep (rtx_insn
*elem
, ds_t ds
)
1869 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1871 DEP_NONREG (dep
) = 1;
1872 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1876 note_reg_use (int r
)
1878 if (sched_deps_info
->note_reg_use
)
1879 sched_deps_info
->note_reg_use (r
);
1883 note_reg_set (int r
)
1885 if (sched_deps_info
->note_reg_set
)
1886 sched_deps_info
->note_reg_set (r
);
1890 note_reg_clobber (int r
)
1892 if (sched_deps_info
->note_reg_clobber
)
1893 sched_deps_info
->note_reg_clobber (r
);
1897 note_mem_dep (rtx m1
, rtx m2
, rtx_insn
*e
, ds_t ds
)
1899 if (sched_deps_info
->note_mem_dep
)
1900 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1904 note_dep (rtx_insn
*e
, ds_t ds
)
1906 if (sched_deps_info
->note_dep
)
1907 sched_deps_info
->note_dep (e
, ds
);
1910 /* Return corresponding to DS reg_note. */
1915 return REG_DEP_TRUE
;
1916 else if (ds
& DEP_OUTPUT
)
1917 return REG_DEP_OUTPUT
;
1918 else if (ds
& DEP_ANTI
)
1919 return REG_DEP_ANTI
;
1922 gcc_assert (ds
& DEP_CONTROL
);
1923 return REG_DEP_CONTROL
;
1929 /* Functions for computation of info needed for register pressure
1930 sensitive insn scheduling. */
1933 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1934 static struct reg_use_data
*
1935 create_insn_reg_use (int regno
, rtx_insn
*insn
)
1937 struct reg_use_data
*use
;
1939 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1942 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1943 INSN_REG_USE_LIST (insn
) = use
;
1947 /* Allocate reg_set_data structure for REGNO and INSN. */
1949 create_insn_reg_set (int regno
, rtx insn
)
1951 struct reg_set_data
*set
;
1953 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1956 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1957 INSN_REG_SET_LIST (insn
) = set
;
1960 /* Set up insn register uses for INSN and dependency context DEPS. */
1962 setup_insn_reg_uses (struct deps_desc
*deps
, rtx_insn
*insn
)
1965 reg_set_iterator rsi
;
1967 struct reg_use_data
*use
, *use2
, *next
;
1968 struct deps_reg
*reg_last
;
1970 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1972 if (i
< FIRST_PSEUDO_REGISTER
1973 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1976 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1977 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1978 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1979 /* Ignore use which is not dying. */
1982 use
= create_insn_reg_use (i
, insn
);
1983 use
->next_regno_use
= use
;
1984 reg_last
= &deps
->reg_last
[i
];
1986 /* Create the cycle list of uses. */
1987 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1989 use2
= create_insn_reg_use (i
, as_a
<rtx_insn
*> (XEXP (list
, 0)));
1990 next
= use
->next_regno_use
;
1991 use
->next_regno_use
= use2
;
1992 use2
->next_regno_use
= next
;
1997 /* Register pressure info for the currently processed insn. */
1998 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
2000 /* Return TRUE if INSN has the use structure for REGNO. */
2002 insn_use_p (rtx insn
, int regno
)
2004 struct reg_use_data
*use
;
2006 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2007 if (use
->regno
== regno
)
2012 /* Update the register pressure info after birth of pseudo register REGNO
2013 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2014 the register is in clobber or unused after the insn. */
2016 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2021 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2022 cl
= sched_regno_pressure_class
[regno
];
2025 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2028 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2029 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2033 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2034 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2038 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2039 reg_pressure_info
[cl
].set_increase
= new_incr
;
2040 if (! insn_use_p (insn
, regno
))
2041 reg_pressure_info
[cl
].change
+= incr
;
2042 create_insn_reg_set (regno
, insn
);
2044 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2048 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2049 hard registers involved in the birth. */
2051 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2052 bool clobber_p
, bool unused_p
)
2055 int new_incr
, last
= regno
+ nregs
;
2057 while (regno
< last
)
2059 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2060 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2062 cl
= sched_regno_pressure_class
[regno
];
2067 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2068 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2072 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2073 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2077 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2078 reg_pressure_info
[cl
].set_increase
= new_incr
;
2079 if (! insn_use_p (insn
, regno
))
2080 reg_pressure_info
[cl
].change
+= 1;
2081 create_insn_reg_set (regno
, insn
);
2083 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2090 /* Update the register pressure info after birth of pseudo or hard
2091 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2092 correspondingly that the register is in clobber or unused after the
2095 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2099 if (GET_CODE (reg
) == SUBREG
)
2100 reg
= SUBREG_REG (reg
);
2105 regno
= REGNO (reg
);
2106 if (regno
< FIRST_PSEUDO_REGISTER
)
2107 mark_insn_hard_regno_birth (insn
, regno
,
2108 hard_regno_nregs
[regno
][GET_MODE (reg
)],
2109 clobber_p
, unused_p
);
2111 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2114 /* Update the register pressure info after death of pseudo register
2117 mark_pseudo_death (int regno
)
2122 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2123 cl
= sched_regno_pressure_class
[regno
];
2126 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2127 reg_pressure_info
[cl
].change
-= incr
;
2131 /* Like mark_pseudo_death except that NREGS saying how many hard
2132 registers involved in the death. */
2134 mark_hard_regno_death (int regno
, int nregs
)
2137 int last
= regno
+ nregs
;
2139 while (regno
< last
)
2141 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2142 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2144 cl
= sched_regno_pressure_class
[regno
];
2146 reg_pressure_info
[cl
].change
-= 1;
2152 /* Update the register pressure info after death of pseudo or hard
2155 mark_reg_death (rtx reg
)
2159 if (GET_CODE (reg
) == SUBREG
)
2160 reg
= SUBREG_REG (reg
);
2165 regno
= REGNO (reg
);
2166 if (regno
< FIRST_PSEUDO_REGISTER
)
2167 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
2169 mark_pseudo_death (regno
);
2172 /* Process SETTER of REG. DATA is an insn containing the setter. */
2174 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2176 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2179 ((rtx
) data
, reg
, false,
2180 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2183 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2185 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2187 if (GET_CODE (setter
) == CLOBBER
)
2188 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2191 /* Set up reg pressure info related to INSN. */
2193 init_insn_reg_pressure_info (rtx insn
)
2197 static struct reg_pressure_data
*pressure_info
;
2200 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2202 if (! INSN_P (insn
))
2205 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2207 cl
= ira_pressure_classes
[i
];
2208 reg_pressure_info
[cl
].clobber_increase
= 0;
2209 reg_pressure_info
[cl
].set_increase
= 0;
2210 reg_pressure_info
[cl
].unused_set_increase
= 0;
2211 reg_pressure_info
[cl
].change
= 0;
2214 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2216 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2219 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2220 if (REG_NOTE_KIND (link
) == REG_INC
)
2221 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2224 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2225 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2226 mark_reg_death (XEXP (link
, 0));
2228 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2230 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2231 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2232 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2234 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2236 cl
= ira_pressure_classes
[i
];
2237 pressure_info
[i
].clobber_increase
2238 = reg_pressure_info
[cl
].clobber_increase
;
2239 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2240 pressure_info
[i
].unused_set_increase
2241 = reg_pressure_info
[cl
].unused_set_increase
;
2242 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2249 /* Internal variable for sched_analyze_[12] () functions.
2250 If it is nonzero, this means that sched_analyze_[12] looks
2251 at the most toplevel SET. */
2252 static bool can_start_lhs_rhs_p
;
2254 /* Extend reg info for the deps context DEPS given that
2255 we have just generated a register numbered REGNO. */
2257 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2259 int max_regno
= regno
+ 1;
2261 gcc_assert (!reload_completed
);
2263 /* In a readonly context, it would not hurt to extend info,
2264 but it should not be needed. */
2265 if (reload_completed
&& deps
->readonly
)
2267 deps
->max_reg
= max_regno
;
2271 if (max_regno
> deps
->max_reg
)
2273 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2275 memset (&deps
->reg_last
[deps
->max_reg
],
2276 0, (max_regno
- deps
->max_reg
)
2277 * sizeof (struct deps_reg
));
2278 deps
->max_reg
= max_regno
;
2282 /* Extends REG_INFO_P if needed. */
2284 maybe_extend_reg_info_p (void)
2286 /* Extend REG_INFO_P, if needed. */
2287 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2289 size_t new_reg_info_p_size
= max_regno
+ 128;
2291 gcc_assert (!reload_completed
&& sel_sched_p ());
2293 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2294 new_reg_info_p_size
,
2296 sizeof (*reg_info_p
));
2297 reg_info_p_size
= new_reg_info_p_size
;
2301 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2302 The type of the reference is specified by REF and can be SET,
2303 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2306 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2307 enum rtx_code ref
, rtx_insn
*insn
)
2309 /* We could emit new pseudos in renaming. Extend the reg structures. */
2310 if (!reload_completed
&& sel_sched_p ()
2311 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2312 extend_deps_reg_info (deps
, regno
);
2314 maybe_extend_reg_info_p ();
2316 /* A hard reg in a wide mode may really be multiple registers.
2317 If so, mark all of them just like the first. */
2318 if (regno
< FIRST_PSEUDO_REGISTER
)
2320 int i
= hard_regno_nregs
[regno
][mode
];
2324 note_reg_set (regno
+ i
);
2326 else if (ref
== USE
)
2329 note_reg_use (regno
+ i
);
2334 note_reg_clobber (regno
+ i
);
2338 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2339 it does not reload. Ignore these as they have served their
2341 else if (regno
>= deps
->max_reg
)
2343 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2344 gcc_assert (code
== USE
|| code
== CLOBBER
);
2350 note_reg_set (regno
);
2351 else if (ref
== USE
)
2352 note_reg_use (regno
);
2354 note_reg_clobber (regno
);
2356 /* Pseudos that are REG_EQUIV to something may be replaced
2357 by that during reloading. We need only add dependencies for
2358 the address in the REG_EQUIV note. */
2359 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2361 rtx t
= get_reg_known_value (regno
);
2363 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2366 /* Don't let it cross a call after scheduling if it doesn't
2367 already cross one. */
2368 if (REG_N_CALLS_CROSSED (regno
) == 0)
2370 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2371 deps
->sched_before_next_call
2372 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2374 add_dependence_list (insn
, deps
->last_function_call
, 1,
2375 REG_DEP_ANTI
, false);
2380 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2381 rtx, X, creating all dependencies generated by the write to the
2382 destination of X, and reads of everything mentioned. */
2385 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2387 rtx dest
= XEXP (x
, 0);
2388 enum rtx_code code
= GET_CODE (x
);
2389 bool cslr_p
= can_start_lhs_rhs_p
;
2391 can_start_lhs_rhs_p
= false;
2397 if (cslr_p
&& sched_deps_info
->start_lhs
)
2398 sched_deps_info
->start_lhs (dest
);
2400 if (GET_CODE (dest
) == PARALLEL
)
2404 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2405 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2406 sched_analyze_1 (deps
,
2407 gen_rtx_CLOBBER (VOIDmode
,
2408 XEXP (XVECEXP (dest
, 0, i
), 0)),
2411 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2412 sched_deps_info
->finish_lhs ();
2416 can_start_lhs_rhs_p
= cslr_p
;
2418 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2420 can_start_lhs_rhs_p
= false;
2426 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2427 || GET_CODE (dest
) == ZERO_EXTRACT
)
2429 if (GET_CODE (dest
) == STRICT_LOW_PART
2430 || GET_CODE (dest
) == ZERO_EXTRACT
2431 || df_read_modify_subreg_p (dest
))
2433 /* These both read and modify the result. We must handle
2434 them as writes to get proper dependencies for following
2435 instructions. We must handle them as reads to get proper
2436 dependencies from this to previous instructions.
2437 Thus we need to call sched_analyze_2. */
2439 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2441 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2443 /* The second and third arguments are values read by this insn. */
2444 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2445 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2447 dest
= XEXP (dest
, 0);
2452 int regno
= REGNO (dest
);
2453 enum machine_mode mode
= GET_MODE (dest
);
2455 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2458 /* Treat all writes to a stack register as modifying the TOS. */
2459 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2461 /* Avoid analyzing the same register twice. */
2462 if (regno
!= FIRST_STACK_REG
)
2463 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2465 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2470 else if (MEM_P (dest
))
2472 /* Writing memory. */
2475 if (sched_deps_info
->use_cselib
)
2477 enum machine_mode address_mode
= get_address_mode (dest
);
2479 t
= shallow_copy_rtx (dest
);
2480 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2481 GET_MODE (t
), insn
);
2483 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2488 /* Pending lists can't get larger with a readonly context. */
2490 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2491 > MAX_PENDING_LIST_LENGTH
))
2493 /* Flush all pending reads and writes to prevent the pending lists
2494 from getting any larger. Insn scheduling runs too slowly when
2495 these lists get long. When compiling GCC with itself,
2496 this flush occurs 8 times for sparc, and 10 times for m88k using
2497 the default value of 32. */
2498 flush_pending_lists (deps
, insn
, false, true);
2502 rtx pending
, pending_mem
;
2504 pending
= deps
->pending_read_insns
;
2505 pending_mem
= deps
->pending_read_mems
;
2508 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2509 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2510 note_mem_dep (t
, XEXP (pending_mem
, 0), as_a
<rtx_insn
*> (XEXP (pending
, 0)),
2513 pending
= XEXP (pending
, 1);
2514 pending_mem
= XEXP (pending_mem
, 1);
2517 pending
= deps
->pending_write_insns
;
2518 pending_mem
= deps
->pending_write_mems
;
2521 if (output_dependence (XEXP (pending_mem
, 0), t
)
2522 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2523 note_mem_dep (t
, XEXP (pending_mem
, 0),
2524 as_a
<rtx_insn
*> (XEXP (pending
, 0)),
2527 pending
= XEXP (pending
, 1);
2528 pending_mem
= XEXP (pending_mem
, 1);
2531 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2532 REG_DEP_ANTI
, true);
2533 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2534 REG_DEP_CONTROL
, true);
2536 if (!deps
->readonly
)
2537 add_insn_mem_dependence (deps
, false, insn
, dest
);
2539 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2542 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2543 sched_deps_info
->finish_lhs ();
2545 /* Analyze reads. */
2546 if (GET_CODE (x
) == SET
)
2548 can_start_lhs_rhs_p
= cslr_p
;
2550 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2552 can_start_lhs_rhs_p
= false;
2556 /* Analyze the uses of memory and registers in rtx X in INSN. */
2558 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2564 bool cslr_p
= can_start_lhs_rhs_p
;
2566 can_start_lhs_rhs_p
= false;
2572 if (cslr_p
&& sched_deps_info
->start_rhs
)
2573 sched_deps_info
->start_rhs (x
);
2575 code
= GET_CODE (x
);
2583 /* Ignore constants. */
2584 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2585 sched_deps_info
->finish_rhs ();
2591 /* User of CC0 depends on immediately preceding insn. */
2592 SCHED_GROUP_P (insn
) = 1;
2593 /* Don't move CC0 setter to another block (it can set up the
2594 same flag for previous CC0 users which is safe). */
2595 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2597 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2598 sched_deps_info
->finish_rhs ();
2605 int regno
= REGNO (x
);
2606 enum machine_mode mode
= GET_MODE (x
);
2608 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2611 /* Treat all reads of a stack register as modifying the TOS. */
2612 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2614 /* Avoid analyzing the same register twice. */
2615 if (regno
!= FIRST_STACK_REG
)
2616 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2617 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2621 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2622 sched_deps_info
->finish_rhs ();
2629 /* Reading memory. */
2631 rtx pending
, pending_mem
;
2634 if (sched_deps_info
->use_cselib
)
2636 enum machine_mode address_mode
= get_address_mode (t
);
2638 t
= shallow_copy_rtx (t
);
2639 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2640 GET_MODE (t
), insn
);
2642 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2646 if (!DEBUG_INSN_P (insn
))
2649 pending
= deps
->pending_read_insns
;
2650 pending_mem
= deps
->pending_read_mems
;
2653 if (read_dependence (XEXP (pending_mem
, 0), t
)
2654 && ! sched_insns_conditions_mutex_p (insn
,
2656 note_mem_dep (t
, XEXP (pending_mem
, 0),
2657 as_a
<rtx_insn
*> (XEXP (pending
, 0)),
2660 pending
= XEXP (pending
, 1);
2661 pending_mem
= XEXP (pending_mem
, 1);
2664 pending
= deps
->pending_write_insns
;
2665 pending_mem
= deps
->pending_write_mems
;
2668 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
, t
)
2669 && ! sched_insns_conditions_mutex_p (insn
,
2671 note_mem_dep (t
, XEXP (pending_mem
, 0),
2672 as_a
<rtx_insn
*> (XEXP (pending
, 0)),
2673 sched_deps_info
->generate_spec_deps
2674 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2676 pending
= XEXP (pending
, 1);
2677 pending_mem
= XEXP (pending_mem
, 1);
2680 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2681 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)),
2684 for (u
= deps
->pending_jump_insns
; u
; u
= XEXP (u
, 1))
2685 if (deps_may_trap_p (x
))
2687 if ((sched_deps_info
->generate_spec_deps
)
2688 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2690 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2693 note_dep (as_a
<rtx_insn
*> (XEXP (u
, 0)), ds
);
2696 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)),
2701 /* Always add these dependencies to pending_reads, since
2702 this insn may be followed by a write. */
2703 if (!deps
->readonly
)
2705 if ((deps
->pending_read_list_length
2706 + deps
->pending_write_list_length
)
2707 > MAX_PENDING_LIST_LENGTH
2708 && !DEBUG_INSN_P (insn
))
2709 flush_pending_lists (deps
, insn
, true, true);
2710 add_insn_mem_dependence (deps
, true, insn
, x
);
2713 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2715 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2716 sched_deps_info
->finish_rhs ();
2721 /* Force pending stores to memory in case a trap handler needs them. */
2723 flush_pending_lists (deps
, insn
, true, false);
2727 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2728 reg_pending_barrier
= TRUE_BARRIER
;
2729 /* Prefetch insn contains addresses only. So if the prefetch
2730 address has no registers, there will be no dependencies on
2731 the prefetch insn. This is wrong with result code
2732 correctness point of view as such prefetch can be moved below
2733 a jump insn which usually generates MOVE_BARRIER preventing
2734 to move insns containing registers or memories through the
2735 barrier. It is also wrong with generated code performance
2736 point of view as prefetch withouth dependecies will have a
2737 tendency to be issued later instead of earlier. It is hard
2738 to generate accurate dependencies for prefetch insns as
2739 prefetch has only the start address but it is better to have
2740 something than nothing. */
2741 if (!deps
->readonly
)
2743 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2744 if (sched_deps_info
->use_cselib
)
2745 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2746 add_insn_mem_dependence (deps
, true, insn
, x
);
2750 case UNSPEC_VOLATILE
:
2751 flush_pending_lists (deps
, insn
, true, true);
2757 /* Traditional and volatile asm instructions must be considered to use
2758 and clobber all hard registers, all pseudo-registers and all of
2759 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2761 Consider for instance a volatile asm that changes the fpu rounding
2762 mode. An insn should not be moved across this even if it only uses
2763 pseudo-regs because it might give an incorrectly rounded result. */
2764 if ((code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2765 && !DEBUG_INSN_P (insn
))
2766 reg_pending_barrier
= TRUE_BARRIER
;
2768 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2769 We can not just fall through here since then we would be confused
2770 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2771 traditional asms unlike their normal usage. */
2773 if (code
== ASM_OPERANDS
)
2775 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2776 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2778 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2779 sched_deps_info
->finish_rhs ();
2790 /* These both read and modify the result. We must handle them as writes
2791 to get proper dependencies for following instructions. We must handle
2792 them as reads to get proper dependencies from this to previous
2793 instructions. Thus we need to pass them to both sched_analyze_1
2794 and sched_analyze_2. We must call sched_analyze_2 first in order
2795 to get the proper antecedent for the read. */
2796 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2797 sched_analyze_1 (deps
, x
, insn
);
2799 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2800 sched_deps_info
->finish_rhs ();
2806 /* op0 = op0 + op1 */
2807 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2808 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2809 sched_analyze_1 (deps
, x
, insn
);
2811 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2812 sched_deps_info
->finish_rhs ();
2820 /* Other cases: walk the insn. */
2821 fmt
= GET_RTX_FORMAT (code
);
2822 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2825 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2826 else if (fmt
[i
] == 'E')
2827 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2828 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2831 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2832 sched_deps_info
->finish_rhs ();
2835 /* Try to group two fuseable insns together to prevent scheduler
2836 from scheduling them apart. */
2839 sched_macro_fuse_insns (rtx_insn
*insn
)
2843 if (any_condjump_p (insn
))
2845 unsigned int condreg1
, condreg2
;
2847 targetm
.fixed_condition_code_regs (&condreg1
, &condreg2
);
2848 cc_reg_1
= gen_rtx_REG (CCmode
, condreg1
);
2849 prev
= prev_nonnote_nondebug_insn (insn
);
2850 if (!reg_referenced_p (cc_reg_1
, PATTERN (insn
))
2852 || !modified_in_p (cc_reg_1
, prev
))
2857 rtx insn_set
= single_set (insn
);
2859 prev
= prev_nonnote_nondebug_insn (insn
);
2862 || !single_set (prev
)
2863 || !modified_in_p (SET_DEST (insn_set
), prev
))
2868 if (targetm
.sched
.macro_fusion_pair_p (prev
, insn
))
2869 SCHED_GROUP_P (insn
) = 1;
2873 /* Analyze an INSN with pattern X to find all dependencies. */
2875 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2877 RTX_CODE code
= GET_CODE (x
);
2880 reg_set_iterator rsi
;
2882 if (! reload_completed
)
2886 extract_insn (insn
);
2887 preprocess_constraints (insn
);
2888 ira_implicitly_set_insn_hard_regs (&temp
);
2889 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2890 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2893 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2896 /* Group compare and branch insns for macro-fusion. */
2897 if (targetm
.sched
.macro_fusion_p
2898 && targetm
.sched
.macro_fusion_p ())
2899 sched_macro_fuse_insns (insn
);
2902 /* Avoid moving trapping instructions across function calls that might
2903 not always return. */
2904 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2905 1, REG_DEP_ANTI
, true);
2907 /* We must avoid creating a situation in which two successors of the
2908 current block have different unwind info after scheduling. If at any
2909 point the two paths re-join this leads to incorrect unwind info. */
2910 /* ??? There are certain situations involving a forced frame pointer in
2911 which, with extra effort, we could fix up the unwind info at a later
2912 CFG join. However, it seems better to notice these cases earlier
2913 during prologue generation and avoid marking the frame pointer setup
2914 as frame-related at all. */
2915 if (RTX_FRAME_RELATED_P (insn
))
2917 /* Make sure prologue insn is scheduled before next jump. */
2918 deps
->sched_before_next_jump
2919 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2921 /* Make sure epilogue insn is scheduled after preceding jumps. */
2922 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2926 if (code
== COND_EXEC
)
2928 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2930 /* ??? Should be recording conditions so we reduce the number of
2931 false dependencies. */
2932 x
= COND_EXEC_CODE (x
);
2933 code
= GET_CODE (x
);
2935 if (code
== SET
|| code
== CLOBBER
)
2937 sched_analyze_1 (deps
, x
, insn
);
2939 /* Bare clobber insns are used for letting life analysis, reg-stack
2940 and others know that a value is dead. Depend on the last call
2941 instruction so that reg-stack won't get confused. */
2942 if (code
== CLOBBER
)
2943 add_dependence_list (insn
, deps
->last_function_call
, 1,
2944 REG_DEP_OUTPUT
, true);
2946 else if (code
== PARALLEL
)
2948 for (i
= XVECLEN (x
, 0); i
--;)
2950 rtx sub
= XVECEXP (x
, 0, i
);
2951 code
= GET_CODE (sub
);
2953 if (code
== COND_EXEC
)
2955 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2956 sub
= COND_EXEC_CODE (sub
);
2957 code
= GET_CODE (sub
);
2959 if (code
== SET
|| code
== CLOBBER
)
2960 sched_analyze_1 (deps
, sub
, insn
);
2962 sched_analyze_2 (deps
, sub
, insn
);
2966 sched_analyze_2 (deps
, x
, insn
);
2968 /* Mark registers CLOBBERED or used by called function. */
2971 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2973 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2974 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2975 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2976 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2978 /* Don't schedule anything after a tail call, tail call needs
2979 to use at least all call-saved registers. */
2980 if (SIBLING_CALL_P (insn
))
2981 reg_pending_barrier
= TRUE_BARRIER
;
2982 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2983 reg_pending_barrier
= MOVE_BARRIER
;
2989 next
= next_nonnote_nondebug_insn (insn
);
2990 if (next
&& BARRIER_P (next
))
2991 reg_pending_barrier
= MOVE_BARRIER
;
2994 rtx pending
, pending_mem
;
2996 if (sched_deps_info
->compute_jump_reg_dependencies
)
2998 (*sched_deps_info
->compute_jump_reg_dependencies
)
2999 (insn
, reg_pending_control_uses
);
3001 /* Make latency of jump equal to 0 by using anti-dependence. */
3002 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3004 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3005 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
3007 add_dependence_list (insn
, reg_last
->implicit_sets
,
3008 0, REG_DEP_ANTI
, false);
3009 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3010 REG_DEP_ANTI
, false);
3014 /* All memory writes and volatile reads must happen before the
3015 jump. Non-volatile reads must happen before the jump iff
3016 the result is needed by the above register used mask. */
3018 pending
= deps
->pending_write_insns
;
3019 pending_mem
= deps
->pending_write_mems
;
3022 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
3023 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (pending
, 0)),
3025 pending
= XEXP (pending
, 1);
3026 pending_mem
= XEXP (pending_mem
, 1);
3029 pending
= deps
->pending_read_insns
;
3030 pending_mem
= deps
->pending_read_mems
;
3033 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
3034 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
3035 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (pending
, 0)),
3037 pending
= XEXP (pending
, 1);
3038 pending_mem
= XEXP (pending_mem
, 1);
3041 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
3042 REG_DEP_ANTI
, true);
3043 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
3044 REG_DEP_ANTI
, true);
3048 /* If this instruction can throw an exception, then moving it changes
3049 where block boundaries fall. This is mighty confusing elsewhere.
3050 Therefore, prevent such an instruction from being moved. Same for
3051 non-jump instructions that define block boundaries.
3052 ??? Unclear whether this is still necessary in EBB mode. If not,
3053 add_branch_dependences should be adjusted for RGN mode instead. */
3054 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
3055 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
3056 reg_pending_barrier
= MOVE_BARRIER
;
3058 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
3060 setup_insn_reg_uses (deps
, insn
);
3061 init_insn_reg_pressure_info (insn
);
3064 /* Add register dependencies for insn. */
3065 if (DEBUG_INSN_P (insn
))
3067 rtx_insn
*prev
= deps
->last_debug_insn
;
3070 if (!deps
->readonly
)
3071 deps
->last_debug_insn
= insn
;
3074 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3076 add_dependence_list (insn
, deps
->last_function_call
, 1,
3077 REG_DEP_ANTI
, false);
3079 if (!sel_sched_p ())
3080 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3081 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)), REG_DEP_ANTI
);
3083 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3085 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3086 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3087 /* There's no point in making REG_DEP_CONTROL dependencies for
3089 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3092 if (!deps
->readonly
)
3093 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3095 CLEAR_REG_SET (reg_pending_uses
);
3097 /* Quite often, a debug insn will refer to stuff in the
3098 previous instruction, but the reason we want this
3099 dependency here is to make sure the scheduler doesn't
3100 gratuitously move a debug insn ahead. This could dirty
3101 DF flags and cause additional analysis that wouldn't have
3102 occurred in compilation without debug insns, and such
3103 additional analysis can modify the generated code. */
3104 prev
= PREV_INSN (insn
);
3106 if (prev
&& NONDEBUG_INSN_P (prev
))
3107 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3111 regset_head set_or_clobbered
;
3113 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3115 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3116 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3117 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3119 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3122 if (!deps
->readonly
)
3124 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3125 reg_last
->uses_length
++;
3129 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3130 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3132 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3133 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3134 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3135 REG_DEP_ANTI
, false);
3136 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3139 if (!deps
->readonly
)
3141 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3142 reg_last
->uses_length
++;
3146 if (targetm
.sched
.exposed_pipeline
)
3148 INIT_REG_SET (&set_or_clobbered
);
3149 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3151 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3153 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3155 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3157 rtx other
= XEXP (list
, 0);
3158 if (INSN_CACHED_COND (other
) != const_true_rtx
3159 && refers_to_regno_p (i
, i
+ 1, INSN_CACHED_COND (other
), NULL
))
3160 INSN_CACHED_COND (other
) = const_true_rtx
;
3165 /* If the current insn is conditional, we can't free any
3167 if (sched_has_condition_p (insn
))
3169 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3171 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3172 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3174 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3175 REG_DEP_ANTI
, false);
3176 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3178 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3179 REG_DEP_CONTROL
, false);
3181 if (!deps
->readonly
)
3184 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3185 reg_last
->clobbers_length
++;
3188 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3190 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3191 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3193 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3194 REG_DEP_ANTI
, false);
3195 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3197 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3199 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3200 REG_DEP_CONTROL
, false);
3202 if (!deps
->readonly
)
3203 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3208 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3210 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3211 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
3212 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
3214 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3215 REG_DEP_OUTPUT
, false);
3216 add_dependence_list_and_free (deps
, insn
,
3217 ®_last
->implicit_sets
, 0,
3218 REG_DEP_ANTI
, false);
3219 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3220 REG_DEP_ANTI
, false);
3221 add_dependence_list_and_free (deps
, insn
,
3222 ®_last
->control_uses
, 0,
3223 REG_DEP_ANTI
, false);
3224 add_dependence_list_and_free (deps
, insn
,
3225 ®_last
->clobbers
, 0,
3226 REG_DEP_OUTPUT
, false);
3228 if (!deps
->readonly
)
3230 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3231 reg_last
->clobbers_length
= 0;
3232 reg_last
->uses_length
= 0;
3237 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3239 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3240 REG_DEP_ANTI
, false);
3241 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3243 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3244 REG_DEP_CONTROL
, false);
3247 if (!deps
->readonly
)
3249 reg_last
->clobbers_length
++;
3251 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3254 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3256 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3258 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3259 REG_DEP_OUTPUT
, false);
3260 add_dependence_list_and_free (deps
, insn
,
3261 ®_last
->implicit_sets
,
3262 0, REG_DEP_ANTI
, false);
3263 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3264 REG_DEP_OUTPUT
, false);
3265 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3266 REG_DEP_ANTI
, false);
3267 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3268 REG_DEP_CONTROL
, false);
3270 if (!deps
->readonly
)
3272 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3273 reg_last
->uses_length
= 0;
3274 reg_last
->clobbers_length
= 0;
3278 if (!deps
->readonly
)
3280 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3282 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3283 reg_last
->control_uses
3284 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3289 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3290 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3292 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3293 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3294 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3295 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3296 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3299 if (!deps
->readonly
)
3300 reg_last
->implicit_sets
3301 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3304 if (!deps
->readonly
)
3306 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3307 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3308 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3309 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3310 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3311 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3312 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3314 /* Set up the pending barrier found. */
3315 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3318 CLEAR_REG_SET (reg_pending_uses
);
3319 CLEAR_REG_SET (reg_pending_clobbers
);
3320 CLEAR_REG_SET (reg_pending_sets
);
3321 CLEAR_REG_SET (reg_pending_control_uses
);
3322 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3323 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3325 /* Add dependencies if a scheduling barrier was found. */
3326 if (reg_pending_barrier
)
3328 /* In the case of barrier the most added dependencies are not
3329 real, so we use anti-dependence here. */
3330 if (sched_has_condition_p (insn
))
3332 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3334 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3335 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3337 add_dependence_list (insn
, reg_last
->sets
, 0,
3338 reg_pending_barrier
== TRUE_BARRIER
3339 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3340 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3341 REG_DEP_ANTI
, true);
3342 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3343 reg_pending_barrier
== TRUE_BARRIER
3344 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3349 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3351 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3352 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3353 REG_DEP_ANTI
, true);
3354 add_dependence_list_and_free (deps
, insn
,
3355 ®_last
->control_uses
, 0,
3356 REG_DEP_CONTROL
, true);
3357 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3358 reg_pending_barrier
== TRUE_BARRIER
3359 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3361 add_dependence_list_and_free (deps
, insn
,
3362 ®_last
->implicit_sets
, 0,
3363 REG_DEP_ANTI
, true);
3364 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3365 reg_pending_barrier
== TRUE_BARRIER
3366 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3369 if (!deps
->readonly
)
3371 reg_last
->uses_length
= 0;
3372 reg_last
->clobbers_length
= 0;
3377 if (!deps
->readonly
)
3378 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3380 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3381 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3382 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3385 /* Don't flush pending lists on speculative checks for
3386 selective scheduling. */
3387 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn
))
3388 flush_pending_lists (deps
, insn
, true, true);
3390 reg_pending_barrier
= NOT_A_BARRIER
;
3393 /* If a post-call group is still open, see if it should remain so.
3394 This insn must be a simple move of a hard reg to a pseudo or
3397 We must avoid moving these insns for correctness on targets
3398 with small register classes, and for special registers like
3399 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3400 hard regs for all targets. */
3402 if (deps
->in_post_call_group_p
)
3404 rtx tmp
, set
= single_set (insn
);
3405 int src_regno
, dest_regno
;
3409 if (DEBUG_INSN_P (insn
))
3410 /* We don't want to mark debug insns as part of the same
3411 sched group. We know they really aren't, but if we use
3412 debug insns to tell that a call group is over, we'll
3413 get different code if debug insns are not there and
3414 instructions that follow seem like they should be part
3417 Also, if we did, chain_to_prev_insn would move the
3418 deps of the debug insn to the call insn, modifying
3419 non-debug post-dependency counts of the debug insn
3420 dependencies and otherwise messing with the scheduling
3423 Instead, let such debug insns be scheduled freely, but
3424 keep the call group open in case there are insns that
3425 should be part of it afterwards. Since we grant debug
3426 insns higher priority than even sched group insns, it
3427 will all turn out all right. */
3428 goto debug_dont_end_call_group
;
3430 goto end_call_group
;
3433 tmp
= SET_DEST (set
);
3434 if (GET_CODE (tmp
) == SUBREG
)
3435 tmp
= SUBREG_REG (tmp
);
3437 dest_regno
= REGNO (tmp
);
3439 goto end_call_group
;
3441 tmp
= SET_SRC (set
);
3442 if (GET_CODE (tmp
) == SUBREG
)
3443 tmp
= SUBREG_REG (tmp
);
3444 if ((GET_CODE (tmp
) == PLUS
3445 || GET_CODE (tmp
) == MINUS
)
3446 && REG_P (XEXP (tmp
, 0))
3447 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3448 && dest_regno
== STACK_POINTER_REGNUM
)
3449 src_regno
= STACK_POINTER_REGNUM
;
3450 else if (REG_P (tmp
))
3451 src_regno
= REGNO (tmp
);
3453 goto end_call_group
;
3455 if (src_regno
< FIRST_PSEUDO_REGISTER
3456 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3459 && deps
->in_post_call_group_p
== post_call_initial
)
3460 deps
->in_post_call_group_p
= post_call
;
3462 if (!sel_sched_p () || sched_emulate_haifa_p
)
3464 SCHED_GROUP_P (insn
) = 1;
3465 CANT_MOVE (insn
) = 1;
3471 if (!deps
->readonly
)
3472 deps
->in_post_call_group_p
= not_post_call
;
3476 debug_dont_end_call_group
:
3477 if ((current_sched_info
->flags
& DO_SPECULATION
)
3478 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3479 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3483 sel_mark_hard_insn (insn
);
3486 sd_iterator_def sd_it
;
3489 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3490 sd_iterator_cond (&sd_it
, &dep
);)
3491 change_spec_dep_to_hard (sd_it
);
3495 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3496 honor their original ordering. */
3497 if (find_reg_note (insn
, REG_ARGS_SIZE
, NULL
))
3499 if (deps
->last_args_size
)
3500 add_dependence (insn
, deps
->last_args_size
, REG_DEP_OUTPUT
);
3501 deps
->last_args_size
= insn
;
3505 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3506 longjmp, loop forever, ...). */
3507 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3508 test for ECF_NORETURN? */
3510 call_may_noreturn_p (rtx insn
)
3514 /* const or pure calls that aren't looping will always return. */
3515 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3516 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3519 call
= get_call_rtx_from (insn
);
3520 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3522 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3523 if (SYMBOL_REF_DECL (symbol
)
3524 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3526 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3528 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3531 case BUILT_IN_BCOPY
:
3532 case BUILT_IN_BZERO
:
3533 case BUILT_IN_INDEX
:
3534 case BUILT_IN_MEMCHR
:
3535 case BUILT_IN_MEMCMP
:
3536 case BUILT_IN_MEMCPY
:
3537 case BUILT_IN_MEMMOVE
:
3538 case BUILT_IN_MEMPCPY
:
3539 case BUILT_IN_MEMSET
:
3540 case BUILT_IN_RINDEX
:
3541 case BUILT_IN_STPCPY
:
3542 case BUILT_IN_STPNCPY
:
3543 case BUILT_IN_STRCAT
:
3544 case BUILT_IN_STRCHR
:
3545 case BUILT_IN_STRCMP
:
3546 case BUILT_IN_STRCPY
:
3547 case BUILT_IN_STRCSPN
:
3548 case BUILT_IN_STRLEN
:
3549 case BUILT_IN_STRNCAT
:
3550 case BUILT_IN_STRNCMP
:
3551 case BUILT_IN_STRNCPY
:
3552 case BUILT_IN_STRPBRK
:
3553 case BUILT_IN_STRRCHR
:
3554 case BUILT_IN_STRSPN
:
3555 case BUILT_IN_STRSTR
:
3556 /* Assume certain string/memory builtins always return. */
3564 /* For all other calls assume that they might not always return. */
3568 /* Return true if INSN should be made dependent on the previous instruction
3569 group, and if all INSN's dependencies should be moved to the first
3570 instruction of that group. */
3573 chain_to_prev_insn_p (rtx insn
)
3577 /* INSN forms a group with the previous instruction. */
3578 if (SCHED_GROUP_P (insn
))
3581 /* If the previous instruction clobbers a register R and this one sets
3582 part of R, the clobber was added specifically to help us track the
3583 liveness of R. There's no point scheduling the clobber and leaving
3584 INSN behind, especially if we move the clobber to another block. */
3585 prev
= prev_nonnote_nondebug_insn (insn
);
3588 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3589 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3591 x
= XEXP (PATTERN (prev
), 0);
3592 if (set_of (x
, insn
))
3599 /* Analyze INSN with DEPS as a context. */
3601 deps_analyze_insn (struct deps_desc
*deps
, rtx_insn
*insn
)
3603 if (sched_deps_info
->start_insn
)
3604 sched_deps_info
->start_insn (insn
);
3606 /* Record the condition for this insn. */
3607 if (NONDEBUG_INSN_P (insn
))
3610 sched_get_condition_with_rev (insn
, NULL
);
3611 t
= INSN_CACHED_COND (insn
);
3612 INSN_COND_DEPS (insn
) = NULL
;
3613 if (reload_completed
3614 && (current_sched_info
->flags
& DO_PREDICATION
)
3616 && REG_P (XEXP (t
, 0))
3617 && CONSTANT_P (XEXP (t
, 1)))
3621 rtx_insn_list
*cond_deps
= NULL
;
3624 nregs
= hard_regno_nregs
[regno
][GET_MODE (t
)];
3627 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3628 cond_deps
= concat_INSN_LIST (reg_last
->sets
, cond_deps
);
3629 cond_deps
= concat_INSN_LIST (reg_last
->clobbers
, cond_deps
);
3630 cond_deps
= concat_INSN_LIST (reg_last
->implicit_sets
, cond_deps
);
3632 INSN_COND_DEPS (insn
) = cond_deps
;
3638 /* Make each JUMP_INSN (but not a speculative check)
3639 a scheduling barrier for memory references. */
3642 && sel_insn_is_speculation_check (insn
)))
3644 /* Keep the list a reasonable size. */
3645 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3646 flush_pending_lists (deps
, insn
, true, true);
3648 deps
->pending_jump_insns
3649 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3652 /* For each insn which shouldn't cross a jump, add a dependence. */
3653 add_dependence_list_and_free (deps
, insn
,
3654 &deps
->sched_before_next_jump
, 1,
3655 REG_DEP_ANTI
, true);
3657 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3659 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3661 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3663 else if (CALL_P (insn
))
3667 CANT_MOVE (insn
) = 1;
3669 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3671 /* This is setjmp. Assume that all registers, not just
3672 hard registers, may be clobbered by this call. */
3673 reg_pending_barrier
= MOVE_BARRIER
;
3677 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3678 /* A call may read and modify global register variables. */
3681 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3682 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3684 /* Other call-clobbered hard regs may be clobbered.
3685 Since we only have a choice between 'might be clobbered'
3686 and 'definitely not clobbered', we must include all
3687 partly call-clobbered registers here. */
3688 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3689 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3690 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3691 /* We don't know what set of fixed registers might be used
3692 by the function, but it is certain that the stack pointer
3693 is among them, but be conservative. */
3694 else if (fixed_regs
[i
])
3695 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3696 /* The frame pointer is normally not used by the function
3697 itself, but by the debugger. */
3698 /* ??? MIPS o32 is an exception. It uses the frame pointer
3699 in the macro expansion of jal but does not represent this
3700 fact in the call_insn rtl. */
3701 else if (i
== FRAME_POINTER_REGNUM
3702 || (i
== HARD_FRAME_POINTER_REGNUM
3703 && (! reload_completed
|| frame_pointer_needed
)))
3704 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3707 /* For each insn which shouldn't cross a call, add a dependence
3708 between that insn and this call insn. */
3709 add_dependence_list_and_free (deps
, insn
,
3710 &deps
->sched_before_next_call
, 1,
3711 REG_DEP_ANTI
, true);
3713 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3715 /* If CALL would be in a sched group, then this will violate
3716 convention that sched group insns have dependencies only on the
3717 previous instruction.
3719 Of course one can say: "Hey! What about head of the sched group?"
3720 And I will answer: "Basic principles (one dep per insn) are always
3722 gcc_assert (!SCHED_GROUP_P (insn
));
3724 /* In the absence of interprocedural alias analysis, we must flush
3725 all pending reads and writes, and start new dependencies starting
3726 from here. But only flush writes for constant calls (which may
3727 be passed a pointer to something we haven't written yet). */
3728 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3730 if (!deps
->readonly
)
3732 /* Remember the last function call for limiting lifetimes. */
3733 free_INSN_LIST_list (&deps
->last_function_call
);
3734 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3736 if (call_may_noreturn_p (insn
))
3738 /* Remember the last function call that might not always return
3739 normally for limiting moves of trapping insns. */
3740 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3741 deps
->last_function_call_may_noreturn
3742 = alloc_INSN_LIST (insn
, NULL_RTX
);
3745 /* Before reload, begin a post-call group, so as to keep the
3746 lifetimes of hard registers correct. */
3747 if (! reload_completed
)
3748 deps
->in_post_call_group_p
= post_call
;
3752 if (sched_deps_info
->use_cselib
)
3753 cselib_process_insn (insn
);
3755 if (sched_deps_info
->finish_insn
)
3756 sched_deps_info
->finish_insn ();
3758 /* Fixup the dependencies in the sched group. */
3759 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3760 && chain_to_prev_insn_p (insn
)
3762 chain_to_prev_insn (insn
);
3765 /* Initialize DEPS for the new block beginning with HEAD. */
3767 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3769 gcc_assert (!deps
->readonly
);
3771 /* Before reload, if the previous block ended in a call, show that
3772 we are inside a post-call group, so as to keep the lifetimes of
3773 hard registers correct. */
3774 if (! reload_completed
&& !LABEL_P (head
))
3776 rtx insn
= prev_nonnote_nondebug_insn (head
);
3778 if (insn
&& CALL_P (insn
))
3779 deps
->in_post_call_group_p
= post_call_initial
;
3783 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3784 dependencies for each insn. */
3786 sched_analyze (struct deps_desc
*deps
, rtx_insn
*head
, rtx_insn
*tail
)
3790 if (sched_deps_info
->use_cselib
)
3791 cselib_init (CSELIB_RECORD_MEMORY
);
3793 deps_start_bb (deps
, head
);
3795 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3800 /* And initialize deps_lists. */
3801 sd_init_insn (insn
);
3802 /* Clean up SCHED_GROUP_P which may be set by last
3804 if (SCHED_GROUP_P (insn
))
3805 SCHED_GROUP_P (insn
) = 0;
3808 deps_analyze_insn (deps
, insn
);
3812 if (sched_deps_info
->use_cselib
)
3820 /* Helper for sched_free_deps ().
3821 Delete INSN's (RESOLVED_P) backward dependencies. */
3823 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3825 sd_iterator_def sd_it
;
3827 sd_list_types_def types
;
3830 types
= SD_LIST_RES_BACK
;
3832 types
= SD_LIST_BACK
;
3834 for (sd_it
= sd_iterator_start (insn
, types
);
3835 sd_iterator_cond (&sd_it
, &dep
);)
3837 dep_link_t link
= *sd_it
.linkp
;
3838 dep_node_t node
= DEP_LINK_NODE (link
);
3839 deps_list_t back_list
;
3840 deps_list_t forw_list
;
3842 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3843 remove_from_deps_list (link
, back_list
);
3844 delete_dep_node (node
);
3848 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3851 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3854 rtx next_tail
= NEXT_INSN (tail
);
3856 /* We make two passes since some insns may be scheduled before their
3857 dependencies are resolved. */
3858 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3859 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3861 /* Clear forward deps and leave the dep_nodes to the
3862 corresponding back_deps list. */
3864 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3866 clear_deps_list (INSN_FORW_DEPS (insn
));
3868 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3869 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3871 /* Clear resolved back deps together with its dep_nodes. */
3872 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3874 sd_finish_insn (insn
);
3878 /* Initialize variables for region data dependence analysis.
3879 When LAZY_REG_LAST is true, do not allocate reg_last array
3880 of struct deps_desc immediately. */
3883 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3885 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3887 deps
->max_reg
= max_reg
;
3889 deps
->reg_last
= NULL
;
3891 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3892 INIT_REG_SET (&deps
->reg_last_in_use
);
3894 deps
->pending_read_insns
= 0;
3895 deps
->pending_read_mems
= 0;
3896 deps
->pending_write_insns
= 0;
3897 deps
->pending_write_mems
= 0;
3898 deps
->pending_jump_insns
= 0;
3899 deps
->pending_read_list_length
= 0;
3900 deps
->pending_write_list_length
= 0;
3901 deps
->pending_flush_length
= 0;
3902 deps
->last_pending_memory_flush
= 0;
3903 deps
->last_function_call
= 0;
3904 deps
->last_function_call_may_noreturn
= 0;
3905 deps
->sched_before_next_call
= 0;
3906 deps
->sched_before_next_jump
= 0;
3907 deps
->in_post_call_group_p
= not_post_call
;
3908 deps
->last_debug_insn
= 0;
3909 deps
->last_args_size
= 0;
3910 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3914 /* Init only reg_last field of DEPS, which was not allocated before as
3915 we inited DEPS lazily. */
3917 init_deps_reg_last (struct deps_desc
*deps
)
3919 gcc_assert (deps
&& deps
->max_reg
> 0);
3920 gcc_assert (deps
->reg_last
== NULL
);
3922 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3926 /* Free insn lists found in DEPS. */
3929 free_deps (struct deps_desc
*deps
)
3932 reg_set_iterator rsi
;
3934 /* We set max_reg to 0 when this context was already freed. */
3935 if (deps
->max_reg
== 0)
3937 gcc_assert (deps
->reg_last
== NULL
);
3942 free_INSN_LIST_list (&deps
->pending_read_insns
);
3943 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3944 free_INSN_LIST_list (&deps
->pending_write_insns
);
3945 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3946 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3948 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3949 times. For a testcase with 42000 regs and 8000 small basic blocks,
3950 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3951 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3953 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3955 free_INSN_LIST_list (®_last
->uses
);
3957 free_INSN_LIST_list (®_last
->sets
);
3958 if (reg_last
->implicit_sets
)
3959 free_INSN_LIST_list (®_last
->implicit_sets
);
3960 if (reg_last
->control_uses
)
3961 free_INSN_LIST_list (®_last
->control_uses
);
3962 if (reg_last
->clobbers
)
3963 free_INSN_LIST_list (®_last
->clobbers
);
3965 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3967 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3969 free (deps
->reg_last
);
3970 deps
->reg_last
= NULL
;
3975 /* Remove INSN from dependence contexts DEPS. */
3977 remove_from_deps (struct deps_desc
*deps
, rtx_insn
*insn
)
3981 reg_set_iterator rsi
;
3983 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3984 &deps
->pending_read_mems
);
3985 if (!DEBUG_INSN_P (insn
))
3986 deps
->pending_read_list_length
-= removed
;
3987 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3988 &deps
->pending_write_mems
);
3989 deps
->pending_write_list_length
-= removed
;
3991 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
3992 deps
->pending_flush_length
-= removed
;
3993 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3994 deps
->pending_flush_length
-= removed
;
3996 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3998 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
4000 remove_from_dependence_list (insn
, ®_last
->uses
);
4002 remove_from_dependence_list (insn
, ®_last
->sets
);
4003 if (reg_last
->implicit_sets
)
4004 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
4005 if (reg_last
->clobbers
)
4006 remove_from_dependence_list (insn
, ®_last
->clobbers
);
4007 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
4008 && !reg_last
->clobbers
)
4009 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
4014 remove_from_dependence_list (insn
, &deps
->last_function_call
);
4015 remove_from_dependence_list (insn
,
4016 &deps
->last_function_call_may_noreturn
);
4018 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
4021 /* Init deps data vector. */
4023 init_deps_data_vector (void)
4025 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
4026 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
4027 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
4030 /* If it is profitable to use them, initialize or extend (depending on
4031 GLOBAL_P) dependency data. */
4033 sched_deps_init (bool global_p
)
4035 /* Average number of insns in the basic block.
4036 '+ 1' is used to make it nonzero. */
4037 int insns_in_block
= sched_max_luid
/ n_basic_blocks_for_fn (cfun
) + 1;
4039 init_deps_data_vector ();
4041 /* We use another caching mechanism for selective scheduling, so
4042 we don't use this one. */
4043 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
4045 /* ?!? We could save some memory by computing a per-region luid mapping
4046 which could reduce both the number of vectors in the cache and the
4047 size of each vector. Instead we just avoid the cache entirely unless
4048 the average number of instructions in a basic block is very high. See
4049 the comment before the declaration of true_dependency_cache for
4050 what we consider "very high". */
4052 extend_dependency_caches (sched_max_luid
, true);
4057 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
4058 /* Allocate lists for one block at a time. */
4060 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
4061 /* Allocate nodes for one block at a time.
4062 We assume that average insn has
4064 5 * insns_in_block
);
4069 /* Create or extend (depending on CREATE_P) dependency caches to
4072 extend_dependency_caches (int n
, bool create_p
)
4074 if (create_p
|| true_dependency_cache
)
4076 int i
, luid
= cache_size
+ n
;
4078 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4080 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4081 output_dependency_cache
, luid
);
4082 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4084 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4087 if (current_sched_info
->flags
& DO_SPECULATION
)
4088 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4091 for (i
= cache_size
; i
< luid
; i
++)
4093 bitmap_initialize (&true_dependency_cache
[i
], 0);
4094 bitmap_initialize (&output_dependency_cache
[i
], 0);
4095 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4096 bitmap_initialize (&control_dependency_cache
[i
], 0);
4098 if (current_sched_info
->flags
& DO_SPECULATION
)
4099 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4105 /* Finalize dependency information for the whole function. */
4107 sched_deps_finish (void)
4109 gcc_assert (deps_pools_are_empty_p ());
4110 free_alloc_pool_if_empty (&dn_pool
);
4111 free_alloc_pool_if_empty (&dl_pool
);
4112 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
4117 if (true_dependency_cache
)
4121 for (i
= 0; i
< cache_size
; i
++)
4123 bitmap_clear (&true_dependency_cache
[i
]);
4124 bitmap_clear (&output_dependency_cache
[i
]);
4125 bitmap_clear (&anti_dependency_cache
[i
]);
4126 bitmap_clear (&control_dependency_cache
[i
]);
4128 if (sched_deps_info
->generate_spec_deps
)
4129 bitmap_clear (&spec_dependency_cache
[i
]);
4131 free (true_dependency_cache
);
4132 true_dependency_cache
= NULL
;
4133 free (output_dependency_cache
);
4134 output_dependency_cache
= NULL
;
4135 free (anti_dependency_cache
);
4136 anti_dependency_cache
= NULL
;
4137 free (control_dependency_cache
);
4138 control_dependency_cache
= NULL
;
4140 if (sched_deps_info
->generate_spec_deps
)
4142 free (spec_dependency_cache
);
4143 spec_dependency_cache
= NULL
;
4149 /* Initialize some global variables needed by the dependency analysis
4153 init_deps_global (void)
4155 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4156 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4157 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4158 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4159 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4160 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4161 reg_pending_barrier
= NOT_A_BARRIER
;
4163 if (!sel_sched_p () || sched_emulate_haifa_p
)
4165 sched_deps_info
->start_insn
= haifa_start_insn
;
4166 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4168 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4169 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4170 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4172 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4173 sched_deps_info
->note_dep
= haifa_note_dep
;
4177 /* Free everything used by the dependency analysis code. */
4180 finish_deps_global (void)
4182 FREE_REG_SET (reg_pending_sets
);
4183 FREE_REG_SET (reg_pending_clobbers
);
4184 FREE_REG_SET (reg_pending_uses
);
4185 FREE_REG_SET (reg_pending_control_uses
);
4188 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4190 estimate_dep_weak (rtx mem1
, rtx mem2
)
4195 /* MEMs are the same - don't speculate. */
4196 return MIN_DEP_WEAK
;
4198 r1
= XEXP (mem1
, 0);
4199 r2
= XEXP (mem2
, 0);
4202 || (REG_P (r1
) && REG_P (r2
)
4203 && REGNO (r1
) == REGNO (r2
)))
4204 /* Again, MEMs are the same. */
4205 return MIN_DEP_WEAK
;
4206 else if ((REG_P (r1
) && !REG_P (r2
))
4207 || (!REG_P (r1
) && REG_P (r2
)))
4208 /* Different addressing modes - reason to be more speculative,
4210 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4212 /* We can't say anything about the dependence. */
4213 return UNCERTAIN_DEP_WEAK
;
4216 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4217 This function can handle same INSN and ELEM (INSN == ELEM).
4218 It is a convenience wrapper. */
4220 add_dependence_1 (rtx_insn
*insn
, rtx_insn
*elem
, enum reg_note dep_type
)
4225 if (dep_type
== REG_DEP_TRUE
)
4227 else if (dep_type
== REG_DEP_OUTPUT
)
4229 else if (dep_type
== REG_DEP_CONTROL
)
4233 gcc_assert (dep_type
== REG_DEP_ANTI
);
4237 /* When add_dependence is called from inside sched-deps.c, we expect
4238 cur_insn to be non-null. */
4239 internal
= cur_insn
!= NULL
;
4241 gcc_assert (insn
== cur_insn
);
4245 note_dep (elem
, ds
);
4250 /* Return weakness of speculative type TYPE in the dep_status DS,
4251 without checking to prevent ICEs on malformed input. */
4253 get_dep_weak_1 (ds_t ds
, ds_t type
)
4259 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4260 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4261 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4262 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4263 default: gcc_unreachable ();
4269 /* Return weakness of speculative type TYPE in the dep_status DS. */
4271 get_dep_weak (ds_t ds
, ds_t type
)
4273 dw_t dw
= get_dep_weak_1 (ds
, type
);
4275 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4279 /* Return the dep_status, which has the same parameters as DS, except for
4280 speculative type TYPE, that will have weakness DW. */
4282 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4284 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4289 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4290 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4291 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4292 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4293 default: gcc_unreachable ();
4298 /* Return the join of two dep_statuses DS1 and DS2.
4299 If MAX_P is true then choose the greater probability,
4300 otherwise multiply probabilities.
4301 This function assumes that both DS1 and DS2 contain speculative bits. */
4303 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4307 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4309 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4311 t
= FIRST_SPEC_TYPE
;
4314 if ((ds1
& t
) && !(ds2
& t
))
4316 else if (!(ds1
& t
) && (ds2
& t
))
4318 else if ((ds1
& t
) && (ds2
& t
))
4320 dw_t dw1
= get_dep_weak (ds1
, t
);
4321 dw_t dw2
= get_dep_weak (ds2
, t
);
4326 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4328 if (dw
< MIN_DEP_WEAK
)
4339 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4342 if (t
== LAST_SPEC_TYPE
)
4344 t
<<= SPEC_TYPE_SHIFT
;
4351 /* Return the join of two dep_statuses DS1 and DS2.
4352 This function assumes that both DS1 and DS2 contain speculative bits. */
4354 ds_merge (ds_t ds1
, ds_t ds2
)
4356 return ds_merge_1 (ds1
, ds2
, false);
4359 /* Return the join of two dep_statuses DS1 and DS2. */
4361 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4363 ds_t new_status
= ds
| ds2
;
4365 if (new_status
& SPECULATIVE
)
4367 if ((ds
&& !(ds
& SPECULATIVE
))
4368 || (ds2
&& !(ds2
& SPECULATIVE
)))
4369 /* Then this dep can't be speculative. */
4370 new_status
&= ~SPECULATIVE
;
4373 /* Both are speculative. Merging probabilities. */
4378 dw
= estimate_dep_weak (mem1
, mem2
);
4379 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4387 new_status
= ds_merge (ds2
, ds
);
4394 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4397 ds_max_merge (ds_t ds1
, ds_t ds2
)
4399 if (ds1
== 0 && ds2
== 0)
4402 if (ds1
== 0 && ds2
!= 0)
4405 if (ds1
!= 0 && ds2
== 0)
4408 return ds_merge_1 (ds1
, ds2
, true);
4411 /* Return the probability of speculation success for the speculation
4419 dt
= FIRST_SPEC_TYPE
;
4424 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4428 if (dt
== LAST_SPEC_TYPE
)
4430 dt
<<= SPEC_TYPE_SHIFT
;
4436 res
/= MAX_DEP_WEAK
;
4438 if (res
< MIN_DEP_WEAK
)
4441 gcc_assert (res
<= MAX_DEP_WEAK
);
4446 /* Return a dep status that contains all speculation types of DS. */
4448 ds_get_speculation_types (ds_t ds
)
4450 if (ds
& BEGIN_DATA
)
4452 if (ds
& BE_IN_DATA
)
4454 if (ds
& BEGIN_CONTROL
)
4455 ds
|= BEGIN_CONTROL
;
4456 if (ds
& BE_IN_CONTROL
)
4457 ds
|= BE_IN_CONTROL
;
4459 return ds
& SPECULATIVE
;
4462 /* Return a dep status that contains maximal weakness for each speculation
4463 type present in DS. */
4465 ds_get_max_dep_weak (ds_t ds
)
4467 if (ds
& BEGIN_DATA
)
4468 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4469 if (ds
& BE_IN_DATA
)
4470 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4471 if (ds
& BEGIN_CONTROL
)
4472 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4473 if (ds
& BE_IN_CONTROL
)
4474 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4479 /* Dump information about the dependence status S. */
4481 dump_ds (FILE *f
, ds_t s
)
4486 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4488 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4489 if (s
& BEGIN_CONTROL
)
4490 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4491 if (s
& BE_IN_CONTROL
)
4492 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4495 fprintf (f
, "HARD_DEP; ");
4498 fprintf (f
, "DEP_TRUE; ");
4500 fprintf (f
, "DEP_OUTPUT; ");
4502 fprintf (f
, "DEP_ANTI; ");
4503 if (s
& DEP_CONTROL
)
4504 fprintf (f
, "DEP_CONTROL; ");
4512 dump_ds (stderr
, s
);
4513 fprintf (stderr
, "\n");
4516 #ifdef ENABLE_CHECKING
4517 /* Verify that dependence type and status are consistent.
4518 If RELAXED_P is true, then skip dep_weakness checks. */
4520 check_dep (dep_t dep
, bool relaxed_p
)
4522 enum reg_note dt
= DEP_TYPE (dep
);
4523 ds_t ds
= DEP_STATUS (dep
);
4525 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4527 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4529 gcc_assert (ds
== 0);
4533 /* Check that dependence type contains the same bits as the status. */
4534 if (dt
== REG_DEP_TRUE
)
4535 gcc_assert (ds
& DEP_TRUE
);
4536 else if (dt
== REG_DEP_OUTPUT
)
4537 gcc_assert ((ds
& DEP_OUTPUT
)
4538 && !(ds
& DEP_TRUE
));
4539 else if (dt
== REG_DEP_ANTI
)
4540 gcc_assert ((ds
& DEP_ANTI
)
4541 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4543 gcc_assert (dt
== REG_DEP_CONTROL
4544 && (ds
& DEP_CONTROL
)
4545 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4547 /* HARD_DEP can not appear in dep_status of a link. */
4548 gcc_assert (!(ds
& HARD_DEP
));
4550 /* Check that dependence status is set correctly when speculation is not
4552 if (!sched_deps_info
->generate_spec_deps
)
4553 gcc_assert (!(ds
& SPECULATIVE
));
4554 else if (ds
& SPECULATIVE
)
4558 ds_t type
= FIRST_SPEC_TYPE
;
4560 /* Check that dependence weakness is in proper range. */
4564 get_dep_weak (ds
, type
);
4566 if (type
== LAST_SPEC_TYPE
)
4568 type
<<= SPEC_TYPE_SHIFT
;
4573 if (ds
& BEGIN_SPEC
)
4575 /* Only true dependence can be data speculative. */
4576 if (ds
& BEGIN_DATA
)
4577 gcc_assert (ds
& DEP_TRUE
);
4579 /* Control dependencies in the insn scheduler are represented by
4580 anti-dependencies, therefore only anti dependence can be
4581 control speculative. */
4582 if (ds
& BEGIN_CONTROL
)
4583 gcc_assert (ds
& DEP_ANTI
);
4587 /* Subsequent speculations should resolve true dependencies. */
4588 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4591 /* Check that true and anti dependencies can't have other speculative
4594 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4595 /* An output dependence can't be speculative at all. */
4596 gcc_assert (!(ds
& DEP_OUTPUT
));
4598 gcc_assert (ds
& BEGIN_CONTROL
);
4601 #endif /* ENABLE_CHECKING */
4603 /* The following code discovers opportunities to switch a memory reference
4604 and an increment by modifying the address. We ensure that this is done
4605 only for dependencies that are only used to show a single register
4606 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4607 instruction involved is subject to only one dep that can cause a pattern
4610 When we discover a suitable dependency, we fill in the dep_replacement
4611 structure to show how to modify the memory reference. */
4613 /* Holds information about a pair of memory reference and register increment
4614 insns which depend on each other, but could possibly be interchanged. */
4621 /* A register occurring in the memory address for which we wish to break
4622 the dependence. This must be identical to the destination register of
4625 /* Any kind of index that is added to that register. */
4627 /* The constant offset used in the memory address. */
4628 HOST_WIDE_INT mem_constant
;
4629 /* The constant added in the increment insn. Negated if the increment is
4630 after the memory address. */
4631 HOST_WIDE_INT inc_constant
;
4632 /* The source register used in the increment. May be different from mem_reg0
4633 if the increment occurs before the memory address. */
4637 /* Verify that the memory location described in MII can be replaced with
4638 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4639 insn remains unchanged by this function. */
4642 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4644 rtx mem
= *mii
->mem_loc
;
4647 /* Jump through a lot of hoops to keep the attributes up to date. We
4648 do not want to call one of the change address variants that take
4649 an offset even though we know the offset in many cases. These
4650 assume you are changing where the address is pointing by the
4652 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4653 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4655 if (sched_verbose
>= 5)
4656 fprintf (sched_dump
, "validation failure\n");
4660 /* Put back the old one. */
4661 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4666 /* Return true if INSN is of a form "a = b op c" where a and b are
4667 regs. op is + if c is a reg and +|- if c is a const. Fill in
4668 informantion in MII about what is found.
4669 BEFORE_MEM indicates whether the increment is found before or after
4670 a corresponding memory reference. */
4673 parse_add_or_inc (struct mem_inc_info
*mii
, rtx_insn
*insn
, bool before_mem
)
4675 rtx pat
= single_set (insn
);
4679 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4682 /* Result must be single reg. */
4683 if (!REG_P (SET_DEST (pat
)))
4686 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4689 mii
->inc_insn
= insn
;
4690 src
= SET_SRC (pat
);
4691 mii
->inc_input
= XEXP (src
, 0);
4693 if (!REG_P (XEXP (src
, 0)))
4696 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4699 cst
= XEXP (src
, 1);
4700 if (!CONST_INT_P (cst
))
4702 mii
->inc_constant
= INTVAL (cst
);
4704 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4708 mii
->inc_constant
= -mii
->inc_constant
;
4713 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4715 /* Note that the sign has already been reversed for !before_mem. */
4716 #ifdef STACK_GROWS_DOWNWARD
4717 return mii
->inc_constant
> 0;
4719 return mii
->inc_constant
< 0;
4725 /* Once a suitable mem reference has been found and the corresponding data
4726 in MII has been filled in, this function is called to find a suitable
4727 add or inc insn involving the register we found in the memory
4731 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4733 sd_iterator_def sd_it
;
4736 sd_it
= sd_iterator_start (mii
->mem_insn
,
4737 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4738 while (sd_iterator_cond (&sd_it
, &dep
))
4740 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4741 rtx_insn
*pro
= DEP_PRO (dep
);
4742 rtx_insn
*con
= DEP_CON (dep
);
4743 rtx_insn
*inc_cand
= backwards
? pro
: con
;
4744 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4746 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4748 struct dep_replacement
*desc
;
4750 rtx newaddr
, newmem
;
4752 if (sched_verbose
>= 5)
4753 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4754 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4756 /* Need to assure that none of the operands of the inc
4757 instruction are assigned to by the mem insn. */
4758 FOR_EACH_INSN_DEF (def
, mii
->mem_insn
)
4759 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4760 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4762 if (sched_verbose
>= 5)
4763 fprintf (sched_dump
,
4764 "inc conflicts with store failure.\n");
4768 /* The inc instruction could have clobbers, make sure those
4769 registers are not used in mem insn. */
4770 FOR_EACH_INSN_DEF (def
, mii
->inc_insn
)
4771 if (!reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4774 FOR_EACH_INSN_USE (use
, mii
->mem_insn
)
4775 if (reg_overlap_mentioned_p (DF_REF_REG (def
),
4778 if (sched_verbose
>= 5)
4779 fprintf (sched_dump
,
4780 "inc clobber used in store failure.\n");
4785 newaddr
= mii
->inc_input
;
4786 if (mii
->mem_index
!= NULL_RTX
)
4787 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4789 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4790 mii
->mem_constant
+ mii
->inc_constant
);
4791 newmem
= attempt_change (mii
, newaddr
);
4792 if (newmem
== NULL_RTX
)
4794 if (sched_verbose
>= 5)
4795 fprintf (sched_dump
, "successful address replacement\n");
4796 desc
= XCNEW (struct dep_replacement
);
4797 DEP_REPLACE (dep
) = desc
;
4798 desc
->loc
= mii
->mem_loc
;
4799 desc
->newval
= newmem
;
4800 desc
->orig
= *desc
->loc
;
4801 desc
->insn
= mii
->mem_insn
;
4802 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4803 INSN_SPEC_BACK_DEPS (con
));
4806 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4807 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4812 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4813 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4819 sd_iterator_next (&sd_it
);
4824 /* A recursive function that walks ADDRESS_OF_X to find memory references
4825 which could be modified during scheduling. We call find_inc for each
4826 one we find that has a recognizable form. MII holds information about
4827 the pair of memory/increment instructions.
4828 We ensure that every instruction with a memory reference (which will be
4829 the location of the replacement) is assigned at most one breakable
4833 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4835 rtx x
= *address_of_x
;
4836 enum rtx_code code
= GET_CODE (x
);
4837 const char *const fmt
= GET_RTX_FORMAT (code
);
4842 rtx reg0
= XEXP (x
, 0);
4844 mii
->mem_loc
= address_of_x
;
4845 mii
->mem_index
= NULL_RTX
;
4846 mii
->mem_constant
= 0;
4847 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4849 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4850 reg0
= XEXP (reg0
, 0);
4852 if (GET_CODE (reg0
) == PLUS
)
4854 mii
->mem_index
= XEXP (reg0
, 1);
4855 reg0
= XEXP (reg0
, 0);
4860 int occurrences
= 0;
4862 /* Make sure this reg appears only once in this insn. Can't use
4863 count_occurrences since that only works for pseudos. */
4864 FOR_EACH_INSN_USE (use
, mii
->mem_insn
)
4865 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (use
)))
4866 if (++occurrences
> 1)
4868 if (sched_verbose
>= 5)
4869 fprintf (sched_dump
, "mem count failure\n");
4873 mii
->mem_reg0
= reg0
;
4874 return find_inc (mii
, true) || find_inc (mii
, false);
4879 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4881 /* If REG occurs inside a MEM used in a bit-field reference,
4882 that is unacceptable. */
4886 /* Time for some deep diving. */
4887 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4891 if (find_mem (mii
, &XEXP (x
, i
)))
4894 else if (fmt
[i
] == 'E')
4897 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4898 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4906 /* Examine the instructions between HEAD and TAIL and try to find
4907 dependencies that can be broken by modifying one of the patterns. */
4910 find_modifiable_mems (rtx_insn
*head
, rtx_insn
*tail
)
4912 rtx_insn
*insn
, *next_tail
= NEXT_INSN (tail
);
4913 int success_in_block
= 0;
4915 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4917 struct mem_inc_info mii
;
4919 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4922 mii
.mem_insn
= insn
;
4923 if (find_mem (&mii
, &PATTERN (insn
)))
4926 if (success_in_block
&& sched_verbose
>= 5)
4927 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4931 #endif /* INSN_SCHEDULING */