+#ifdef INSN_SCHEDULING
+
+#ifdef ENABLE_CHECKING
+#define CHECK (true)
+#else
+#define CHECK (false)
+#endif
+
+/* In deps->last_pending_memory_flush marks JUMP_INSNs that weren't
+ added to the list because of flush_pending_lists, stands just
+ for itself and not for any other pending memory reads/writes. */
+#define NON_FLUSH_JUMP_KIND REG_DEP_ANTI
+#define NON_FLUSH_JUMP_P(x) (REG_NOTE_KIND (x) == NON_FLUSH_JUMP_KIND)
+
+/* Holds current parameters for the dependency analyzer. */
+struct sched_deps_info_def *sched_deps_info;
+
+/* The data is specific to the Haifa scheduler. */
+VEC(haifa_deps_insn_data_def, heap) *h_d_i_d = NULL;
+
+/* Return the major type present in the DS. */
+enum reg_note
+ds_to_dk (ds_t ds)
+{
+ if (ds & DEP_TRUE)
+ return REG_DEP_TRUE;
+
+ if (ds & DEP_OUTPUT)
+ return REG_DEP_OUTPUT;
+
+ gcc_assert (ds & DEP_ANTI);
+
+ return REG_DEP_ANTI;
+}
+
+/* Return equivalent dep_status. */
+ds_t
+dk_to_ds (enum reg_note dk)
+{
+ switch (dk)
+ {
+ case REG_DEP_TRUE:
+ return DEP_TRUE;
+
+ case REG_DEP_OUTPUT:
+ return DEP_OUTPUT;
+
+ default:
+ gcc_assert (dk == REG_DEP_ANTI);
+ return DEP_ANTI;
+ }
+}
+
+/* Functions to operate with dependence information container - dep_t. */
+
+/* Init DEP with the arguments. */
+void
+init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
+{
+ DEP_PRO (dep) = pro;
+ DEP_CON (dep) = con;
+ DEP_TYPE (dep) = type;
+ DEP_STATUS (dep) = ds;
+}
+
+/* Init DEP with the arguments.
+ While most of the scheduler (including targets) only need the major type
+ of the dependency, it is convenient to hide full dep_status from them. */
+void
+init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
+{
+ ds_t ds;
+
+ if ((current_sched_info->flags & USE_DEPS_LIST))
+ ds = dk_to_ds (kind);
+ else
+ ds = -1;
+
+ init_dep_1 (dep, pro, con, kind, ds);
+}
+
+/* Make a copy of FROM in TO. */
+static void
+copy_dep (dep_t to, dep_t from)
+{
+ memcpy (to, from, sizeof (*to));
+}
+
+static void dump_ds (FILE *, ds_t);
+
+/* Define flags for dump_dep (). */
+
+/* Dump producer of the dependence. */
+#define DUMP_DEP_PRO (2)
+
+/* Dump consumer of the dependence. */
+#define DUMP_DEP_CON (4)
+
+/* Dump type of the dependence. */
+#define DUMP_DEP_TYPE (8)
+
+/* Dump status of the dependence. */
+#define DUMP_DEP_STATUS (16)
+
+/* Dump all information about the dependence. */
+#define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
+ |DUMP_DEP_STATUS)
+
+/* Dump DEP to DUMP.
+ FLAGS is a bit mask specifying what information about DEP needs
+ to be printed.
+ If FLAGS has the very first bit set, then dump all information about DEP
+ and propagate this bit into the callee dump functions. */
+static void
+dump_dep (FILE *dump, dep_t dep, int flags)
+{
+ if (flags & 1)
+ flags |= DUMP_DEP_ALL;
+
+ fprintf (dump, "<");
+
+ if (flags & DUMP_DEP_PRO)
+ fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
+
+ if (flags & DUMP_DEP_CON)
+ fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
+
+ if (flags & DUMP_DEP_TYPE)
+ {
+ char t;
+ enum reg_note type = DEP_TYPE (dep);
+
+ switch (type)
+ {
+ case REG_DEP_TRUE:
+ t = 't';
+ break;
+
+ case REG_DEP_OUTPUT:
+ t = 'o';
+ break;
+
+ case REG_DEP_ANTI:
+ t = 'a';
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+
+ fprintf (dump, "%c; ", t);
+ }
+
+ if (flags & DUMP_DEP_STATUS)
+ {
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ dump_ds (dump, DEP_STATUS (dep));
+ }
+
+ fprintf (dump, ">");
+}
+
+/* Default flags for dump_dep (). */
+static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
+
+/* Dump all fields of DEP to STDERR. */
+void
+sd_debug_dep (dep_t dep)
+{
+ dump_dep (stderr, dep, 1);
+ fprintf (stderr, "\n");
+}
+
+/* Determine whether DEP is a dependency link of a non-debug insn on a
+ debug insn. */
+
+static inline bool
+depl_on_debug_p (dep_link_t dep)
+{
+ return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
+ && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
+}
+
+/* Functions to operate with a single link from the dependencies lists -
+ dep_link_t. */
+
+/* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
+ PREV_NEXT_P. */
+static void
+attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
+{
+ dep_link_t next = *prev_nextp;
+
+ gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
+ && DEP_LINK_NEXT (l) == NULL);
+
+ /* Init node being inserted. */
+ DEP_LINK_PREV_NEXTP (l) = prev_nextp;
+ DEP_LINK_NEXT (l) = next;
+
+ /* Fix next node. */
+ if (next != NULL)
+ {
+ gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
+
+ DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
+ }
+
+ /* Fix prev node. */
+ *prev_nextp = l;
+}
+
+/* Add dep_link LINK to deps_list L. */
+static void
+add_to_deps_list (dep_link_t link, deps_list_t l)
+{
+ attach_dep_link (link, &DEPS_LIST_FIRST (l));
+
+ /* Don't count debug deps. */
+ if (!depl_on_debug_p (link))
+ ++DEPS_LIST_N_LINKS (l);
+}
+
+/* Detach dep_link L from the list. */
+static void
+detach_dep_link (dep_link_t l)
+{
+ dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
+ dep_link_t next = DEP_LINK_NEXT (l);
+
+ *prev_nextp = next;
+
+ if (next != NULL)
+ DEP_LINK_PREV_NEXTP (next) = prev_nextp;
+
+ DEP_LINK_PREV_NEXTP (l) = NULL;
+ DEP_LINK_NEXT (l) = NULL;
+}
+
+/* Remove link LINK from list LIST. */
+static void
+remove_from_deps_list (dep_link_t link, deps_list_t list)
+{
+ detach_dep_link (link);
+
+ /* Don't count debug deps. */
+ if (!depl_on_debug_p (link))
+ --DEPS_LIST_N_LINKS (list);
+}
+
+/* Move link LINK from list FROM to list TO. */
+static void
+move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
+{
+ remove_from_deps_list (link, from);
+ add_to_deps_list (link, to);
+}
+
+/* Return true of LINK is not attached to any list. */
+static bool
+dep_link_is_detached_p (dep_link_t link)
+{
+ return DEP_LINK_PREV_NEXTP (link) == NULL;
+}
+
+/* Pool to hold all dependency nodes (dep_node_t). */
+static alloc_pool dn_pool;
+
+/* Number of dep_nodes out there. */
+static int dn_pool_diff = 0;
+
+/* Create a dep_node. */
+static dep_node_t
+create_dep_node (void)
+{
+ dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
+ dep_link_t back = DEP_NODE_BACK (n);
+ dep_link_t forw = DEP_NODE_FORW (n);
+
+ DEP_LINK_NODE (back) = n;
+ DEP_LINK_NEXT (back) = NULL;
+ DEP_LINK_PREV_NEXTP (back) = NULL;
+
+ DEP_LINK_NODE (forw) = n;
+ DEP_LINK_NEXT (forw) = NULL;
+ DEP_LINK_PREV_NEXTP (forw) = NULL;
+
+ ++dn_pool_diff;
+
+ return n;
+}
+
+/* Delete dep_node N. N must not be connected to any deps_list. */
+static void
+delete_dep_node (dep_node_t n)
+{
+ gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
+ && dep_link_is_detached_p (DEP_NODE_FORW (n)));
+
+ --dn_pool_diff;
+
+ pool_free (dn_pool, n);
+}
+
+/* Pool to hold dependencies lists (deps_list_t). */
+static alloc_pool dl_pool;
+
+/* Number of deps_lists out there. */
+static int dl_pool_diff = 0;
+
+/* Functions to operate with dependences lists - deps_list_t. */
+
+/* Return true if list L is empty. */
+static bool
+deps_list_empty_p (deps_list_t l)
+{
+ return DEPS_LIST_N_LINKS (l) == 0;
+}
+
+/* Create a new deps_list. */
+static deps_list_t
+create_deps_list (void)
+{
+ deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
+
+ DEPS_LIST_FIRST (l) = NULL;
+ DEPS_LIST_N_LINKS (l) = 0;
+
+ ++dl_pool_diff;
+ return l;
+}
+
+/* Free deps_list L. */
+static void
+free_deps_list (deps_list_t l)
+{
+ gcc_assert (deps_list_empty_p (l));
+
+ --dl_pool_diff;
+
+ pool_free (dl_pool, l);
+}
+
+/* Return true if there is no dep_nodes and deps_lists out there.
+ After the region is scheduled all the dependency nodes and lists
+ should [generally] be returned to pool. */
+bool
+deps_pools_are_empty_p (void)
+{
+ return dn_pool_diff == 0 && dl_pool_diff == 0;
+}
+
+/* Remove all elements from L. */
+static void
+clear_deps_list (deps_list_t l)
+{
+ do
+ {
+ dep_link_t link = DEPS_LIST_FIRST (l);
+
+ if (link == NULL)
+ break;
+
+ remove_from_deps_list (link, l);
+ }
+ while (1);
+}
+
+static regset reg_pending_sets;
+static regset reg_pending_clobbers;
+static regset reg_pending_uses;
+static enum reg_pending_barrier_mode reg_pending_barrier;
+
+/* Hard registers implicitly clobbered or used (or may be implicitly
+ clobbered or used) by the currently analyzed insn. For example,
+ insn in its constraint has one register class. Even if there is
+ currently no hard register in the insn, the particular hard
+ register will be in the insn after reload pass because the
+ constraint requires it. */
+static HARD_REG_SET implicit_reg_pending_clobbers;
+static HARD_REG_SET implicit_reg_pending_uses;
+
+/* To speed up the test for duplicate dependency links we keep a
+ record of dependencies created by add_dependence when the average
+ number of instructions in a basic block is very large.
+
+ Studies have shown that there is typically around 5 instructions between
+ branches for typical C code. So we can make a guess that the average
+ basic block is approximately 5 instructions long; we will choose 100X
+ the average size as a very large basic block.
+
+ Each insn has associated bitmaps for its dependencies. Each bitmap
+ has enough entries to represent a dependency on any other insn in
+ the insn chain. All bitmap for true dependencies cache is
+ allocated then the rest two ones are also allocated. */
+static bitmap_head *true_dependency_cache = NULL;
+static bitmap_head *output_dependency_cache = NULL;
+static bitmap_head *anti_dependency_cache = NULL;
+static bitmap_head *spec_dependency_cache = NULL;
+static int cache_size;
+
+static int deps_may_trap_p (const_rtx);
+static void add_dependence_list (rtx, rtx, int, enum reg_note);
+static void add_dependence_list_and_free (struct deps_desc *, rtx,
+ rtx *, int, enum reg_note);
+static void delete_all_dependences (rtx);
+static void fixup_sched_groups (rtx);
+
+static void flush_pending_lists (struct deps_desc *, rtx, int, int);
+static void sched_analyze_1 (struct deps_desc *, rtx, rtx);
+static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
+static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
+
+static bool sched_has_condition_p (const_rtx);
+static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
+
+static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
+ rtx, rtx);
+static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
+
+#ifdef ENABLE_CHECKING
+static void check_dep (dep_t, bool);
+#endif
+\f
+/* Return nonzero if a load of the memory reference MEM can cause a trap. */
+
+static int
+deps_may_trap_p (const_rtx mem)
+{
+ const_rtx addr = XEXP (mem, 0);
+
+ if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
+ {
+ const_rtx t = get_reg_known_value (REGNO (addr));
+ if (t)
+ addr = t;
+ }
+ return rtx_addr_can_trap_p (addr);
+}
+\f
+
+/* Find the condition under which INSN is executed. If REV is not NULL,
+ it is set to TRUE when the returned comparison should be reversed
+ to get the actual condition. */
+static rtx
+sched_get_condition_with_rev (const_rtx insn, bool *rev)
+{
+ rtx pat = PATTERN (insn);
+ rtx src;
+
+ if (pat == 0)
+ return 0;
+
+ if (rev)
+ *rev = false;
+
+ if (GET_CODE (pat) == COND_EXEC)
+ return COND_EXEC_TEST (pat);
+
+ if (!any_condjump_p (insn) || !onlyjump_p (insn))
+ return 0;
+
+ src = SET_SRC (pc_set (insn));
+
+ if (XEXP (src, 2) == pc_rtx)
+ return XEXP (src, 0);
+ else if (XEXP (src, 1) == pc_rtx)
+ {
+ rtx cond = XEXP (src, 0);
+ enum rtx_code revcode = reversed_comparison_code (cond, insn);
+
+ if (revcode == UNKNOWN)
+ return 0;
+
+ if (rev)
+ *rev = true;
+ return cond;
+ }
+
+ return 0;
+}
+
+/* True when we can find a condition under which INSN is executed. */
+static bool
+sched_has_condition_p (const_rtx insn)
+{
+ return !! sched_get_condition_with_rev (insn, NULL);
+}
+
+\f
+
+/* Return nonzero if conditions COND1 and COND2 can never be both true. */
+static int
+conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
+{
+ if (COMPARISON_P (cond1)
+ && COMPARISON_P (cond2)
+ && GET_CODE (cond1) ==
+ (rev1==rev2
+ ? reversed_comparison_code (cond2, NULL)
+ : GET_CODE (cond2))
+ && XEXP (cond1, 0) == XEXP (cond2, 0)
+ && XEXP (cond1, 1) == XEXP (cond2, 1))
+ return 1;
+ return 0;
+}
+
+/* Return true if insn1 and insn2 can never depend on one another because
+ the conditions under which they are executed are mutually exclusive. */
+bool
+sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
+{
+ rtx cond1, cond2;
+ bool rev1 = false, rev2 = false;
+
+ /* df doesn't handle conditional lifetimes entirely correctly;
+ calls mess up the conditional lifetimes. */
+ if (!CALL_P (insn1) && !CALL_P (insn2))
+ {
+ cond1 = sched_get_condition_with_rev (insn1, &rev1);
+ cond2 = sched_get_condition_with_rev (insn2, &rev2);
+ if (cond1 && cond2
+ && conditions_mutex_p (cond1, cond2, rev1, rev2)
+ /* Make sure first instruction doesn't affect condition of second
+ instruction if switched. */
+ && !modified_in_p (cond1, insn2)
+ /* Make sure second instruction doesn't affect condition of first
+ instruction if switched. */
+ && !modified_in_p (cond2, insn1))
+ return true;
+ }
+ return false;
+}
+\f
+
+/* Return true if INSN can potentially be speculated with type DS. */
+bool
+sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
+{
+ if (HAS_INTERNAL_DEP (insn))
+ return false;
+
+ if (!NONJUMP_INSN_P (insn))
+ return false;
+
+ if (SCHED_GROUP_P (insn))
+ return false;
+
+ if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
+ return false;
+
+ if (side_effects_p (PATTERN (insn)))
+ return false;
+
+ if (ds & BE_IN_SPEC)
+ /* The following instructions, which depend on a speculatively scheduled
+ instruction, cannot be speculatively scheduled along. */
+ {
+ if (may_trap_or_fault_p (PATTERN (insn)))
+ /* If instruction might fault, it cannot be speculatively scheduled.
+ For control speculation it's obvious why and for data speculation
+ it's because the insn might get wrong input if speculation
+ wasn't successful. */
+ return false;
+
+ if ((ds & BE_IN_DATA)
+ && sched_has_condition_p (insn))
+ /* If this is a predicated instruction, then it cannot be
+ speculatively scheduled. See PR35659. */
+ return false;
+ }
+
+ return true;
+}
+
+/* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
+ initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
+ and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
+ This function is used to switch sd_iterator to the next list.
+ !!! For internal use only. Might consider moving it to sched-int.h. */
+void
+sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
+ deps_list_t *list_ptr, bool *resolved_p_ptr)
+{
+ sd_list_types_def types = *types_ptr;
+
+ if (types & SD_LIST_HARD_BACK)
+ {
+ *list_ptr = INSN_HARD_BACK_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_HARD_BACK;
+ }
+ else if (types & SD_LIST_SPEC_BACK)
+ {
+ *list_ptr = INSN_SPEC_BACK_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_SPEC_BACK;
+ }
+ else if (types & SD_LIST_FORW)
+ {
+ *list_ptr = INSN_FORW_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_FORW;
+ }
+ else if (types & SD_LIST_RES_BACK)
+ {
+ *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
+ *resolved_p_ptr = true;
+ *types_ptr = types & ~SD_LIST_RES_BACK;
+ }
+ else if (types & SD_LIST_RES_FORW)
+ {
+ *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
+ *resolved_p_ptr = true;
+ *types_ptr = types & ~SD_LIST_RES_FORW;
+ }
+ else
+ {
+ *list_ptr = NULL;
+ *resolved_p_ptr = false;
+ *types_ptr = SD_LIST_NONE;
+ }
+}
+
+/* Return the summary size of INSN's lists defined by LIST_TYPES. */
+int
+sd_lists_size (const_rtx insn, sd_list_types_def list_types)
+{
+ int size = 0;
+
+ while (list_types != SD_LIST_NONE)
+ {
+ deps_list_t list;
+ bool resolved_p;
+
+ sd_next_list (insn, &list_types, &list, &resolved_p);
+ if (list)
+ size += DEPS_LIST_N_LINKS (list);
+ }
+
+ return size;
+}
+
+/* Return true if INSN's lists defined by LIST_TYPES are all empty. */
+
+bool
+sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
+{
+ while (list_types != SD_LIST_NONE)
+ {
+ deps_list_t list;
+ bool resolved_p;
+
+ sd_next_list (insn, &list_types, &list, &resolved_p);
+ if (!deps_list_empty_p (list))
+ return false;
+ }
+
+ return true;
+}
+
+/* Initialize data for INSN. */
+void
+sd_init_insn (rtx insn)
+{
+ INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
+ INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
+ INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
+ INSN_FORW_DEPS (insn) = create_deps_list ();
+ INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
+
+ /* ??? It would be nice to allocate dependency caches here. */
+}
+
+/* Free data for INSN. */
+void
+sd_finish_insn (rtx insn)
+{
+ /* ??? It would be nice to deallocate dependency caches here. */
+
+ free_deps_list (INSN_HARD_BACK_DEPS (insn));
+ INSN_HARD_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_SPEC_BACK_DEPS (insn));
+ INSN_SPEC_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
+ INSN_RESOLVED_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_FORW_DEPS (insn));
+ INSN_FORW_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
+ INSN_RESOLVED_FORW_DEPS (insn) = NULL;
+}
+
+/* Find a dependency between producer PRO and consumer CON.
+ Search through resolved dependency lists if RESOLVED_P is true.
+ If no such dependency is found return NULL,
+ otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
+ with an iterator pointing to it. */
+static dep_t
+sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
+ sd_iterator_def *sd_it_ptr)
+{
+ sd_list_types_def pro_list_type;
+ sd_list_types_def con_list_type;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ bool found_p = false;
+
+ if (resolved_p)
+ {
+ pro_list_type = SD_LIST_RES_FORW;
+ con_list_type = SD_LIST_RES_BACK;
+ }
+ else
+ {
+ pro_list_type = SD_LIST_FORW;
+ con_list_type = SD_LIST_BACK;
+ }
+
+ /* Walk through either back list of INSN or forw list of ELEM
+ depending on which one is shorter. */
+ if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
+ {
+ /* Find the dep_link with producer PRO in consumer's back_deps. */
+ FOR_EACH_DEP (con, con_list_type, sd_it, dep)
+ if (DEP_PRO (dep) == pro)
+ {
+ found_p = true;
+ break;
+ }
+ }
+ else
+ {
+ /* Find the dep_link with consumer CON in producer's forw_deps. */
+ FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
+ if (DEP_CON (dep) == con)
+ {
+ found_p = true;
+ break;
+ }
+ }
+
+ if (found_p)
+ {
+ if (sd_it_ptr != NULL)
+ *sd_it_ptr = sd_it;
+
+ return dep;
+ }
+
+ return NULL;
+}
+
+/* Find a dependency between producer PRO and consumer CON.
+ Use dependency [if available] to check if dependency is present at all.
+ Search through resolved dependency lists if RESOLVED_P is true.
+ If the dependency or NULL if none found. */
+dep_t
+sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
+{
+ if (true_dependency_cache != NULL)
+ /* Avoiding the list walk below can cut compile times dramatically
+ for some code. */
+ {
+ int elem_luid = INSN_LUID (pro);
+ int insn_luid = INSN_LUID (con);
+
+ gcc_assert (output_dependency_cache != NULL
+ && anti_dependency_cache != NULL);
+
+ if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
+ && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
+ && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+ return NULL;
+ }
+
+ return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
+}
+
+/* Add or update a dependence described by DEP.
+ MEM1 and MEM2, if non-null, correspond to memory locations in case of
+ data speculation.
+
+ The function returns a value indicating if an old entry has been changed
+ or a new entry has been added to insn's backward deps.
+
+ This function merely checks if producer and consumer is the same insn
+ and doesn't create a dep in this case. Actual manipulation of
+ dependence data structures is performed in add_or_update_dep_1. */
+static enum DEPS_ADJUST_RESULT
+maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
+{
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ gcc_assert (INSN_P (insn) && INSN_P (elem));
+
+ /* Don't depend an insn on itself. */
+ if (insn == elem)
+ {
+ if (sched_deps_info->generate_spec_deps)
+ /* INSN has an internal dependence, which we can't overcome. */
+ HAS_INTERNAL_DEP (insn) = 1;
+
+ return DEP_NODEP;
+ }
+
+ return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
+}
+
+/* Ask dependency caches what needs to be done for dependence DEP.
+ Return DEP_CREATED if new dependence should be created and there is no
+ need to try to find one searching the dependencies lists.
+ Return DEP_PRESENT if there already is a dependence described by DEP and
+ hence nothing is to be done.
+ Return DEP_CHANGED if there already is a dependence, but it should be
+ updated to incorporate additional information from DEP. */
+static enum DEPS_ADJUST_RESULT
+ask_dependency_caches (dep_t dep)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ gcc_assert (true_dependency_cache != NULL
+ && output_dependency_cache != NULL
+ && anti_dependency_cache != NULL);
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ enum reg_note present_dep_type;
+
+ if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_TRUE;
+ else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_OUTPUT;
+ else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_ANTI;
+ else
+ /* There is no existing dep so it should be created. */
+ return DEP_CREATED;
+
+ if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
+ /* DEP does not add anything to the existing dependence. */
+ return DEP_PRESENT;
+ }
+ else
+ {
+ ds_t present_dep_types = 0;
+
+ if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_TRUE;
+ if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_OUTPUT;
+ if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_ANTI;
+
+ if (present_dep_types == 0)
+ /* There is no existing dep so it should be created. */
+ return DEP_CREATED;
+
+ if (!(current_sched_info->flags & DO_SPECULATION)
+ || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
+ {
+ if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
+ == present_dep_types)
+ /* DEP does not add anything to the existing dependence. */
+ return DEP_PRESENT;
+ }
+ else
+ {
+ /* Only true dependencies can be data speculative and
+ only anti dependencies can be control speculative. */
+ gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
+ == present_dep_types);
+
+ /* if (DEP is SPECULATIVE) then
+ ..we should update DEP_STATUS
+ else
+ ..we should reset existing dep to non-speculative. */
+ }
+ }
+
+ return DEP_CHANGED;
+}
+
+/* Set dependency caches according to DEP. */
+static void
+set_dependency_caches (dep_t dep)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ switch (DEP_TYPE (dep))
+ {
+ case REG_DEP_TRUE:
+ bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_OUTPUT:
+ bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_ANTI:
+ bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+ else
+ {
+ ds_t ds = DEP_STATUS (dep);
+
+ if (ds & DEP_TRUE)
+ bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
+ if (ds & DEP_OUTPUT)
+ bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
+ if (ds & DEP_ANTI)
+ bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
+
+ if (ds & SPECULATIVE)
+ {
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+ bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
+ }
+ }
+}
+
+/* Type of dependence DEP have changed from OLD_TYPE. Update dependency
+ caches accordingly. */
+static void
+update_dependency_caches (dep_t dep, enum reg_note old_type)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ /* Clear corresponding cache entry because type of the link
+ may have changed. Keep them if we use_deps_list. */
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ switch (old_type)
+ {
+ case REG_DEP_OUTPUT:
+ bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_ANTI:
+ bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ set_dependency_caches (dep);
+}
+
+/* Convert a dependence pointed to by SD_IT to be non-speculative. */
+static void
+change_spec_dep_to_hard (sd_iterator_def sd_it)
+{
+ dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+ dep_link_t link = DEP_NODE_BACK (node);
+ dep_t dep = DEP_NODE_DEP (node);
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
+
+ DEP_STATUS (dep) &= ~SPECULATIVE;
+
+ if (true_dependency_cache != NULL)
+ /* Clear the cache entry. */
+ bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+}
+
+/* Update DEP to incorporate information from NEW_DEP.
+ SD_IT points to DEP in case it should be moved to another list.
+ MEM1 and MEM2, if nonnull, correspond to memory locations in case if
+ data-speculative dependence should be updated. */
+static enum DEPS_ADJUST_RESULT
+update_dep (dep_t dep, dep_t new_dep,
+ sd_iterator_def sd_it ATTRIBUTE_UNUSED,
+ rtx mem1 ATTRIBUTE_UNUSED,
+ rtx mem2 ATTRIBUTE_UNUSED)
+{
+ enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
+ enum reg_note old_type = DEP_TYPE (dep);
+
+ /* If this is a more restrictive type of dependence than the
+ existing one, then change the existing dependence to this
+ type. */
+ if ((int) DEP_TYPE (new_dep) < (int) old_type)
+ {
+ DEP_TYPE (dep) = DEP_TYPE (new_dep);
+ res = DEP_CHANGED;
+ }
+
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ /* Update DEP_STATUS. */
+ {
+ ds_t dep_status = DEP_STATUS (dep);
+ ds_t ds = DEP_STATUS (new_dep);
+ ds_t new_status = ds | dep_status;
+
+ if (new_status & SPECULATIVE)
+ /* Either existing dep or a dep we're adding or both are
+ speculative. */
+ {
+ if (!(ds & SPECULATIVE)
+ || !(dep_status & SPECULATIVE))
+ /* The new dep can't be speculative. */
+ {
+ new_status &= ~SPECULATIVE;
+
+ if (dep_status & SPECULATIVE)
+ /* The old dep was speculative, but now it
+ isn't. */
+ change_spec_dep_to_hard (sd_it);
+ }
+ else
+ {
+ /* Both are speculative. Merge probabilities. */
+ if (mem1 != NULL)
+ {
+ dw_t dw;
+
+ dw = estimate_dep_weak (mem1, mem2);
+ ds = set_dep_weak (ds, BEGIN_DATA, dw);
+ }
+
+ new_status = ds_merge (dep_status, ds);
+ }
+ }
+
+ ds = new_status;
+
+ if (dep_status != ds)
+ {
+ DEP_STATUS (dep) = ds;
+ res = DEP_CHANGED;
+ }
+ }
+
+ if (true_dependency_cache != NULL
+ && res == DEP_CHANGED)
+ update_dependency_caches (dep, old_type);
+
+ return res;
+}
+
+/* Add or update a dependence described by DEP.
+ MEM1 and MEM2, if non-null, correspond to memory locations in case of
+ data speculation.
+
+ The function returns a value indicating if an old entry has been changed
+ or a new entry has been added to insn's backward deps or nothing has
+ been updated at all. */
+static enum DEPS_ADJUST_RESULT
+add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
+ rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
+{
+ bool maybe_present_p = true;
+ bool present_p = false;
+
+ gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
+ && DEP_PRO (new_dep) != DEP_CON (new_dep));
+
+#ifdef ENABLE_CHECKING
+ check_dep (new_dep, mem1 != NULL);
+#endif
+
+ if (true_dependency_cache != NULL)
+ {
+ switch (ask_dependency_caches (new_dep))
+ {
+ case DEP_PRESENT:
+ return DEP_PRESENT;
+
+ case DEP_CHANGED:
+ maybe_present_p = true;
+ present_p = true;
+ break;
+
+ case DEP_CREATED:
+ maybe_present_p = false;
+ present_p = false;
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ }
+
+ /* Check that we don't already have this dependence. */
+ if (maybe_present_p)
+ {
+ dep_t present_dep;
+ sd_iterator_def sd_it;
+
+ gcc_assert (true_dependency_cache == NULL || present_p);
+
+ present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
+ DEP_CON (new_dep),
+ resolved_p, &sd_it);
+
+ if (present_dep != NULL)
+ /* We found an existing dependency between ELEM and INSN. */
+ return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
+ else
+ /* We didn't find a dep, it shouldn't present in the cache. */
+ gcc_assert (!present_p);
+ }
+
+ /* Might want to check one level of transitivity to save conses.
+ This check should be done in maybe_add_or_update_dep_1.
+ Since we made it to add_or_update_dep_1, we must create
+ (or update) a link. */
+
+ if (mem1 != NULL_RTX)
+ {
+ gcc_assert (sched_deps_info->generate_spec_deps);
+ DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
+ estimate_dep_weak (mem1, mem2));
+ }
+
+ sd_add_dep (new_dep, resolved_p);
+
+ return DEP_CREATED;
+}
+
+/* Initialize BACK_LIST_PTR with consumer's backward list and
+ FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
+ initialize with lists that hold resolved deps. */
+static void
+get_back_and_forw_lists (dep_t dep, bool resolved_p,
+ deps_list_t *back_list_ptr,
+ deps_list_t *forw_list_ptr)
+{
+ rtx con = DEP_CON (dep);
+
+ if (!resolved_p)
+ {
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && (DEP_STATUS (dep) & SPECULATIVE))
+ *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
+ else
+ *back_list_ptr = INSN_HARD_BACK_DEPS (con);
+
+ *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
+ }
+ else
+ {
+ *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
+ *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
+ }
+}
+
+/* Add dependence described by DEP.
+ If RESOLVED_P is true treat the dependence as a resolved one. */
+void
+sd_add_dep (dep_t dep, bool resolved_p)
+{
+ dep_node_t n = create_dep_node ();
+ deps_list_t con_back_deps;
+ deps_list_t pro_forw_deps;
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
+
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
+ DEP_STATUS (dep) &= ~SPECULATIVE;
+
+ copy_dep (DEP_NODE_DEP (n), dep);
+
+ get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
+
+ add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
+
+#ifdef ENABLE_CHECKING
+ check_dep (dep, false);
+#endif
+
+ add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
+
+ /* If we are adding a dependency to INSN's LOG_LINKs, then note that
+ in the bitmap caches of dependency information. */
+ if (true_dependency_cache != NULL)
+ set_dependency_caches (dep);
+}
+
+/* Add or update backward dependence between INSN and ELEM
+ with given type DEP_TYPE and dep_status DS.
+ This function is a convenience wrapper. */
+enum DEPS_ADJUST_RESULT
+sd_add_or_update_dep (dep_t dep, bool resolved_p)
+{
+ return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
+}
+
+/* Resolved dependence pointed to by SD_IT.
+ SD_IT will advance to the next element. */
+void
+sd_resolve_dep (sd_iterator_def sd_it)
+{
+ dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+ dep_t dep = DEP_NODE_DEP (node);
+ rtx pro = DEP_PRO (dep);
+ rtx con = DEP_CON (dep);
+
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && (DEP_STATUS (dep) & SPECULATIVE))
+ move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
+ INSN_RESOLVED_BACK_DEPS (con));
+ else
+ move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
+ INSN_RESOLVED_BACK_DEPS (con));
+
+ move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
+ INSN_RESOLVED_FORW_DEPS (pro));
+}
+
+/* Make TO depend on all the FROM's producers.
+ If RESOLVED_P is true add dependencies to the resolved lists. */
+void
+sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
+{
+ sd_list_types_def list_type;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
+
+ FOR_EACH_DEP (from, list_type, sd_it, dep)
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ copy_dep (new_dep, dep);
+ DEP_CON (new_dep) = to;
+ sd_add_dep (new_dep, resolved_p);
+ }
+}
+
+/* Remove a dependency referred to by SD_IT.
+ SD_IT will point to the next dependence after removal. */
+void
+sd_delete_dep (sd_iterator_def sd_it)
+{
+ dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
+ dep_t dep = DEP_NODE_DEP (n);
+ rtx pro = DEP_PRO (dep);
+ rtx con = DEP_CON (dep);
+ deps_list_t con_back_deps;
+ deps_list_t pro_forw_deps;
+
+ if (true_dependency_cache != NULL)
+ {
+ int elem_luid = INSN_LUID (pro);
+ int insn_luid = INSN_LUID (con);
+
+ bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
+ bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
+
+ if (current_sched_info->flags & DO_SPECULATION)
+ bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
+ }
+
+ get_back_and_forw_lists (dep, sd_it.resolved_p,
+ &con_back_deps, &pro_forw_deps);
+
+ remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
+ remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
+
+ delete_dep_node (n);
+}
+
+/* Dump size of the lists. */
+#define DUMP_LISTS_SIZE (2)
+
+/* Dump dependencies of the lists. */
+#define DUMP_LISTS_DEPS (4)
+
+/* Dump all information about the lists. */
+#define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
+
+/* Dump deps_lists of INSN specified by TYPES to DUMP.
+ FLAGS is a bit mask specifying what information about the lists needs
+ to be printed.
+ If FLAGS has the very first bit set, then dump all information about
+ the lists and propagate this bit into the callee dump functions. */
+static void
+dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ int all;
+
+ all = (flags & 1);
+
+ if (all)
+ flags |= DUMP_LISTS_ALL;
+
+ fprintf (dump, "[");
+
+ if (flags & DUMP_LISTS_SIZE)
+ fprintf (dump, "%d; ", sd_lists_size (insn, types));
+
+ if (flags & DUMP_LISTS_DEPS)
+ {
+ FOR_EACH_DEP (insn, types, sd_it, dep)
+ {
+ dump_dep (dump, dep, dump_dep_flags | all);
+ fprintf (dump, " ");
+ }
+ }
+}
+
+/* Dump all information about deps_lists of INSN specified by TYPES
+ to STDERR. */
+void
+sd_debug_lists (rtx insn, sd_list_types_def types)
+{
+ dump_lists (stderr, insn, types, 1);
+ fprintf (stderr, "\n");
+}
+
+/* A convenience wrapper to operate on an entire list. */
+
+static void
+add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
+{
+ for (; list; list = XEXP (list, 1))
+ {
+ if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
+ add_dependence (insn, XEXP (list, 0), dep_type);
+ }
+}
+
+/* Similar, but free *LISTP at the same time, when the context
+ is not readonly. */
+
+static void
+add_dependence_list_and_free (struct deps_desc *deps, rtx insn, rtx *listp,
+ int uncond, enum reg_note dep_type)
+{
+ rtx list, next;
+
+ /* We don't want to short-circuit dependencies involving debug
+ insns, because they may cause actual dependencies to be
+ disregarded. */
+ if (deps->readonly || DEBUG_INSN_P (insn))
+ {
+ add_dependence_list (insn, *listp, uncond, dep_type);
+ return;
+ }
+
+ for (list = *listp, *listp = NULL; list ; list = next)
+ {
+ next = XEXP (list, 1);
+ if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
+ add_dependence (insn, XEXP (list, 0), dep_type);
+ free_INSN_LIST_node (list);
+ }
+}
+
+/* Remove all occurences of INSN from LIST. Return the number of
+ occurences removed. */
+
+static int
+remove_from_dependence_list (rtx insn, rtx* listp)
+{
+ int removed = 0;
+
+ while (*listp)
+ {
+ if (XEXP (*listp, 0) == insn)
+ {
+ remove_free_INSN_LIST_node (listp);
+ removed++;
+ continue;
+ }
+
+ listp = &XEXP (*listp, 1);
+ }
+
+ return removed;
+}
+
+/* Same as above, but process two lists at once. */
+static int
+remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
+{
+ int removed = 0;
+
+ while (*listp)
+ {
+ if (XEXP (*listp, 0) == insn)
+ {
+ remove_free_INSN_LIST_node (listp);
+ remove_free_EXPR_LIST_node (exprp);
+ removed++;
+ continue;
+ }
+
+ listp = &XEXP (*listp, 1);
+ exprp = &XEXP (*exprp, 1);
+ }
+
+ return removed;
+}
+
+/* Clear all dependencies for an insn. */
+static void
+delete_all_dependences (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ /* The below cycle can be optimized to clear the caches and back_deps
+ in one call but that would provoke duplication of code from
+ delete_dep (). */
+
+ for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
+ sd_delete_dep (sd_it);
+}
+
+/* All insns in a scheduling group except the first should only have
+ dependencies on the previous insn in the group. So we find the
+ first instruction in the scheduling group by walking the dependence
+ chains backwards. Then we add the dependencies for the group to
+ the previous nonnote insn. */
+
+static void
+fixup_sched_groups (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ rtx prev_nonnote;
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ {
+ rtx i = insn;
+ rtx pro = DEP_PRO (dep);
+
+ do
+ {
+ i = prev_nonnote_insn (i);
+
+ if (pro == i)
+ goto next_link;
+ } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
+
+ if (! sched_insns_conditions_mutex_p (i, pro))
+ add_dependence (i, pro, DEP_TYPE (dep));
+ next_link:;
+ }
+
+ delete_all_dependences (insn);
+
+ prev_nonnote = prev_nonnote_nondebug_insn (insn);
+ if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
+ && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
+ add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
+}
+\f
+/* Process an insn's memory dependencies. There are four kinds of
+ dependencies:
+
+ (0) read dependence: read follows read
+ (1) true dependence: read follows write
+ (2) output dependence: write follows write
+ (3) anti dependence: write follows read
+
+ We are careful to build only dependencies which actually exist, and
+ use transitivity to avoid building too many links. */
+
+/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
+ The MEM is a memory reference contained within INSN, which we are saving
+ so that we can do memory aliasing on it. */
+
+static void
+add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
+ rtx insn, rtx mem)
+{
+ rtx *insn_list;
+ rtx *mem_list;
+ rtx link;
+
+ gcc_assert (!deps->readonly);
+ if (read_p)
+ {
+ insn_list = &deps->pending_read_insns;
+ mem_list = &deps->pending_read_mems;
+ if (!DEBUG_INSN_P (insn))
+ deps->pending_read_list_length++;
+ }
+ else
+ {
+ insn_list = &deps->pending_write_insns;
+ mem_list = &deps->pending_write_mems;
+ deps->pending_write_list_length++;
+ }
+
+ link = alloc_INSN_LIST (insn, *insn_list);
+ *insn_list = link;
+
+ if (sched_deps_info->use_cselib)
+ {
+ mem = shallow_copy_rtx (mem);
+ XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0), GET_MODE (mem));
+ }
+ link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
+ *mem_list = link;
+}
+
+/* Make a dependency between every memory reference on the pending lists
+ and INSN, thus flushing the pending lists. FOR_READ is true if emitting
+ dependencies for a read operation, similarly with FOR_WRITE. */
+
+static void
+flush_pending_lists (struct deps_desc *deps, rtx insn, int for_read,
+ int for_write)
+{
+ if (for_write)
+ {
+ add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
+ 1, REG_DEP_ANTI);
+ if (!deps->readonly)
+ {
+ free_EXPR_LIST_list (&deps->pending_read_mems);
+ deps->pending_read_list_length = 0;
+ }
+ }
+
+ add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
+ for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
+
+ add_dependence_list_and_free (deps, insn,
+ &deps->last_pending_memory_flush, 1,
+ for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
+ if (!deps->readonly)
+ {
+ free_EXPR_LIST_list (&deps->pending_write_mems);
+ deps->pending_write_list_length = 0;