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
)));
357 pool_free (dn_pool
, n
);
360 /* Pool to hold dependencies lists (deps_list_t). */
361 static alloc_pool dl_pool
;
363 /* Number of deps_lists out there. */
364 static int dl_pool_diff
= 0;
366 /* Functions to operate with dependences lists - deps_list_t. */
368 /* Return true if list L is empty. */
370 deps_list_empty_p (deps_list_t l
)
372 return DEPS_LIST_N_LINKS (l
) == 0;
375 /* Create a new deps_list. */
377 create_deps_list (void)
379 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
381 DEPS_LIST_FIRST (l
) = NULL
;
382 DEPS_LIST_N_LINKS (l
) = 0;
388 /* Free deps_list L. */
390 free_deps_list (deps_list_t l
)
392 gcc_assert (deps_list_empty_p (l
));
396 pool_free (dl_pool
, l
);
399 /* Return true if there is no dep_nodes and deps_lists out there.
400 After the region is scheduled all the dependency nodes and lists
401 should [generally] be returned to pool. */
403 deps_pools_are_empty_p (void)
405 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
408 /* Remove all elements from L. */
410 clear_deps_list (deps_list_t l
)
414 dep_link_t link
= DEPS_LIST_FIRST (l
);
419 remove_from_deps_list (link
, l
);
424 /* Decide whether a dependency should be treated as a hard or a speculative
427 dep_spec_p (dep_t dep
)
429 if (current_sched_info
->flags
& DO_SPECULATION
)
431 if (DEP_STATUS (dep
) & SPECULATIVE
)
434 if (current_sched_info
->flags
& DO_PREDICATION
)
436 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
439 if (DEP_REPLACE (dep
) != NULL
)
444 static regset reg_pending_sets
;
445 static regset reg_pending_clobbers
;
446 static regset reg_pending_uses
;
447 static regset reg_pending_control_uses
;
448 static enum reg_pending_barrier_mode reg_pending_barrier
;
450 /* Hard registers implicitly clobbered or used (or may be implicitly
451 clobbered or used) by the currently analyzed insn. For example,
452 insn in its constraint has one register class. Even if there is
453 currently no hard register in the insn, the particular hard
454 register will be in the insn after reload pass because the
455 constraint requires it. */
456 static HARD_REG_SET implicit_reg_pending_clobbers
;
457 static HARD_REG_SET implicit_reg_pending_uses
;
459 /* To speed up the test for duplicate dependency links we keep a
460 record of dependencies created by add_dependence when the average
461 number of instructions in a basic block is very large.
463 Studies have shown that there is typically around 5 instructions between
464 branches for typical C code. So we can make a guess that the average
465 basic block is approximately 5 instructions long; we will choose 100X
466 the average size as a very large basic block.
468 Each insn has associated bitmaps for its dependencies. Each bitmap
469 has enough entries to represent a dependency on any other insn in
470 the insn chain. All bitmap for true dependencies cache is
471 allocated then the rest two ones are also allocated. */
472 static bitmap_head
*true_dependency_cache
= NULL
;
473 static bitmap_head
*output_dependency_cache
= NULL
;
474 static bitmap_head
*anti_dependency_cache
= NULL
;
475 static bitmap_head
*control_dependency_cache
= NULL
;
476 static bitmap_head
*spec_dependency_cache
= NULL
;
477 static int cache_size
;
479 /* True if we should mark added dependencies as a non-register deps. */
480 static bool mark_as_hard
;
482 static int deps_may_trap_p (const_rtx
);
483 static void add_dependence_1 (rtx
, rtx
, enum reg_note
);
484 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
, bool);
485 static void add_dependence_list_and_free (struct deps_desc
*, rtx
,
486 rtx
*, int, enum reg_note
, bool);
487 static void delete_all_dependences (rtx
);
488 static void chain_to_prev_insn (rtx
);
490 static void flush_pending_lists (struct deps_desc
*, rtx
, int, int);
491 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx
);
492 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx
);
493 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx
);
495 static bool sched_has_condition_p (const_rtx
);
496 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
498 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
500 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
502 #ifdef ENABLE_CHECKING
503 static void check_dep (dep_t
, bool);
506 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
509 deps_may_trap_p (const_rtx mem
)
511 const_rtx addr
= XEXP (mem
, 0);
513 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
515 const_rtx t
= get_reg_known_value (REGNO (addr
));
519 return rtx_addr_can_trap_p (addr
);
523 /* Find the condition under which INSN is executed. If REV is not NULL,
524 it is set to TRUE when the returned comparison should be reversed
525 to get the actual condition. */
527 sched_get_condition_with_rev_uncached (const_rtx insn
, bool *rev
)
529 rtx pat
= PATTERN (insn
);
535 if (GET_CODE (pat
) == COND_EXEC
)
536 return COND_EXEC_TEST (pat
);
538 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
541 src
= SET_SRC (pc_set (insn
));
543 if (XEXP (src
, 2) == pc_rtx
)
544 return XEXP (src
, 0);
545 else if (XEXP (src
, 1) == pc_rtx
)
547 rtx cond
= XEXP (src
, 0);
548 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
550 if (revcode
== UNKNOWN
)
561 /* Return the condition under which INSN does not execute (i.e. the
562 not-taken condition for a conditional branch), or NULL if we cannot
563 find such a condition. The caller should make a copy of the condition
566 sched_get_reverse_condition_uncached (const_rtx insn
)
569 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
570 if (cond
== NULL_RTX
)
574 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
575 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
582 /* Caching variant of sched_get_condition_with_rev_uncached.
583 We only do actual work the first time we come here for an insn; the
584 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
586 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
590 if (INSN_LUID (insn
) == 0)
591 return sched_get_condition_with_rev_uncached (insn
, rev
);
593 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
596 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
599 *rev
= INSN_REVERSE_COND (insn
);
600 return INSN_CACHED_COND (insn
);
603 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
604 INSN_REVERSE_COND (insn
) = tmp
;
606 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
608 INSN_CACHED_COND (insn
) = const_true_rtx
;
613 *rev
= INSN_REVERSE_COND (insn
);
614 return INSN_CACHED_COND (insn
);
617 /* True when we can find a condition under which INSN is executed. */
619 sched_has_condition_p (const_rtx insn
)
621 return !! sched_get_condition_with_rev (insn
, NULL
);
626 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
628 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
630 if (COMPARISON_P (cond1
)
631 && COMPARISON_P (cond2
)
632 && GET_CODE (cond1
) ==
634 ? reversed_comparison_code (cond2
, NULL
)
636 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
637 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
642 /* Return true if insn1 and insn2 can never depend on one another because
643 the conditions under which they are executed are mutually exclusive. */
645 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
648 bool rev1
= false, rev2
= false;
650 /* df doesn't handle conditional lifetimes entirely correctly;
651 calls mess up the conditional lifetimes. */
652 if (!CALL_P (insn1
) && !CALL_P (insn2
))
654 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
655 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
657 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
658 /* Make sure first instruction doesn't affect condition of second
659 instruction if switched. */
660 && !modified_in_p (cond1
, insn2
)
661 /* Make sure second instruction doesn't affect condition of first
662 instruction if switched. */
663 && !modified_in_p (cond2
, insn1
))
670 /* Return true if INSN can potentially be speculated with type DS. */
672 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
674 if (HAS_INTERNAL_DEP (insn
))
677 if (!NONJUMP_INSN_P (insn
))
680 if (SCHED_GROUP_P (insn
))
683 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
686 if (side_effects_p (PATTERN (insn
)))
690 /* The following instructions, which depend on a speculatively scheduled
691 instruction, cannot be speculatively scheduled along. */
693 if (may_trap_or_fault_p (PATTERN (insn
)))
694 /* If instruction might fault, it cannot be speculatively scheduled.
695 For control speculation it's obvious why and for data speculation
696 it's because the insn might get wrong input if speculation
697 wasn't successful. */
700 if ((ds
& BE_IN_DATA
)
701 && sched_has_condition_p (insn
))
702 /* If this is a predicated instruction, then it cannot be
703 speculatively scheduled. See PR35659. */
710 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
711 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
712 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
713 This function is used to switch sd_iterator to the next list.
714 !!! For internal use only. Might consider moving it to sched-int.h. */
716 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
717 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
719 sd_list_types_def types
= *types_ptr
;
721 if (types
& SD_LIST_HARD_BACK
)
723 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
724 *resolved_p_ptr
= false;
725 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
727 else if (types
& SD_LIST_SPEC_BACK
)
729 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
730 *resolved_p_ptr
= false;
731 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
733 else if (types
& SD_LIST_FORW
)
735 *list_ptr
= INSN_FORW_DEPS (insn
);
736 *resolved_p_ptr
= false;
737 *types_ptr
= types
& ~SD_LIST_FORW
;
739 else if (types
& SD_LIST_RES_BACK
)
741 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
742 *resolved_p_ptr
= true;
743 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
745 else if (types
& SD_LIST_RES_FORW
)
747 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
748 *resolved_p_ptr
= true;
749 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
754 *resolved_p_ptr
= false;
755 *types_ptr
= SD_LIST_NONE
;
759 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
761 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
765 while (list_types
!= SD_LIST_NONE
)
770 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
772 size
+= DEPS_LIST_N_LINKS (list
);
778 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
781 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
783 while (list_types
!= SD_LIST_NONE
)
788 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
789 if (!deps_list_empty_p (list
))
796 /* Initialize data for INSN. */
798 sd_init_insn (rtx insn
)
800 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
801 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
802 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
803 INSN_FORW_DEPS (insn
) = create_deps_list ();
804 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
806 /* ??? It would be nice to allocate dependency caches here. */
809 /* Free data for INSN. */
811 sd_finish_insn (rtx insn
)
813 /* ??? It would be nice to deallocate dependency caches here. */
815 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
816 INSN_HARD_BACK_DEPS (insn
) = NULL
;
818 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
819 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
821 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
822 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
824 free_deps_list (INSN_FORW_DEPS (insn
));
825 INSN_FORW_DEPS (insn
) = NULL
;
827 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
828 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
831 /* Find a dependency between producer PRO and consumer CON.
832 Search through resolved dependency lists if RESOLVED_P is true.
833 If no such dependency is found return NULL,
834 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
835 with an iterator pointing to it. */
837 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
838 sd_iterator_def
*sd_it_ptr
)
840 sd_list_types_def pro_list_type
;
841 sd_list_types_def con_list_type
;
842 sd_iterator_def sd_it
;
844 bool found_p
= false;
848 pro_list_type
= SD_LIST_RES_FORW
;
849 con_list_type
= SD_LIST_RES_BACK
;
853 pro_list_type
= SD_LIST_FORW
;
854 con_list_type
= SD_LIST_BACK
;
857 /* Walk through either back list of INSN or forw list of ELEM
858 depending on which one is shorter. */
859 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
861 /* Find the dep_link with producer PRO in consumer's back_deps. */
862 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
863 if (DEP_PRO (dep
) == pro
)
871 /* Find the dep_link with consumer CON in producer's forw_deps. */
872 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
873 if (DEP_CON (dep
) == con
)
882 if (sd_it_ptr
!= NULL
)
891 /* Find a dependency between producer PRO and consumer CON.
892 Use dependency [if available] to check if dependency is present at all.
893 Search through resolved dependency lists if RESOLVED_P is true.
894 If the dependency or NULL if none found. */
896 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
898 if (true_dependency_cache
!= NULL
)
899 /* Avoiding the list walk below can cut compile times dramatically
902 int elem_luid
= INSN_LUID (pro
);
903 int insn_luid
= INSN_LUID (con
);
905 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
906 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
907 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
908 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
912 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
915 /* Add or update a dependence described by DEP.
916 MEM1 and MEM2, if non-null, correspond to memory locations in case of
919 The function returns a value indicating if an old entry has been changed
920 or a new entry has been added to insn's backward deps.
922 This function merely checks if producer and consumer is the same insn
923 and doesn't create a dep in this case. Actual manipulation of
924 dependence data structures is performed in add_or_update_dep_1. */
925 static enum DEPS_ADJUST_RESULT
926 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
928 rtx elem
= DEP_PRO (dep
);
929 rtx insn
= DEP_CON (dep
);
931 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
933 /* Don't depend an insn on itself. */
936 if (sched_deps_info
->generate_spec_deps
)
937 /* INSN has an internal dependence, which we can't overcome. */
938 HAS_INTERNAL_DEP (insn
) = 1;
943 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
946 /* Ask dependency caches what needs to be done for dependence DEP.
947 Return DEP_CREATED if new dependence should be created and there is no
948 need to try to find one searching the dependencies lists.
949 Return DEP_PRESENT if there already is a dependence described by DEP and
950 hence nothing is to be done.
951 Return DEP_CHANGED if there already is a dependence, but it should be
952 updated to incorporate additional information from DEP. */
953 static enum DEPS_ADJUST_RESULT
954 ask_dependency_caches (dep_t dep
)
956 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
957 int insn_luid
= INSN_LUID (DEP_CON (dep
));
959 gcc_assert (true_dependency_cache
!= NULL
960 && output_dependency_cache
!= NULL
961 && anti_dependency_cache
!= NULL
962 && control_dependency_cache
!= NULL
);
964 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
966 enum reg_note present_dep_type
;
968 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
969 present_dep_type
= REG_DEP_TRUE
;
970 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
971 present_dep_type
= REG_DEP_OUTPUT
;
972 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
973 present_dep_type
= REG_DEP_ANTI
;
974 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
975 present_dep_type
= REG_DEP_CONTROL
;
977 /* There is no existing dep so it should be created. */
980 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
981 /* DEP does not add anything to the existing dependence. */
986 ds_t present_dep_types
= 0;
988 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
989 present_dep_types
|= DEP_TRUE
;
990 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
991 present_dep_types
|= DEP_OUTPUT
;
992 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
993 present_dep_types
|= DEP_ANTI
;
994 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
995 present_dep_types
|= DEP_CONTROL
;
997 if (present_dep_types
== 0)
998 /* There is no existing dep so it should be created. */
1001 if (!(current_sched_info
->flags
& DO_SPECULATION
)
1002 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
1004 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
1005 == present_dep_types
)
1006 /* DEP does not add anything to the existing dependence. */
1011 /* Only true dependencies can be data speculative and
1012 only anti dependencies can be control speculative. */
1013 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1014 == present_dep_types
);
1016 /* if (DEP is SPECULATIVE) then
1017 ..we should update DEP_STATUS
1019 ..we should reset existing dep to non-speculative. */
1026 /* Set dependency caches according to DEP. */
1028 set_dependency_caches (dep_t dep
)
1030 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1031 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1033 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1035 switch (DEP_TYPE (dep
))
1038 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1041 case REG_DEP_OUTPUT
:
1042 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1046 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1049 case REG_DEP_CONTROL
:
1050 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1059 ds_t ds
= DEP_STATUS (dep
);
1062 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1063 if (ds
& DEP_OUTPUT
)
1064 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1066 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1067 if (ds
& DEP_CONTROL
)
1068 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1070 if (ds
& SPECULATIVE
)
1072 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1073 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1078 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1079 caches accordingly. */
1081 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1083 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1084 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1086 /* Clear corresponding cache entry because type of the link
1087 may have changed. Keep them if we use_deps_list. */
1088 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1092 case REG_DEP_OUTPUT
:
1093 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1097 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1100 case REG_DEP_CONTROL
:
1101 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1109 set_dependency_caches (dep
);
1112 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1114 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1116 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1117 dep_link_t link
= DEP_NODE_BACK (node
);
1118 dep_t dep
= DEP_NODE_DEP (node
);
1119 rtx elem
= DEP_PRO (dep
);
1120 rtx insn
= DEP_CON (dep
);
1122 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1124 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1126 if (true_dependency_cache
!= NULL
)
1127 /* Clear the cache entry. */
1128 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1132 /* Update DEP to incorporate information from NEW_DEP.
1133 SD_IT points to DEP in case it should be moved to another list.
1134 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1135 data-speculative dependence should be updated. */
1136 static enum DEPS_ADJUST_RESULT
1137 update_dep (dep_t dep
, dep_t new_dep
,
1138 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1139 rtx mem1 ATTRIBUTE_UNUSED
,
1140 rtx mem2 ATTRIBUTE_UNUSED
)
1142 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1143 enum reg_note old_type
= DEP_TYPE (dep
);
1144 bool was_spec
= dep_spec_p (dep
);
1146 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1147 DEP_MULTIPLE (dep
) = 1;
1149 /* If this is a more restrictive type of dependence than the
1150 existing one, then change the existing dependence to this
1152 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1154 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1158 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1159 /* Update DEP_STATUS. */
1161 ds_t dep_status
= DEP_STATUS (dep
);
1162 ds_t ds
= DEP_STATUS (new_dep
);
1163 ds_t new_status
= ds
| dep_status
;
1165 if (new_status
& SPECULATIVE
)
1167 /* Either existing dep or a dep we're adding or both are
1169 if (!(ds
& SPECULATIVE
)
1170 || !(dep_status
& SPECULATIVE
))
1171 /* The new dep can't be speculative. */
1172 new_status
&= ~SPECULATIVE
;
1175 /* Both are speculative. Merge probabilities. */
1180 dw
= estimate_dep_weak (mem1
, mem2
);
1181 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1184 new_status
= ds_merge (dep_status
, ds
);
1190 if (dep_status
!= ds
)
1192 DEP_STATUS (dep
) = ds
;
1197 if (was_spec
&& !dep_spec_p (dep
))
1198 /* The old dep was speculative, but now it isn't. */
1199 change_spec_dep_to_hard (sd_it
);
1201 if (true_dependency_cache
!= NULL
1202 && res
== DEP_CHANGED
)
1203 update_dependency_caches (dep
, old_type
);
1208 /* Add or update a dependence described by DEP.
1209 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1212 The function returns a value indicating if an old entry has been changed
1213 or a new entry has been added to insn's backward deps or nothing has
1214 been updated at all. */
1215 static enum DEPS_ADJUST_RESULT
1216 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1217 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1219 bool maybe_present_p
= true;
1220 bool present_p
= false;
1222 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1223 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1225 #ifdef ENABLE_CHECKING
1226 check_dep (new_dep
, mem1
!= NULL
);
1229 if (true_dependency_cache
!= NULL
)
1231 switch (ask_dependency_caches (new_dep
))
1237 maybe_present_p
= true;
1242 maybe_present_p
= false;
1252 /* Check that we don't already have this dependence. */
1253 if (maybe_present_p
)
1256 sd_iterator_def sd_it
;
1258 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1260 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1262 resolved_p
, &sd_it
);
1264 if (present_dep
!= NULL
)
1265 /* We found an existing dependency between ELEM and INSN. */
1266 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1268 /* We didn't find a dep, it shouldn't present in the cache. */
1269 gcc_assert (!present_p
);
1272 /* Might want to check one level of transitivity to save conses.
1273 This check should be done in maybe_add_or_update_dep_1.
1274 Since we made it to add_or_update_dep_1, we must create
1275 (or update) a link. */
1277 if (mem1
!= NULL_RTX
)
1279 gcc_assert (sched_deps_info
->generate_spec_deps
);
1280 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1281 estimate_dep_weak (mem1
, mem2
));
1284 sd_add_dep (new_dep
, resolved_p
);
1289 /* Initialize BACK_LIST_PTR with consumer's backward list and
1290 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1291 initialize with lists that hold resolved deps. */
1293 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1294 deps_list_t
*back_list_ptr
,
1295 deps_list_t
*forw_list_ptr
)
1297 rtx con
= DEP_CON (dep
);
1301 if (dep_spec_p (dep
))
1302 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1304 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1306 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1310 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1311 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1315 /* Add dependence described by DEP.
1316 If RESOLVED_P is true treat the dependence as a resolved one. */
1318 sd_add_dep (dep_t dep
, bool resolved_p
)
1320 dep_node_t n
= create_dep_node ();
1321 deps_list_t con_back_deps
;
1322 deps_list_t pro_forw_deps
;
1323 rtx elem
= DEP_PRO (dep
);
1324 rtx insn
= DEP_CON (dep
);
1326 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1328 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1329 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1330 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1332 copy_dep (DEP_NODE_DEP (n
), dep
);
1334 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1336 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1338 #ifdef ENABLE_CHECKING
1339 check_dep (dep
, false);
1342 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1344 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1345 in the bitmap caches of dependency information. */
1346 if (true_dependency_cache
!= NULL
)
1347 set_dependency_caches (dep
);
1350 /* Add or update backward dependence between INSN and ELEM
1351 with given type DEP_TYPE and dep_status DS.
1352 This function is a convenience wrapper. */
1353 enum DEPS_ADJUST_RESULT
1354 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1356 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1359 /* Resolved dependence pointed to by SD_IT.
1360 SD_IT will advance to the next element. */
1362 sd_resolve_dep (sd_iterator_def sd_it
)
1364 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1365 dep_t dep
= DEP_NODE_DEP (node
);
1366 rtx pro
= DEP_PRO (dep
);
1367 rtx con
= DEP_CON (dep
);
1369 if (dep_spec_p (dep
))
1370 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1371 INSN_RESOLVED_BACK_DEPS (con
));
1373 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1374 INSN_RESOLVED_BACK_DEPS (con
));
1376 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1377 INSN_RESOLVED_FORW_DEPS (pro
));
1380 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1381 pointed to by SD_IT to unresolved state. */
1383 sd_unresolve_dep (sd_iterator_def sd_it
)
1385 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1386 dep_t dep
= DEP_NODE_DEP (node
);
1387 rtx pro
= DEP_PRO (dep
);
1388 rtx con
= DEP_CON (dep
);
1390 if (dep_spec_p (dep
))
1391 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1392 INSN_SPEC_BACK_DEPS (con
));
1394 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1395 INSN_HARD_BACK_DEPS (con
));
1397 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1398 INSN_FORW_DEPS (pro
));
1401 /* Make TO depend on all the FROM's producers.
1402 If RESOLVED_P is true add dependencies to the resolved lists. */
1404 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1406 sd_list_types_def list_type
;
1407 sd_iterator_def sd_it
;
1410 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1412 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1414 dep_def _new_dep
, *new_dep
= &_new_dep
;
1416 copy_dep (new_dep
, dep
);
1417 DEP_CON (new_dep
) = to
;
1418 sd_add_dep (new_dep
, resolved_p
);
1422 /* Remove a dependency referred to by SD_IT.
1423 SD_IT will point to the next dependence after removal. */
1425 sd_delete_dep (sd_iterator_def sd_it
)
1427 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1428 dep_t dep
= DEP_NODE_DEP (n
);
1429 rtx pro
= DEP_PRO (dep
);
1430 rtx con
= DEP_CON (dep
);
1431 deps_list_t con_back_deps
;
1432 deps_list_t pro_forw_deps
;
1434 if (true_dependency_cache
!= NULL
)
1436 int elem_luid
= INSN_LUID (pro
);
1437 int insn_luid
= INSN_LUID (con
);
1439 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1440 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1441 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1442 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1444 if (current_sched_info
->flags
& DO_SPECULATION
)
1445 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1448 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1449 &con_back_deps
, &pro_forw_deps
);
1451 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1452 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1454 delete_dep_node (n
);
1457 /* Dump size of the lists. */
1458 #define DUMP_LISTS_SIZE (2)
1460 /* Dump dependencies of the lists. */
1461 #define DUMP_LISTS_DEPS (4)
1463 /* Dump all information about the lists. */
1464 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1466 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1467 FLAGS is a bit mask specifying what information about the lists needs
1469 If FLAGS has the very first bit set, then dump all information about
1470 the lists and propagate this bit into the callee dump functions. */
1472 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1474 sd_iterator_def sd_it
;
1481 flags
|= DUMP_LISTS_ALL
;
1483 fprintf (dump
, "[");
1485 if (flags
& DUMP_LISTS_SIZE
)
1486 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1488 if (flags
& DUMP_LISTS_DEPS
)
1490 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1492 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1493 fprintf (dump
, " ");
1498 /* Dump all information about deps_lists of INSN specified by TYPES
1501 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1503 dump_lists (stderr
, insn
, types
, 1);
1504 fprintf (stderr
, "\n");
1507 /* A wrapper around add_dependence_1, to add a dependence of CON on
1508 PRO, with type DEP_TYPE. This function implements special handling
1509 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1510 the type to REG_DEP_ANTI if we can determine that predication is
1511 impossible; otherwise we add additional true dependencies on the
1512 INSN_COND_DEPS list of the jump (which PRO must be). */
1514 add_dependence (rtx con
, rtx pro
, enum reg_note dep_type
)
1516 if (dep_type
== REG_DEP_CONTROL
1517 && !(current_sched_info
->flags
& DO_PREDICATION
))
1518 dep_type
= REG_DEP_ANTI
;
1520 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1521 so we must also make the insn dependent on the setter of the
1523 if (dep_type
== REG_DEP_CONTROL
)
1526 rtx other
= real_insn_for_shadow (real_pro
);
1529 if (other
!= NULL_RTX
)
1531 cond
= sched_get_reverse_condition_uncached (real_pro
);
1532 /* Verify that the insn does not use a different value in
1533 the condition register than the one that was present at
1535 if (cond
== NULL_RTX
)
1536 dep_type
= REG_DEP_ANTI
;
1537 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1540 CLEAR_HARD_REG_SET (uses
);
1541 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1542 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1543 dep_type
= REG_DEP_ANTI
;
1545 if (dep_type
== REG_DEP_CONTROL
)
1547 if (sched_verbose
>= 5)
1548 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1549 INSN_UID (real_pro
));
1550 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1551 REG_DEP_TRUE
, false);
1555 add_dependence_1 (con
, pro
, dep_type
);
1558 /* A convenience wrapper to operate on an entire list. HARD should be
1559 true if DEP_NONREG should be set on newly created dependencies. */
1562 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
,
1565 mark_as_hard
= hard
;
1566 for (; list
; list
= XEXP (list
, 1))
1568 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1569 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1571 mark_as_hard
= false;
1574 /* Similar, but free *LISTP at the same time, when the context
1575 is not readonly. HARD should be true if DEP_NONREG should be set on
1576 newly created dependencies. */
1579 add_dependence_list_and_free (struct deps_desc
*deps
, rtx insn
, rtx
*listp
,
1580 int uncond
, enum reg_note dep_type
, bool hard
)
1582 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1584 /* We don't want to short-circuit dependencies involving debug
1585 insns, because they may cause actual dependencies to be
1587 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1590 free_INSN_LIST_list (listp
);
1593 /* Remove all occurrences of INSN from LIST. Return the number of
1594 occurrences removed. */
1597 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1603 if (XEXP (*listp
, 0) == insn
)
1605 remove_free_INSN_LIST_node (listp
);
1610 listp
= &XEXP (*listp
, 1);
1616 /* Same as above, but process two lists at once. */
1618 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1624 if (XEXP (*listp
, 0) == insn
)
1626 remove_free_INSN_LIST_node (listp
);
1627 remove_free_EXPR_LIST_node (exprp
);
1632 listp
= &XEXP (*listp
, 1);
1633 exprp
= &XEXP (*exprp
, 1);
1639 /* Clear all dependencies for an insn. */
1641 delete_all_dependences (rtx insn
)
1643 sd_iterator_def sd_it
;
1646 /* The below cycle can be optimized to clear the caches and back_deps
1647 in one call but that would provoke duplication of code from
1650 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1651 sd_iterator_cond (&sd_it
, &dep
);)
1652 sd_delete_dep (sd_it
);
1655 /* All insns in a scheduling group except the first should only have
1656 dependencies on the previous insn in the group. So we find the
1657 first instruction in the scheduling group by walking the dependence
1658 chains backwards. Then we add the dependencies for the group to
1659 the previous nonnote insn. */
1662 chain_to_prev_insn (rtx insn
)
1664 sd_iterator_def sd_it
;
1668 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1671 rtx pro
= DEP_PRO (dep
);
1675 i
= prev_nonnote_insn (i
);
1679 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1681 if (! sched_insns_conditions_mutex_p (i
, pro
))
1682 add_dependence (i
, pro
, DEP_TYPE (dep
));
1686 delete_all_dependences (insn
);
1688 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1689 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1690 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1691 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1694 /* Process an insn's memory dependencies. There are four kinds of
1697 (0) read dependence: read follows read
1698 (1) true dependence: read follows write
1699 (2) output dependence: write follows write
1700 (3) anti dependence: write follows read
1702 We are careful to build only dependencies which actually exist, and
1703 use transitivity to avoid building too many links. */
1705 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1706 The MEM is a memory reference contained within INSN, which we are saving
1707 so that we can do memory aliasing on it. */
1710 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1717 gcc_assert (!deps
->readonly
);
1720 insn_list
= &deps
->pending_read_insns
;
1721 mem_list
= &deps
->pending_read_mems
;
1722 if (!DEBUG_INSN_P (insn
))
1723 deps
->pending_read_list_length
++;
1727 insn_list
= &deps
->pending_write_insns
;
1728 mem_list
= &deps
->pending_write_mems
;
1729 deps
->pending_write_list_length
++;
1732 link
= alloc_INSN_LIST (insn
, *insn_list
);
1735 if (sched_deps_info
->use_cselib
)
1737 mem
= shallow_copy_rtx (mem
);
1738 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1739 GET_MODE (mem
), insn
);
1741 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1745 /* Make a dependency between every memory reference on the pending lists
1746 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1747 dependencies for a read operation, similarly with FOR_WRITE. */
1750 flush_pending_lists (struct deps_desc
*deps
, rtx insn
, int for_read
,
1755 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1756 1, REG_DEP_ANTI
, true);
1757 if (!deps
->readonly
)
1759 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1760 deps
->pending_read_list_length
= 0;
1764 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1765 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1768 add_dependence_list_and_free (deps
, insn
,
1769 &deps
->last_pending_memory_flush
, 1,
1770 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1773 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1774 REG_DEP_ANTI
, true);
1776 if (DEBUG_INSN_P (insn
))
1779 free_INSN_LIST_list (&deps
->pending_read_insns
);
1780 free_INSN_LIST_list (&deps
->pending_write_insns
);
1781 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1782 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1785 if (!deps
->readonly
)
1787 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1788 deps
->pending_write_list_length
= 0;
1790 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1791 deps
->pending_flush_length
= 1;
1793 mark_as_hard
= false;
1796 /* Instruction which dependencies we are analyzing. */
1797 static rtx cur_insn
= NULL_RTX
;
1799 /* Implement hooks for haifa scheduler. */
1802 haifa_start_insn (rtx insn
)
1804 gcc_assert (insn
&& !cur_insn
);
1810 haifa_finish_insn (void)
1816 haifa_note_reg_set (int regno
)
1818 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1822 haifa_note_reg_clobber (int regno
)
1824 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1828 haifa_note_reg_use (int regno
)
1830 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1834 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1836 if (!(ds
& SPECULATIVE
))
1839 pending_mem
= NULL_RTX
;
1842 gcc_assert (ds
& BEGIN_DATA
);
1845 dep_def _dep
, *dep
= &_dep
;
1847 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1848 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1849 DEP_NONREG (dep
) = 1;
1850 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1856 haifa_note_dep (rtx elem
, ds_t ds
)
1861 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1863 DEP_NONREG (dep
) = 1;
1864 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1868 note_reg_use (int r
)
1870 if (sched_deps_info
->note_reg_use
)
1871 sched_deps_info
->note_reg_use (r
);
1875 note_reg_set (int r
)
1877 if (sched_deps_info
->note_reg_set
)
1878 sched_deps_info
->note_reg_set (r
);
1882 note_reg_clobber (int r
)
1884 if (sched_deps_info
->note_reg_clobber
)
1885 sched_deps_info
->note_reg_clobber (r
);
1889 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1891 if (sched_deps_info
->note_mem_dep
)
1892 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1896 note_dep (rtx e
, ds_t ds
)
1898 if (sched_deps_info
->note_dep
)
1899 sched_deps_info
->note_dep (e
, ds
);
1902 /* Return corresponding to DS reg_note. */
1907 return REG_DEP_TRUE
;
1908 else if (ds
& DEP_OUTPUT
)
1909 return REG_DEP_OUTPUT
;
1910 else if (ds
& DEP_ANTI
)
1911 return REG_DEP_ANTI
;
1914 gcc_assert (ds
& DEP_CONTROL
);
1915 return REG_DEP_CONTROL
;
1921 /* Functions for computation of info needed for register pressure
1922 sensitive insn scheduling. */
1925 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1926 static struct reg_use_data
*
1927 create_insn_reg_use (int regno
, rtx insn
)
1929 struct reg_use_data
*use
;
1931 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1934 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1935 INSN_REG_USE_LIST (insn
) = use
;
1939 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1940 static struct reg_set_data
*
1941 create_insn_reg_set (int regno
, rtx insn
)
1943 struct reg_set_data
*set
;
1945 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1948 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1949 INSN_REG_SET_LIST (insn
) = set
;
1953 /* Set up insn register uses for INSN and dependency context DEPS. */
1955 setup_insn_reg_uses (struct deps_desc
*deps
, rtx insn
)
1958 reg_set_iterator rsi
;
1960 struct reg_use_data
*use
, *use2
, *next
;
1961 struct deps_reg
*reg_last
;
1963 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1965 if (i
< FIRST_PSEUDO_REGISTER
1966 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1969 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1970 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1971 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1972 /* Ignore use which is not dying. */
1975 use
= create_insn_reg_use (i
, insn
);
1976 use
->next_regno_use
= use
;
1977 reg_last
= &deps
->reg_last
[i
];
1979 /* Create the cycle list of uses. */
1980 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1982 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1983 next
= use
->next_regno_use
;
1984 use
->next_regno_use
= use2
;
1985 use2
->next_regno_use
= next
;
1990 /* Register pressure info for the currently processed insn. */
1991 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1993 /* Return TRUE if INSN has the use structure for REGNO. */
1995 insn_use_p (rtx insn
, int regno
)
1997 struct reg_use_data
*use
;
1999 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2000 if (use
->regno
== regno
)
2005 /* Update the register pressure info after birth of pseudo register REGNO
2006 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2007 the register is in clobber or unused after the insn. */
2009 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2014 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2015 cl
= sched_regno_pressure_class
[regno
];
2018 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2021 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2022 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2026 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2027 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2031 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2032 reg_pressure_info
[cl
].set_increase
= new_incr
;
2033 if (! insn_use_p (insn
, regno
))
2034 reg_pressure_info
[cl
].change
+= incr
;
2035 create_insn_reg_set (regno
, insn
);
2037 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2041 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2042 hard registers involved in the birth. */
2044 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2045 bool clobber_p
, bool unused_p
)
2048 int new_incr
, last
= regno
+ nregs
;
2050 while (regno
< last
)
2052 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2053 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2055 cl
= sched_regno_pressure_class
[regno
];
2060 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2061 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2065 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2066 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2070 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2071 reg_pressure_info
[cl
].set_increase
= new_incr
;
2072 if (! insn_use_p (insn
, regno
))
2073 reg_pressure_info
[cl
].change
+= 1;
2074 create_insn_reg_set (regno
, insn
);
2076 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2083 /* Update the register pressure info after birth of pseudo or hard
2084 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2085 correspondingly that the register is in clobber or unused after the
2088 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2092 if (GET_CODE (reg
) == SUBREG
)
2093 reg
= SUBREG_REG (reg
);
2098 regno
= REGNO (reg
);
2099 if (regno
< FIRST_PSEUDO_REGISTER
)
2100 mark_insn_hard_regno_birth (insn
, regno
,
2101 hard_regno_nregs
[regno
][GET_MODE (reg
)],
2102 clobber_p
, unused_p
);
2104 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2107 /* Update the register pressure info after death of pseudo register
2110 mark_pseudo_death (int regno
)
2115 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2116 cl
= sched_regno_pressure_class
[regno
];
2119 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2120 reg_pressure_info
[cl
].change
-= incr
;
2124 /* Like mark_pseudo_death except that NREGS saying how many hard
2125 registers involved in the death. */
2127 mark_hard_regno_death (int regno
, int nregs
)
2130 int last
= regno
+ nregs
;
2132 while (regno
< last
)
2134 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2135 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2137 cl
= sched_regno_pressure_class
[regno
];
2139 reg_pressure_info
[cl
].change
-= 1;
2145 /* Update the register pressure info after death of pseudo or hard
2148 mark_reg_death (rtx reg
)
2152 if (GET_CODE (reg
) == SUBREG
)
2153 reg
= SUBREG_REG (reg
);
2158 regno
= REGNO (reg
);
2159 if (regno
< FIRST_PSEUDO_REGISTER
)
2160 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
2162 mark_pseudo_death (regno
);
2165 /* Process SETTER of REG. DATA is an insn containing the setter. */
2167 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2169 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2172 ((rtx
) data
, reg
, false,
2173 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2176 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2178 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2180 if (GET_CODE (setter
) == CLOBBER
)
2181 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2184 /* Set up reg pressure info related to INSN. */
2186 init_insn_reg_pressure_info (rtx insn
)
2190 static struct reg_pressure_data
*pressure_info
;
2193 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2195 if (! INSN_P (insn
))
2198 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2200 cl
= ira_pressure_classes
[i
];
2201 reg_pressure_info
[cl
].clobber_increase
= 0;
2202 reg_pressure_info
[cl
].set_increase
= 0;
2203 reg_pressure_info
[cl
].unused_set_increase
= 0;
2204 reg_pressure_info
[cl
].change
= 0;
2207 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2209 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2212 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2213 if (REG_NOTE_KIND (link
) == REG_INC
)
2214 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2217 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2218 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2219 mark_reg_death (XEXP (link
, 0));
2221 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2223 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2224 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2225 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2227 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2229 cl
= ira_pressure_classes
[i
];
2230 pressure_info
[i
].clobber_increase
2231 = reg_pressure_info
[cl
].clobber_increase
;
2232 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2233 pressure_info
[i
].unused_set_increase
2234 = reg_pressure_info
[cl
].unused_set_increase
;
2235 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2242 /* Internal variable for sched_analyze_[12] () functions.
2243 If it is nonzero, this means that sched_analyze_[12] looks
2244 at the most toplevel SET. */
2245 static bool can_start_lhs_rhs_p
;
2247 /* Extend reg info for the deps context DEPS given that
2248 we have just generated a register numbered REGNO. */
2250 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2252 int max_regno
= regno
+ 1;
2254 gcc_assert (!reload_completed
);
2256 /* In a readonly context, it would not hurt to extend info,
2257 but it should not be needed. */
2258 if (reload_completed
&& deps
->readonly
)
2260 deps
->max_reg
= max_regno
;
2264 if (max_regno
> deps
->max_reg
)
2266 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2268 memset (&deps
->reg_last
[deps
->max_reg
],
2269 0, (max_regno
- deps
->max_reg
)
2270 * sizeof (struct deps_reg
));
2271 deps
->max_reg
= max_regno
;
2275 /* Extends REG_INFO_P if needed. */
2277 maybe_extend_reg_info_p (void)
2279 /* Extend REG_INFO_P, if needed. */
2280 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2282 size_t new_reg_info_p_size
= max_regno
+ 128;
2284 gcc_assert (!reload_completed
&& sel_sched_p ());
2286 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2287 new_reg_info_p_size
,
2289 sizeof (*reg_info_p
));
2290 reg_info_p_size
= new_reg_info_p_size
;
2294 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2295 The type of the reference is specified by REF and can be SET,
2296 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2299 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2300 enum rtx_code ref
, rtx insn
)
2302 /* We could emit new pseudos in renaming. Extend the reg structures. */
2303 if (!reload_completed
&& sel_sched_p ()
2304 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2305 extend_deps_reg_info (deps
, regno
);
2307 maybe_extend_reg_info_p ();
2309 /* A hard reg in a wide mode may really be multiple registers.
2310 If so, mark all of them just like the first. */
2311 if (regno
< FIRST_PSEUDO_REGISTER
)
2313 int i
= hard_regno_nregs
[regno
][mode
];
2317 note_reg_set (regno
+ i
);
2319 else if (ref
== USE
)
2322 note_reg_use (regno
+ i
);
2327 note_reg_clobber (regno
+ i
);
2331 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2332 it does not reload. Ignore these as they have served their
2334 else if (regno
>= deps
->max_reg
)
2336 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2337 gcc_assert (code
== USE
|| code
== CLOBBER
);
2343 note_reg_set (regno
);
2344 else if (ref
== USE
)
2345 note_reg_use (regno
);
2347 note_reg_clobber (regno
);
2349 /* Pseudos that are REG_EQUIV to something may be replaced
2350 by that during reloading. We need only add dependencies for
2351 the address in the REG_EQUIV note. */
2352 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2354 rtx t
= get_reg_known_value (regno
);
2356 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2359 /* Don't let it cross a call after scheduling if it doesn't
2360 already cross one. */
2361 if (REG_N_CALLS_CROSSED (regno
) == 0)
2363 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2364 deps
->sched_before_next_call
2365 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2367 add_dependence_list (insn
, deps
->last_function_call
, 1,
2368 REG_DEP_ANTI
, false);
2373 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2374 rtx, X, creating all dependencies generated by the write to the
2375 destination of X, and reads of everything mentioned. */
2378 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2380 rtx dest
= XEXP (x
, 0);
2381 enum rtx_code code
= GET_CODE (x
);
2382 bool cslr_p
= can_start_lhs_rhs_p
;
2384 can_start_lhs_rhs_p
= false;
2390 if (cslr_p
&& sched_deps_info
->start_lhs
)
2391 sched_deps_info
->start_lhs (dest
);
2393 if (GET_CODE (dest
) == PARALLEL
)
2397 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2398 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2399 sched_analyze_1 (deps
,
2400 gen_rtx_CLOBBER (VOIDmode
,
2401 XEXP (XVECEXP (dest
, 0, i
), 0)),
2404 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2405 sched_deps_info
->finish_lhs ();
2409 can_start_lhs_rhs_p
= cslr_p
;
2411 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2413 can_start_lhs_rhs_p
= false;
2419 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2420 || GET_CODE (dest
) == ZERO_EXTRACT
)
2422 if (GET_CODE (dest
) == STRICT_LOW_PART
2423 || GET_CODE (dest
) == ZERO_EXTRACT
2424 || df_read_modify_subreg_p (dest
))
2426 /* These both read and modify the result. We must handle
2427 them as writes to get proper dependencies for following
2428 instructions. We must handle them as reads to get proper
2429 dependencies from this to previous instructions.
2430 Thus we need to call sched_analyze_2. */
2432 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2434 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2436 /* The second and third arguments are values read by this insn. */
2437 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2438 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2440 dest
= XEXP (dest
, 0);
2445 int regno
= REGNO (dest
);
2446 enum machine_mode mode
= GET_MODE (dest
);
2448 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2451 /* Treat all writes to a stack register as modifying the TOS. */
2452 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2454 /* Avoid analyzing the same register twice. */
2455 if (regno
!= FIRST_STACK_REG
)
2456 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2458 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2463 else if (MEM_P (dest
))
2465 /* Writing memory. */
2468 if (sched_deps_info
->use_cselib
)
2470 enum machine_mode address_mode
= get_address_mode (dest
);
2472 t
= shallow_copy_rtx (dest
);
2473 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2474 GET_MODE (t
), insn
);
2476 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2481 /* Pending lists can't get larger with a readonly context. */
2483 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2484 > MAX_PENDING_LIST_LENGTH
))
2486 /* Flush all pending reads and writes to prevent the pending lists
2487 from getting any larger. Insn scheduling runs too slowly when
2488 these lists get long. When compiling GCC with itself,
2489 this flush occurs 8 times for sparc, and 10 times for m88k using
2490 the default value of 32. */
2491 flush_pending_lists (deps
, insn
, false, true);
2495 rtx pending
, pending_mem
;
2497 pending
= deps
->pending_read_insns
;
2498 pending_mem
= deps
->pending_read_mems
;
2501 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2502 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2503 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2506 pending
= XEXP (pending
, 1);
2507 pending_mem
= XEXP (pending_mem
, 1);
2510 pending
= deps
->pending_write_insns
;
2511 pending_mem
= deps
->pending_write_mems
;
2514 if (output_dependence (XEXP (pending_mem
, 0), t
)
2515 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2516 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2519 pending
= XEXP (pending
, 1);
2520 pending_mem
= XEXP (pending_mem
, 1);
2523 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2524 REG_DEP_ANTI
, true);
2525 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2526 REG_DEP_CONTROL
, true);
2528 if (!deps
->readonly
)
2529 add_insn_mem_dependence (deps
, false, insn
, dest
);
2531 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2534 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2535 sched_deps_info
->finish_lhs ();
2537 /* Analyze reads. */
2538 if (GET_CODE (x
) == SET
)
2540 can_start_lhs_rhs_p
= cslr_p
;
2542 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2544 can_start_lhs_rhs_p
= false;
2548 /* Analyze the uses of memory and registers in rtx X in INSN. */
2550 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2556 bool cslr_p
= can_start_lhs_rhs_p
;
2558 can_start_lhs_rhs_p
= false;
2564 if (cslr_p
&& sched_deps_info
->start_rhs
)
2565 sched_deps_info
->start_rhs (x
);
2567 code
= GET_CODE (x
);
2575 /* Ignore constants. */
2576 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2577 sched_deps_info
->finish_rhs ();
2583 /* User of CC0 depends on immediately preceding insn. */
2584 SCHED_GROUP_P (insn
) = 1;
2585 /* Don't move CC0 setter to another block (it can set up the
2586 same flag for previous CC0 users which is safe). */
2587 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2589 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2590 sched_deps_info
->finish_rhs ();
2597 int regno
= REGNO (x
);
2598 enum machine_mode mode
= GET_MODE (x
);
2600 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2603 /* Treat all reads of a stack register as modifying the TOS. */
2604 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2606 /* Avoid analyzing the same register twice. */
2607 if (regno
!= FIRST_STACK_REG
)
2608 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2609 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2613 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2614 sched_deps_info
->finish_rhs ();
2621 /* Reading memory. */
2623 rtx pending
, pending_mem
;
2626 if (sched_deps_info
->use_cselib
)
2628 enum machine_mode address_mode
= get_address_mode (t
);
2630 t
= shallow_copy_rtx (t
);
2631 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2632 GET_MODE (t
), insn
);
2634 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2638 if (!DEBUG_INSN_P (insn
))
2641 pending
= deps
->pending_read_insns
;
2642 pending_mem
= deps
->pending_read_mems
;
2645 if (read_dependence (XEXP (pending_mem
, 0), t
)
2646 && ! sched_insns_conditions_mutex_p (insn
,
2648 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2651 pending
= XEXP (pending
, 1);
2652 pending_mem
= XEXP (pending_mem
, 1);
2655 pending
= deps
->pending_write_insns
;
2656 pending_mem
= deps
->pending_write_mems
;
2659 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
, t
)
2660 && ! sched_insns_conditions_mutex_p (insn
,
2662 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2663 sched_deps_info
->generate_spec_deps
2664 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2666 pending
= XEXP (pending
, 1);
2667 pending_mem
= XEXP (pending_mem
, 1);
2670 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2671 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2673 for (u
= deps
->pending_jump_insns
; u
; u
= XEXP (u
, 1))
2674 if (deps_may_trap_p (x
))
2676 if ((sched_deps_info
->generate_spec_deps
)
2677 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2679 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2682 note_dep (XEXP (u
, 0), ds
);
2685 add_dependence (insn
, XEXP (u
, 0), REG_DEP_CONTROL
);
2689 /* Always add these dependencies to pending_reads, since
2690 this insn may be followed by a write. */
2691 if (!deps
->readonly
)
2692 add_insn_mem_dependence (deps
, true, insn
, x
);
2694 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2696 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2697 sched_deps_info
->finish_rhs ();
2702 /* Force pending stores to memory in case a trap handler needs them. */
2704 flush_pending_lists (deps
, insn
, true, false);
2708 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2709 reg_pending_barrier
= TRUE_BARRIER
;
2710 /* Prefetch insn contains addresses only. So if the prefetch
2711 address has no registers, there will be no dependencies on
2712 the prefetch insn. This is wrong with result code
2713 correctness point of view as such prefetch can be moved below
2714 a jump insn which usually generates MOVE_BARRIER preventing
2715 to move insns containing registers or memories through the
2716 barrier. It is also wrong with generated code performance
2717 point of view as prefetch withouth dependecies will have a
2718 tendency to be issued later instead of earlier. It is hard
2719 to generate accurate dependencies for prefetch insns as
2720 prefetch has only the start address but it is better to have
2721 something than nothing. */
2722 if (!deps
->readonly
)
2724 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2725 if (sched_deps_info
->use_cselib
)
2726 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2727 add_insn_mem_dependence (deps
, true, insn
, x
);
2731 case UNSPEC_VOLATILE
:
2732 flush_pending_lists (deps
, insn
, true, true);
2738 /* Traditional and volatile asm instructions must be considered to use
2739 and clobber all hard registers, all pseudo-registers and all of
2740 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2742 Consider for instance a volatile asm that changes the fpu rounding
2743 mode. An insn should not be moved across this even if it only uses
2744 pseudo-regs because it might give an incorrectly rounded result. */
2745 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2746 reg_pending_barrier
= TRUE_BARRIER
;
2748 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2749 We can not just fall through here since then we would be confused
2750 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2751 traditional asms unlike their normal usage. */
2753 if (code
== ASM_OPERANDS
)
2755 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2756 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2758 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2759 sched_deps_info
->finish_rhs ();
2770 /* These both read and modify the result. We must handle them as writes
2771 to get proper dependencies for following instructions. We must handle
2772 them as reads to get proper dependencies from this to previous
2773 instructions. Thus we need to pass them to both sched_analyze_1
2774 and sched_analyze_2. We must call sched_analyze_2 first in order
2775 to get the proper antecedent for the read. */
2776 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2777 sched_analyze_1 (deps
, x
, insn
);
2779 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2780 sched_deps_info
->finish_rhs ();
2786 /* op0 = op0 + op1 */
2787 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2788 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2789 sched_analyze_1 (deps
, x
, insn
);
2791 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2792 sched_deps_info
->finish_rhs ();
2800 /* Other cases: walk the insn. */
2801 fmt
= GET_RTX_FORMAT (code
);
2802 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2805 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2806 else if (fmt
[i
] == 'E')
2807 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2808 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2811 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2812 sched_deps_info
->finish_rhs ();
2815 /* Analyze an INSN with pattern X to find all dependencies. */
2817 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx insn
)
2819 RTX_CODE code
= GET_CODE (x
);
2822 reg_set_iterator rsi
;
2824 if (! reload_completed
)
2828 extract_insn (insn
);
2829 preprocess_constraints ();
2830 ira_implicitly_set_insn_hard_regs (&temp
);
2831 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2832 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2835 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2839 /* Avoid moving trapping instructions across function calls that might
2840 not always return. */
2841 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2842 1, REG_DEP_ANTI
, true);
2844 /* We must avoid creating a situation in which two successors of the
2845 current block have different unwind info after scheduling. If at any
2846 point the two paths re-join this leads to incorrect unwind info. */
2847 /* ??? There are certain situations involving a forced frame pointer in
2848 which, with extra effort, we could fix up the unwind info at a later
2849 CFG join. However, it seems better to notice these cases earlier
2850 during prologue generation and avoid marking the frame pointer setup
2851 as frame-related at all. */
2852 if (RTX_FRAME_RELATED_P (insn
))
2854 /* Make sure prologue insn is scheduled before next jump. */
2855 deps
->sched_before_next_jump
2856 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2858 /* Make sure epilogue insn is scheduled after preceding jumps. */
2859 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2863 if (code
== COND_EXEC
)
2865 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2867 /* ??? Should be recording conditions so we reduce the number of
2868 false dependencies. */
2869 x
= COND_EXEC_CODE (x
);
2870 code
= GET_CODE (x
);
2872 if (code
== SET
|| code
== CLOBBER
)
2874 sched_analyze_1 (deps
, x
, insn
);
2876 /* Bare clobber insns are used for letting life analysis, reg-stack
2877 and others know that a value is dead. Depend on the last call
2878 instruction so that reg-stack won't get confused. */
2879 if (code
== CLOBBER
)
2880 add_dependence_list (insn
, deps
->last_function_call
, 1,
2881 REG_DEP_OUTPUT
, true);
2883 else if (code
== PARALLEL
)
2885 for (i
= XVECLEN (x
, 0); i
--;)
2887 rtx sub
= XVECEXP (x
, 0, i
);
2888 code
= GET_CODE (sub
);
2890 if (code
== COND_EXEC
)
2892 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2893 sub
= COND_EXEC_CODE (sub
);
2894 code
= GET_CODE (sub
);
2896 if (code
== SET
|| code
== CLOBBER
)
2897 sched_analyze_1 (deps
, sub
, insn
);
2899 sched_analyze_2 (deps
, sub
, insn
);
2903 sched_analyze_2 (deps
, x
, insn
);
2905 /* Mark registers CLOBBERED or used by called function. */
2908 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2910 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2911 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2912 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2913 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2915 /* Don't schedule anything after a tail call, tail call needs
2916 to use at least all call-saved registers. */
2917 if (SIBLING_CALL_P (insn
))
2918 reg_pending_barrier
= TRUE_BARRIER
;
2919 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2920 reg_pending_barrier
= MOVE_BARRIER
;
2926 next
= next_nonnote_nondebug_insn (insn
);
2927 if (next
&& BARRIER_P (next
))
2928 reg_pending_barrier
= MOVE_BARRIER
;
2931 rtx pending
, pending_mem
;
2933 if (sched_deps_info
->compute_jump_reg_dependencies
)
2935 (*sched_deps_info
->compute_jump_reg_dependencies
)
2936 (insn
, reg_pending_control_uses
);
2938 /* Make latency of jump equal to 0 by using anti-dependence. */
2939 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
2941 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2942 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
2944 add_dependence_list (insn
, reg_last
->implicit_sets
,
2945 0, REG_DEP_ANTI
, false);
2946 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2947 REG_DEP_ANTI
, false);
2951 /* All memory writes and volatile reads must happen before the
2952 jump. Non-volatile reads must happen before the jump iff
2953 the result is needed by the above register used mask. */
2955 pending
= deps
->pending_write_insns
;
2956 pending_mem
= deps
->pending_write_mems
;
2959 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2960 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2961 pending
= XEXP (pending
, 1);
2962 pending_mem
= XEXP (pending_mem
, 1);
2965 pending
= deps
->pending_read_insns
;
2966 pending_mem
= deps
->pending_read_mems
;
2969 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2970 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2971 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2972 pending
= XEXP (pending
, 1);
2973 pending_mem
= XEXP (pending_mem
, 1);
2976 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2977 REG_DEP_ANTI
, true);
2978 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2979 REG_DEP_ANTI
, true);
2983 /* If this instruction can throw an exception, then moving it changes
2984 where block boundaries fall. This is mighty confusing elsewhere.
2985 Therefore, prevent such an instruction from being moved. Same for
2986 non-jump instructions that define block boundaries.
2987 ??? Unclear whether this is still necessary in EBB mode. If not,
2988 add_branch_dependences should be adjusted for RGN mode instead. */
2989 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2990 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2991 reg_pending_barrier
= MOVE_BARRIER
;
2993 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2995 setup_insn_reg_uses (deps
, insn
);
2996 init_insn_reg_pressure_info (insn
);
2999 /* Add register dependencies for insn. */
3000 if (DEBUG_INSN_P (insn
))
3002 rtx prev
= deps
->last_debug_insn
;
3005 if (!deps
->readonly
)
3006 deps
->last_debug_insn
= insn
;
3009 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3011 add_dependence_list (insn
, deps
->last_function_call
, 1,
3012 REG_DEP_ANTI
, false);
3014 if (!sel_sched_p ())
3015 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3016 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3018 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3020 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3021 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3022 /* There's no point in making REG_DEP_CONTROL dependencies for
3024 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3027 if (!deps
->readonly
)
3028 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3030 CLEAR_REG_SET (reg_pending_uses
);
3032 /* Quite often, a debug insn will refer to stuff in the
3033 previous instruction, but the reason we want this
3034 dependency here is to make sure the scheduler doesn't
3035 gratuitously move a debug insn ahead. This could dirty
3036 DF flags and cause additional analysis that wouldn't have
3037 occurred in compilation without debug insns, and such
3038 additional analysis can modify the generated code. */
3039 prev
= PREV_INSN (insn
);
3041 if (prev
&& NONDEBUG_INSN_P (prev
))
3042 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3046 regset_head set_or_clobbered
;
3048 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3050 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3051 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3052 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3054 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3057 if (!deps
->readonly
)
3059 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3060 reg_last
->uses_length
++;
3064 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3065 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3067 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3068 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3069 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3070 REG_DEP_ANTI
, false);
3071 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3074 if (!deps
->readonly
)
3076 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3077 reg_last
->uses_length
++;
3081 if (targetm
.sched
.exposed_pipeline
)
3083 INIT_REG_SET (&set_or_clobbered
);
3084 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3086 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3088 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3090 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3092 rtx other
= XEXP (list
, 0);
3093 if (INSN_CACHED_COND (other
) != const_true_rtx
3094 && refers_to_regno_p (i
, i
+ 1, INSN_CACHED_COND (other
), NULL
))
3095 INSN_CACHED_COND (other
) = const_true_rtx
;
3100 /* If the current insn is conditional, we can't free any
3102 if (sched_has_condition_p (insn
))
3104 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3106 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3107 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3109 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3110 REG_DEP_ANTI
, false);
3111 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3113 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3114 REG_DEP_CONTROL
, false);
3116 if (!deps
->readonly
)
3119 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3120 reg_last
->clobbers_length
++;
3123 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3125 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3126 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3128 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3129 REG_DEP_ANTI
, false);
3130 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3132 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3134 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3135 REG_DEP_CONTROL
, false);
3137 if (!deps
->readonly
)
3138 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3143 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3145 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3146 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
3147 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
3149 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3150 REG_DEP_OUTPUT
, false);
3151 add_dependence_list_and_free (deps
, insn
,
3152 ®_last
->implicit_sets
, 0,
3153 REG_DEP_ANTI
, false);
3154 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3155 REG_DEP_ANTI
, false);
3156 add_dependence_list_and_free (deps
, insn
,
3157 ®_last
->control_uses
, 0,
3158 REG_DEP_ANTI
, false);
3159 add_dependence_list_and_free (deps
, insn
,
3160 ®_last
->clobbers
, 0,
3161 REG_DEP_OUTPUT
, false);
3163 if (!deps
->readonly
)
3165 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3166 reg_last
->clobbers_length
= 0;
3167 reg_last
->uses_length
= 0;
3172 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3174 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3175 REG_DEP_ANTI
, false);
3176 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3178 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3179 REG_DEP_CONTROL
, false);
3182 if (!deps
->readonly
)
3184 reg_last
->clobbers_length
++;
3186 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3189 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3191 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3193 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3194 REG_DEP_OUTPUT
, false);
3195 add_dependence_list_and_free (deps
, insn
,
3196 ®_last
->implicit_sets
,
3197 0, REG_DEP_ANTI
, false);
3198 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3199 REG_DEP_OUTPUT
, false);
3200 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3201 REG_DEP_ANTI
, false);
3202 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3203 REG_DEP_CONTROL
, false);
3205 if (!deps
->readonly
)
3207 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3208 reg_last
->uses_length
= 0;
3209 reg_last
->clobbers_length
= 0;
3213 if (!deps
->readonly
)
3215 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3217 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3218 reg_last
->control_uses
3219 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3224 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3225 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3227 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3228 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3229 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3230 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3231 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3234 if (!deps
->readonly
)
3235 reg_last
->implicit_sets
3236 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3239 if (!deps
->readonly
)
3241 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3242 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3243 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3244 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3245 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3246 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3247 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3249 /* Set up the pending barrier found. */
3250 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3253 CLEAR_REG_SET (reg_pending_uses
);
3254 CLEAR_REG_SET (reg_pending_clobbers
);
3255 CLEAR_REG_SET (reg_pending_sets
);
3256 CLEAR_REG_SET (reg_pending_control_uses
);
3257 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3258 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3260 /* Add dependencies if a scheduling barrier was found. */
3261 if (reg_pending_barrier
)
3263 /* In the case of barrier the most added dependencies are not
3264 real, so we use anti-dependence here. */
3265 if (sched_has_condition_p (insn
))
3267 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3269 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3270 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3272 add_dependence_list (insn
, reg_last
->sets
, 0,
3273 reg_pending_barrier
== TRUE_BARRIER
3274 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3275 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3276 REG_DEP_ANTI
, true);
3277 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3278 reg_pending_barrier
== TRUE_BARRIER
3279 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3284 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3286 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3287 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3288 REG_DEP_ANTI
, true);
3289 add_dependence_list_and_free (deps
, insn
,
3290 ®_last
->control_uses
, 0,
3291 REG_DEP_CONTROL
, true);
3292 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3293 reg_pending_barrier
== TRUE_BARRIER
3294 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3296 add_dependence_list_and_free (deps
, insn
,
3297 ®_last
->implicit_sets
, 0,
3298 REG_DEP_ANTI
, true);
3299 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3300 reg_pending_barrier
== TRUE_BARRIER
3301 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3304 if (!deps
->readonly
)
3306 reg_last
->uses_length
= 0;
3307 reg_last
->clobbers_length
= 0;
3312 if (!deps
->readonly
)
3313 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3315 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3316 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3317 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3320 /* Flush pending lists on jumps, but not on speculative checks. */
3321 if (JUMP_P (insn
) && !(sel_sched_p ()
3322 && sel_insn_is_speculation_check (insn
)))
3323 flush_pending_lists (deps
, insn
, true, true);
3325 reg_pending_barrier
= NOT_A_BARRIER
;
3328 /* If a post-call group is still open, see if it should remain so.
3329 This insn must be a simple move of a hard reg to a pseudo or
3332 We must avoid moving these insns for correctness on targets
3333 with small register classes, and for special registers like
3334 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3335 hard regs for all targets. */
3337 if (deps
->in_post_call_group_p
)
3339 rtx tmp
, set
= single_set (insn
);
3340 int src_regno
, dest_regno
;
3344 if (DEBUG_INSN_P (insn
))
3345 /* We don't want to mark debug insns as part of the same
3346 sched group. We know they really aren't, but if we use
3347 debug insns to tell that a call group is over, we'll
3348 get different code if debug insns are not there and
3349 instructions that follow seem like they should be part
3352 Also, if we did, chain_to_prev_insn would move the
3353 deps of the debug insn to the call insn, modifying
3354 non-debug post-dependency counts of the debug insn
3355 dependencies and otherwise messing with the scheduling
3358 Instead, let such debug insns be scheduled freely, but
3359 keep the call group open in case there are insns that
3360 should be part of it afterwards. Since we grant debug
3361 insns higher priority than even sched group insns, it
3362 will all turn out all right. */
3363 goto debug_dont_end_call_group
;
3365 goto end_call_group
;
3368 tmp
= SET_DEST (set
);
3369 if (GET_CODE (tmp
) == SUBREG
)
3370 tmp
= SUBREG_REG (tmp
);
3372 dest_regno
= REGNO (tmp
);
3374 goto end_call_group
;
3376 tmp
= SET_SRC (set
);
3377 if (GET_CODE (tmp
) == SUBREG
)
3378 tmp
= SUBREG_REG (tmp
);
3379 if ((GET_CODE (tmp
) == PLUS
3380 || GET_CODE (tmp
) == MINUS
)
3381 && REG_P (XEXP (tmp
, 0))
3382 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3383 && dest_regno
== STACK_POINTER_REGNUM
)
3384 src_regno
= STACK_POINTER_REGNUM
;
3385 else if (REG_P (tmp
))
3386 src_regno
= REGNO (tmp
);
3388 goto end_call_group
;
3390 if (src_regno
< FIRST_PSEUDO_REGISTER
3391 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3394 && deps
->in_post_call_group_p
== post_call_initial
)
3395 deps
->in_post_call_group_p
= post_call
;
3397 if (!sel_sched_p () || sched_emulate_haifa_p
)
3399 SCHED_GROUP_P (insn
) = 1;
3400 CANT_MOVE (insn
) = 1;
3406 if (!deps
->readonly
)
3407 deps
->in_post_call_group_p
= not_post_call
;
3411 debug_dont_end_call_group
:
3412 if ((current_sched_info
->flags
& DO_SPECULATION
)
3413 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3414 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3418 sel_mark_hard_insn (insn
);
3421 sd_iterator_def sd_it
;
3424 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3425 sd_iterator_cond (&sd_it
, &dep
);)
3426 change_spec_dep_to_hard (sd_it
);
3431 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3432 longjmp, loop forever, ...). */
3433 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3434 test for ECF_NORETURN? */
3436 call_may_noreturn_p (rtx insn
)
3440 /* const or pure calls that aren't looping will always return. */
3441 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3442 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3445 call
= get_call_rtx_from (insn
);
3446 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3448 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3449 if (SYMBOL_REF_DECL (symbol
)
3450 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3452 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3454 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3457 case BUILT_IN_BCOPY
:
3458 case BUILT_IN_BZERO
:
3459 case BUILT_IN_INDEX
:
3460 case BUILT_IN_MEMCHR
:
3461 case BUILT_IN_MEMCMP
:
3462 case BUILT_IN_MEMCPY
:
3463 case BUILT_IN_MEMMOVE
:
3464 case BUILT_IN_MEMPCPY
:
3465 case BUILT_IN_MEMSET
:
3466 case BUILT_IN_RINDEX
:
3467 case BUILT_IN_STPCPY
:
3468 case BUILT_IN_STPNCPY
:
3469 case BUILT_IN_STRCAT
:
3470 case BUILT_IN_STRCHR
:
3471 case BUILT_IN_STRCMP
:
3472 case BUILT_IN_STRCPY
:
3473 case BUILT_IN_STRCSPN
:
3474 case BUILT_IN_STRLEN
:
3475 case BUILT_IN_STRNCAT
:
3476 case BUILT_IN_STRNCMP
:
3477 case BUILT_IN_STRNCPY
:
3478 case BUILT_IN_STRPBRK
:
3479 case BUILT_IN_STRRCHR
:
3480 case BUILT_IN_STRSPN
:
3481 case BUILT_IN_STRSTR
:
3482 /* Assume certain string/memory builtins always return. */
3490 /* For all other calls assume that they might not always return. */
3494 /* Return true if INSN should be made dependent on the previous instruction
3495 group, and if all INSN's dependencies should be moved to the first
3496 instruction of that group. */
3499 chain_to_prev_insn_p (rtx insn
)
3503 /* INSN forms a group with the previous instruction. */
3504 if (SCHED_GROUP_P (insn
))
3507 /* If the previous instruction clobbers a register R and this one sets
3508 part of R, the clobber was added specifically to help us track the
3509 liveness of R. There's no point scheduling the clobber and leaving
3510 INSN behind, especially if we move the clobber to another block. */
3511 prev
= prev_nonnote_nondebug_insn (insn
);
3514 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3515 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3517 x
= XEXP (PATTERN (prev
), 0);
3518 if (set_of (x
, insn
))
3525 /* Analyze INSN with DEPS as a context. */
3527 deps_analyze_insn (struct deps_desc
*deps
, rtx insn
)
3529 if (sched_deps_info
->start_insn
)
3530 sched_deps_info
->start_insn (insn
);
3532 /* Record the condition for this insn. */
3533 if (NONDEBUG_INSN_P (insn
))
3536 sched_get_condition_with_rev (insn
, NULL
);
3537 t
= INSN_CACHED_COND (insn
);
3538 INSN_COND_DEPS (insn
) = NULL_RTX
;
3539 if (reload_completed
3540 && (current_sched_info
->flags
& DO_PREDICATION
)
3542 && REG_P (XEXP (t
, 0))
3543 && CONSTANT_P (XEXP (t
, 1)))
3549 nregs
= hard_regno_nregs
[regno
][GET_MODE (t
)];
3553 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3554 t
= concat_INSN_LIST (reg_last
->sets
, t
);
3555 t
= concat_INSN_LIST (reg_last
->clobbers
, t
);
3556 t
= concat_INSN_LIST (reg_last
->implicit_sets
, t
);
3558 INSN_COND_DEPS (insn
) = t
;
3564 /* Make each JUMP_INSN (but not a speculative check)
3565 a scheduling barrier for memory references. */
3568 && sel_insn_is_speculation_check (insn
)))
3570 /* Keep the list a reasonable size. */
3571 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3572 flush_pending_lists (deps
, insn
, true, true);
3574 deps
->pending_jump_insns
3575 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3578 /* For each insn which shouldn't cross a jump, add a dependence. */
3579 add_dependence_list_and_free (deps
, insn
,
3580 &deps
->sched_before_next_jump
, 1,
3581 REG_DEP_ANTI
, true);
3583 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3585 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3587 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3589 else if (CALL_P (insn
))
3593 CANT_MOVE (insn
) = 1;
3595 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3597 /* This is setjmp. Assume that all registers, not just
3598 hard registers, may be clobbered by this call. */
3599 reg_pending_barrier
= MOVE_BARRIER
;
3603 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3604 /* A call may read and modify global register variables. */
3607 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3608 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3610 /* Other call-clobbered hard regs may be clobbered.
3611 Since we only have a choice between 'might be clobbered'
3612 and 'definitely not clobbered', we must include all
3613 partly call-clobbered registers here. */
3614 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3615 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3616 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3617 /* We don't know what set of fixed registers might be used
3618 by the function, but it is certain that the stack pointer
3619 is among them, but be conservative. */
3620 else if (fixed_regs
[i
])
3621 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3622 /* The frame pointer is normally not used by the function
3623 itself, but by the debugger. */
3624 /* ??? MIPS o32 is an exception. It uses the frame pointer
3625 in the macro expansion of jal but does not represent this
3626 fact in the call_insn rtl. */
3627 else if (i
== FRAME_POINTER_REGNUM
3628 || (i
== HARD_FRAME_POINTER_REGNUM
3629 && (! reload_completed
|| frame_pointer_needed
)))
3630 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3633 /* For each insn which shouldn't cross a call, add a dependence
3634 between that insn and this call insn. */
3635 add_dependence_list_and_free (deps
, insn
,
3636 &deps
->sched_before_next_call
, 1,
3637 REG_DEP_ANTI
, true);
3639 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3641 /* If CALL would be in a sched group, then this will violate
3642 convention that sched group insns have dependencies only on the
3643 previous instruction.
3645 Of course one can say: "Hey! What about head of the sched group?"
3646 And I will answer: "Basic principles (one dep per insn) are always
3648 gcc_assert (!SCHED_GROUP_P (insn
));
3650 /* In the absence of interprocedural alias analysis, we must flush
3651 all pending reads and writes, and start new dependencies starting
3652 from here. But only flush writes for constant calls (which may
3653 be passed a pointer to something we haven't written yet). */
3654 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3656 if (!deps
->readonly
)
3658 /* Remember the last function call for limiting lifetimes. */
3659 free_INSN_LIST_list (&deps
->last_function_call
);
3660 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3662 if (call_may_noreturn_p (insn
))
3664 /* Remember the last function call that might not always return
3665 normally for limiting moves of trapping insns. */
3666 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3667 deps
->last_function_call_may_noreturn
3668 = alloc_INSN_LIST (insn
, NULL_RTX
);
3671 /* Before reload, begin a post-call group, so as to keep the
3672 lifetimes of hard registers correct. */
3673 if (! reload_completed
)
3674 deps
->in_post_call_group_p
= post_call
;
3678 if (sched_deps_info
->use_cselib
)
3679 cselib_process_insn (insn
);
3681 /* EH_REGION insn notes can not appear until well after we complete
3684 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3685 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3687 if (sched_deps_info
->finish_insn
)
3688 sched_deps_info
->finish_insn ();
3690 /* Fixup the dependencies in the sched group. */
3691 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3692 && chain_to_prev_insn_p (insn
)
3694 chain_to_prev_insn (insn
);
3697 /* Initialize DEPS for the new block beginning with HEAD. */
3699 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3701 gcc_assert (!deps
->readonly
);
3703 /* Before reload, if the previous block ended in a call, show that
3704 we are inside a post-call group, so as to keep the lifetimes of
3705 hard registers correct. */
3706 if (! reload_completed
&& !LABEL_P (head
))
3708 rtx insn
= prev_nonnote_nondebug_insn (head
);
3710 if (insn
&& CALL_P (insn
))
3711 deps
->in_post_call_group_p
= post_call_initial
;
3715 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3716 dependencies for each insn. */
3718 sched_analyze (struct deps_desc
*deps
, rtx head
, rtx tail
)
3722 if (sched_deps_info
->use_cselib
)
3723 cselib_init (CSELIB_RECORD_MEMORY
);
3725 deps_start_bb (deps
, head
);
3727 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3732 /* And initialize deps_lists. */
3733 sd_init_insn (insn
);
3736 deps_analyze_insn (deps
, insn
);
3740 if (sched_deps_info
->use_cselib
)
3748 /* Helper for sched_free_deps ().
3749 Delete INSN's (RESOLVED_P) backward dependencies. */
3751 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3753 sd_iterator_def sd_it
;
3755 sd_list_types_def types
;
3758 types
= SD_LIST_RES_BACK
;
3760 types
= SD_LIST_BACK
;
3762 for (sd_it
= sd_iterator_start (insn
, types
);
3763 sd_iterator_cond (&sd_it
, &dep
);)
3765 dep_link_t link
= *sd_it
.linkp
;
3766 dep_node_t node
= DEP_LINK_NODE (link
);
3767 deps_list_t back_list
;
3768 deps_list_t forw_list
;
3770 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3771 remove_from_deps_list (link
, back_list
);
3772 delete_dep_node (node
);
3776 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3779 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3782 rtx next_tail
= NEXT_INSN (tail
);
3784 /* We make two passes since some insns may be scheduled before their
3785 dependencies are resolved. */
3786 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3787 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3789 /* Clear forward deps and leave the dep_nodes to the
3790 corresponding back_deps list. */
3792 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3794 clear_deps_list (INSN_FORW_DEPS (insn
));
3796 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3797 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3799 /* Clear resolved back deps together with its dep_nodes. */
3800 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3802 sd_finish_insn (insn
);
3806 /* Initialize variables for region data dependence analysis.
3807 When LAZY_REG_LAST is true, do not allocate reg_last array
3808 of struct deps_desc immediately. */
3811 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3813 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3815 deps
->max_reg
= max_reg
;
3817 deps
->reg_last
= NULL
;
3819 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3820 INIT_REG_SET (&deps
->reg_last_in_use
);
3822 deps
->pending_read_insns
= 0;
3823 deps
->pending_read_mems
= 0;
3824 deps
->pending_write_insns
= 0;
3825 deps
->pending_write_mems
= 0;
3826 deps
->pending_jump_insns
= 0;
3827 deps
->pending_read_list_length
= 0;
3828 deps
->pending_write_list_length
= 0;
3829 deps
->pending_flush_length
= 0;
3830 deps
->last_pending_memory_flush
= 0;
3831 deps
->last_function_call
= 0;
3832 deps
->last_function_call_may_noreturn
= 0;
3833 deps
->sched_before_next_call
= 0;
3834 deps
->sched_before_next_jump
= 0;
3835 deps
->in_post_call_group_p
= not_post_call
;
3836 deps
->last_debug_insn
= 0;
3837 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3841 /* Init only reg_last field of DEPS, which was not allocated before as
3842 we inited DEPS lazily. */
3844 init_deps_reg_last (struct deps_desc
*deps
)
3846 gcc_assert (deps
&& deps
->max_reg
> 0);
3847 gcc_assert (deps
->reg_last
== NULL
);
3849 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3853 /* Free insn lists found in DEPS. */
3856 free_deps (struct deps_desc
*deps
)
3859 reg_set_iterator rsi
;
3861 /* We set max_reg to 0 when this context was already freed. */
3862 if (deps
->max_reg
== 0)
3864 gcc_assert (deps
->reg_last
== NULL
);
3869 free_INSN_LIST_list (&deps
->pending_read_insns
);
3870 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3871 free_INSN_LIST_list (&deps
->pending_write_insns
);
3872 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3873 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3875 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3876 times. For a testcase with 42000 regs and 8000 small basic blocks,
3877 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3878 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3880 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3882 free_INSN_LIST_list (®_last
->uses
);
3884 free_INSN_LIST_list (®_last
->sets
);
3885 if (reg_last
->implicit_sets
)
3886 free_INSN_LIST_list (®_last
->implicit_sets
);
3887 if (reg_last
->control_uses
)
3888 free_INSN_LIST_list (®_last
->control_uses
);
3889 if (reg_last
->clobbers
)
3890 free_INSN_LIST_list (®_last
->clobbers
);
3892 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3894 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3896 free (deps
->reg_last
);
3897 deps
->reg_last
= NULL
;
3902 /* Remove INSN from dependence contexts DEPS. */
3904 remove_from_deps (struct deps_desc
*deps
, rtx insn
)
3908 reg_set_iterator rsi
;
3910 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3911 &deps
->pending_read_mems
);
3912 if (!DEBUG_INSN_P (insn
))
3913 deps
->pending_read_list_length
-= removed
;
3914 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3915 &deps
->pending_write_mems
);
3916 deps
->pending_write_list_length
-= removed
;
3918 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
3919 deps
->pending_flush_length
-= removed
;
3920 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3921 deps
->pending_flush_length
-= removed
;
3923 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3925 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3927 remove_from_dependence_list (insn
, ®_last
->uses
);
3929 remove_from_dependence_list (insn
, ®_last
->sets
);
3930 if (reg_last
->implicit_sets
)
3931 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3932 if (reg_last
->clobbers
)
3933 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3934 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3935 && !reg_last
->clobbers
)
3936 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3941 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3942 remove_from_dependence_list (insn
,
3943 &deps
->last_function_call_may_noreturn
);
3945 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3948 /* Init deps data vector. */
3950 init_deps_data_vector (void)
3952 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
3953 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
3954 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
3957 /* If it is profitable to use them, initialize or extend (depending on
3958 GLOBAL_P) dependency data. */
3960 sched_deps_init (bool global_p
)
3962 /* Average number of insns in the basic block.
3963 '+ 1' is used to make it nonzero. */
3964 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3966 init_deps_data_vector ();
3968 /* We use another caching mechanism for selective scheduling, so
3969 we don't use this one. */
3970 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3972 /* ?!? We could save some memory by computing a per-region luid mapping
3973 which could reduce both the number of vectors in the cache and the
3974 size of each vector. Instead we just avoid the cache entirely unless
3975 the average number of instructions in a basic block is very high. See
3976 the comment before the declaration of true_dependency_cache for
3977 what we consider "very high". */
3979 extend_dependency_caches (sched_max_luid
, true);
3984 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3985 /* Allocate lists for one block at a time. */
3987 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3988 /* Allocate nodes for one block at a time.
3989 We assume that average insn has
3991 5 * insns_in_block
);
3996 /* Create or extend (depending on CREATE_P) dependency caches to
3999 extend_dependency_caches (int n
, bool create_p
)
4001 if (create_p
|| true_dependency_cache
)
4003 int i
, luid
= cache_size
+ n
;
4005 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4007 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4008 output_dependency_cache
, luid
);
4009 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4011 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4014 if (current_sched_info
->flags
& DO_SPECULATION
)
4015 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4018 for (i
= cache_size
; i
< luid
; i
++)
4020 bitmap_initialize (&true_dependency_cache
[i
], 0);
4021 bitmap_initialize (&output_dependency_cache
[i
], 0);
4022 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4023 bitmap_initialize (&control_dependency_cache
[i
], 0);
4025 if (current_sched_info
->flags
& DO_SPECULATION
)
4026 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4032 /* Finalize dependency information for the whole function. */
4034 sched_deps_finish (void)
4036 gcc_assert (deps_pools_are_empty_p ());
4037 free_alloc_pool_if_empty (&dn_pool
);
4038 free_alloc_pool_if_empty (&dl_pool
);
4039 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
4044 if (true_dependency_cache
)
4048 for (i
= 0; i
< cache_size
; i
++)
4050 bitmap_clear (&true_dependency_cache
[i
]);
4051 bitmap_clear (&output_dependency_cache
[i
]);
4052 bitmap_clear (&anti_dependency_cache
[i
]);
4053 bitmap_clear (&control_dependency_cache
[i
]);
4055 if (sched_deps_info
->generate_spec_deps
)
4056 bitmap_clear (&spec_dependency_cache
[i
]);
4058 free (true_dependency_cache
);
4059 true_dependency_cache
= NULL
;
4060 free (output_dependency_cache
);
4061 output_dependency_cache
= NULL
;
4062 free (anti_dependency_cache
);
4063 anti_dependency_cache
= NULL
;
4064 free (control_dependency_cache
);
4065 control_dependency_cache
= NULL
;
4067 if (sched_deps_info
->generate_spec_deps
)
4069 free (spec_dependency_cache
);
4070 spec_dependency_cache
= NULL
;
4076 /* Initialize some global variables needed by the dependency analysis
4080 init_deps_global (void)
4082 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4083 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4084 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4085 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4086 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4087 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4088 reg_pending_barrier
= NOT_A_BARRIER
;
4090 if (!sel_sched_p () || sched_emulate_haifa_p
)
4092 sched_deps_info
->start_insn
= haifa_start_insn
;
4093 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4095 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4096 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4097 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4099 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4100 sched_deps_info
->note_dep
= haifa_note_dep
;
4104 /* Free everything used by the dependency analysis code. */
4107 finish_deps_global (void)
4109 FREE_REG_SET (reg_pending_sets
);
4110 FREE_REG_SET (reg_pending_clobbers
);
4111 FREE_REG_SET (reg_pending_uses
);
4112 FREE_REG_SET (reg_pending_control_uses
);
4115 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4117 estimate_dep_weak (rtx mem1
, rtx mem2
)
4122 /* MEMs are the same - don't speculate. */
4123 return MIN_DEP_WEAK
;
4125 r1
= XEXP (mem1
, 0);
4126 r2
= XEXP (mem2
, 0);
4129 || (REG_P (r1
) && REG_P (r2
)
4130 && REGNO (r1
) == REGNO (r2
)))
4131 /* Again, MEMs are the same. */
4132 return MIN_DEP_WEAK
;
4133 else if ((REG_P (r1
) && !REG_P (r2
))
4134 || (!REG_P (r1
) && REG_P (r2
)))
4135 /* Different addressing modes - reason to be more speculative,
4137 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4139 /* We can't say anything about the dependence. */
4140 return UNCERTAIN_DEP_WEAK
;
4143 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4144 This function can handle same INSN and ELEM (INSN == ELEM).
4145 It is a convenience wrapper. */
4147 add_dependence_1 (rtx insn
, rtx elem
, enum reg_note dep_type
)
4152 if (dep_type
== REG_DEP_TRUE
)
4154 else if (dep_type
== REG_DEP_OUTPUT
)
4156 else if (dep_type
== REG_DEP_CONTROL
)
4160 gcc_assert (dep_type
== REG_DEP_ANTI
);
4164 /* When add_dependence is called from inside sched-deps.c, we expect
4165 cur_insn to be non-null. */
4166 internal
= cur_insn
!= NULL
;
4168 gcc_assert (insn
== cur_insn
);
4172 note_dep (elem
, ds
);
4177 /* Return weakness of speculative type TYPE in the dep_status DS. */
4179 get_dep_weak_1 (ds_t ds
, ds_t type
)
4185 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4186 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4187 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4188 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4189 default: gcc_unreachable ();
4196 get_dep_weak (ds_t ds
, ds_t type
)
4198 dw_t dw
= get_dep_weak_1 (ds
, type
);
4200 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4204 /* Return the dep_status, which has the same parameters as DS, except for
4205 speculative type TYPE, that will have weakness DW. */
4207 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4209 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4214 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4215 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4216 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4217 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4218 default: gcc_unreachable ();
4223 /* Return the join of two dep_statuses DS1 and DS2.
4224 If MAX_P is true then choose the greater probability,
4225 otherwise multiply probabilities.
4226 This function assumes that both DS1 and DS2 contain speculative bits. */
4228 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4232 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4234 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4236 t
= FIRST_SPEC_TYPE
;
4239 if ((ds1
& t
) && !(ds2
& t
))
4241 else if (!(ds1
& t
) && (ds2
& t
))
4243 else if ((ds1
& t
) && (ds2
& t
))
4245 dw_t dw1
= get_dep_weak (ds1
, t
);
4246 dw_t dw2
= get_dep_weak (ds2
, t
);
4251 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4253 if (dw
< MIN_DEP_WEAK
)
4264 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4267 if (t
== LAST_SPEC_TYPE
)
4269 t
<<= SPEC_TYPE_SHIFT
;
4276 /* Return the join of two dep_statuses DS1 and DS2.
4277 This function assumes that both DS1 and DS2 contain speculative bits. */
4279 ds_merge (ds_t ds1
, ds_t ds2
)
4281 return ds_merge_1 (ds1
, ds2
, false);
4284 /* Return the join of two dep_statuses DS1 and DS2. */
4286 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4288 ds_t new_status
= ds
| ds2
;
4290 if (new_status
& SPECULATIVE
)
4292 if ((ds
&& !(ds
& SPECULATIVE
))
4293 || (ds2
&& !(ds2
& SPECULATIVE
)))
4294 /* Then this dep can't be speculative. */
4295 new_status
&= ~SPECULATIVE
;
4298 /* Both are speculative. Merging probabilities. */
4303 dw
= estimate_dep_weak (mem1
, mem2
);
4304 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4312 new_status
= ds_merge (ds2
, ds
);
4319 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4322 ds_max_merge (ds_t ds1
, ds_t ds2
)
4324 if (ds1
== 0 && ds2
== 0)
4327 if (ds1
== 0 && ds2
!= 0)
4330 if (ds1
!= 0 && ds2
== 0)
4333 return ds_merge_1 (ds1
, ds2
, true);
4336 /* Return the probability of speculation success for the speculation
4344 dt
= FIRST_SPEC_TYPE
;
4349 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4353 if (dt
== LAST_SPEC_TYPE
)
4355 dt
<<= SPEC_TYPE_SHIFT
;
4361 res
/= MAX_DEP_WEAK
;
4363 if (res
< MIN_DEP_WEAK
)
4366 gcc_assert (res
<= MAX_DEP_WEAK
);
4371 /* Return a dep status that contains all speculation types of DS. */
4373 ds_get_speculation_types (ds_t ds
)
4375 if (ds
& BEGIN_DATA
)
4377 if (ds
& BE_IN_DATA
)
4379 if (ds
& BEGIN_CONTROL
)
4380 ds
|= BEGIN_CONTROL
;
4381 if (ds
& BE_IN_CONTROL
)
4382 ds
|= BE_IN_CONTROL
;
4384 return ds
& SPECULATIVE
;
4387 /* Return a dep status that contains maximal weakness for each speculation
4388 type present in DS. */
4390 ds_get_max_dep_weak (ds_t ds
)
4392 if (ds
& BEGIN_DATA
)
4393 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4394 if (ds
& BE_IN_DATA
)
4395 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4396 if (ds
& BEGIN_CONTROL
)
4397 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4398 if (ds
& BE_IN_CONTROL
)
4399 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4404 /* Dump information about the dependence status S. */
4406 dump_ds (FILE *f
, ds_t s
)
4411 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4413 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4414 if (s
& BEGIN_CONTROL
)
4415 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4416 if (s
& BE_IN_CONTROL
)
4417 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4420 fprintf (f
, "HARD_DEP; ");
4423 fprintf (f
, "DEP_TRUE; ");
4425 fprintf (f
, "DEP_OUTPUT; ");
4427 fprintf (f
, "DEP_ANTI; ");
4428 if (s
& DEP_CONTROL
)
4429 fprintf (f
, "DEP_CONTROL; ");
4437 dump_ds (stderr
, s
);
4438 fprintf (stderr
, "\n");
4441 #ifdef ENABLE_CHECKING
4442 /* Verify that dependence type and status are consistent.
4443 If RELAXED_P is true, then skip dep_weakness checks. */
4445 check_dep (dep_t dep
, bool relaxed_p
)
4447 enum reg_note dt
= DEP_TYPE (dep
);
4448 ds_t ds
= DEP_STATUS (dep
);
4450 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4452 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4454 gcc_assert (ds
== 0);
4458 /* Check that dependence type contains the same bits as the status. */
4459 if (dt
== REG_DEP_TRUE
)
4460 gcc_assert (ds
& DEP_TRUE
);
4461 else if (dt
== REG_DEP_OUTPUT
)
4462 gcc_assert ((ds
& DEP_OUTPUT
)
4463 && !(ds
& DEP_TRUE
));
4464 else if (dt
== REG_DEP_ANTI
)
4465 gcc_assert ((ds
& DEP_ANTI
)
4466 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4468 gcc_assert (dt
== REG_DEP_CONTROL
4469 && (ds
& DEP_CONTROL
)
4470 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4472 /* HARD_DEP can not appear in dep_status of a link. */
4473 gcc_assert (!(ds
& HARD_DEP
));
4475 /* Check that dependence status is set correctly when speculation is not
4477 if (!sched_deps_info
->generate_spec_deps
)
4478 gcc_assert (!(ds
& SPECULATIVE
));
4479 else if (ds
& SPECULATIVE
)
4483 ds_t type
= FIRST_SPEC_TYPE
;
4485 /* Check that dependence weakness is in proper range. */
4489 get_dep_weak (ds
, type
);
4491 if (type
== LAST_SPEC_TYPE
)
4493 type
<<= SPEC_TYPE_SHIFT
;
4498 if (ds
& BEGIN_SPEC
)
4500 /* Only true dependence can be data speculative. */
4501 if (ds
& BEGIN_DATA
)
4502 gcc_assert (ds
& DEP_TRUE
);
4504 /* Control dependencies in the insn scheduler are represented by
4505 anti-dependencies, therefore only anti dependence can be
4506 control speculative. */
4507 if (ds
& BEGIN_CONTROL
)
4508 gcc_assert (ds
& DEP_ANTI
);
4512 /* Subsequent speculations should resolve true dependencies. */
4513 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4516 /* Check that true and anti dependencies can't have other speculative
4519 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4520 /* An output dependence can't be speculative at all. */
4521 gcc_assert (!(ds
& DEP_OUTPUT
));
4523 gcc_assert (ds
& BEGIN_CONTROL
);
4526 #endif /* ENABLE_CHECKING */
4528 /* The following code discovers opportunities to switch a memory reference
4529 and an increment by modifying the address. We ensure that this is done
4530 only for dependencies that are only used to show a single register
4531 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4532 instruction involved is subject to only one dep that can cause a pattern
4535 When we discover a suitable dependency, we fill in the dep_replacement
4536 structure to show how to modify the memory reference. */
4538 /* Holds information about a pair of memory reference and register increment
4539 insns which depend on each other, but could possibly be interchanged. */
4546 /* A register occurring in the memory address for which we wish to break
4547 the dependence. This must be identical to the destination register of
4550 /* Any kind of index that is added to that register. */
4552 /* The constant offset used in the memory address. */
4553 HOST_WIDE_INT mem_constant
;
4554 /* The constant added in the increment insn. Negated if the increment is
4555 after the memory address. */
4556 HOST_WIDE_INT inc_constant
;
4557 /* The source register used in the increment. May be different from mem_reg0
4558 if the increment occurs before the memory address. */
4562 /* Verify that the memory location described in MII can be replaced with
4563 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4564 insn remains unchanged by this function. */
4567 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4569 rtx mem
= *mii
->mem_loc
;
4572 /* Jump thru a lot of hoops to keep the attributes up to date. We
4573 do not want to call one of the change address variants that take
4574 an offset even though we know the offset in many cases. These
4575 assume you are changing where the address is pointing by the
4577 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4578 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4580 if (sched_verbose
>= 5)
4581 fprintf (sched_dump
, "validation failure\n");
4585 /* Put back the old one. */
4586 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4591 /* Return true if INSN is of a form "a = b op c" where a and b are
4592 regs. op is + if c is a reg and +|- if c is a const. Fill in
4593 informantion in MII about what is found.
4594 BEFORE_MEM indicates whether the increment is found before or after
4595 a corresponding memory reference. */
4598 parse_add_or_inc (struct mem_inc_info
*mii
, rtx insn
, bool before_mem
)
4600 rtx pat
= single_set (insn
);
4604 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4607 /* Result must be single reg. */
4608 if (!REG_P (SET_DEST (pat
)))
4611 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4614 mii
->inc_insn
= insn
;
4615 src
= SET_SRC (pat
);
4616 mii
->inc_input
= XEXP (src
, 0);
4618 if (!REG_P (XEXP (src
, 0)))
4621 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4624 cst
= XEXP (src
, 1);
4625 if (!CONST_INT_P (cst
))
4627 mii
->inc_constant
= INTVAL (cst
);
4629 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4633 mii
->inc_constant
= -mii
->inc_constant
;
4638 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4640 /* Note that the sign has already been reversed for !before_mem. */
4641 #ifdef STACK_GROWS_DOWNWARD
4642 return mii
->inc_constant
> 0;
4644 return mii
->inc_constant
< 0;
4650 /* Once a suitable mem reference has been found and the corresponding data
4651 in MII has been filled in, this function is called to find a suitable
4652 add or inc insn involving the register we found in the memory
4656 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4658 sd_iterator_def sd_it
;
4661 sd_it
= sd_iterator_start (mii
->mem_insn
,
4662 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4663 while (sd_iterator_cond (&sd_it
, &dep
))
4665 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4666 rtx pro
= DEP_PRO (dep
);
4667 rtx con
= DEP_CON (dep
);
4668 rtx inc_cand
= backwards
? pro
: con
;
4669 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4671 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4673 struct dep_replacement
*desc
;
4675 rtx newaddr
, newmem
;
4677 if (sched_verbose
>= 5)
4678 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4679 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4681 /* Need to assure that none of the operands of the inc
4682 instruction are assigned to by the mem insn. */
4683 for (def_rec
= DF_INSN_DEFS (mii
->mem_insn
); *def_rec
; def_rec
++)
4685 df_ref def
= *def_rec
;
4686 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4687 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4689 if (sched_verbose
>= 5)
4690 fprintf (sched_dump
,
4691 "inc conflicts with store failure.\n");
4695 newaddr
= mii
->inc_input
;
4696 if (mii
->mem_index
!= NULL_RTX
)
4697 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4699 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4700 mii
->mem_constant
+ mii
->inc_constant
);
4701 newmem
= attempt_change (mii
, newaddr
);
4702 if (newmem
== NULL_RTX
)
4704 if (sched_verbose
>= 5)
4705 fprintf (sched_dump
, "successful address replacement\n");
4706 desc
= XCNEW (struct dep_replacement
);
4707 DEP_REPLACE (dep
) = desc
;
4708 desc
->loc
= mii
->mem_loc
;
4709 desc
->newval
= newmem
;
4710 desc
->orig
= *desc
->loc
;
4711 desc
->insn
= mii
->mem_insn
;
4712 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4713 INSN_SPEC_BACK_DEPS (con
));
4716 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4717 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4722 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4723 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4729 sd_iterator_next (&sd_it
);
4734 /* A recursive function that walks ADDRESS_OF_X to find memory references
4735 which could be modified during scheduling. We call find_inc for each
4736 one we find that has a recognizable form. MII holds information about
4737 the pair of memory/increment instructions.
4738 We ensure that every instruction with a memory reference (which will be
4739 the location of the replacement) is assigned at most one breakable
4743 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4745 rtx x
= *address_of_x
;
4746 enum rtx_code code
= GET_CODE (x
);
4747 const char *const fmt
= GET_RTX_FORMAT (code
);
4752 rtx reg0
= XEXP (x
, 0);
4754 mii
->mem_loc
= address_of_x
;
4755 mii
->mem_index
= NULL_RTX
;
4756 mii
->mem_constant
= 0;
4757 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4759 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4760 reg0
= XEXP (reg0
, 0);
4762 if (GET_CODE (reg0
) == PLUS
)
4764 mii
->mem_index
= XEXP (reg0
, 1);
4765 reg0
= XEXP (reg0
, 0);
4770 int occurrences
= 0;
4772 /* Make sure this reg appears only once in this insn. Can't use
4773 count_occurrences since that only works for pseudos. */
4774 for (def_rec
= DF_INSN_USES (mii
->mem_insn
); *def_rec
; def_rec
++)
4776 df_ref def
= *def_rec
;
4777 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (def
)))
4778 if (++occurrences
> 1)
4780 if (sched_verbose
>= 5)
4781 fprintf (sched_dump
, "mem count failure\n");
4786 mii
->mem_reg0
= reg0
;
4787 return find_inc (mii
, true) || find_inc (mii
, false);
4792 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4794 /* If REG occurs inside a MEM used in a bit-field reference,
4795 that is unacceptable. */
4799 /* Time for some deep diving. */
4800 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4804 if (find_mem (mii
, &XEXP (x
, i
)))
4807 else if (fmt
[i
] == 'E')
4810 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4811 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4819 /* Examine the instructions between HEAD and TAIL and try to find
4820 dependencies that can be broken by modifying one of the patterns. */
4823 find_modifiable_mems (rtx head
, rtx tail
)
4825 rtx insn
, next_tail
= NEXT_INSN (tail
);
4826 int success_in_block
= 0;
4828 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4830 struct mem_inc_info mii
;
4832 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4835 mii
.mem_insn
= insn
;
4836 if (find_mem (&mii
, &PATTERN (insn
)))
4839 if (success_in_block
&& sched_verbose
>= 5)
4840 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4844 #endif /* INSN_SCHEDULING */