1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992-2013 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 pro
, rtx 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 pro
, rtx 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
, rtx
, enum reg_note
);
486 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
, bool);
487 static void add_dependence_list_and_free (struct deps_desc
*, rtx
,
488 rtx
*, int, enum reg_note
, bool);
489 static void delete_all_dependences (rtx
);
490 static void chain_to_prev_insn (rtx
);
492 static void flush_pending_lists (struct deps_desc
*, rtx
, int, int);
493 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx
);
494 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx
);
495 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx
);
497 static bool sched_has_condition_p (const_rtx
);
498 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
500 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
502 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
504 #ifdef ENABLE_CHECKING
505 static void check_dep (dep_t
, bool);
508 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
511 deps_may_trap_p (const_rtx mem
)
513 const_rtx addr
= XEXP (mem
, 0);
515 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
517 const_rtx t
= get_reg_known_value (REGNO (addr
));
521 return rtx_addr_can_trap_p (addr
);
525 /* Find the condition under which INSN is executed. If REV is not NULL,
526 it is set to TRUE when the returned comparison should be reversed
527 to get the actual condition. */
529 sched_get_condition_with_rev_uncached (const_rtx insn
, bool *rev
)
531 rtx pat
= PATTERN (insn
);
537 if (GET_CODE (pat
) == COND_EXEC
)
538 return COND_EXEC_TEST (pat
);
540 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
543 src
= SET_SRC (pc_set (insn
));
545 if (XEXP (src
, 2) == pc_rtx
)
546 return XEXP (src
, 0);
547 else if (XEXP (src
, 1) == pc_rtx
)
549 rtx cond
= XEXP (src
, 0);
550 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
552 if (revcode
== UNKNOWN
)
563 /* Return the condition under which INSN does not execute (i.e. the
564 not-taken condition for a conditional branch), or NULL if we cannot
565 find such a condition. The caller should make a copy of the condition
568 sched_get_reverse_condition_uncached (const_rtx insn
)
571 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
572 if (cond
== NULL_RTX
)
576 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
577 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
584 /* Caching variant of sched_get_condition_with_rev_uncached.
585 We only do actual work the first time we come here for an insn; the
586 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
588 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
592 if (INSN_LUID (insn
) == 0)
593 return sched_get_condition_with_rev_uncached (insn
, rev
);
595 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
598 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
601 *rev
= INSN_REVERSE_COND (insn
);
602 return INSN_CACHED_COND (insn
);
605 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
606 INSN_REVERSE_COND (insn
) = tmp
;
608 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
610 INSN_CACHED_COND (insn
) = const_true_rtx
;
615 *rev
= INSN_REVERSE_COND (insn
);
616 return INSN_CACHED_COND (insn
);
619 /* True when we can find a condition under which INSN is executed. */
621 sched_has_condition_p (const_rtx insn
)
623 return !! sched_get_condition_with_rev (insn
, NULL
);
628 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
630 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
632 if (COMPARISON_P (cond1
)
633 && COMPARISON_P (cond2
)
634 && GET_CODE (cond1
) ==
636 ? reversed_comparison_code (cond2
, NULL
)
638 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
639 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
644 /* Return true if insn1 and insn2 can never depend on one another because
645 the conditions under which they are executed are mutually exclusive. */
647 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
650 bool rev1
= false, rev2
= false;
652 /* df doesn't handle conditional lifetimes entirely correctly;
653 calls mess up the conditional lifetimes. */
654 if (!CALL_P (insn1
) && !CALL_P (insn2
))
656 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
657 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
659 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
660 /* Make sure first instruction doesn't affect condition of second
661 instruction if switched. */
662 && !modified_in_p (cond1
, insn2
)
663 /* Make sure second instruction doesn't affect condition of first
664 instruction if switched. */
665 && !modified_in_p (cond2
, insn1
))
672 /* Return true if INSN can potentially be speculated with type DS. */
674 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
676 if (HAS_INTERNAL_DEP (insn
))
679 if (!NONJUMP_INSN_P (insn
))
682 if (SCHED_GROUP_P (insn
))
685 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
688 if (side_effects_p (PATTERN (insn
)))
692 /* The following instructions, which depend on a speculatively scheduled
693 instruction, cannot be speculatively scheduled along. */
695 if (may_trap_or_fault_p (PATTERN (insn
)))
696 /* If instruction might fault, it cannot be speculatively scheduled.
697 For control speculation it's obvious why and for data speculation
698 it's because the insn might get wrong input if speculation
699 wasn't successful. */
702 if ((ds
& BE_IN_DATA
)
703 && sched_has_condition_p (insn
))
704 /* If this is a predicated instruction, then it cannot be
705 speculatively scheduled. See PR35659. */
712 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
713 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
714 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
715 This function is used to switch sd_iterator to the next list.
716 !!! For internal use only. Might consider moving it to sched-int.h. */
718 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
719 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
721 sd_list_types_def types
= *types_ptr
;
723 if (types
& SD_LIST_HARD_BACK
)
725 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
726 *resolved_p_ptr
= false;
727 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
729 else if (types
& SD_LIST_SPEC_BACK
)
731 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
732 *resolved_p_ptr
= false;
733 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
735 else if (types
& SD_LIST_FORW
)
737 *list_ptr
= INSN_FORW_DEPS (insn
);
738 *resolved_p_ptr
= false;
739 *types_ptr
= types
& ~SD_LIST_FORW
;
741 else if (types
& SD_LIST_RES_BACK
)
743 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
744 *resolved_p_ptr
= true;
745 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
747 else if (types
& SD_LIST_RES_FORW
)
749 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
750 *resolved_p_ptr
= true;
751 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
756 *resolved_p_ptr
= false;
757 *types_ptr
= SD_LIST_NONE
;
761 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
763 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
767 while (list_types
!= SD_LIST_NONE
)
772 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
774 size
+= DEPS_LIST_N_LINKS (list
);
780 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
783 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
785 while (list_types
!= SD_LIST_NONE
)
790 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
791 if (!deps_list_empty_p (list
))
798 /* Initialize data for INSN. */
800 sd_init_insn (rtx insn
)
802 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
803 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
804 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
805 INSN_FORW_DEPS (insn
) = create_deps_list ();
806 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
808 /* ??? It would be nice to allocate dependency caches here. */
811 /* Free data for INSN. */
813 sd_finish_insn (rtx insn
)
815 /* ??? It would be nice to deallocate dependency caches here. */
817 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
818 INSN_HARD_BACK_DEPS (insn
) = NULL
;
820 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
821 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
823 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
824 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
826 free_deps_list (INSN_FORW_DEPS (insn
));
827 INSN_FORW_DEPS (insn
) = NULL
;
829 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
830 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
833 /* Find a dependency between producer PRO and consumer CON.
834 Search through resolved dependency lists if RESOLVED_P is true.
835 If no such dependency is found return NULL,
836 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
837 with an iterator pointing to it. */
839 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
840 sd_iterator_def
*sd_it_ptr
)
842 sd_list_types_def pro_list_type
;
843 sd_list_types_def con_list_type
;
844 sd_iterator_def sd_it
;
846 bool found_p
= false;
850 pro_list_type
= SD_LIST_RES_FORW
;
851 con_list_type
= SD_LIST_RES_BACK
;
855 pro_list_type
= SD_LIST_FORW
;
856 con_list_type
= SD_LIST_BACK
;
859 /* Walk through either back list of INSN or forw list of ELEM
860 depending on which one is shorter. */
861 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
863 /* Find the dep_link with producer PRO in consumer's back_deps. */
864 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
865 if (DEP_PRO (dep
) == pro
)
873 /* Find the dep_link with consumer CON in producer's forw_deps. */
874 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
875 if (DEP_CON (dep
) == con
)
884 if (sd_it_ptr
!= NULL
)
893 /* Find a dependency between producer PRO and consumer CON.
894 Use dependency [if available] to check if dependency is present at all.
895 Search through resolved dependency lists if RESOLVED_P is true.
896 If the dependency or NULL if none found. */
898 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
900 if (true_dependency_cache
!= NULL
)
901 /* Avoiding the list walk below can cut compile times dramatically
904 int elem_luid
= INSN_LUID (pro
);
905 int insn_luid
= INSN_LUID (con
);
907 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
908 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
909 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
910 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
914 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
917 /* Add or update a dependence described by DEP.
918 MEM1 and MEM2, if non-null, correspond to memory locations in case of
921 The function returns a value indicating if an old entry has been changed
922 or a new entry has been added to insn's backward deps.
924 This function merely checks if producer and consumer is the same insn
925 and doesn't create a dep in this case. Actual manipulation of
926 dependence data structures is performed in add_or_update_dep_1. */
927 static enum DEPS_ADJUST_RESULT
928 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
930 rtx elem
= DEP_PRO (dep
);
931 rtx insn
= DEP_CON (dep
);
933 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
935 /* Don't depend an insn on itself. */
938 if (sched_deps_info
->generate_spec_deps
)
939 /* INSN has an internal dependence, which we can't overcome. */
940 HAS_INTERNAL_DEP (insn
) = 1;
945 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
948 /* Ask dependency caches what needs to be done for dependence DEP.
949 Return DEP_CREATED if new dependence should be created and there is no
950 need to try to find one searching the dependencies lists.
951 Return DEP_PRESENT if there already is a dependence described by DEP and
952 hence nothing is to be done.
953 Return DEP_CHANGED if there already is a dependence, but it should be
954 updated to incorporate additional information from DEP. */
955 static enum DEPS_ADJUST_RESULT
956 ask_dependency_caches (dep_t dep
)
958 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
959 int insn_luid
= INSN_LUID (DEP_CON (dep
));
961 gcc_assert (true_dependency_cache
!= NULL
962 && output_dependency_cache
!= NULL
963 && anti_dependency_cache
!= NULL
964 && control_dependency_cache
!= NULL
);
966 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
968 enum reg_note present_dep_type
;
970 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
971 present_dep_type
= REG_DEP_TRUE
;
972 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
973 present_dep_type
= REG_DEP_OUTPUT
;
974 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
975 present_dep_type
= REG_DEP_ANTI
;
976 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
977 present_dep_type
= REG_DEP_CONTROL
;
979 /* There is no existing dep so it should be created. */
982 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
983 /* DEP does not add anything to the existing dependence. */
988 ds_t present_dep_types
= 0;
990 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
991 present_dep_types
|= DEP_TRUE
;
992 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
993 present_dep_types
|= DEP_OUTPUT
;
994 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
995 present_dep_types
|= DEP_ANTI
;
996 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
997 present_dep_types
|= DEP_CONTROL
;
999 if (present_dep_types
== 0)
1000 /* There is no existing dep so it should be created. */
1003 if (!(current_sched_info
->flags
& DO_SPECULATION
)
1004 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
1006 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
1007 == present_dep_types
)
1008 /* DEP does not add anything to the existing dependence. */
1013 /* Only true dependencies can be data speculative and
1014 only anti dependencies can be control speculative. */
1015 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1016 == present_dep_types
);
1018 /* if (DEP is SPECULATIVE) then
1019 ..we should update DEP_STATUS
1021 ..we should reset existing dep to non-speculative. */
1028 /* Set dependency caches according to DEP. */
1030 set_dependency_caches (dep_t dep
)
1032 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1033 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1035 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1037 switch (DEP_TYPE (dep
))
1040 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1043 case REG_DEP_OUTPUT
:
1044 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1048 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1051 case REG_DEP_CONTROL
:
1052 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1061 ds_t ds
= DEP_STATUS (dep
);
1064 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1065 if (ds
& DEP_OUTPUT
)
1066 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1068 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1069 if (ds
& DEP_CONTROL
)
1070 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1072 if (ds
& SPECULATIVE
)
1074 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1075 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1080 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1081 caches accordingly. */
1083 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1085 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1086 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1088 /* Clear corresponding cache entry because type of the link
1089 may have changed. Keep them if we use_deps_list. */
1090 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1094 case REG_DEP_OUTPUT
:
1095 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1099 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1102 case REG_DEP_CONTROL
:
1103 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1111 set_dependency_caches (dep
);
1114 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1116 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1118 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1119 dep_link_t link
= DEP_NODE_BACK (node
);
1120 dep_t dep
= DEP_NODE_DEP (node
);
1121 rtx elem
= DEP_PRO (dep
);
1122 rtx insn
= DEP_CON (dep
);
1124 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1126 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1128 if (true_dependency_cache
!= NULL
)
1129 /* Clear the cache entry. */
1130 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1134 /* Update DEP to incorporate information from NEW_DEP.
1135 SD_IT points to DEP in case it should be moved to another list.
1136 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1137 data-speculative dependence should be updated. */
1138 static enum DEPS_ADJUST_RESULT
1139 update_dep (dep_t dep
, dep_t new_dep
,
1140 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1141 rtx mem1 ATTRIBUTE_UNUSED
,
1142 rtx mem2 ATTRIBUTE_UNUSED
)
1144 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1145 enum reg_note old_type
= DEP_TYPE (dep
);
1146 bool was_spec
= dep_spec_p (dep
);
1148 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1149 DEP_MULTIPLE (dep
) = 1;
1151 /* If this is a more restrictive type of dependence than the
1152 existing one, then change the existing dependence to this
1154 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1156 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1160 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1161 /* Update DEP_STATUS. */
1163 ds_t dep_status
= DEP_STATUS (dep
);
1164 ds_t ds
= DEP_STATUS (new_dep
);
1165 ds_t new_status
= ds
| dep_status
;
1167 if (new_status
& SPECULATIVE
)
1169 /* Either existing dep or a dep we're adding or both are
1171 if (!(ds
& SPECULATIVE
)
1172 || !(dep_status
& SPECULATIVE
))
1173 /* The new dep can't be speculative. */
1174 new_status
&= ~SPECULATIVE
;
1177 /* Both are speculative. Merge probabilities. */
1182 dw
= estimate_dep_weak (mem1
, mem2
);
1183 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1186 new_status
= ds_merge (dep_status
, ds
);
1192 if (dep_status
!= ds
)
1194 DEP_STATUS (dep
) = ds
;
1199 if (was_spec
&& !dep_spec_p (dep
))
1200 /* The old dep was speculative, but now it isn't. */
1201 change_spec_dep_to_hard (sd_it
);
1203 if (true_dependency_cache
!= NULL
1204 && res
== DEP_CHANGED
)
1205 update_dependency_caches (dep
, old_type
);
1210 /* Add or update a dependence described by DEP.
1211 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1214 The function returns a value indicating if an old entry has been changed
1215 or a new entry has been added to insn's backward deps or nothing has
1216 been updated at all. */
1217 static enum DEPS_ADJUST_RESULT
1218 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1219 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1221 bool maybe_present_p
= true;
1222 bool present_p
= false;
1224 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1225 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1227 #ifdef ENABLE_CHECKING
1228 check_dep (new_dep
, mem1
!= NULL
);
1231 if (true_dependency_cache
!= NULL
)
1233 switch (ask_dependency_caches (new_dep
))
1239 maybe_present_p
= true;
1244 maybe_present_p
= false;
1254 /* Check that we don't already have this dependence. */
1255 if (maybe_present_p
)
1258 sd_iterator_def sd_it
;
1260 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1262 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1264 resolved_p
, &sd_it
);
1266 if (present_dep
!= NULL
)
1267 /* We found an existing dependency between ELEM and INSN. */
1268 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1270 /* We didn't find a dep, it shouldn't present in the cache. */
1271 gcc_assert (!present_p
);
1274 /* Might want to check one level of transitivity to save conses.
1275 This check should be done in maybe_add_or_update_dep_1.
1276 Since we made it to add_or_update_dep_1, we must create
1277 (or update) a link. */
1279 if (mem1
!= NULL_RTX
)
1281 gcc_assert (sched_deps_info
->generate_spec_deps
);
1282 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1283 estimate_dep_weak (mem1
, mem2
));
1286 sd_add_dep (new_dep
, resolved_p
);
1291 /* Initialize BACK_LIST_PTR with consumer's backward list and
1292 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1293 initialize with lists that hold resolved deps. */
1295 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1296 deps_list_t
*back_list_ptr
,
1297 deps_list_t
*forw_list_ptr
)
1299 rtx con
= DEP_CON (dep
);
1303 if (dep_spec_p (dep
))
1304 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1306 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1308 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1312 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1313 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1317 /* Add dependence described by DEP.
1318 If RESOLVED_P is true treat the dependence as a resolved one. */
1320 sd_add_dep (dep_t dep
, bool resolved_p
)
1322 dep_node_t n
= create_dep_node ();
1323 deps_list_t con_back_deps
;
1324 deps_list_t pro_forw_deps
;
1325 rtx elem
= DEP_PRO (dep
);
1326 rtx insn
= DEP_CON (dep
);
1328 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1330 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1331 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1332 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1334 copy_dep (DEP_NODE_DEP (n
), dep
);
1336 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1338 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1340 #ifdef ENABLE_CHECKING
1341 check_dep (dep
, false);
1344 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1346 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1347 in the bitmap caches of dependency information. */
1348 if (true_dependency_cache
!= NULL
)
1349 set_dependency_caches (dep
);
1352 /* Add or update backward dependence between INSN and ELEM
1353 with given type DEP_TYPE and dep_status DS.
1354 This function is a convenience wrapper. */
1355 enum DEPS_ADJUST_RESULT
1356 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1358 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1361 /* Resolved dependence pointed to by SD_IT.
1362 SD_IT will advance to the next element. */
1364 sd_resolve_dep (sd_iterator_def sd_it
)
1366 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1367 dep_t dep
= DEP_NODE_DEP (node
);
1368 rtx pro
= DEP_PRO (dep
);
1369 rtx con
= DEP_CON (dep
);
1371 if (dep_spec_p (dep
))
1372 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1373 INSN_RESOLVED_BACK_DEPS (con
));
1375 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1376 INSN_RESOLVED_BACK_DEPS (con
));
1378 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1379 INSN_RESOLVED_FORW_DEPS (pro
));
1382 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1383 pointed to by SD_IT to unresolved state. */
1385 sd_unresolve_dep (sd_iterator_def sd_it
)
1387 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1388 dep_t dep
= DEP_NODE_DEP (node
);
1389 rtx pro
= DEP_PRO (dep
);
1390 rtx con
= DEP_CON (dep
);
1392 if (dep_spec_p (dep
))
1393 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1394 INSN_SPEC_BACK_DEPS (con
));
1396 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1397 INSN_HARD_BACK_DEPS (con
));
1399 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1400 INSN_FORW_DEPS (pro
));
1403 /* Make TO depend on all the FROM's producers.
1404 If RESOLVED_P is true add dependencies to the resolved lists. */
1406 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1408 sd_list_types_def list_type
;
1409 sd_iterator_def sd_it
;
1412 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1414 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1416 dep_def _new_dep
, *new_dep
= &_new_dep
;
1418 copy_dep (new_dep
, dep
);
1419 DEP_CON (new_dep
) = to
;
1420 sd_add_dep (new_dep
, resolved_p
);
1424 /* Remove a dependency referred to by SD_IT.
1425 SD_IT will point to the next dependence after removal. */
1427 sd_delete_dep (sd_iterator_def sd_it
)
1429 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1430 dep_t dep
= DEP_NODE_DEP (n
);
1431 rtx pro
= DEP_PRO (dep
);
1432 rtx con
= DEP_CON (dep
);
1433 deps_list_t con_back_deps
;
1434 deps_list_t pro_forw_deps
;
1436 if (true_dependency_cache
!= NULL
)
1438 int elem_luid
= INSN_LUID (pro
);
1439 int insn_luid
= INSN_LUID (con
);
1441 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1442 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1443 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1444 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1446 if (current_sched_info
->flags
& DO_SPECULATION
)
1447 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1450 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1451 &con_back_deps
, &pro_forw_deps
);
1453 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1454 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1456 delete_dep_node (n
);
1459 /* Dump size of the lists. */
1460 #define DUMP_LISTS_SIZE (2)
1462 /* Dump dependencies of the lists. */
1463 #define DUMP_LISTS_DEPS (4)
1465 /* Dump all information about the lists. */
1466 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1468 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1469 FLAGS is a bit mask specifying what information about the lists needs
1471 If FLAGS has the very first bit set, then dump all information about
1472 the lists and propagate this bit into the callee dump functions. */
1474 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1476 sd_iterator_def sd_it
;
1483 flags
|= DUMP_LISTS_ALL
;
1485 fprintf (dump
, "[");
1487 if (flags
& DUMP_LISTS_SIZE
)
1488 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1490 if (flags
& DUMP_LISTS_DEPS
)
1492 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1494 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1495 fprintf (dump
, " ");
1500 /* Dump all information about deps_lists of INSN specified by TYPES
1503 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1505 dump_lists (stderr
, insn
, types
, 1);
1506 fprintf (stderr
, "\n");
1509 /* A wrapper around add_dependence_1, to add a dependence of CON on
1510 PRO, with type DEP_TYPE. This function implements special handling
1511 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1512 the type to REG_DEP_ANTI if we can determine that predication is
1513 impossible; otherwise we add additional true dependencies on the
1514 INSN_COND_DEPS list of the jump (which PRO must be). */
1516 add_dependence (rtx con
, rtx pro
, enum reg_note dep_type
)
1518 if (dep_type
== REG_DEP_CONTROL
1519 && !(current_sched_info
->flags
& DO_PREDICATION
))
1520 dep_type
= REG_DEP_ANTI
;
1522 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1523 so we must also make the insn dependent on the setter of the
1525 if (dep_type
== REG_DEP_CONTROL
)
1528 rtx other
= real_insn_for_shadow (real_pro
);
1531 if (other
!= NULL_RTX
)
1533 cond
= sched_get_reverse_condition_uncached (real_pro
);
1534 /* Verify that the insn does not use a different value in
1535 the condition register than the one that was present at
1537 if (cond
== NULL_RTX
)
1538 dep_type
= REG_DEP_ANTI
;
1539 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1542 CLEAR_HARD_REG_SET (uses
);
1543 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1544 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1545 dep_type
= REG_DEP_ANTI
;
1547 if (dep_type
== REG_DEP_CONTROL
)
1549 if (sched_verbose
>= 5)
1550 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1551 INSN_UID (real_pro
));
1552 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1553 REG_DEP_TRUE
, false);
1557 add_dependence_1 (con
, pro
, dep_type
);
1560 /* A convenience wrapper to operate on an entire list. HARD should be
1561 true if DEP_NONREG should be set on newly created dependencies. */
1564 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
,
1567 mark_as_hard
= hard
;
1568 for (; list
; list
= XEXP (list
, 1))
1570 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1571 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1573 mark_as_hard
= false;
1576 /* Similar, but free *LISTP at the same time, when the context
1577 is not readonly. HARD should be true if DEP_NONREG should be set on
1578 newly created dependencies. */
1581 add_dependence_list_and_free (struct deps_desc
*deps
, rtx insn
, rtx
*listp
,
1582 int uncond
, enum reg_note dep_type
, bool hard
)
1584 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1586 /* We don't want to short-circuit dependencies involving debug
1587 insns, because they may cause actual dependencies to be
1589 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1592 free_INSN_LIST_list (listp
);
1595 /* Remove all occurrences of INSN from LIST. Return the number of
1596 occurrences removed. */
1599 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1605 if (XEXP (*listp
, 0) == insn
)
1607 remove_free_INSN_LIST_node (listp
);
1612 listp
= &XEXP (*listp
, 1);
1618 /* Same as above, but process two lists at once. */
1620 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1626 if (XEXP (*listp
, 0) == insn
)
1628 remove_free_INSN_LIST_node (listp
);
1629 remove_free_EXPR_LIST_node (exprp
);
1634 listp
= &XEXP (*listp
, 1);
1635 exprp
= &XEXP (*exprp
, 1);
1641 /* Clear all dependencies for an insn. */
1643 delete_all_dependences (rtx insn
)
1645 sd_iterator_def sd_it
;
1648 /* The below cycle can be optimized to clear the caches and back_deps
1649 in one call but that would provoke duplication of code from
1652 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1653 sd_iterator_cond (&sd_it
, &dep
);)
1654 sd_delete_dep (sd_it
);
1657 /* All insns in a scheduling group except the first should only have
1658 dependencies on the previous insn in the group. So we find the
1659 first instruction in the scheduling group by walking the dependence
1660 chains backwards. Then we add the dependencies for the group to
1661 the previous nonnote insn. */
1664 chain_to_prev_insn (rtx insn
)
1666 sd_iterator_def sd_it
;
1670 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1673 rtx pro
= DEP_PRO (dep
);
1677 i
= prev_nonnote_insn (i
);
1681 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1683 if (! sched_insns_conditions_mutex_p (i
, pro
))
1684 add_dependence (i
, pro
, DEP_TYPE (dep
));
1688 delete_all_dependences (insn
);
1690 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1691 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1692 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1693 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1696 /* Process an insn's memory dependencies. There are four kinds of
1699 (0) read dependence: read follows read
1700 (1) true dependence: read follows write
1701 (2) output dependence: write follows write
1702 (3) anti dependence: write follows read
1704 We are careful to build only dependencies which actually exist, and
1705 use transitivity to avoid building too many links. */
1707 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1708 The MEM is a memory reference contained within INSN, which we are saving
1709 so that we can do memory aliasing on it. */
1712 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1719 gcc_assert (!deps
->readonly
);
1722 insn_list
= &deps
->pending_read_insns
;
1723 mem_list
= &deps
->pending_read_mems
;
1724 if (!DEBUG_INSN_P (insn
))
1725 deps
->pending_read_list_length
++;
1729 insn_list
= &deps
->pending_write_insns
;
1730 mem_list
= &deps
->pending_write_mems
;
1731 deps
->pending_write_list_length
++;
1734 link
= alloc_INSN_LIST (insn
, *insn_list
);
1737 if (sched_deps_info
->use_cselib
)
1739 mem
= shallow_copy_rtx (mem
);
1740 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1741 GET_MODE (mem
), insn
);
1743 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1747 /* Make a dependency between every memory reference on the pending lists
1748 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1749 dependencies for a read operation, similarly with FOR_WRITE. */
1752 flush_pending_lists (struct deps_desc
*deps
, rtx insn
, int for_read
,
1757 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1758 1, REG_DEP_ANTI
, true);
1759 if (!deps
->readonly
)
1761 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1762 deps
->pending_read_list_length
= 0;
1766 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1767 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1770 add_dependence_list_and_free (deps
, insn
,
1771 &deps
->last_pending_memory_flush
, 1,
1772 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1775 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1776 REG_DEP_ANTI
, true);
1778 if (DEBUG_INSN_P (insn
))
1781 free_INSN_LIST_list (&deps
->pending_read_insns
);
1782 free_INSN_LIST_list (&deps
->pending_write_insns
);
1783 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1784 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1787 if (!deps
->readonly
)
1789 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1790 deps
->pending_write_list_length
= 0;
1792 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1793 deps
->pending_flush_length
= 1;
1795 mark_as_hard
= false;
1798 /* Instruction which dependencies we are analyzing. */
1799 static rtx cur_insn
= NULL_RTX
;
1801 /* Implement hooks for haifa scheduler. */
1804 haifa_start_insn (rtx insn
)
1806 gcc_assert (insn
&& !cur_insn
);
1812 haifa_finish_insn (void)
1818 haifa_note_reg_set (int regno
)
1820 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1824 haifa_note_reg_clobber (int regno
)
1826 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1830 haifa_note_reg_use (int regno
)
1832 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1836 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1838 if (!(ds
& SPECULATIVE
))
1841 pending_mem
= NULL_RTX
;
1844 gcc_assert (ds
& BEGIN_DATA
);
1847 dep_def _dep
, *dep
= &_dep
;
1849 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1850 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1851 DEP_NONREG (dep
) = 1;
1852 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1858 haifa_note_dep (rtx elem
, ds_t ds
)
1863 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1865 DEP_NONREG (dep
) = 1;
1866 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1870 note_reg_use (int r
)
1872 if (sched_deps_info
->note_reg_use
)
1873 sched_deps_info
->note_reg_use (r
);
1877 note_reg_set (int r
)
1879 if (sched_deps_info
->note_reg_set
)
1880 sched_deps_info
->note_reg_set (r
);
1884 note_reg_clobber (int r
)
1886 if (sched_deps_info
->note_reg_clobber
)
1887 sched_deps_info
->note_reg_clobber (r
);
1891 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1893 if (sched_deps_info
->note_mem_dep
)
1894 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1898 note_dep (rtx e
, ds_t ds
)
1900 if (sched_deps_info
->note_dep
)
1901 sched_deps_info
->note_dep (e
, ds
);
1904 /* Return corresponding to DS reg_note. */
1909 return REG_DEP_TRUE
;
1910 else if (ds
& DEP_OUTPUT
)
1911 return REG_DEP_OUTPUT
;
1912 else if (ds
& DEP_ANTI
)
1913 return REG_DEP_ANTI
;
1916 gcc_assert (ds
& DEP_CONTROL
);
1917 return REG_DEP_CONTROL
;
1923 /* Functions for computation of info needed for register pressure
1924 sensitive insn scheduling. */
1927 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1928 static struct reg_use_data
*
1929 create_insn_reg_use (int regno
, rtx insn
)
1931 struct reg_use_data
*use
;
1933 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1936 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1937 INSN_REG_USE_LIST (insn
) = use
;
1941 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1942 static struct reg_set_data
*
1943 create_insn_reg_set (int regno
, rtx insn
)
1945 struct reg_set_data
*set
;
1947 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1950 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1951 INSN_REG_SET_LIST (insn
) = set
;
1955 /* Set up insn register uses for INSN and dependency context DEPS. */
1957 setup_insn_reg_uses (struct deps_desc
*deps
, rtx insn
)
1960 reg_set_iterator rsi
;
1962 struct reg_use_data
*use
, *use2
, *next
;
1963 struct deps_reg
*reg_last
;
1965 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1967 if (i
< FIRST_PSEUDO_REGISTER
1968 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1971 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1972 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1973 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1974 /* Ignore use which is not dying. */
1977 use
= create_insn_reg_use (i
, insn
);
1978 use
->next_regno_use
= use
;
1979 reg_last
= &deps
->reg_last
[i
];
1981 /* Create the cycle list of uses. */
1982 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1984 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1985 next
= use
->next_regno_use
;
1986 use
->next_regno_use
= use2
;
1987 use2
->next_regno_use
= next
;
1992 /* Register pressure info for the currently processed insn. */
1993 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1995 /* Return TRUE if INSN has the use structure for REGNO. */
1997 insn_use_p (rtx insn
, int regno
)
1999 struct reg_use_data
*use
;
2001 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2002 if (use
->regno
== regno
)
2007 /* Update the register pressure info after birth of pseudo register REGNO
2008 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2009 the register is in clobber or unused after the insn. */
2011 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2016 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2017 cl
= sched_regno_pressure_class
[regno
];
2020 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2023 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2024 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2028 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2029 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2033 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2034 reg_pressure_info
[cl
].set_increase
= new_incr
;
2035 if (! insn_use_p (insn
, regno
))
2036 reg_pressure_info
[cl
].change
+= incr
;
2037 create_insn_reg_set (regno
, insn
);
2039 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2043 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2044 hard registers involved in the birth. */
2046 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2047 bool clobber_p
, bool unused_p
)
2050 int new_incr
, last
= regno
+ nregs
;
2052 while (regno
< last
)
2054 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2055 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2057 cl
= sched_regno_pressure_class
[regno
];
2062 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2063 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2067 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2068 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2072 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2073 reg_pressure_info
[cl
].set_increase
= new_incr
;
2074 if (! insn_use_p (insn
, regno
))
2075 reg_pressure_info
[cl
].change
+= 1;
2076 create_insn_reg_set (regno
, insn
);
2078 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2085 /* Update the register pressure info after birth of pseudo or hard
2086 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2087 correspondingly that the register is in clobber or unused after the
2090 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2094 if (GET_CODE (reg
) == SUBREG
)
2095 reg
= SUBREG_REG (reg
);
2100 regno
= REGNO (reg
);
2101 if (regno
< FIRST_PSEUDO_REGISTER
)
2102 mark_insn_hard_regno_birth (insn
, regno
,
2103 hard_regno_nregs
[regno
][GET_MODE (reg
)],
2104 clobber_p
, unused_p
);
2106 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2109 /* Update the register pressure info after death of pseudo register
2112 mark_pseudo_death (int regno
)
2117 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2118 cl
= sched_regno_pressure_class
[regno
];
2121 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2122 reg_pressure_info
[cl
].change
-= incr
;
2126 /* Like mark_pseudo_death except that NREGS saying how many hard
2127 registers involved in the death. */
2129 mark_hard_regno_death (int regno
, int nregs
)
2132 int last
= regno
+ nregs
;
2134 while (regno
< last
)
2136 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2137 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2139 cl
= sched_regno_pressure_class
[regno
];
2141 reg_pressure_info
[cl
].change
-= 1;
2147 /* Update the register pressure info after death of pseudo or hard
2150 mark_reg_death (rtx reg
)
2154 if (GET_CODE (reg
) == SUBREG
)
2155 reg
= SUBREG_REG (reg
);
2160 regno
= REGNO (reg
);
2161 if (regno
< FIRST_PSEUDO_REGISTER
)
2162 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
2164 mark_pseudo_death (regno
);
2167 /* Process SETTER of REG. DATA is an insn containing the setter. */
2169 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2171 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2174 ((rtx
) data
, reg
, false,
2175 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2178 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2180 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2182 if (GET_CODE (setter
) == CLOBBER
)
2183 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2186 /* Set up reg pressure info related to INSN. */
2188 init_insn_reg_pressure_info (rtx insn
)
2192 static struct reg_pressure_data
*pressure_info
;
2195 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2197 if (! INSN_P (insn
))
2200 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2202 cl
= ira_pressure_classes
[i
];
2203 reg_pressure_info
[cl
].clobber_increase
= 0;
2204 reg_pressure_info
[cl
].set_increase
= 0;
2205 reg_pressure_info
[cl
].unused_set_increase
= 0;
2206 reg_pressure_info
[cl
].change
= 0;
2209 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2211 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2214 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2215 if (REG_NOTE_KIND (link
) == REG_INC
)
2216 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2219 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2220 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2221 mark_reg_death (XEXP (link
, 0));
2223 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2225 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2226 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2227 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2229 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2231 cl
= ira_pressure_classes
[i
];
2232 pressure_info
[i
].clobber_increase
2233 = reg_pressure_info
[cl
].clobber_increase
;
2234 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2235 pressure_info
[i
].unused_set_increase
2236 = reg_pressure_info
[cl
].unused_set_increase
;
2237 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2244 /* Internal variable for sched_analyze_[12] () functions.
2245 If it is nonzero, this means that sched_analyze_[12] looks
2246 at the most toplevel SET. */
2247 static bool can_start_lhs_rhs_p
;
2249 /* Extend reg info for the deps context DEPS given that
2250 we have just generated a register numbered REGNO. */
2252 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2254 int max_regno
= regno
+ 1;
2256 gcc_assert (!reload_completed
);
2258 /* In a readonly context, it would not hurt to extend info,
2259 but it should not be needed. */
2260 if (reload_completed
&& deps
->readonly
)
2262 deps
->max_reg
= max_regno
;
2266 if (max_regno
> deps
->max_reg
)
2268 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2270 memset (&deps
->reg_last
[deps
->max_reg
],
2271 0, (max_regno
- deps
->max_reg
)
2272 * sizeof (struct deps_reg
));
2273 deps
->max_reg
= max_regno
;
2277 /* Extends REG_INFO_P if needed. */
2279 maybe_extend_reg_info_p (void)
2281 /* Extend REG_INFO_P, if needed. */
2282 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2284 size_t new_reg_info_p_size
= max_regno
+ 128;
2286 gcc_assert (!reload_completed
&& sel_sched_p ());
2288 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2289 new_reg_info_p_size
,
2291 sizeof (*reg_info_p
));
2292 reg_info_p_size
= new_reg_info_p_size
;
2296 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2297 The type of the reference is specified by REF and can be SET,
2298 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2301 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2302 enum rtx_code ref
, rtx insn
)
2304 /* We could emit new pseudos in renaming. Extend the reg structures. */
2305 if (!reload_completed
&& sel_sched_p ()
2306 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2307 extend_deps_reg_info (deps
, regno
);
2309 maybe_extend_reg_info_p ();
2311 /* A hard reg in a wide mode may really be multiple registers.
2312 If so, mark all of them just like the first. */
2313 if (regno
< FIRST_PSEUDO_REGISTER
)
2315 int i
= hard_regno_nregs
[regno
][mode
];
2319 note_reg_set (regno
+ i
);
2321 else if (ref
== USE
)
2324 note_reg_use (regno
+ i
);
2329 note_reg_clobber (regno
+ i
);
2333 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2334 it does not reload. Ignore these as they have served their
2336 else if (regno
>= deps
->max_reg
)
2338 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2339 gcc_assert (code
== USE
|| code
== CLOBBER
);
2345 note_reg_set (regno
);
2346 else if (ref
== USE
)
2347 note_reg_use (regno
);
2349 note_reg_clobber (regno
);
2351 /* Pseudos that are REG_EQUIV to something may be replaced
2352 by that during reloading. We need only add dependencies for
2353 the address in the REG_EQUIV note. */
2354 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2356 rtx t
= get_reg_known_value (regno
);
2358 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2361 /* Don't let it cross a call after scheduling if it doesn't
2362 already cross one. */
2363 if (REG_N_CALLS_CROSSED (regno
) == 0)
2365 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2366 deps
->sched_before_next_call
2367 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2369 add_dependence_list (insn
, deps
->last_function_call
, 1,
2370 REG_DEP_ANTI
, false);
2375 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2376 rtx, X, creating all dependencies generated by the write to the
2377 destination of X, and reads of everything mentioned. */
2380 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2382 rtx dest
= XEXP (x
, 0);
2383 enum rtx_code code
= GET_CODE (x
);
2384 bool cslr_p
= can_start_lhs_rhs_p
;
2386 can_start_lhs_rhs_p
= false;
2392 if (cslr_p
&& sched_deps_info
->start_lhs
)
2393 sched_deps_info
->start_lhs (dest
);
2395 if (GET_CODE (dest
) == PARALLEL
)
2399 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2400 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2401 sched_analyze_1 (deps
,
2402 gen_rtx_CLOBBER (VOIDmode
,
2403 XEXP (XVECEXP (dest
, 0, i
), 0)),
2406 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2407 sched_deps_info
->finish_lhs ();
2411 can_start_lhs_rhs_p
= cslr_p
;
2413 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2415 can_start_lhs_rhs_p
= false;
2421 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2422 || GET_CODE (dest
) == ZERO_EXTRACT
)
2424 if (GET_CODE (dest
) == STRICT_LOW_PART
2425 || GET_CODE (dest
) == ZERO_EXTRACT
2426 || df_read_modify_subreg_p (dest
))
2428 /* These both read and modify the result. We must handle
2429 them as writes to get proper dependencies for following
2430 instructions. We must handle them as reads to get proper
2431 dependencies from this to previous instructions.
2432 Thus we need to call sched_analyze_2. */
2434 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2436 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2438 /* The second and third arguments are values read by this insn. */
2439 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2440 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2442 dest
= XEXP (dest
, 0);
2447 int regno
= REGNO (dest
);
2448 enum machine_mode mode
= GET_MODE (dest
);
2450 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2453 /* Treat all writes to a stack register as modifying the TOS. */
2454 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2456 /* Avoid analyzing the same register twice. */
2457 if (regno
!= FIRST_STACK_REG
)
2458 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2460 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2465 else if (MEM_P (dest
))
2467 /* Writing memory. */
2470 if (sched_deps_info
->use_cselib
)
2472 enum machine_mode address_mode
= get_address_mode (dest
);
2474 t
= shallow_copy_rtx (dest
);
2475 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2476 GET_MODE (t
), insn
);
2478 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2483 /* Pending lists can't get larger with a readonly context. */
2485 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2486 > MAX_PENDING_LIST_LENGTH
))
2488 /* Flush all pending reads and writes to prevent the pending lists
2489 from getting any larger. Insn scheduling runs too slowly when
2490 these lists get long. When compiling GCC with itself,
2491 this flush occurs 8 times for sparc, and 10 times for m88k using
2492 the default value of 32. */
2493 flush_pending_lists (deps
, insn
, false, true);
2497 rtx pending
, pending_mem
;
2499 pending
= deps
->pending_read_insns
;
2500 pending_mem
= deps
->pending_read_mems
;
2503 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2504 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2505 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2508 pending
= XEXP (pending
, 1);
2509 pending_mem
= XEXP (pending_mem
, 1);
2512 pending
= deps
->pending_write_insns
;
2513 pending_mem
= deps
->pending_write_mems
;
2516 if (output_dependence (XEXP (pending_mem
, 0), t
)
2517 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2518 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2521 pending
= XEXP (pending
, 1);
2522 pending_mem
= XEXP (pending_mem
, 1);
2525 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2526 REG_DEP_ANTI
, true);
2527 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2528 REG_DEP_CONTROL
, true);
2530 if (!deps
->readonly
)
2531 add_insn_mem_dependence (deps
, false, insn
, dest
);
2533 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2536 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2537 sched_deps_info
->finish_lhs ();
2539 /* Analyze reads. */
2540 if (GET_CODE (x
) == SET
)
2542 can_start_lhs_rhs_p
= cslr_p
;
2544 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2546 can_start_lhs_rhs_p
= false;
2550 /* Analyze the uses of memory and registers in rtx X in INSN. */
2552 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2558 bool cslr_p
= can_start_lhs_rhs_p
;
2560 can_start_lhs_rhs_p
= false;
2566 if (cslr_p
&& sched_deps_info
->start_rhs
)
2567 sched_deps_info
->start_rhs (x
);
2569 code
= GET_CODE (x
);
2577 /* Ignore constants. */
2578 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2579 sched_deps_info
->finish_rhs ();
2585 /* User of CC0 depends on immediately preceding insn. */
2586 SCHED_GROUP_P (insn
) = 1;
2587 /* Don't move CC0 setter to another block (it can set up the
2588 same flag for previous CC0 users which is safe). */
2589 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2591 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2592 sched_deps_info
->finish_rhs ();
2599 int regno
= REGNO (x
);
2600 enum machine_mode mode
= GET_MODE (x
);
2602 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2605 /* Treat all reads of a stack register as modifying the TOS. */
2606 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2608 /* Avoid analyzing the same register twice. */
2609 if (regno
!= FIRST_STACK_REG
)
2610 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2611 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2615 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2616 sched_deps_info
->finish_rhs ();
2623 /* Reading memory. */
2625 rtx pending
, pending_mem
;
2628 if (sched_deps_info
->use_cselib
)
2630 enum machine_mode address_mode
= get_address_mode (t
);
2632 t
= shallow_copy_rtx (t
);
2633 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2634 GET_MODE (t
), insn
);
2636 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2640 if (!DEBUG_INSN_P (insn
))
2643 pending
= deps
->pending_read_insns
;
2644 pending_mem
= deps
->pending_read_mems
;
2647 if (read_dependence (XEXP (pending_mem
, 0), t
)
2648 && ! sched_insns_conditions_mutex_p (insn
,
2650 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2653 pending
= XEXP (pending
, 1);
2654 pending_mem
= XEXP (pending_mem
, 1);
2657 pending
= deps
->pending_write_insns
;
2658 pending_mem
= deps
->pending_write_mems
;
2661 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
, t
)
2662 && ! sched_insns_conditions_mutex_p (insn
,
2664 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2665 sched_deps_info
->generate_spec_deps
2666 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2668 pending
= XEXP (pending
, 1);
2669 pending_mem
= XEXP (pending_mem
, 1);
2672 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2673 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2675 for (u
= deps
->pending_jump_insns
; u
; u
= XEXP (u
, 1))
2676 if (deps_may_trap_p (x
))
2678 if ((sched_deps_info
->generate_spec_deps
)
2679 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2681 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2684 note_dep (XEXP (u
, 0), ds
);
2687 add_dependence (insn
, XEXP (u
, 0), REG_DEP_CONTROL
);
2691 /* Always add these dependencies to pending_reads, since
2692 this insn may be followed by a write. */
2693 if (!deps
->readonly
)
2694 add_insn_mem_dependence (deps
, true, insn
, x
);
2696 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2698 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2699 sched_deps_info
->finish_rhs ();
2704 /* Force pending stores to memory in case a trap handler needs them. */
2706 flush_pending_lists (deps
, insn
, true, false);
2710 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2711 reg_pending_barrier
= TRUE_BARRIER
;
2712 /* Prefetch insn contains addresses only. So if the prefetch
2713 address has no registers, there will be no dependencies on
2714 the prefetch insn. This is wrong with result code
2715 correctness point of view as such prefetch can be moved below
2716 a jump insn which usually generates MOVE_BARRIER preventing
2717 to move insns containing registers or memories through the
2718 barrier. It is also wrong with generated code performance
2719 point of view as prefetch withouth dependecies will have a
2720 tendency to be issued later instead of earlier. It is hard
2721 to generate accurate dependencies for prefetch insns as
2722 prefetch has only the start address but it is better to have
2723 something than nothing. */
2724 if (!deps
->readonly
)
2726 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2727 if (sched_deps_info
->use_cselib
)
2728 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2729 add_insn_mem_dependence (deps
, true, insn
, x
);
2733 case UNSPEC_VOLATILE
:
2734 flush_pending_lists (deps
, insn
, true, true);
2740 /* Traditional and volatile asm instructions must be considered to use
2741 and clobber all hard registers, all pseudo-registers and all of
2742 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2744 Consider for instance a volatile asm that changes the fpu rounding
2745 mode. An insn should not be moved across this even if it only uses
2746 pseudo-regs because it might give an incorrectly rounded result. */
2747 if ((code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2748 && !DEBUG_INSN_P (insn
))
2749 reg_pending_barrier
= TRUE_BARRIER
;
2751 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2752 We can not just fall through here since then we would be confused
2753 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2754 traditional asms unlike their normal usage. */
2756 if (code
== ASM_OPERANDS
)
2758 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2759 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2761 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2762 sched_deps_info
->finish_rhs ();
2773 /* These both read and modify the result. We must handle them as writes
2774 to get proper dependencies for following instructions. We must handle
2775 them as reads to get proper dependencies from this to previous
2776 instructions. Thus we need to pass them to both sched_analyze_1
2777 and sched_analyze_2. We must call sched_analyze_2 first in order
2778 to get the proper antecedent for the read. */
2779 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2780 sched_analyze_1 (deps
, x
, insn
);
2782 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2783 sched_deps_info
->finish_rhs ();
2789 /* op0 = op0 + op1 */
2790 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2791 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2792 sched_analyze_1 (deps
, x
, insn
);
2794 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2795 sched_deps_info
->finish_rhs ();
2803 /* Other cases: walk the insn. */
2804 fmt
= GET_RTX_FORMAT (code
);
2805 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2808 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2809 else if (fmt
[i
] == 'E')
2810 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2811 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2814 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2815 sched_deps_info
->finish_rhs ();
2818 /* Analyze an INSN with pattern X to find all dependencies. */
2820 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx insn
)
2822 RTX_CODE code
= GET_CODE (x
);
2825 reg_set_iterator rsi
;
2827 if (! reload_completed
)
2831 extract_insn (insn
);
2832 preprocess_constraints ();
2833 ira_implicitly_set_insn_hard_regs (&temp
);
2834 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2835 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2838 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2842 /* Avoid moving trapping instructions across function calls that might
2843 not always return. */
2844 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2845 1, REG_DEP_ANTI
, true);
2847 /* We must avoid creating a situation in which two successors of the
2848 current block have different unwind info after scheduling. If at any
2849 point the two paths re-join this leads to incorrect unwind info. */
2850 /* ??? There are certain situations involving a forced frame pointer in
2851 which, with extra effort, we could fix up the unwind info at a later
2852 CFG join. However, it seems better to notice these cases earlier
2853 during prologue generation and avoid marking the frame pointer setup
2854 as frame-related at all. */
2855 if (RTX_FRAME_RELATED_P (insn
))
2857 /* Make sure prologue insn is scheduled before next jump. */
2858 deps
->sched_before_next_jump
2859 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2861 /* Make sure epilogue insn is scheduled after preceding jumps. */
2862 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2866 if (code
== COND_EXEC
)
2868 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2870 /* ??? Should be recording conditions so we reduce the number of
2871 false dependencies. */
2872 x
= COND_EXEC_CODE (x
);
2873 code
= GET_CODE (x
);
2875 if (code
== SET
|| code
== CLOBBER
)
2877 sched_analyze_1 (deps
, x
, insn
);
2879 /* Bare clobber insns are used for letting life analysis, reg-stack
2880 and others know that a value is dead. Depend on the last call
2881 instruction so that reg-stack won't get confused. */
2882 if (code
== CLOBBER
)
2883 add_dependence_list (insn
, deps
->last_function_call
, 1,
2884 REG_DEP_OUTPUT
, true);
2886 else if (code
== PARALLEL
)
2888 for (i
= XVECLEN (x
, 0); i
--;)
2890 rtx sub
= XVECEXP (x
, 0, i
);
2891 code
= GET_CODE (sub
);
2893 if (code
== COND_EXEC
)
2895 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2896 sub
= COND_EXEC_CODE (sub
);
2897 code
= GET_CODE (sub
);
2899 if (code
== SET
|| code
== CLOBBER
)
2900 sched_analyze_1 (deps
, sub
, insn
);
2902 sched_analyze_2 (deps
, sub
, insn
);
2906 sched_analyze_2 (deps
, x
, insn
);
2908 /* Mark registers CLOBBERED or used by called function. */
2911 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2913 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2914 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2915 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2916 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2918 /* Don't schedule anything after a tail call, tail call needs
2919 to use at least all call-saved registers. */
2920 if (SIBLING_CALL_P (insn
))
2921 reg_pending_barrier
= TRUE_BARRIER
;
2922 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2923 reg_pending_barrier
= MOVE_BARRIER
;
2929 next
= next_nonnote_nondebug_insn (insn
);
2930 if (next
&& BARRIER_P (next
))
2931 reg_pending_barrier
= MOVE_BARRIER
;
2934 rtx pending
, pending_mem
;
2936 if (sched_deps_info
->compute_jump_reg_dependencies
)
2938 (*sched_deps_info
->compute_jump_reg_dependencies
)
2939 (insn
, reg_pending_control_uses
);
2941 /* Make latency of jump equal to 0 by using anti-dependence. */
2942 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
2944 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2945 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
2947 add_dependence_list (insn
, reg_last
->implicit_sets
,
2948 0, REG_DEP_ANTI
, false);
2949 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2950 REG_DEP_ANTI
, false);
2954 /* All memory writes and volatile reads must happen before the
2955 jump. Non-volatile reads must happen before the jump iff
2956 the result is needed by the above register used mask. */
2958 pending
= deps
->pending_write_insns
;
2959 pending_mem
= deps
->pending_write_mems
;
2962 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2963 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2964 pending
= XEXP (pending
, 1);
2965 pending_mem
= XEXP (pending_mem
, 1);
2968 pending
= deps
->pending_read_insns
;
2969 pending_mem
= deps
->pending_read_mems
;
2972 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2973 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2974 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2975 pending
= XEXP (pending
, 1);
2976 pending_mem
= XEXP (pending_mem
, 1);
2979 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2980 REG_DEP_ANTI
, true);
2981 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2982 REG_DEP_ANTI
, true);
2986 /* If this instruction can throw an exception, then moving it changes
2987 where block boundaries fall. This is mighty confusing elsewhere.
2988 Therefore, prevent such an instruction from being moved. Same for
2989 non-jump instructions that define block boundaries.
2990 ??? Unclear whether this is still necessary in EBB mode. If not,
2991 add_branch_dependences should be adjusted for RGN mode instead. */
2992 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2993 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2994 reg_pending_barrier
= MOVE_BARRIER
;
2996 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2998 setup_insn_reg_uses (deps
, insn
);
2999 init_insn_reg_pressure_info (insn
);
3002 /* Add register dependencies for insn. */
3003 if (DEBUG_INSN_P (insn
))
3005 rtx prev
= deps
->last_debug_insn
;
3008 if (!deps
->readonly
)
3009 deps
->last_debug_insn
= insn
;
3012 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3014 add_dependence_list (insn
, deps
->last_function_call
, 1,
3015 REG_DEP_ANTI
, false);
3017 if (!sel_sched_p ())
3018 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3019 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3021 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3023 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3024 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3025 /* There's no point in making REG_DEP_CONTROL dependencies for
3027 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3030 if (!deps
->readonly
)
3031 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3033 CLEAR_REG_SET (reg_pending_uses
);
3035 /* Quite often, a debug insn will refer to stuff in the
3036 previous instruction, but the reason we want this
3037 dependency here is to make sure the scheduler doesn't
3038 gratuitously move a debug insn ahead. This could dirty
3039 DF flags and cause additional analysis that wouldn't have
3040 occurred in compilation without debug insns, and such
3041 additional analysis can modify the generated code. */
3042 prev
= PREV_INSN (insn
);
3044 if (prev
&& NONDEBUG_INSN_P (prev
))
3045 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3049 regset_head set_or_clobbered
;
3051 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3053 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3054 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3055 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3057 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3060 if (!deps
->readonly
)
3062 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3063 reg_last
->uses_length
++;
3067 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3068 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3070 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3071 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3072 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3073 REG_DEP_ANTI
, false);
3074 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3077 if (!deps
->readonly
)
3079 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3080 reg_last
->uses_length
++;
3084 if (targetm
.sched
.exposed_pipeline
)
3086 INIT_REG_SET (&set_or_clobbered
);
3087 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3089 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3091 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3093 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3095 rtx other
= XEXP (list
, 0);
3096 if (INSN_CACHED_COND (other
) != const_true_rtx
3097 && refers_to_regno_p (i
, i
+ 1, INSN_CACHED_COND (other
), NULL
))
3098 INSN_CACHED_COND (other
) = const_true_rtx
;
3103 /* If the current insn is conditional, we can't free any
3105 if (sched_has_condition_p (insn
))
3107 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3109 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3110 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3112 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3113 REG_DEP_ANTI
, false);
3114 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3116 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3117 REG_DEP_CONTROL
, false);
3119 if (!deps
->readonly
)
3122 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3123 reg_last
->clobbers_length
++;
3126 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3128 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3129 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3131 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3132 REG_DEP_ANTI
, false);
3133 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3135 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3137 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3138 REG_DEP_CONTROL
, false);
3140 if (!deps
->readonly
)
3141 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3146 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3148 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3149 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
3150 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
3152 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3153 REG_DEP_OUTPUT
, false);
3154 add_dependence_list_and_free (deps
, insn
,
3155 ®_last
->implicit_sets
, 0,
3156 REG_DEP_ANTI
, false);
3157 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3158 REG_DEP_ANTI
, false);
3159 add_dependence_list_and_free (deps
, insn
,
3160 ®_last
->control_uses
, 0,
3161 REG_DEP_ANTI
, false);
3162 add_dependence_list_and_free (deps
, insn
,
3163 ®_last
->clobbers
, 0,
3164 REG_DEP_OUTPUT
, false);
3166 if (!deps
->readonly
)
3168 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3169 reg_last
->clobbers_length
= 0;
3170 reg_last
->uses_length
= 0;
3175 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3177 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3178 REG_DEP_ANTI
, false);
3179 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3181 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3182 REG_DEP_CONTROL
, false);
3185 if (!deps
->readonly
)
3187 reg_last
->clobbers_length
++;
3189 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3192 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3194 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3196 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3197 REG_DEP_OUTPUT
, false);
3198 add_dependence_list_and_free (deps
, insn
,
3199 ®_last
->implicit_sets
,
3200 0, REG_DEP_ANTI
, false);
3201 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3202 REG_DEP_OUTPUT
, false);
3203 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3204 REG_DEP_ANTI
, false);
3205 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3206 REG_DEP_CONTROL
, false);
3208 if (!deps
->readonly
)
3210 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3211 reg_last
->uses_length
= 0;
3212 reg_last
->clobbers_length
= 0;
3216 if (!deps
->readonly
)
3218 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3220 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3221 reg_last
->control_uses
3222 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3227 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3228 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3230 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3231 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3232 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3233 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3234 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3237 if (!deps
->readonly
)
3238 reg_last
->implicit_sets
3239 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3242 if (!deps
->readonly
)
3244 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3245 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3246 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3247 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3248 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3249 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3250 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3252 /* Set up the pending barrier found. */
3253 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3256 CLEAR_REG_SET (reg_pending_uses
);
3257 CLEAR_REG_SET (reg_pending_clobbers
);
3258 CLEAR_REG_SET (reg_pending_sets
);
3259 CLEAR_REG_SET (reg_pending_control_uses
);
3260 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3261 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3263 /* Add dependencies if a scheduling barrier was found. */
3264 if (reg_pending_barrier
)
3266 /* In the case of barrier the most added dependencies are not
3267 real, so we use anti-dependence here. */
3268 if (sched_has_condition_p (insn
))
3270 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3272 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3273 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3275 add_dependence_list (insn
, reg_last
->sets
, 0,
3276 reg_pending_barrier
== TRUE_BARRIER
3277 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3278 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3279 REG_DEP_ANTI
, true);
3280 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3281 reg_pending_barrier
== TRUE_BARRIER
3282 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3287 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3289 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3290 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3291 REG_DEP_ANTI
, true);
3292 add_dependence_list_and_free (deps
, insn
,
3293 ®_last
->control_uses
, 0,
3294 REG_DEP_CONTROL
, true);
3295 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3296 reg_pending_barrier
== TRUE_BARRIER
3297 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3299 add_dependence_list_and_free (deps
, insn
,
3300 ®_last
->implicit_sets
, 0,
3301 REG_DEP_ANTI
, true);
3302 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3303 reg_pending_barrier
== TRUE_BARRIER
3304 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3307 if (!deps
->readonly
)
3309 reg_last
->uses_length
= 0;
3310 reg_last
->clobbers_length
= 0;
3315 if (!deps
->readonly
)
3316 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3318 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3319 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3320 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3323 /* Don't flush pending lists on speculative checks for
3324 selective scheduling. */
3325 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn
))
3326 flush_pending_lists (deps
, insn
, true, true);
3328 reg_pending_barrier
= NOT_A_BARRIER
;
3331 /* If a post-call group is still open, see if it should remain so.
3332 This insn must be a simple move of a hard reg to a pseudo or
3335 We must avoid moving these insns for correctness on targets
3336 with small register classes, and for special registers like
3337 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3338 hard regs for all targets. */
3340 if (deps
->in_post_call_group_p
)
3342 rtx tmp
, set
= single_set (insn
);
3343 int src_regno
, dest_regno
;
3347 if (DEBUG_INSN_P (insn
))
3348 /* We don't want to mark debug insns as part of the same
3349 sched group. We know they really aren't, but if we use
3350 debug insns to tell that a call group is over, we'll
3351 get different code if debug insns are not there and
3352 instructions that follow seem like they should be part
3355 Also, if we did, chain_to_prev_insn would move the
3356 deps of the debug insn to the call insn, modifying
3357 non-debug post-dependency counts of the debug insn
3358 dependencies and otherwise messing with the scheduling
3361 Instead, let such debug insns be scheduled freely, but
3362 keep the call group open in case there are insns that
3363 should be part of it afterwards. Since we grant debug
3364 insns higher priority than even sched group insns, it
3365 will all turn out all right. */
3366 goto debug_dont_end_call_group
;
3368 goto end_call_group
;
3371 tmp
= SET_DEST (set
);
3372 if (GET_CODE (tmp
) == SUBREG
)
3373 tmp
= SUBREG_REG (tmp
);
3375 dest_regno
= REGNO (tmp
);
3377 goto end_call_group
;
3379 tmp
= SET_SRC (set
);
3380 if (GET_CODE (tmp
) == SUBREG
)
3381 tmp
= SUBREG_REG (tmp
);
3382 if ((GET_CODE (tmp
) == PLUS
3383 || GET_CODE (tmp
) == MINUS
)
3384 && REG_P (XEXP (tmp
, 0))
3385 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3386 && dest_regno
== STACK_POINTER_REGNUM
)
3387 src_regno
= STACK_POINTER_REGNUM
;
3388 else if (REG_P (tmp
))
3389 src_regno
= REGNO (tmp
);
3391 goto end_call_group
;
3393 if (src_regno
< FIRST_PSEUDO_REGISTER
3394 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3397 && deps
->in_post_call_group_p
== post_call_initial
)
3398 deps
->in_post_call_group_p
= post_call
;
3400 if (!sel_sched_p () || sched_emulate_haifa_p
)
3402 SCHED_GROUP_P (insn
) = 1;
3403 CANT_MOVE (insn
) = 1;
3409 if (!deps
->readonly
)
3410 deps
->in_post_call_group_p
= not_post_call
;
3414 debug_dont_end_call_group
:
3415 if ((current_sched_info
->flags
& DO_SPECULATION
)
3416 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3417 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3421 sel_mark_hard_insn (insn
);
3424 sd_iterator_def sd_it
;
3427 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3428 sd_iterator_cond (&sd_it
, &dep
);)
3429 change_spec_dep_to_hard (sd_it
);
3434 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3435 longjmp, loop forever, ...). */
3436 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3437 test for ECF_NORETURN? */
3439 call_may_noreturn_p (rtx insn
)
3443 /* const or pure calls that aren't looping will always return. */
3444 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3445 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3448 call
= get_call_rtx_from (insn
);
3449 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3451 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3452 if (SYMBOL_REF_DECL (symbol
)
3453 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3455 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3457 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3460 case BUILT_IN_BCOPY
:
3461 case BUILT_IN_BZERO
:
3462 case BUILT_IN_INDEX
:
3463 case BUILT_IN_MEMCHR
:
3464 case BUILT_IN_MEMCMP
:
3465 case BUILT_IN_MEMCPY
:
3466 case BUILT_IN_MEMMOVE
:
3467 case BUILT_IN_MEMPCPY
:
3468 case BUILT_IN_MEMSET
:
3469 case BUILT_IN_RINDEX
:
3470 case BUILT_IN_STPCPY
:
3471 case BUILT_IN_STPNCPY
:
3472 case BUILT_IN_STRCAT
:
3473 case BUILT_IN_STRCHR
:
3474 case BUILT_IN_STRCMP
:
3475 case BUILT_IN_STRCPY
:
3476 case BUILT_IN_STRCSPN
:
3477 case BUILT_IN_STRLEN
:
3478 case BUILT_IN_STRNCAT
:
3479 case BUILT_IN_STRNCMP
:
3480 case BUILT_IN_STRNCPY
:
3481 case BUILT_IN_STRPBRK
:
3482 case BUILT_IN_STRRCHR
:
3483 case BUILT_IN_STRSPN
:
3484 case BUILT_IN_STRSTR
:
3485 /* Assume certain string/memory builtins always return. */
3493 /* For all other calls assume that they might not always return. */
3497 /* Return true if INSN should be made dependent on the previous instruction
3498 group, and if all INSN's dependencies should be moved to the first
3499 instruction of that group. */
3502 chain_to_prev_insn_p (rtx insn
)
3506 /* INSN forms a group with the previous instruction. */
3507 if (SCHED_GROUP_P (insn
))
3510 /* If the previous instruction clobbers a register R and this one sets
3511 part of R, the clobber was added specifically to help us track the
3512 liveness of R. There's no point scheduling the clobber and leaving
3513 INSN behind, especially if we move the clobber to another block. */
3514 prev
= prev_nonnote_nondebug_insn (insn
);
3517 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3518 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3520 x
= XEXP (PATTERN (prev
), 0);
3521 if (set_of (x
, insn
))
3528 /* Analyze INSN with DEPS as a context. */
3530 deps_analyze_insn (struct deps_desc
*deps
, rtx insn
)
3532 if (sched_deps_info
->start_insn
)
3533 sched_deps_info
->start_insn (insn
);
3535 /* Record the condition for this insn. */
3536 if (NONDEBUG_INSN_P (insn
))
3539 sched_get_condition_with_rev (insn
, NULL
);
3540 t
= INSN_CACHED_COND (insn
);
3541 INSN_COND_DEPS (insn
) = NULL_RTX
;
3542 if (reload_completed
3543 && (current_sched_info
->flags
& DO_PREDICATION
)
3545 && REG_P (XEXP (t
, 0))
3546 && CONSTANT_P (XEXP (t
, 1)))
3552 nregs
= hard_regno_nregs
[regno
][GET_MODE (t
)];
3556 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3557 t
= concat_INSN_LIST (reg_last
->sets
, t
);
3558 t
= concat_INSN_LIST (reg_last
->clobbers
, t
);
3559 t
= concat_INSN_LIST (reg_last
->implicit_sets
, t
);
3561 INSN_COND_DEPS (insn
) = t
;
3567 /* Make each JUMP_INSN (but not a speculative check)
3568 a scheduling barrier for memory references. */
3571 && sel_insn_is_speculation_check (insn
)))
3573 /* Keep the list a reasonable size. */
3574 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3575 flush_pending_lists (deps
, insn
, true, true);
3577 deps
->pending_jump_insns
3578 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3581 /* For each insn which shouldn't cross a jump, add a dependence. */
3582 add_dependence_list_and_free (deps
, insn
,
3583 &deps
->sched_before_next_jump
, 1,
3584 REG_DEP_ANTI
, true);
3586 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3588 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3590 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3592 else if (CALL_P (insn
))
3596 CANT_MOVE (insn
) = 1;
3598 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3600 /* This is setjmp. Assume that all registers, not just
3601 hard registers, may be clobbered by this call. */
3602 reg_pending_barrier
= MOVE_BARRIER
;
3606 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3607 /* A call may read and modify global register variables. */
3610 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3611 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3613 /* Other call-clobbered hard regs may be clobbered.
3614 Since we only have a choice between 'might be clobbered'
3615 and 'definitely not clobbered', we must include all
3616 partly call-clobbered registers here. */
3617 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3618 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3619 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3620 /* We don't know what set of fixed registers might be used
3621 by the function, but it is certain that the stack pointer
3622 is among them, but be conservative. */
3623 else if (fixed_regs
[i
])
3624 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3625 /* The frame pointer is normally not used by the function
3626 itself, but by the debugger. */
3627 /* ??? MIPS o32 is an exception. It uses the frame pointer
3628 in the macro expansion of jal but does not represent this
3629 fact in the call_insn rtl. */
3630 else if (i
== FRAME_POINTER_REGNUM
3631 || (i
== HARD_FRAME_POINTER_REGNUM
3632 && (! reload_completed
|| frame_pointer_needed
)))
3633 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3636 /* For each insn which shouldn't cross a call, add a dependence
3637 between that insn and this call insn. */
3638 add_dependence_list_and_free (deps
, insn
,
3639 &deps
->sched_before_next_call
, 1,
3640 REG_DEP_ANTI
, true);
3642 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3644 /* If CALL would be in a sched group, then this will violate
3645 convention that sched group insns have dependencies only on the
3646 previous instruction.
3648 Of course one can say: "Hey! What about head of the sched group?"
3649 And I will answer: "Basic principles (one dep per insn) are always
3651 gcc_assert (!SCHED_GROUP_P (insn
));
3653 /* In the absence of interprocedural alias analysis, we must flush
3654 all pending reads and writes, and start new dependencies starting
3655 from here. But only flush writes for constant calls (which may
3656 be passed a pointer to something we haven't written yet). */
3657 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3659 if (!deps
->readonly
)
3661 /* Remember the last function call for limiting lifetimes. */
3662 free_INSN_LIST_list (&deps
->last_function_call
);
3663 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3665 if (call_may_noreturn_p (insn
))
3667 /* Remember the last function call that might not always return
3668 normally for limiting moves of trapping insns. */
3669 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3670 deps
->last_function_call_may_noreturn
3671 = alloc_INSN_LIST (insn
, NULL_RTX
);
3674 /* Before reload, begin a post-call group, so as to keep the
3675 lifetimes of hard registers correct. */
3676 if (! reload_completed
)
3677 deps
->in_post_call_group_p
= post_call
;
3681 if (sched_deps_info
->use_cselib
)
3682 cselib_process_insn (insn
);
3684 /* EH_REGION insn notes can not appear until well after we complete
3687 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3688 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3690 if (sched_deps_info
->finish_insn
)
3691 sched_deps_info
->finish_insn ();
3693 /* Fixup the dependencies in the sched group. */
3694 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3695 && chain_to_prev_insn_p (insn
)
3697 chain_to_prev_insn (insn
);
3700 /* Initialize DEPS for the new block beginning with HEAD. */
3702 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3704 gcc_assert (!deps
->readonly
);
3706 /* Before reload, if the previous block ended in a call, show that
3707 we are inside a post-call group, so as to keep the lifetimes of
3708 hard registers correct. */
3709 if (! reload_completed
&& !LABEL_P (head
))
3711 rtx insn
= prev_nonnote_nondebug_insn (head
);
3713 if (insn
&& CALL_P (insn
))
3714 deps
->in_post_call_group_p
= post_call_initial
;
3718 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3719 dependencies for each insn. */
3721 sched_analyze (struct deps_desc
*deps
, rtx head
, rtx tail
)
3725 if (sched_deps_info
->use_cselib
)
3726 cselib_init (CSELIB_RECORD_MEMORY
);
3728 deps_start_bb (deps
, head
);
3730 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3735 /* And initialize deps_lists. */
3736 sd_init_insn (insn
);
3739 deps_analyze_insn (deps
, insn
);
3743 if (sched_deps_info
->use_cselib
)
3751 /* Helper for sched_free_deps ().
3752 Delete INSN's (RESOLVED_P) backward dependencies. */
3754 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3756 sd_iterator_def sd_it
;
3758 sd_list_types_def types
;
3761 types
= SD_LIST_RES_BACK
;
3763 types
= SD_LIST_BACK
;
3765 for (sd_it
= sd_iterator_start (insn
, types
);
3766 sd_iterator_cond (&sd_it
, &dep
);)
3768 dep_link_t link
= *sd_it
.linkp
;
3769 dep_node_t node
= DEP_LINK_NODE (link
);
3770 deps_list_t back_list
;
3771 deps_list_t forw_list
;
3773 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3774 remove_from_deps_list (link
, back_list
);
3775 delete_dep_node (node
);
3779 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3782 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3785 rtx next_tail
= NEXT_INSN (tail
);
3787 /* We make two passes since some insns may be scheduled before their
3788 dependencies are resolved. */
3789 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3790 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3792 /* Clear forward deps and leave the dep_nodes to the
3793 corresponding back_deps list. */
3795 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3797 clear_deps_list (INSN_FORW_DEPS (insn
));
3799 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3800 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3802 /* Clear resolved back deps together with its dep_nodes. */
3803 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3805 sd_finish_insn (insn
);
3809 /* Initialize variables for region data dependence analysis.
3810 When LAZY_REG_LAST is true, do not allocate reg_last array
3811 of struct deps_desc immediately. */
3814 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3816 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3818 deps
->max_reg
= max_reg
;
3820 deps
->reg_last
= NULL
;
3822 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3823 INIT_REG_SET (&deps
->reg_last_in_use
);
3825 deps
->pending_read_insns
= 0;
3826 deps
->pending_read_mems
= 0;
3827 deps
->pending_write_insns
= 0;
3828 deps
->pending_write_mems
= 0;
3829 deps
->pending_jump_insns
= 0;
3830 deps
->pending_read_list_length
= 0;
3831 deps
->pending_write_list_length
= 0;
3832 deps
->pending_flush_length
= 0;
3833 deps
->last_pending_memory_flush
= 0;
3834 deps
->last_function_call
= 0;
3835 deps
->last_function_call_may_noreturn
= 0;
3836 deps
->sched_before_next_call
= 0;
3837 deps
->sched_before_next_jump
= 0;
3838 deps
->in_post_call_group_p
= not_post_call
;
3839 deps
->last_debug_insn
= 0;
3840 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3844 /* Init only reg_last field of DEPS, which was not allocated before as
3845 we inited DEPS lazily. */
3847 init_deps_reg_last (struct deps_desc
*deps
)
3849 gcc_assert (deps
&& deps
->max_reg
> 0);
3850 gcc_assert (deps
->reg_last
== NULL
);
3852 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3856 /* Free insn lists found in DEPS. */
3859 free_deps (struct deps_desc
*deps
)
3862 reg_set_iterator rsi
;
3864 /* We set max_reg to 0 when this context was already freed. */
3865 if (deps
->max_reg
== 0)
3867 gcc_assert (deps
->reg_last
== NULL
);
3872 free_INSN_LIST_list (&deps
->pending_read_insns
);
3873 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3874 free_INSN_LIST_list (&deps
->pending_write_insns
);
3875 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3876 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3878 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3879 times. For a testcase with 42000 regs and 8000 small basic blocks,
3880 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3881 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3883 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3885 free_INSN_LIST_list (®_last
->uses
);
3887 free_INSN_LIST_list (®_last
->sets
);
3888 if (reg_last
->implicit_sets
)
3889 free_INSN_LIST_list (®_last
->implicit_sets
);
3890 if (reg_last
->control_uses
)
3891 free_INSN_LIST_list (®_last
->control_uses
);
3892 if (reg_last
->clobbers
)
3893 free_INSN_LIST_list (®_last
->clobbers
);
3895 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3897 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3899 free (deps
->reg_last
);
3900 deps
->reg_last
= NULL
;
3905 /* Remove INSN from dependence contexts DEPS. */
3907 remove_from_deps (struct deps_desc
*deps
, rtx insn
)
3911 reg_set_iterator rsi
;
3913 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3914 &deps
->pending_read_mems
);
3915 if (!DEBUG_INSN_P (insn
))
3916 deps
->pending_read_list_length
-= removed
;
3917 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3918 &deps
->pending_write_mems
);
3919 deps
->pending_write_list_length
-= removed
;
3921 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
3922 deps
->pending_flush_length
-= removed
;
3923 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3924 deps
->pending_flush_length
-= removed
;
3926 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3928 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3930 remove_from_dependence_list (insn
, ®_last
->uses
);
3932 remove_from_dependence_list (insn
, ®_last
->sets
);
3933 if (reg_last
->implicit_sets
)
3934 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3935 if (reg_last
->clobbers
)
3936 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3937 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3938 && !reg_last
->clobbers
)
3939 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3944 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3945 remove_from_dependence_list (insn
,
3946 &deps
->last_function_call_may_noreturn
);
3948 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3951 /* Init deps data vector. */
3953 init_deps_data_vector (void)
3955 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
3956 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
3957 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
3960 /* If it is profitable to use them, initialize or extend (depending on
3961 GLOBAL_P) dependency data. */
3963 sched_deps_init (bool global_p
)
3965 /* Average number of insns in the basic block.
3966 '+ 1' is used to make it nonzero. */
3967 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3969 init_deps_data_vector ();
3971 /* We use another caching mechanism for selective scheduling, so
3972 we don't use this one. */
3973 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3975 /* ?!? We could save some memory by computing a per-region luid mapping
3976 which could reduce both the number of vectors in the cache and the
3977 size of each vector. Instead we just avoid the cache entirely unless
3978 the average number of instructions in a basic block is very high. See
3979 the comment before the declaration of true_dependency_cache for
3980 what we consider "very high". */
3982 extend_dependency_caches (sched_max_luid
, true);
3987 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3988 /* Allocate lists for one block at a time. */
3990 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3991 /* Allocate nodes for one block at a time.
3992 We assume that average insn has
3994 5 * insns_in_block
);
3999 /* Create or extend (depending on CREATE_P) dependency caches to
4002 extend_dependency_caches (int n
, bool create_p
)
4004 if (create_p
|| true_dependency_cache
)
4006 int i
, luid
= cache_size
+ n
;
4008 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4010 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4011 output_dependency_cache
, luid
);
4012 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4014 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4017 if (current_sched_info
->flags
& DO_SPECULATION
)
4018 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4021 for (i
= cache_size
; i
< luid
; i
++)
4023 bitmap_initialize (&true_dependency_cache
[i
], 0);
4024 bitmap_initialize (&output_dependency_cache
[i
], 0);
4025 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4026 bitmap_initialize (&control_dependency_cache
[i
], 0);
4028 if (current_sched_info
->flags
& DO_SPECULATION
)
4029 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4035 /* Finalize dependency information for the whole function. */
4037 sched_deps_finish (void)
4039 gcc_assert (deps_pools_are_empty_p ());
4040 free_alloc_pool_if_empty (&dn_pool
);
4041 free_alloc_pool_if_empty (&dl_pool
);
4042 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
4047 if (true_dependency_cache
)
4051 for (i
= 0; i
< cache_size
; i
++)
4053 bitmap_clear (&true_dependency_cache
[i
]);
4054 bitmap_clear (&output_dependency_cache
[i
]);
4055 bitmap_clear (&anti_dependency_cache
[i
]);
4056 bitmap_clear (&control_dependency_cache
[i
]);
4058 if (sched_deps_info
->generate_spec_deps
)
4059 bitmap_clear (&spec_dependency_cache
[i
]);
4061 free (true_dependency_cache
);
4062 true_dependency_cache
= NULL
;
4063 free (output_dependency_cache
);
4064 output_dependency_cache
= NULL
;
4065 free (anti_dependency_cache
);
4066 anti_dependency_cache
= NULL
;
4067 free (control_dependency_cache
);
4068 control_dependency_cache
= NULL
;
4070 if (sched_deps_info
->generate_spec_deps
)
4072 free (spec_dependency_cache
);
4073 spec_dependency_cache
= NULL
;
4079 /* Initialize some global variables needed by the dependency analysis
4083 init_deps_global (void)
4085 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4086 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4087 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4088 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4089 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4090 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4091 reg_pending_barrier
= NOT_A_BARRIER
;
4093 if (!sel_sched_p () || sched_emulate_haifa_p
)
4095 sched_deps_info
->start_insn
= haifa_start_insn
;
4096 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4098 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4099 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4100 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4102 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4103 sched_deps_info
->note_dep
= haifa_note_dep
;
4107 /* Free everything used by the dependency analysis code. */
4110 finish_deps_global (void)
4112 FREE_REG_SET (reg_pending_sets
);
4113 FREE_REG_SET (reg_pending_clobbers
);
4114 FREE_REG_SET (reg_pending_uses
);
4115 FREE_REG_SET (reg_pending_control_uses
);
4118 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4120 estimate_dep_weak (rtx mem1
, rtx mem2
)
4125 /* MEMs are the same - don't speculate. */
4126 return MIN_DEP_WEAK
;
4128 r1
= XEXP (mem1
, 0);
4129 r2
= XEXP (mem2
, 0);
4132 || (REG_P (r1
) && REG_P (r2
)
4133 && REGNO (r1
) == REGNO (r2
)))
4134 /* Again, MEMs are the same. */
4135 return MIN_DEP_WEAK
;
4136 else if ((REG_P (r1
) && !REG_P (r2
))
4137 || (!REG_P (r1
) && REG_P (r2
)))
4138 /* Different addressing modes - reason to be more speculative,
4140 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4142 /* We can't say anything about the dependence. */
4143 return UNCERTAIN_DEP_WEAK
;
4146 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4147 This function can handle same INSN and ELEM (INSN == ELEM).
4148 It is a convenience wrapper. */
4150 add_dependence_1 (rtx insn
, rtx elem
, enum reg_note dep_type
)
4155 if (dep_type
== REG_DEP_TRUE
)
4157 else if (dep_type
== REG_DEP_OUTPUT
)
4159 else if (dep_type
== REG_DEP_CONTROL
)
4163 gcc_assert (dep_type
== REG_DEP_ANTI
);
4167 /* When add_dependence is called from inside sched-deps.c, we expect
4168 cur_insn to be non-null. */
4169 internal
= cur_insn
!= NULL
;
4171 gcc_assert (insn
== cur_insn
);
4175 note_dep (elem
, ds
);
4180 /* Return weakness of speculative type TYPE in the dep_status DS. */
4182 get_dep_weak_1 (ds_t ds
, ds_t type
)
4188 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4189 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4190 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4191 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4192 default: gcc_unreachable ();
4199 get_dep_weak (ds_t ds
, ds_t type
)
4201 dw_t dw
= get_dep_weak_1 (ds
, type
);
4203 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4207 /* Return the dep_status, which has the same parameters as DS, except for
4208 speculative type TYPE, that will have weakness DW. */
4210 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4212 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4217 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4218 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4219 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4220 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4221 default: gcc_unreachable ();
4226 /* Return the join of two dep_statuses DS1 and DS2.
4227 If MAX_P is true then choose the greater probability,
4228 otherwise multiply probabilities.
4229 This function assumes that both DS1 and DS2 contain speculative bits. */
4231 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4235 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4237 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4239 t
= FIRST_SPEC_TYPE
;
4242 if ((ds1
& t
) && !(ds2
& t
))
4244 else if (!(ds1
& t
) && (ds2
& t
))
4246 else if ((ds1
& t
) && (ds2
& t
))
4248 dw_t dw1
= get_dep_weak (ds1
, t
);
4249 dw_t dw2
= get_dep_weak (ds2
, t
);
4254 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4256 if (dw
< MIN_DEP_WEAK
)
4267 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4270 if (t
== LAST_SPEC_TYPE
)
4272 t
<<= SPEC_TYPE_SHIFT
;
4279 /* Return the join of two dep_statuses DS1 and DS2.
4280 This function assumes that both DS1 and DS2 contain speculative bits. */
4282 ds_merge (ds_t ds1
, ds_t ds2
)
4284 return ds_merge_1 (ds1
, ds2
, false);
4287 /* Return the join of two dep_statuses DS1 and DS2. */
4289 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4291 ds_t new_status
= ds
| ds2
;
4293 if (new_status
& SPECULATIVE
)
4295 if ((ds
&& !(ds
& SPECULATIVE
))
4296 || (ds2
&& !(ds2
& SPECULATIVE
)))
4297 /* Then this dep can't be speculative. */
4298 new_status
&= ~SPECULATIVE
;
4301 /* Both are speculative. Merging probabilities. */
4306 dw
= estimate_dep_weak (mem1
, mem2
);
4307 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4315 new_status
= ds_merge (ds2
, ds
);
4322 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4325 ds_max_merge (ds_t ds1
, ds_t ds2
)
4327 if (ds1
== 0 && ds2
== 0)
4330 if (ds1
== 0 && ds2
!= 0)
4333 if (ds1
!= 0 && ds2
== 0)
4336 return ds_merge_1 (ds1
, ds2
, true);
4339 /* Return the probability of speculation success for the speculation
4347 dt
= FIRST_SPEC_TYPE
;
4352 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4356 if (dt
== LAST_SPEC_TYPE
)
4358 dt
<<= SPEC_TYPE_SHIFT
;
4364 res
/= MAX_DEP_WEAK
;
4366 if (res
< MIN_DEP_WEAK
)
4369 gcc_assert (res
<= MAX_DEP_WEAK
);
4374 /* Return a dep status that contains all speculation types of DS. */
4376 ds_get_speculation_types (ds_t ds
)
4378 if (ds
& BEGIN_DATA
)
4380 if (ds
& BE_IN_DATA
)
4382 if (ds
& BEGIN_CONTROL
)
4383 ds
|= BEGIN_CONTROL
;
4384 if (ds
& BE_IN_CONTROL
)
4385 ds
|= BE_IN_CONTROL
;
4387 return ds
& SPECULATIVE
;
4390 /* Return a dep status that contains maximal weakness for each speculation
4391 type present in DS. */
4393 ds_get_max_dep_weak (ds_t ds
)
4395 if (ds
& BEGIN_DATA
)
4396 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4397 if (ds
& BE_IN_DATA
)
4398 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4399 if (ds
& BEGIN_CONTROL
)
4400 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4401 if (ds
& BE_IN_CONTROL
)
4402 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4407 /* Dump information about the dependence status S. */
4409 dump_ds (FILE *f
, ds_t s
)
4414 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4416 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4417 if (s
& BEGIN_CONTROL
)
4418 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4419 if (s
& BE_IN_CONTROL
)
4420 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4423 fprintf (f
, "HARD_DEP; ");
4426 fprintf (f
, "DEP_TRUE; ");
4428 fprintf (f
, "DEP_OUTPUT; ");
4430 fprintf (f
, "DEP_ANTI; ");
4431 if (s
& DEP_CONTROL
)
4432 fprintf (f
, "DEP_CONTROL; ");
4440 dump_ds (stderr
, s
);
4441 fprintf (stderr
, "\n");
4444 #ifdef ENABLE_CHECKING
4445 /* Verify that dependence type and status are consistent.
4446 If RELAXED_P is true, then skip dep_weakness checks. */
4448 check_dep (dep_t dep
, bool relaxed_p
)
4450 enum reg_note dt
= DEP_TYPE (dep
);
4451 ds_t ds
= DEP_STATUS (dep
);
4453 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4455 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4457 gcc_assert (ds
== 0);
4461 /* Check that dependence type contains the same bits as the status. */
4462 if (dt
== REG_DEP_TRUE
)
4463 gcc_assert (ds
& DEP_TRUE
);
4464 else if (dt
== REG_DEP_OUTPUT
)
4465 gcc_assert ((ds
& DEP_OUTPUT
)
4466 && !(ds
& DEP_TRUE
));
4467 else if (dt
== REG_DEP_ANTI
)
4468 gcc_assert ((ds
& DEP_ANTI
)
4469 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4471 gcc_assert (dt
== REG_DEP_CONTROL
4472 && (ds
& DEP_CONTROL
)
4473 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4475 /* HARD_DEP can not appear in dep_status of a link. */
4476 gcc_assert (!(ds
& HARD_DEP
));
4478 /* Check that dependence status is set correctly when speculation is not
4480 if (!sched_deps_info
->generate_spec_deps
)
4481 gcc_assert (!(ds
& SPECULATIVE
));
4482 else if (ds
& SPECULATIVE
)
4486 ds_t type
= FIRST_SPEC_TYPE
;
4488 /* Check that dependence weakness is in proper range. */
4492 get_dep_weak (ds
, type
);
4494 if (type
== LAST_SPEC_TYPE
)
4496 type
<<= SPEC_TYPE_SHIFT
;
4501 if (ds
& BEGIN_SPEC
)
4503 /* Only true dependence can be data speculative. */
4504 if (ds
& BEGIN_DATA
)
4505 gcc_assert (ds
& DEP_TRUE
);
4507 /* Control dependencies in the insn scheduler are represented by
4508 anti-dependencies, therefore only anti dependence can be
4509 control speculative. */
4510 if (ds
& BEGIN_CONTROL
)
4511 gcc_assert (ds
& DEP_ANTI
);
4515 /* Subsequent speculations should resolve true dependencies. */
4516 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4519 /* Check that true and anti dependencies can't have other speculative
4522 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4523 /* An output dependence can't be speculative at all. */
4524 gcc_assert (!(ds
& DEP_OUTPUT
));
4526 gcc_assert (ds
& BEGIN_CONTROL
);
4529 #endif /* ENABLE_CHECKING */
4531 /* The following code discovers opportunities to switch a memory reference
4532 and an increment by modifying the address. We ensure that this is done
4533 only for dependencies that are only used to show a single register
4534 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4535 instruction involved is subject to only one dep that can cause a pattern
4538 When we discover a suitable dependency, we fill in the dep_replacement
4539 structure to show how to modify the memory reference. */
4541 /* Holds information about a pair of memory reference and register increment
4542 insns which depend on each other, but could possibly be interchanged. */
4549 /* A register occurring in the memory address for which we wish to break
4550 the dependence. This must be identical to the destination register of
4553 /* Any kind of index that is added to that register. */
4555 /* The constant offset used in the memory address. */
4556 HOST_WIDE_INT mem_constant
;
4557 /* The constant added in the increment insn. Negated if the increment is
4558 after the memory address. */
4559 HOST_WIDE_INT inc_constant
;
4560 /* The source register used in the increment. May be different from mem_reg0
4561 if the increment occurs before the memory address. */
4565 /* Verify that the memory location described in MII can be replaced with
4566 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4567 insn remains unchanged by this function. */
4570 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4572 rtx mem
= *mii
->mem_loc
;
4575 /* Jump thru a lot of hoops to keep the attributes up to date. We
4576 do not want to call one of the change address variants that take
4577 an offset even though we know the offset in many cases. These
4578 assume you are changing where the address is pointing by the
4580 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4581 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4583 if (sched_verbose
>= 5)
4584 fprintf (sched_dump
, "validation failure\n");
4588 /* Put back the old one. */
4589 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4594 /* Return true if INSN is of a form "a = b op c" where a and b are
4595 regs. op is + if c is a reg and +|- if c is a const. Fill in
4596 informantion in MII about what is found.
4597 BEFORE_MEM indicates whether the increment is found before or after
4598 a corresponding memory reference. */
4601 parse_add_or_inc (struct mem_inc_info
*mii
, rtx insn
, bool before_mem
)
4603 rtx pat
= single_set (insn
);
4607 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4610 /* Result must be single reg. */
4611 if (!REG_P (SET_DEST (pat
)))
4614 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4617 mii
->inc_insn
= insn
;
4618 src
= SET_SRC (pat
);
4619 mii
->inc_input
= XEXP (src
, 0);
4621 if (!REG_P (XEXP (src
, 0)))
4624 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4627 cst
= XEXP (src
, 1);
4628 if (!CONST_INT_P (cst
))
4630 mii
->inc_constant
= INTVAL (cst
);
4632 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4636 mii
->inc_constant
= -mii
->inc_constant
;
4641 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4643 /* Note that the sign has already been reversed for !before_mem. */
4644 #ifdef STACK_GROWS_DOWNWARD
4645 return mii
->inc_constant
> 0;
4647 return mii
->inc_constant
< 0;
4653 /* Once a suitable mem reference has been found and the corresponding data
4654 in MII has been filled in, this function is called to find a suitable
4655 add or inc insn involving the register we found in the memory
4659 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4661 sd_iterator_def sd_it
;
4664 sd_it
= sd_iterator_start (mii
->mem_insn
,
4665 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4666 while (sd_iterator_cond (&sd_it
, &dep
))
4668 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4669 rtx pro
= DEP_PRO (dep
);
4670 rtx con
= DEP_CON (dep
);
4671 rtx inc_cand
= backwards
? pro
: con
;
4672 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4674 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4676 struct dep_replacement
*desc
;
4678 rtx newaddr
, newmem
;
4680 if (sched_verbose
>= 5)
4681 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4682 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4684 /* Need to assure that none of the operands of the inc
4685 instruction are assigned to by the mem insn. */
4686 for (def_rec
= DF_INSN_DEFS (mii
->mem_insn
); *def_rec
; def_rec
++)
4688 df_ref def
= *def_rec
;
4689 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4690 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4692 if (sched_verbose
>= 5)
4693 fprintf (sched_dump
,
4694 "inc conflicts with store failure.\n");
4698 newaddr
= mii
->inc_input
;
4699 if (mii
->mem_index
!= NULL_RTX
)
4700 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4702 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4703 mii
->mem_constant
+ mii
->inc_constant
);
4704 newmem
= attempt_change (mii
, newaddr
);
4705 if (newmem
== NULL_RTX
)
4707 if (sched_verbose
>= 5)
4708 fprintf (sched_dump
, "successful address replacement\n");
4709 desc
= XCNEW (struct dep_replacement
);
4710 DEP_REPLACE (dep
) = desc
;
4711 desc
->loc
= mii
->mem_loc
;
4712 desc
->newval
= newmem
;
4713 desc
->orig
= *desc
->loc
;
4714 desc
->insn
= mii
->mem_insn
;
4715 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4716 INSN_SPEC_BACK_DEPS (con
));
4719 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4720 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4725 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4726 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4732 sd_iterator_next (&sd_it
);
4737 /* A recursive function that walks ADDRESS_OF_X to find memory references
4738 which could be modified during scheduling. We call find_inc for each
4739 one we find that has a recognizable form. MII holds information about
4740 the pair of memory/increment instructions.
4741 We ensure that every instruction with a memory reference (which will be
4742 the location of the replacement) is assigned at most one breakable
4746 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4748 rtx x
= *address_of_x
;
4749 enum rtx_code code
= GET_CODE (x
);
4750 const char *const fmt
= GET_RTX_FORMAT (code
);
4755 rtx reg0
= XEXP (x
, 0);
4757 mii
->mem_loc
= address_of_x
;
4758 mii
->mem_index
= NULL_RTX
;
4759 mii
->mem_constant
= 0;
4760 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4762 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4763 reg0
= XEXP (reg0
, 0);
4765 if (GET_CODE (reg0
) == PLUS
)
4767 mii
->mem_index
= XEXP (reg0
, 1);
4768 reg0
= XEXP (reg0
, 0);
4773 int occurrences
= 0;
4775 /* Make sure this reg appears only once in this insn. Can't use
4776 count_occurrences since that only works for pseudos. */
4777 for (def_rec
= DF_INSN_USES (mii
->mem_insn
); *def_rec
; def_rec
++)
4779 df_ref def
= *def_rec
;
4780 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (def
)))
4781 if (++occurrences
> 1)
4783 if (sched_verbose
>= 5)
4784 fprintf (sched_dump
, "mem count failure\n");
4789 mii
->mem_reg0
= reg0
;
4790 return find_inc (mii
, true) || find_inc (mii
, false);
4795 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4797 /* If REG occurs inside a MEM used in a bit-field reference,
4798 that is unacceptable. */
4802 /* Time for some deep diving. */
4803 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4807 if (find_mem (mii
, &XEXP (x
, i
)))
4810 else if (fmt
[i
] == 'E')
4813 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4814 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4822 /* Examine the instructions between HEAD and TAIL and try to find
4823 dependencies that can be broken by modifying one of the patterns. */
4826 find_modifiable_mems (rtx head
, rtx tail
)
4828 rtx insn
, next_tail
= NEXT_INSN (tail
);
4829 int success_in_block
= 0;
4831 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4833 struct mem_inc_info mii
;
4835 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4838 mii
.mem_insn
= insn
;
4839 if (find_mem (&mii
, &PATTERN (insn
)))
4842 if (success_in_block
&& sched_verbose
>= 5)
4843 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4847 #endif /* INSN_SCHEDULING */