1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992-2014 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
27 #include "diagnostic-core.h"
29 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
31 #include "hard-reg-set.h"
40 #include "insn-config.h"
41 #include "insn-attr.h"
45 #include "sched-int.h"
51 #ifdef INSN_SCHEDULING
53 #ifdef ENABLE_CHECKING
59 /* Holds current parameters for the dependency analyzer. */
60 struct sched_deps_info_def
*sched_deps_info
;
62 /* The data is specific to the Haifa scheduler. */
63 vec
<haifa_deps_insn_data_def
>
66 /* Return the major type present in the DS. */
74 return REG_DEP_OUTPUT
;
77 return REG_DEP_CONTROL
;
79 gcc_assert (ds
& DEP_ANTI
);
84 /* Return equivalent dep_status. */
86 dk_to_ds (enum reg_note dk
)
100 gcc_assert (dk
== REG_DEP_ANTI
);
105 /* Functions to operate with dependence information container - dep_t. */
107 /* Init DEP with the arguments. */
109 init_dep_1 (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note type
, ds_t ds
)
113 DEP_TYPE (dep
) = type
;
114 DEP_STATUS (dep
) = ds
;
115 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
116 DEP_NONREG (dep
) = 0;
117 DEP_MULTIPLE (dep
) = 0;
118 DEP_REPLACE (dep
) = NULL
;
121 /* Init DEP with the arguments.
122 While most of the scheduler (including targets) only need the major type
123 of the dependency, it is convenient to hide full dep_status from them. */
125 init_dep (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note kind
)
129 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
130 ds
= dk_to_ds (kind
);
134 init_dep_1 (dep
, pro
, con
, kind
, ds
);
137 /* Make a copy of FROM in TO. */
139 copy_dep (dep_t to
, dep_t from
)
141 memcpy (to
, from
, sizeof (*to
));
144 static void dump_ds (FILE *, ds_t
);
146 /* Define flags for dump_dep (). */
148 /* Dump producer of the dependence. */
149 #define DUMP_DEP_PRO (2)
151 /* Dump consumer of the dependence. */
152 #define DUMP_DEP_CON (4)
154 /* Dump type of the dependence. */
155 #define DUMP_DEP_TYPE (8)
157 /* Dump status of the dependence. */
158 #define DUMP_DEP_STATUS (16)
160 /* Dump all information about the dependence. */
161 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
165 FLAGS is a bit mask specifying what information about DEP needs
167 If FLAGS has the very first bit set, then dump all information about DEP
168 and propagate this bit into the callee dump functions. */
170 dump_dep (FILE *dump
, dep_t dep
, int flags
)
173 flags
|= DUMP_DEP_ALL
;
177 if (flags
& DUMP_DEP_PRO
)
178 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
180 if (flags
& DUMP_DEP_CON
)
181 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
183 if (flags
& DUMP_DEP_TYPE
)
186 enum reg_note type
= DEP_TYPE (dep
);
198 case REG_DEP_CONTROL
:
211 fprintf (dump
, "%c; ", t
);
214 if (flags
& DUMP_DEP_STATUS
)
216 if (current_sched_info
->flags
& USE_DEPS_LIST
)
217 dump_ds (dump
, DEP_STATUS (dep
));
223 /* Default flags for dump_dep (). */
224 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
226 /* Dump all fields of DEP to STDERR. */
228 sd_debug_dep (dep_t dep
)
230 dump_dep (stderr
, dep
, 1);
231 fprintf (stderr
, "\n");
234 /* Determine whether DEP is a dependency link of a non-debug insn on a
238 depl_on_debug_p (dep_link_t dep
)
240 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
241 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
244 /* Functions to operate with a single link from the dependencies lists -
247 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
250 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
252 dep_link_t next
= *prev_nextp
;
254 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
255 && DEP_LINK_NEXT (l
) == NULL
);
257 /* Init node being inserted. */
258 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
259 DEP_LINK_NEXT (l
) = next
;
264 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
266 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
273 /* Add dep_link LINK to deps_list L. */
275 add_to_deps_list (dep_link_t link
, deps_list_t l
)
277 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
279 /* Don't count debug deps. */
280 if (!depl_on_debug_p (link
))
281 ++DEPS_LIST_N_LINKS (l
);
284 /* Detach dep_link L from the list. */
286 detach_dep_link (dep_link_t l
)
288 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
289 dep_link_t next
= DEP_LINK_NEXT (l
);
294 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
296 DEP_LINK_PREV_NEXTP (l
) = NULL
;
297 DEP_LINK_NEXT (l
) = NULL
;
300 /* Remove link LINK from list LIST. */
302 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
304 detach_dep_link (link
);
306 /* Don't count debug deps. */
307 if (!depl_on_debug_p (link
))
308 --DEPS_LIST_N_LINKS (list
);
311 /* Move link LINK from list FROM to list TO. */
313 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
315 remove_from_deps_list (link
, from
);
316 add_to_deps_list (link
, to
);
319 /* Return true of LINK is not attached to any list. */
321 dep_link_is_detached_p (dep_link_t link
)
323 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
326 /* Pool to hold all dependency nodes (dep_node_t). */
327 static alloc_pool dn_pool
;
329 /* Number of dep_nodes out there. */
330 static int dn_pool_diff
= 0;
332 /* Create a dep_node. */
334 create_dep_node (void)
336 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
337 dep_link_t back
= DEP_NODE_BACK (n
);
338 dep_link_t forw
= DEP_NODE_FORW (n
);
340 DEP_LINK_NODE (back
) = n
;
341 DEP_LINK_NEXT (back
) = NULL
;
342 DEP_LINK_PREV_NEXTP (back
) = NULL
;
344 DEP_LINK_NODE (forw
) = n
;
345 DEP_LINK_NEXT (forw
) = NULL
;
346 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
353 /* Delete dep_node N. N must not be connected to any deps_list. */
355 delete_dep_node (dep_node_t n
)
357 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
358 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
360 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n
)));
364 pool_free (dn_pool
, n
);
367 /* Pool to hold dependencies lists (deps_list_t). */
368 static alloc_pool dl_pool
;
370 /* Number of deps_lists out there. */
371 static int dl_pool_diff
= 0;
373 /* Functions to operate with dependences lists - deps_list_t. */
375 /* Return true if list L is empty. */
377 deps_list_empty_p (deps_list_t l
)
379 return DEPS_LIST_N_LINKS (l
) == 0;
382 /* Create a new deps_list. */
384 create_deps_list (void)
386 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
388 DEPS_LIST_FIRST (l
) = NULL
;
389 DEPS_LIST_N_LINKS (l
) = 0;
395 /* Free deps_list L. */
397 free_deps_list (deps_list_t l
)
399 gcc_assert (deps_list_empty_p (l
));
403 pool_free (dl_pool
, l
);
406 /* Return true if there is no dep_nodes and deps_lists out there.
407 After the region is scheduled all the dependency nodes and lists
408 should [generally] be returned to pool. */
410 deps_pools_are_empty_p (void)
412 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
415 /* Remove all elements from L. */
417 clear_deps_list (deps_list_t l
)
421 dep_link_t link
= DEPS_LIST_FIRST (l
);
426 remove_from_deps_list (link
, l
);
431 /* Decide whether a dependency should be treated as a hard or a speculative
434 dep_spec_p (dep_t dep
)
436 if (current_sched_info
->flags
& DO_SPECULATION
)
438 if (DEP_STATUS (dep
) & SPECULATIVE
)
441 if (current_sched_info
->flags
& DO_PREDICATION
)
443 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
446 if (DEP_REPLACE (dep
) != NULL
)
451 static regset reg_pending_sets
;
452 static regset reg_pending_clobbers
;
453 static regset reg_pending_uses
;
454 static regset reg_pending_control_uses
;
455 static enum reg_pending_barrier_mode reg_pending_barrier
;
457 /* Hard registers implicitly clobbered or used (or may be implicitly
458 clobbered or used) by the currently analyzed insn. For example,
459 insn in its constraint has one register class. Even if there is
460 currently no hard register in the insn, the particular hard
461 register will be in the insn after reload pass because the
462 constraint requires it. */
463 static HARD_REG_SET implicit_reg_pending_clobbers
;
464 static HARD_REG_SET implicit_reg_pending_uses
;
466 /* To speed up the test for duplicate dependency links we keep a
467 record of dependencies created by add_dependence when the average
468 number of instructions in a basic block is very large.
470 Studies have shown that there is typically around 5 instructions between
471 branches for typical C code. So we can make a guess that the average
472 basic block is approximately 5 instructions long; we will choose 100X
473 the average size as a very large basic block.
475 Each insn has associated bitmaps for its dependencies. Each bitmap
476 has enough entries to represent a dependency on any other insn in
477 the insn chain. All bitmap for true dependencies cache is
478 allocated then the rest two ones are also allocated. */
479 static bitmap_head
*true_dependency_cache
= NULL
;
480 static bitmap_head
*output_dependency_cache
= NULL
;
481 static bitmap_head
*anti_dependency_cache
= NULL
;
482 static bitmap_head
*control_dependency_cache
= NULL
;
483 static bitmap_head
*spec_dependency_cache
= NULL
;
484 static int cache_size
;
486 /* True if we should mark added dependencies as a non-register deps. */
487 static bool mark_as_hard
;
489 static int deps_may_trap_p (const_rtx
);
490 static void add_dependence_1 (rtx_insn
*, rtx_insn
*, enum reg_note
);
491 static void add_dependence_list (rtx_insn
*, rtx_insn_list
*, int,
492 enum reg_note
, bool);
493 static void add_dependence_list_and_free (struct deps_desc
*, rtx_insn
*,
494 rtx_insn_list
**, int, enum reg_note
,
496 static void delete_all_dependences (rtx
);
497 static void chain_to_prev_insn (rtx_insn
*);
499 static void flush_pending_lists (struct deps_desc
*, rtx_insn
*, int, int);
500 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx_insn
*);
501 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx_insn
*);
502 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx_insn
*);
504 static bool sched_has_condition_p (const rtx_insn
*);
505 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
507 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
509 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
511 #ifdef ENABLE_CHECKING
512 static void check_dep (dep_t
, bool);
515 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
518 deps_may_trap_p (const_rtx mem
)
520 const_rtx addr
= XEXP (mem
, 0);
522 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
524 const_rtx t
= get_reg_known_value (REGNO (addr
));
528 return rtx_addr_can_trap_p (addr
);
532 /* Find the condition under which INSN is executed. If REV is not NULL,
533 it is set to TRUE when the returned comparison should be reversed
534 to get the actual condition. */
536 sched_get_condition_with_rev_uncached (const rtx_insn
*insn
, bool *rev
)
538 rtx pat
= PATTERN (insn
);
544 if (GET_CODE (pat
) == COND_EXEC
)
545 return COND_EXEC_TEST (pat
);
547 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
550 src
= SET_SRC (pc_set (insn
));
552 if (XEXP (src
, 2) == pc_rtx
)
553 return XEXP (src
, 0);
554 else if (XEXP (src
, 1) == pc_rtx
)
556 rtx cond
= XEXP (src
, 0);
557 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
559 if (revcode
== UNKNOWN
)
570 /* Return the condition under which INSN does not execute (i.e. the
571 not-taken condition for a conditional branch), or NULL if we cannot
572 find such a condition. The caller should make a copy of the condition
575 sched_get_reverse_condition_uncached (const rtx_insn
*insn
)
578 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
579 if (cond
== NULL_RTX
)
583 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
584 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
591 /* Caching variant of sched_get_condition_with_rev_uncached.
592 We only do actual work the first time we come here for an insn; the
593 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
595 sched_get_condition_with_rev (const rtx_insn
*insn
, bool *rev
)
599 if (INSN_LUID (insn
) == 0)
600 return sched_get_condition_with_rev_uncached (insn
, rev
);
602 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
605 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
608 *rev
= INSN_REVERSE_COND (insn
);
609 return INSN_CACHED_COND (insn
);
612 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
613 INSN_REVERSE_COND (insn
) = tmp
;
615 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
617 INSN_CACHED_COND (insn
) = const_true_rtx
;
622 *rev
= INSN_REVERSE_COND (insn
);
623 return INSN_CACHED_COND (insn
);
626 /* True when we can find a condition under which INSN is executed. */
628 sched_has_condition_p (const rtx_insn
*insn
)
630 return !! sched_get_condition_with_rev (insn
, NULL
);
635 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
637 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
639 if (COMPARISON_P (cond1
)
640 && COMPARISON_P (cond2
)
641 && GET_CODE (cond1
) ==
643 ? reversed_comparison_code (cond2
, NULL
)
645 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
646 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
651 /* Return true if insn1 and insn2 can never depend on one another because
652 the conditions under which they are executed are mutually exclusive. */
654 sched_insns_conditions_mutex_p (const rtx_insn
*insn1
, const rtx_insn
*insn2
)
657 bool rev1
= false, rev2
= false;
659 /* df doesn't handle conditional lifetimes entirely correctly;
660 calls mess up the conditional lifetimes. */
661 if (!CALL_P (insn1
) && !CALL_P (insn2
))
663 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
664 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
666 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
667 /* Make sure first instruction doesn't affect condition of second
668 instruction if switched. */
669 && !modified_in_p (cond1
, insn2
)
670 /* Make sure second instruction doesn't affect condition of first
671 instruction if switched. */
672 && !modified_in_p (cond2
, insn1
))
679 /* Return true if INSN can potentially be speculated with type DS. */
681 sched_insn_is_legitimate_for_speculation_p (const rtx_insn
*insn
, ds_t ds
)
683 if (HAS_INTERNAL_DEP (insn
))
686 if (!NONJUMP_INSN_P (insn
))
689 if (SCHED_GROUP_P (insn
))
692 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn
)))
695 if (side_effects_p (PATTERN (insn
)))
699 /* The following instructions, which depend on a speculatively scheduled
700 instruction, cannot be speculatively scheduled along. */
702 if (may_trap_or_fault_p (PATTERN (insn
)))
703 /* If instruction might fault, it cannot be speculatively scheduled.
704 For control speculation it's obvious why and for data speculation
705 it's because the insn might get wrong input if speculation
706 wasn't successful. */
709 if ((ds
& BE_IN_DATA
)
710 && sched_has_condition_p (insn
))
711 /* If this is a predicated instruction, then it cannot be
712 speculatively scheduled. See PR35659. */
719 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
720 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
721 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
722 This function is used to switch sd_iterator to the next list.
723 !!! For internal use only. Might consider moving it to sched-int.h. */
725 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
726 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
728 sd_list_types_def types
= *types_ptr
;
730 if (types
& SD_LIST_HARD_BACK
)
732 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
733 *resolved_p_ptr
= false;
734 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
736 else if (types
& SD_LIST_SPEC_BACK
)
738 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
739 *resolved_p_ptr
= false;
740 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
742 else if (types
& SD_LIST_FORW
)
744 *list_ptr
= INSN_FORW_DEPS (insn
);
745 *resolved_p_ptr
= false;
746 *types_ptr
= types
& ~SD_LIST_FORW
;
748 else if (types
& SD_LIST_RES_BACK
)
750 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
751 *resolved_p_ptr
= true;
752 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
754 else if (types
& SD_LIST_RES_FORW
)
756 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
757 *resolved_p_ptr
= true;
758 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
763 *resolved_p_ptr
= false;
764 *types_ptr
= SD_LIST_NONE
;
768 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
770 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
774 while (list_types
!= SD_LIST_NONE
)
779 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
781 size
+= DEPS_LIST_N_LINKS (list
);
787 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
790 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
792 while (list_types
!= SD_LIST_NONE
)
797 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
798 if (!deps_list_empty_p (list
))
805 /* Initialize data for INSN. */
807 sd_init_insn (rtx insn
)
809 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
810 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
811 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
812 INSN_FORW_DEPS (insn
) = create_deps_list ();
813 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
815 /* ??? It would be nice to allocate dependency caches here. */
818 /* Free data for INSN. */
820 sd_finish_insn (rtx insn
)
822 /* ??? It would be nice to deallocate dependency caches here. */
824 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
825 INSN_HARD_BACK_DEPS (insn
) = NULL
;
827 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
828 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
830 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
831 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
833 free_deps_list (INSN_FORW_DEPS (insn
));
834 INSN_FORW_DEPS (insn
) = NULL
;
836 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
837 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
840 /* Find a dependency between producer PRO and consumer CON.
841 Search through resolved dependency lists if RESOLVED_P is true.
842 If no such dependency is found return NULL,
843 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
844 with an iterator pointing to it. */
846 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
847 sd_iterator_def
*sd_it_ptr
)
849 sd_list_types_def pro_list_type
;
850 sd_list_types_def con_list_type
;
851 sd_iterator_def sd_it
;
853 bool found_p
= false;
857 pro_list_type
= SD_LIST_RES_FORW
;
858 con_list_type
= SD_LIST_RES_BACK
;
862 pro_list_type
= SD_LIST_FORW
;
863 con_list_type
= SD_LIST_BACK
;
866 /* Walk through either back list of INSN or forw list of ELEM
867 depending on which one is shorter. */
868 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
870 /* Find the dep_link with producer PRO in consumer's back_deps. */
871 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
872 if (DEP_PRO (dep
) == pro
)
880 /* Find the dep_link with consumer CON in producer's forw_deps. */
881 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
882 if (DEP_CON (dep
) == con
)
891 if (sd_it_ptr
!= NULL
)
900 /* Find a dependency between producer PRO and consumer CON.
901 Use dependency [if available] to check if dependency is present at all.
902 Search through resolved dependency lists if RESOLVED_P is true.
903 If the dependency or NULL if none found. */
905 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
907 if (true_dependency_cache
!= NULL
)
908 /* Avoiding the list walk below can cut compile times dramatically
911 int elem_luid
= INSN_LUID (pro
);
912 int insn_luid
= INSN_LUID (con
);
914 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
915 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
916 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
917 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
921 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
924 /* Add or update a dependence described by DEP.
925 MEM1 and MEM2, if non-null, correspond to memory locations in case of
928 The function returns a value indicating if an old entry has been changed
929 or a new entry has been added to insn's backward deps.
931 This function merely checks if producer and consumer is the same insn
932 and doesn't create a dep in this case. Actual manipulation of
933 dependence data structures is performed in add_or_update_dep_1. */
934 static enum DEPS_ADJUST_RESULT
935 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
937 rtx_insn
*elem
= DEP_PRO (dep
);
938 rtx_insn
*insn
= DEP_CON (dep
);
940 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
942 /* Don't depend an insn on itself. */
945 if (sched_deps_info
->generate_spec_deps
)
946 /* INSN has an internal dependence, which we can't overcome. */
947 HAS_INTERNAL_DEP (insn
) = 1;
952 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
955 /* Ask dependency caches what needs to be done for dependence DEP.
956 Return DEP_CREATED if new dependence should be created and there is no
957 need to try to find one searching the dependencies lists.
958 Return DEP_PRESENT if there already is a dependence described by DEP and
959 hence nothing is to be done.
960 Return DEP_CHANGED if there already is a dependence, but it should be
961 updated to incorporate additional information from DEP. */
962 static enum DEPS_ADJUST_RESULT
963 ask_dependency_caches (dep_t dep
)
965 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
966 int insn_luid
= INSN_LUID (DEP_CON (dep
));
968 gcc_assert (true_dependency_cache
!= NULL
969 && output_dependency_cache
!= NULL
970 && anti_dependency_cache
!= NULL
971 && control_dependency_cache
!= NULL
);
973 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
975 enum reg_note present_dep_type
;
977 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
978 present_dep_type
= REG_DEP_TRUE
;
979 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
980 present_dep_type
= REG_DEP_OUTPUT
;
981 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
982 present_dep_type
= REG_DEP_ANTI
;
983 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
984 present_dep_type
= REG_DEP_CONTROL
;
986 /* There is no existing dep so it should be created. */
989 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
990 /* DEP does not add anything to the existing dependence. */
995 ds_t present_dep_types
= 0;
997 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
998 present_dep_types
|= DEP_TRUE
;
999 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
1000 present_dep_types
|= DEP_OUTPUT
;
1001 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
1002 present_dep_types
|= DEP_ANTI
;
1003 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
1004 present_dep_types
|= DEP_CONTROL
;
1006 if (present_dep_types
== 0)
1007 /* There is no existing dep so it should be created. */
1010 if (!(current_sched_info
->flags
& DO_SPECULATION
)
1011 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
1013 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
1014 == present_dep_types
)
1015 /* DEP does not add anything to the existing dependence. */
1020 /* Only true dependencies can be data speculative and
1021 only anti dependencies can be control speculative. */
1022 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1023 == present_dep_types
);
1025 /* if (DEP is SPECULATIVE) then
1026 ..we should update DEP_STATUS
1028 ..we should reset existing dep to non-speculative. */
1035 /* Set dependency caches according to DEP. */
1037 set_dependency_caches (dep_t dep
)
1039 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1040 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1042 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1044 switch (DEP_TYPE (dep
))
1047 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1050 case REG_DEP_OUTPUT
:
1051 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1055 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1058 case REG_DEP_CONTROL
:
1059 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1068 ds_t ds
= DEP_STATUS (dep
);
1071 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1072 if (ds
& DEP_OUTPUT
)
1073 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1075 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1076 if (ds
& DEP_CONTROL
)
1077 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1079 if (ds
& SPECULATIVE
)
1081 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1082 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1087 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1088 caches accordingly. */
1090 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1092 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1093 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1095 /* Clear corresponding cache entry because type of the link
1096 may have changed. Keep them if we use_deps_list. */
1097 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1101 case REG_DEP_OUTPUT
:
1102 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1106 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1109 case REG_DEP_CONTROL
:
1110 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1118 set_dependency_caches (dep
);
1121 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1123 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1125 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1126 dep_link_t link
= DEP_NODE_BACK (node
);
1127 dep_t dep
= DEP_NODE_DEP (node
);
1128 rtx_insn
*elem
= DEP_PRO (dep
);
1129 rtx_insn
*insn
= DEP_CON (dep
);
1131 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1133 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1135 if (true_dependency_cache
!= NULL
)
1136 /* Clear the cache entry. */
1137 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1141 /* Update DEP to incorporate information from NEW_DEP.
1142 SD_IT points to DEP in case it should be moved to another list.
1143 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1144 data-speculative dependence should be updated. */
1145 static enum DEPS_ADJUST_RESULT
1146 update_dep (dep_t dep
, dep_t new_dep
,
1147 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1148 rtx mem1 ATTRIBUTE_UNUSED
,
1149 rtx mem2 ATTRIBUTE_UNUSED
)
1151 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1152 enum reg_note old_type
= DEP_TYPE (dep
);
1153 bool was_spec
= dep_spec_p (dep
);
1155 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1156 DEP_MULTIPLE (dep
) = 1;
1158 /* If this is a more restrictive type of dependence than the
1159 existing one, then change the existing dependence to this
1161 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1163 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1167 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1168 /* Update DEP_STATUS. */
1170 ds_t dep_status
= DEP_STATUS (dep
);
1171 ds_t ds
= DEP_STATUS (new_dep
);
1172 ds_t new_status
= ds
| dep_status
;
1174 if (new_status
& SPECULATIVE
)
1176 /* Either existing dep or a dep we're adding or both are
1178 if (!(ds
& SPECULATIVE
)
1179 || !(dep_status
& SPECULATIVE
))
1180 /* The new dep can't be speculative. */
1181 new_status
&= ~SPECULATIVE
;
1184 /* Both are speculative. Merge probabilities. */
1189 dw
= estimate_dep_weak (mem1
, mem2
);
1190 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1193 new_status
= ds_merge (dep_status
, ds
);
1199 if (dep_status
!= ds
)
1201 DEP_STATUS (dep
) = ds
;
1206 if (was_spec
&& !dep_spec_p (dep
))
1207 /* The old dep was speculative, but now it isn't. */
1208 change_spec_dep_to_hard (sd_it
);
1210 if (true_dependency_cache
!= NULL
1211 && res
== DEP_CHANGED
)
1212 update_dependency_caches (dep
, old_type
);
1217 /* Add or update a dependence described by DEP.
1218 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1221 The function returns a value indicating if an old entry has been changed
1222 or a new entry has been added to insn's backward deps or nothing has
1223 been updated at all. */
1224 static enum DEPS_ADJUST_RESULT
1225 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1226 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1228 bool maybe_present_p
= true;
1229 bool present_p
= false;
1231 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1232 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1234 #ifdef ENABLE_CHECKING
1235 check_dep (new_dep
, mem1
!= NULL
);
1238 if (true_dependency_cache
!= NULL
)
1240 switch (ask_dependency_caches (new_dep
))
1244 sd_iterator_def sd_it
;
1246 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1248 resolved_p
, &sd_it
);
1249 DEP_MULTIPLE (present_dep
) = 1;
1253 maybe_present_p
= true;
1258 maybe_present_p
= false;
1268 /* Check that we don't already have this dependence. */
1269 if (maybe_present_p
)
1272 sd_iterator_def sd_it
;
1274 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1276 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1278 resolved_p
, &sd_it
);
1280 if (present_dep
!= NULL
)
1281 /* We found an existing dependency between ELEM and INSN. */
1282 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1284 /* We didn't find a dep, it shouldn't present in the cache. */
1285 gcc_assert (!present_p
);
1288 /* Might want to check one level of transitivity to save conses.
1289 This check should be done in maybe_add_or_update_dep_1.
1290 Since we made it to add_or_update_dep_1, we must create
1291 (or update) a link. */
1293 if (mem1
!= NULL_RTX
)
1295 gcc_assert (sched_deps_info
->generate_spec_deps
);
1296 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1297 estimate_dep_weak (mem1
, mem2
));
1300 sd_add_dep (new_dep
, resolved_p
);
1305 /* Initialize BACK_LIST_PTR with consumer's backward list and
1306 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1307 initialize with lists that hold resolved deps. */
1309 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1310 deps_list_t
*back_list_ptr
,
1311 deps_list_t
*forw_list_ptr
)
1313 rtx_insn
*con
= DEP_CON (dep
);
1317 if (dep_spec_p (dep
))
1318 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1320 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1322 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1326 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1327 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1331 /* Add dependence described by DEP.
1332 If RESOLVED_P is true treat the dependence as a resolved one. */
1334 sd_add_dep (dep_t dep
, bool resolved_p
)
1336 dep_node_t n
= create_dep_node ();
1337 deps_list_t con_back_deps
;
1338 deps_list_t pro_forw_deps
;
1339 rtx_insn
*elem
= DEP_PRO (dep
);
1340 rtx_insn
*insn
= DEP_CON (dep
);
1342 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1344 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1345 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1346 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1348 copy_dep (DEP_NODE_DEP (n
), dep
);
1350 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1352 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1354 #ifdef ENABLE_CHECKING
1355 check_dep (dep
, false);
1358 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1360 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1361 in the bitmap caches of dependency information. */
1362 if (true_dependency_cache
!= NULL
)
1363 set_dependency_caches (dep
);
1366 /* Add or update backward dependence between INSN and ELEM
1367 with given type DEP_TYPE and dep_status DS.
1368 This function is a convenience wrapper. */
1369 enum DEPS_ADJUST_RESULT
1370 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1372 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1375 /* Resolved dependence pointed to by SD_IT.
1376 SD_IT will advance to the next element. */
1378 sd_resolve_dep (sd_iterator_def sd_it
)
1380 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1381 dep_t dep
= DEP_NODE_DEP (node
);
1382 rtx_insn
*pro
= DEP_PRO (dep
);
1383 rtx_insn
*con
= DEP_CON (dep
);
1385 if (dep_spec_p (dep
))
1386 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1387 INSN_RESOLVED_BACK_DEPS (con
));
1389 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1390 INSN_RESOLVED_BACK_DEPS (con
));
1392 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1393 INSN_RESOLVED_FORW_DEPS (pro
));
1396 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1397 pointed to by SD_IT to unresolved state. */
1399 sd_unresolve_dep (sd_iterator_def sd_it
)
1401 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1402 dep_t dep
= DEP_NODE_DEP (node
);
1403 rtx_insn
*pro
= DEP_PRO (dep
);
1404 rtx_insn
*con
= DEP_CON (dep
);
1406 if (dep_spec_p (dep
))
1407 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1408 INSN_SPEC_BACK_DEPS (con
));
1410 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1411 INSN_HARD_BACK_DEPS (con
));
1413 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1414 INSN_FORW_DEPS (pro
));
1417 /* Make TO depend on all the FROM's producers.
1418 If RESOLVED_P is true add dependencies to the resolved lists. */
1420 sd_copy_back_deps (rtx_insn
*to
, rtx_insn
*from
, bool resolved_p
)
1422 sd_list_types_def list_type
;
1423 sd_iterator_def sd_it
;
1426 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1428 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1430 dep_def _new_dep
, *new_dep
= &_new_dep
;
1432 copy_dep (new_dep
, dep
);
1433 DEP_CON (new_dep
) = to
;
1434 sd_add_dep (new_dep
, resolved_p
);
1438 /* Remove a dependency referred to by SD_IT.
1439 SD_IT will point to the next dependence after removal. */
1441 sd_delete_dep (sd_iterator_def sd_it
)
1443 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1444 dep_t dep
= DEP_NODE_DEP (n
);
1445 rtx_insn
*pro
= DEP_PRO (dep
);
1446 rtx_insn
*con
= DEP_CON (dep
);
1447 deps_list_t con_back_deps
;
1448 deps_list_t pro_forw_deps
;
1450 if (true_dependency_cache
!= NULL
)
1452 int elem_luid
= INSN_LUID (pro
);
1453 int insn_luid
= INSN_LUID (con
);
1455 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1456 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1457 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1458 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1460 if (current_sched_info
->flags
& DO_SPECULATION
)
1461 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1464 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1465 &con_back_deps
, &pro_forw_deps
);
1467 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1468 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1470 delete_dep_node (n
);
1473 /* Dump size of the lists. */
1474 #define DUMP_LISTS_SIZE (2)
1476 /* Dump dependencies of the lists. */
1477 #define DUMP_LISTS_DEPS (4)
1479 /* Dump all information about the lists. */
1480 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1482 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1483 FLAGS is a bit mask specifying what information about the lists needs
1485 If FLAGS has the very first bit set, then dump all information about
1486 the lists and propagate this bit into the callee dump functions. */
1488 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1490 sd_iterator_def sd_it
;
1497 flags
|= DUMP_LISTS_ALL
;
1499 fprintf (dump
, "[");
1501 if (flags
& DUMP_LISTS_SIZE
)
1502 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1504 if (flags
& DUMP_LISTS_DEPS
)
1506 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1508 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1509 fprintf (dump
, " ");
1514 /* Dump all information about deps_lists of INSN specified by TYPES
1517 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1519 dump_lists (stderr
, insn
, types
, 1);
1520 fprintf (stderr
, "\n");
1523 /* A wrapper around add_dependence_1, to add a dependence of CON on
1524 PRO, with type DEP_TYPE. This function implements special handling
1525 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1526 the type to REG_DEP_ANTI if we can determine that predication is
1527 impossible; otherwise we add additional true dependencies on the
1528 INSN_COND_DEPS list of the jump (which PRO must be). */
1530 add_dependence (rtx_insn
*con
, rtx_insn
*pro
, enum reg_note dep_type
)
1532 if (dep_type
== REG_DEP_CONTROL
1533 && !(current_sched_info
->flags
& DO_PREDICATION
))
1534 dep_type
= REG_DEP_ANTI
;
1536 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1537 so we must also make the insn dependent on the setter of the
1539 if (dep_type
== REG_DEP_CONTROL
)
1541 rtx_insn
*real_pro
= pro
;
1542 rtx_insn
*other
= real_insn_for_shadow (real_pro
);
1545 if (other
!= NULL_RTX
)
1547 cond
= sched_get_reverse_condition_uncached (real_pro
);
1548 /* Verify that the insn does not use a different value in
1549 the condition register than the one that was present at
1551 if (cond
== NULL_RTX
)
1552 dep_type
= REG_DEP_ANTI
;
1553 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1556 CLEAR_HARD_REG_SET (uses
);
1557 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1558 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1559 dep_type
= REG_DEP_ANTI
;
1561 if (dep_type
== REG_DEP_CONTROL
)
1563 if (sched_verbose
>= 5)
1564 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1565 INSN_UID (real_pro
));
1566 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1567 REG_DEP_TRUE
, false);
1571 add_dependence_1 (con
, pro
, dep_type
);
1574 /* A convenience wrapper to operate on an entire list. HARD should be
1575 true if DEP_NONREG should be set on newly created dependencies. */
1578 add_dependence_list (rtx_insn
*insn
, rtx_insn_list
*list
, int uncond
,
1579 enum reg_note dep_type
, bool hard
)
1581 mark_as_hard
= hard
;
1582 for (; list
; list
= list
->next ())
1584 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, list
->insn ()))
1585 add_dependence (insn
, list
->insn (), dep_type
);
1587 mark_as_hard
= false;
1590 /* Similar, but free *LISTP at the same time, when the context
1591 is not readonly. HARD should be true if DEP_NONREG should be set on
1592 newly created dependencies. */
1595 add_dependence_list_and_free (struct deps_desc
*deps
, rtx_insn
*insn
,
1596 rtx_insn_list
**listp
,
1597 int uncond
, enum reg_note dep_type
, bool hard
)
1599 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1601 /* We don't want to short-circuit dependencies involving debug
1602 insns, because they may cause actual dependencies to be
1604 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1607 free_INSN_LIST_list (listp
);
1610 /* Remove all occurrences of INSN from LIST. Return the number of
1611 occurrences removed. */
1614 remove_from_dependence_list (rtx insn
, rtx_insn_list
**listp
)
1620 if ((*listp
)->insn () == insn
)
1622 remove_free_INSN_LIST_node (listp
);
1627 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1633 /* Same as above, but process two lists at once. */
1635 remove_from_both_dependence_lists (rtx insn
,
1636 rtx_insn_list
**listp
,
1637 rtx_expr_list
**exprp
)
1643 if (XEXP (*listp
, 0) == insn
)
1645 remove_free_INSN_LIST_node (listp
);
1646 remove_free_EXPR_LIST_node (exprp
);
1651 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1652 exprp
= (rtx_expr_list
**)&XEXP (*exprp
, 1);
1658 /* Clear all dependencies for an insn. */
1660 delete_all_dependences (rtx insn
)
1662 sd_iterator_def sd_it
;
1665 /* The below cycle can be optimized to clear the caches and back_deps
1666 in one call but that would provoke duplication of code from
1669 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1670 sd_iterator_cond (&sd_it
, &dep
);)
1671 sd_delete_dep (sd_it
);
1674 /* All insns in a scheduling group except the first should only have
1675 dependencies on the previous insn in the group. So we find the
1676 first instruction in the scheduling group by walking the dependence
1677 chains backwards. Then we add the dependencies for the group to
1678 the previous nonnote insn. */
1681 chain_to_prev_insn (rtx_insn
*insn
)
1683 sd_iterator_def sd_it
;
1685 rtx_insn
*prev_nonnote
;
1687 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1690 rtx_insn
*pro
= DEP_PRO (dep
);
1694 i
= prev_nonnote_insn (i
);
1698 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1700 if (! sched_insns_conditions_mutex_p (i
, pro
))
1701 add_dependence (i
, pro
, DEP_TYPE (dep
));
1705 delete_all_dependences (insn
);
1707 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1708 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1709 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1710 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1713 /* Process an insn's memory dependencies. There are four kinds of
1716 (0) read dependence: read follows read
1717 (1) true dependence: read follows write
1718 (2) output dependence: write follows write
1719 (3) anti dependence: write follows read
1721 We are careful to build only dependencies which actually exist, and
1722 use transitivity to avoid building too many links. */
1724 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1725 The MEM is a memory reference contained within INSN, which we are saving
1726 so that we can do memory aliasing on it. */
1729 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1730 rtx_insn
*insn
, rtx mem
)
1732 rtx_insn_list
**insn_list
;
1733 rtx_insn_list
*insn_node
;
1734 rtx_expr_list
**mem_list
;
1735 rtx_expr_list
*mem_node
;
1737 gcc_assert (!deps
->readonly
);
1740 insn_list
= &deps
->pending_read_insns
;
1741 mem_list
= &deps
->pending_read_mems
;
1742 if (!DEBUG_INSN_P (insn
))
1743 deps
->pending_read_list_length
++;
1747 insn_list
= &deps
->pending_write_insns
;
1748 mem_list
= &deps
->pending_write_mems
;
1749 deps
->pending_write_list_length
++;
1752 insn_node
= alloc_INSN_LIST (insn
, *insn_list
);
1753 *insn_list
= insn_node
;
1755 if (sched_deps_info
->use_cselib
)
1757 mem
= shallow_copy_rtx (mem
);
1758 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1759 GET_MODE (mem
), insn
);
1761 mem_node
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1762 *mem_list
= mem_node
;
1765 /* Make a dependency between every memory reference on the pending lists
1766 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1767 dependencies for a read operation, similarly with FOR_WRITE. */
1770 flush_pending_lists (struct deps_desc
*deps
, rtx_insn
*insn
, int for_read
,
1775 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1776 1, REG_DEP_ANTI
, true);
1777 if (!deps
->readonly
)
1779 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1780 deps
->pending_read_list_length
= 0;
1784 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1785 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1788 add_dependence_list_and_free (deps
, insn
,
1789 &deps
->last_pending_memory_flush
, 1,
1790 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1793 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1794 REG_DEP_ANTI
, true);
1796 if (DEBUG_INSN_P (insn
))
1799 free_INSN_LIST_list (&deps
->pending_read_insns
);
1800 free_INSN_LIST_list (&deps
->pending_write_insns
);
1801 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1802 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1805 if (!deps
->readonly
)
1807 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1808 deps
->pending_write_list_length
= 0;
1810 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1811 deps
->pending_flush_length
= 1;
1813 mark_as_hard
= false;
1816 /* Instruction which dependencies we are analyzing. */
1817 static rtx_insn
*cur_insn
= NULL
;
1819 /* Implement hooks for haifa scheduler. */
1822 haifa_start_insn (rtx_insn
*insn
)
1824 gcc_assert (insn
&& !cur_insn
);
1830 haifa_finish_insn (void)
1836 haifa_note_reg_set (int regno
)
1838 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1842 haifa_note_reg_clobber (int regno
)
1844 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1848 haifa_note_reg_use (int regno
)
1850 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1854 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx_insn
*pending_insn
, ds_t ds
)
1856 if (!(ds
& SPECULATIVE
))
1859 pending_mem
= NULL_RTX
;
1862 gcc_assert (ds
& BEGIN_DATA
);
1865 dep_def _dep
, *dep
= &_dep
;
1867 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1868 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1869 DEP_NONREG (dep
) = 1;
1870 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1876 haifa_note_dep (rtx_insn
*elem
, ds_t ds
)
1881 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1883 DEP_NONREG (dep
) = 1;
1884 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1888 note_reg_use (int r
)
1890 if (sched_deps_info
->note_reg_use
)
1891 sched_deps_info
->note_reg_use (r
);
1895 note_reg_set (int r
)
1897 if (sched_deps_info
->note_reg_set
)
1898 sched_deps_info
->note_reg_set (r
);
1902 note_reg_clobber (int r
)
1904 if (sched_deps_info
->note_reg_clobber
)
1905 sched_deps_info
->note_reg_clobber (r
);
1909 note_mem_dep (rtx m1
, rtx m2
, rtx_insn
*e
, ds_t ds
)
1911 if (sched_deps_info
->note_mem_dep
)
1912 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1916 note_dep (rtx_insn
*e
, ds_t ds
)
1918 if (sched_deps_info
->note_dep
)
1919 sched_deps_info
->note_dep (e
, ds
);
1922 /* Return corresponding to DS reg_note. */
1927 return REG_DEP_TRUE
;
1928 else if (ds
& DEP_OUTPUT
)
1929 return REG_DEP_OUTPUT
;
1930 else if (ds
& DEP_ANTI
)
1931 return REG_DEP_ANTI
;
1934 gcc_assert (ds
& DEP_CONTROL
);
1935 return REG_DEP_CONTROL
;
1941 /* Functions for computation of info needed for register pressure
1942 sensitive insn scheduling. */
1945 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1946 static struct reg_use_data
*
1947 create_insn_reg_use (int regno
, rtx_insn
*insn
)
1949 struct reg_use_data
*use
;
1951 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1954 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1955 INSN_REG_USE_LIST (insn
) = use
;
1959 /* Allocate reg_set_data structure for REGNO and INSN. */
1961 create_insn_reg_set (int regno
, rtx insn
)
1963 struct reg_set_data
*set
;
1965 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1968 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1969 INSN_REG_SET_LIST (insn
) = set
;
1972 /* Set up insn register uses for INSN and dependency context DEPS. */
1974 setup_insn_reg_uses (struct deps_desc
*deps
, rtx_insn
*insn
)
1977 reg_set_iterator rsi
;
1978 struct reg_use_data
*use
, *use2
, *next
;
1979 struct deps_reg
*reg_last
;
1981 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1983 if (i
< FIRST_PSEUDO_REGISTER
1984 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1987 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1988 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1989 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1990 /* Ignore use which is not dying. */
1993 use
= create_insn_reg_use (i
, insn
);
1994 use
->next_regno_use
= use
;
1995 reg_last
= &deps
->reg_last
[i
];
1997 /* Create the cycle list of uses. */
1998 for (rtx_insn_list
*list
= reg_last
->uses
; list
; list
= list
->next ())
2000 use2
= create_insn_reg_use (i
, list
->insn ());
2001 next
= use
->next_regno_use
;
2002 use
->next_regno_use
= use2
;
2003 use2
->next_regno_use
= next
;
2008 /* Register pressure info for the currently processed insn. */
2009 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
2011 /* Return TRUE if INSN has the use structure for REGNO. */
2013 insn_use_p (rtx insn
, int regno
)
2015 struct reg_use_data
*use
;
2017 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2018 if (use
->regno
== regno
)
2023 /* Update the register pressure info after birth of pseudo register REGNO
2024 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2025 the register is in clobber or unused after the insn. */
2027 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2032 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2033 cl
= sched_regno_pressure_class
[regno
];
2036 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2039 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2040 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2044 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2045 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2049 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2050 reg_pressure_info
[cl
].set_increase
= new_incr
;
2051 if (! insn_use_p (insn
, regno
))
2052 reg_pressure_info
[cl
].change
+= incr
;
2053 create_insn_reg_set (regno
, insn
);
2055 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2059 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2060 hard registers involved in the birth. */
2062 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2063 bool clobber_p
, bool unused_p
)
2066 int new_incr
, last
= regno
+ nregs
;
2068 while (regno
< last
)
2070 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2071 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2073 cl
= sched_regno_pressure_class
[regno
];
2078 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2079 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2083 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2084 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2088 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2089 reg_pressure_info
[cl
].set_increase
= new_incr
;
2090 if (! insn_use_p (insn
, regno
))
2091 reg_pressure_info
[cl
].change
+= 1;
2092 create_insn_reg_set (regno
, insn
);
2094 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2101 /* Update the register pressure info after birth of pseudo or hard
2102 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2103 correspondingly that the register is in clobber or unused after the
2106 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2110 if (GET_CODE (reg
) == SUBREG
)
2111 reg
= SUBREG_REG (reg
);
2116 regno
= REGNO (reg
);
2117 if (regno
< FIRST_PSEUDO_REGISTER
)
2118 mark_insn_hard_regno_birth (insn
, regno
,
2119 hard_regno_nregs
[regno
][GET_MODE (reg
)],
2120 clobber_p
, unused_p
);
2122 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2125 /* Update the register pressure info after death of pseudo register
2128 mark_pseudo_death (int regno
)
2133 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2134 cl
= sched_regno_pressure_class
[regno
];
2137 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2138 reg_pressure_info
[cl
].change
-= incr
;
2142 /* Like mark_pseudo_death except that NREGS saying how many hard
2143 registers involved in the death. */
2145 mark_hard_regno_death (int regno
, int nregs
)
2148 int last
= regno
+ nregs
;
2150 while (regno
< last
)
2152 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2153 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2155 cl
= sched_regno_pressure_class
[regno
];
2157 reg_pressure_info
[cl
].change
-= 1;
2163 /* Update the register pressure info after death of pseudo or hard
2166 mark_reg_death (rtx reg
)
2170 if (GET_CODE (reg
) == SUBREG
)
2171 reg
= SUBREG_REG (reg
);
2176 regno
= REGNO (reg
);
2177 if (regno
< FIRST_PSEUDO_REGISTER
)
2178 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
2180 mark_pseudo_death (regno
);
2183 /* Process SETTER of REG. DATA is an insn containing the setter. */
2185 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2187 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2190 ((rtx
) data
, reg
, false,
2191 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2194 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2196 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2198 if (GET_CODE (setter
) == CLOBBER
)
2199 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2202 /* Set up reg pressure info related to INSN. */
2204 init_insn_reg_pressure_info (rtx insn
)
2208 static struct reg_pressure_data
*pressure_info
;
2211 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2213 if (! INSN_P (insn
))
2216 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2218 cl
= ira_pressure_classes
[i
];
2219 reg_pressure_info
[cl
].clobber_increase
= 0;
2220 reg_pressure_info
[cl
].set_increase
= 0;
2221 reg_pressure_info
[cl
].unused_set_increase
= 0;
2222 reg_pressure_info
[cl
].change
= 0;
2225 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2227 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2230 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2231 if (REG_NOTE_KIND (link
) == REG_INC
)
2232 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2235 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2236 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2237 mark_reg_death (XEXP (link
, 0));
2239 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2241 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2242 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2243 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2245 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2247 cl
= ira_pressure_classes
[i
];
2248 pressure_info
[i
].clobber_increase
2249 = reg_pressure_info
[cl
].clobber_increase
;
2250 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2251 pressure_info
[i
].unused_set_increase
2252 = reg_pressure_info
[cl
].unused_set_increase
;
2253 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2260 /* Internal variable for sched_analyze_[12] () functions.
2261 If it is nonzero, this means that sched_analyze_[12] looks
2262 at the most toplevel SET. */
2263 static bool can_start_lhs_rhs_p
;
2265 /* Extend reg info for the deps context DEPS given that
2266 we have just generated a register numbered REGNO. */
2268 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2270 int max_regno
= regno
+ 1;
2272 gcc_assert (!reload_completed
);
2274 /* In a readonly context, it would not hurt to extend info,
2275 but it should not be needed. */
2276 if (reload_completed
&& deps
->readonly
)
2278 deps
->max_reg
= max_regno
;
2282 if (max_regno
> deps
->max_reg
)
2284 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2286 memset (&deps
->reg_last
[deps
->max_reg
],
2287 0, (max_regno
- deps
->max_reg
)
2288 * sizeof (struct deps_reg
));
2289 deps
->max_reg
= max_regno
;
2293 /* Extends REG_INFO_P if needed. */
2295 maybe_extend_reg_info_p (void)
2297 /* Extend REG_INFO_P, if needed. */
2298 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2300 size_t new_reg_info_p_size
= max_regno
+ 128;
2302 gcc_assert (!reload_completed
&& sel_sched_p ());
2304 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2305 new_reg_info_p_size
,
2307 sizeof (*reg_info_p
));
2308 reg_info_p_size
= new_reg_info_p_size
;
2312 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2313 The type of the reference is specified by REF and can be SET,
2314 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2317 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2318 enum rtx_code ref
, rtx_insn
*insn
)
2320 /* We could emit new pseudos in renaming. Extend the reg structures. */
2321 if (!reload_completed
&& sel_sched_p ()
2322 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2323 extend_deps_reg_info (deps
, regno
);
2325 maybe_extend_reg_info_p ();
2327 /* A hard reg in a wide mode may really be multiple registers.
2328 If so, mark all of them just like the first. */
2329 if (regno
< FIRST_PSEUDO_REGISTER
)
2331 int i
= hard_regno_nregs
[regno
][mode
];
2335 note_reg_set (regno
+ i
);
2337 else if (ref
== USE
)
2340 note_reg_use (regno
+ i
);
2345 note_reg_clobber (regno
+ i
);
2349 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2350 it does not reload. Ignore these as they have served their
2352 else if (regno
>= deps
->max_reg
)
2354 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2355 gcc_assert (code
== USE
|| code
== CLOBBER
);
2361 note_reg_set (regno
);
2362 else if (ref
== USE
)
2363 note_reg_use (regno
);
2365 note_reg_clobber (regno
);
2367 /* Pseudos that are REG_EQUIV to something may be replaced
2368 by that during reloading. We need only add dependencies for
2369 the address in the REG_EQUIV note. */
2370 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2372 rtx t
= get_reg_known_value (regno
);
2374 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2377 /* Don't let it cross a call after scheduling if it doesn't
2378 already cross one. */
2379 if (REG_N_CALLS_CROSSED (regno
) == 0)
2381 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2382 deps
->sched_before_next_call
2383 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2385 add_dependence_list (insn
, deps
->last_function_call
, 1,
2386 REG_DEP_ANTI
, false);
2391 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2392 rtx, X, creating all dependencies generated by the write to the
2393 destination of X, and reads of everything mentioned. */
2396 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2398 rtx dest
= XEXP (x
, 0);
2399 enum rtx_code code
= GET_CODE (x
);
2400 bool cslr_p
= can_start_lhs_rhs_p
;
2402 can_start_lhs_rhs_p
= false;
2408 if (cslr_p
&& sched_deps_info
->start_lhs
)
2409 sched_deps_info
->start_lhs (dest
);
2411 if (GET_CODE (dest
) == PARALLEL
)
2415 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2416 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2417 sched_analyze_1 (deps
,
2418 gen_rtx_CLOBBER (VOIDmode
,
2419 XEXP (XVECEXP (dest
, 0, i
), 0)),
2422 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2423 sched_deps_info
->finish_lhs ();
2427 can_start_lhs_rhs_p
= cslr_p
;
2429 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2431 can_start_lhs_rhs_p
= false;
2437 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2438 || GET_CODE (dest
) == ZERO_EXTRACT
)
2440 if (GET_CODE (dest
) == STRICT_LOW_PART
2441 || GET_CODE (dest
) == ZERO_EXTRACT
2442 || df_read_modify_subreg_p (dest
))
2444 /* These both read and modify the result. We must handle
2445 them as writes to get proper dependencies for following
2446 instructions. We must handle them as reads to get proper
2447 dependencies from this to previous instructions.
2448 Thus we need to call sched_analyze_2. */
2450 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2452 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2454 /* The second and third arguments are values read by this insn. */
2455 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2456 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2458 dest
= XEXP (dest
, 0);
2463 int regno
= REGNO (dest
);
2464 enum machine_mode mode
= GET_MODE (dest
);
2466 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2469 /* Treat all writes to a stack register as modifying the TOS. */
2470 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2472 /* Avoid analyzing the same register twice. */
2473 if (regno
!= FIRST_STACK_REG
)
2474 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2476 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2481 else if (MEM_P (dest
))
2483 /* Writing memory. */
2486 if (sched_deps_info
->use_cselib
)
2488 enum machine_mode address_mode
= get_address_mode (dest
);
2490 t
= shallow_copy_rtx (dest
);
2491 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2492 GET_MODE (t
), insn
);
2494 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2499 /* Pending lists can't get larger with a readonly context. */
2501 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2502 > MAX_PENDING_LIST_LENGTH
))
2504 /* Flush all pending reads and writes to prevent the pending lists
2505 from getting any larger. Insn scheduling runs too slowly when
2506 these lists get long. When compiling GCC with itself,
2507 this flush occurs 8 times for sparc, and 10 times for m88k using
2508 the default value of 32. */
2509 flush_pending_lists (deps
, insn
, false, true);
2513 rtx_insn_list
*pending
;
2514 rtx_expr_list
*pending_mem
;
2516 pending
= deps
->pending_read_insns
;
2517 pending_mem
= deps
->pending_read_mems
;
2520 if (anti_dependence (pending_mem
->element (), t
)
2521 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2522 note_mem_dep (t
, pending_mem
->element (), pending
->insn (),
2525 pending
= pending
->next ();
2526 pending_mem
= pending_mem
->next ();
2529 pending
= deps
->pending_write_insns
;
2530 pending_mem
= deps
->pending_write_mems
;
2533 if (output_dependence (pending_mem
->element (), t
)
2534 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2535 note_mem_dep (t
, pending_mem
->element (),
2539 pending
= pending
->next ();
2540 pending_mem
= pending_mem
-> next ();
2543 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2544 REG_DEP_ANTI
, true);
2545 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2546 REG_DEP_CONTROL
, true);
2548 if (!deps
->readonly
)
2549 add_insn_mem_dependence (deps
, false, insn
, dest
);
2551 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2554 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2555 sched_deps_info
->finish_lhs ();
2557 /* Analyze reads. */
2558 if (GET_CODE (x
) == SET
)
2560 can_start_lhs_rhs_p
= cslr_p
;
2562 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2564 can_start_lhs_rhs_p
= false;
2568 /* Analyze the uses of memory and registers in rtx X in INSN. */
2570 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2576 bool cslr_p
= can_start_lhs_rhs_p
;
2578 can_start_lhs_rhs_p
= false;
2584 if (cslr_p
&& sched_deps_info
->start_rhs
)
2585 sched_deps_info
->start_rhs (x
);
2587 code
= GET_CODE (x
);
2595 /* Ignore constants. */
2596 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2597 sched_deps_info
->finish_rhs ();
2603 /* User of CC0 depends on immediately preceding insn. */
2604 SCHED_GROUP_P (insn
) = 1;
2605 /* Don't move CC0 setter to another block (it can set up the
2606 same flag for previous CC0 users which is safe). */
2607 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2609 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2610 sched_deps_info
->finish_rhs ();
2617 int regno
= REGNO (x
);
2618 enum machine_mode mode
= GET_MODE (x
);
2620 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2623 /* Treat all reads of a stack register as modifying the TOS. */
2624 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2626 /* Avoid analyzing the same register twice. */
2627 if (regno
!= FIRST_STACK_REG
)
2628 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2629 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2633 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2634 sched_deps_info
->finish_rhs ();
2641 /* Reading memory. */
2643 rtx_insn_list
*pending
;
2644 rtx_expr_list
*pending_mem
;
2647 if (sched_deps_info
->use_cselib
)
2649 enum machine_mode address_mode
= get_address_mode (t
);
2651 t
= shallow_copy_rtx (t
);
2652 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2653 GET_MODE (t
), insn
);
2655 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2659 if (!DEBUG_INSN_P (insn
))
2662 pending
= deps
->pending_read_insns
;
2663 pending_mem
= deps
->pending_read_mems
;
2666 if (read_dependence (pending_mem
->element (), t
)
2667 && ! sched_insns_conditions_mutex_p (insn
,
2669 note_mem_dep (t
, pending_mem
->element (),
2673 pending
= pending
->next ();
2674 pending_mem
= pending_mem
->next ();
2677 pending
= deps
->pending_write_insns
;
2678 pending_mem
= deps
->pending_write_mems
;
2681 if (true_dependence (pending_mem
->element (), VOIDmode
, t
)
2682 && ! sched_insns_conditions_mutex_p (insn
,
2684 note_mem_dep (t
, pending_mem
->element (),
2686 sched_deps_info
->generate_spec_deps
2687 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2689 pending
= pending
->next ();
2690 pending_mem
= pending_mem
->next ();
2693 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2694 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)),
2697 for (u
= deps
->pending_jump_insns
; u
; u
= XEXP (u
, 1))
2698 if (deps_may_trap_p (x
))
2700 if ((sched_deps_info
->generate_spec_deps
)
2701 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2703 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2706 note_dep (as_a
<rtx_insn
*> (XEXP (u
, 0)), ds
);
2709 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)),
2714 /* Always add these dependencies to pending_reads, since
2715 this insn may be followed by a write. */
2716 if (!deps
->readonly
)
2718 if ((deps
->pending_read_list_length
2719 + deps
->pending_write_list_length
)
2720 > MAX_PENDING_LIST_LENGTH
2721 && !DEBUG_INSN_P (insn
))
2722 flush_pending_lists (deps
, insn
, true, true);
2723 add_insn_mem_dependence (deps
, true, insn
, x
);
2726 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2728 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2729 sched_deps_info
->finish_rhs ();
2734 /* Force pending stores to memory in case a trap handler needs them. */
2736 flush_pending_lists (deps
, insn
, true, false);
2740 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2741 reg_pending_barrier
= TRUE_BARRIER
;
2742 /* Prefetch insn contains addresses only. So if the prefetch
2743 address has no registers, there will be no dependencies on
2744 the prefetch insn. This is wrong with result code
2745 correctness point of view as such prefetch can be moved below
2746 a jump insn which usually generates MOVE_BARRIER preventing
2747 to move insns containing registers or memories through the
2748 barrier. It is also wrong with generated code performance
2749 point of view as prefetch withouth dependecies will have a
2750 tendency to be issued later instead of earlier. It is hard
2751 to generate accurate dependencies for prefetch insns as
2752 prefetch has only the start address but it is better to have
2753 something than nothing. */
2754 if (!deps
->readonly
)
2756 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2757 if (sched_deps_info
->use_cselib
)
2758 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2759 add_insn_mem_dependence (deps
, true, insn
, x
);
2763 case UNSPEC_VOLATILE
:
2764 flush_pending_lists (deps
, insn
, true, true);
2770 /* Traditional and volatile asm instructions must be considered to use
2771 and clobber all hard registers, all pseudo-registers and all of
2772 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2774 Consider for instance a volatile asm that changes the fpu rounding
2775 mode. An insn should not be moved across this even if it only uses
2776 pseudo-regs because it might give an incorrectly rounded result. */
2777 if ((code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2778 && !DEBUG_INSN_P (insn
))
2779 reg_pending_barrier
= TRUE_BARRIER
;
2781 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2782 We can not just fall through here since then we would be confused
2783 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2784 traditional asms unlike their normal usage. */
2786 if (code
== ASM_OPERANDS
)
2788 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2789 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2791 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2792 sched_deps_info
->finish_rhs ();
2803 /* These both read and modify the result. We must handle them as writes
2804 to get proper dependencies for following instructions. We must handle
2805 them as reads to get proper dependencies from this to previous
2806 instructions. Thus we need to pass them to both sched_analyze_1
2807 and sched_analyze_2. We must call sched_analyze_2 first in order
2808 to get the proper antecedent for the read. */
2809 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2810 sched_analyze_1 (deps
, x
, insn
);
2812 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2813 sched_deps_info
->finish_rhs ();
2819 /* op0 = op0 + op1 */
2820 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2821 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2822 sched_analyze_1 (deps
, x
, insn
);
2824 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2825 sched_deps_info
->finish_rhs ();
2833 /* Other cases: walk the insn. */
2834 fmt
= GET_RTX_FORMAT (code
);
2835 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2838 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2839 else if (fmt
[i
] == 'E')
2840 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2841 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2844 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2845 sched_deps_info
->finish_rhs ();
2848 /* Try to group two fuseable insns together to prevent scheduler
2849 from scheduling them apart. */
2852 sched_macro_fuse_insns (rtx_insn
*insn
)
2856 if (any_condjump_p (insn
))
2858 unsigned int condreg1
, condreg2
;
2860 targetm
.fixed_condition_code_regs (&condreg1
, &condreg2
);
2861 cc_reg_1
= gen_rtx_REG (CCmode
, condreg1
);
2862 prev
= prev_nonnote_nondebug_insn (insn
);
2863 if (!reg_referenced_p (cc_reg_1
, PATTERN (insn
))
2865 || !modified_in_p (cc_reg_1
, prev
))
2870 rtx insn_set
= single_set (insn
);
2872 prev
= prev_nonnote_nondebug_insn (insn
);
2875 || !single_set (prev
)
2876 || !modified_in_p (SET_DEST (insn_set
), prev
))
2881 if (targetm
.sched
.macro_fusion_pair_p (prev
, insn
))
2882 SCHED_GROUP_P (insn
) = 1;
2886 /* Analyze an INSN with pattern X to find all dependencies. */
2888 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2890 RTX_CODE code
= GET_CODE (x
);
2893 reg_set_iterator rsi
;
2895 if (! reload_completed
)
2899 extract_insn (insn
);
2900 preprocess_constraints (insn
);
2901 ira_implicitly_set_insn_hard_regs (&temp
);
2902 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2903 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2906 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2909 /* Group compare and branch insns for macro-fusion. */
2910 if (targetm
.sched
.macro_fusion_p
2911 && targetm
.sched
.macro_fusion_p ())
2912 sched_macro_fuse_insns (insn
);
2915 /* Avoid moving trapping instructions across function calls that might
2916 not always return. */
2917 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2918 1, REG_DEP_ANTI
, true);
2920 /* We must avoid creating a situation in which two successors of the
2921 current block have different unwind info after scheduling. If at any
2922 point the two paths re-join this leads to incorrect unwind info. */
2923 /* ??? There are certain situations involving a forced frame pointer in
2924 which, with extra effort, we could fix up the unwind info at a later
2925 CFG join. However, it seems better to notice these cases earlier
2926 during prologue generation and avoid marking the frame pointer setup
2927 as frame-related at all. */
2928 if (RTX_FRAME_RELATED_P (insn
))
2930 /* Make sure prologue insn is scheduled before next jump. */
2931 deps
->sched_before_next_jump
2932 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2934 /* Make sure epilogue insn is scheduled after preceding jumps. */
2935 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2939 if (code
== COND_EXEC
)
2941 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2943 /* ??? Should be recording conditions so we reduce the number of
2944 false dependencies. */
2945 x
= COND_EXEC_CODE (x
);
2946 code
= GET_CODE (x
);
2948 if (code
== SET
|| code
== CLOBBER
)
2950 sched_analyze_1 (deps
, x
, insn
);
2952 /* Bare clobber insns are used for letting life analysis, reg-stack
2953 and others know that a value is dead. Depend on the last call
2954 instruction so that reg-stack won't get confused. */
2955 if (code
== CLOBBER
)
2956 add_dependence_list (insn
, deps
->last_function_call
, 1,
2957 REG_DEP_OUTPUT
, true);
2959 else if (code
== PARALLEL
)
2961 for (i
= XVECLEN (x
, 0); i
--;)
2963 rtx sub
= XVECEXP (x
, 0, i
);
2964 code
= GET_CODE (sub
);
2966 if (code
== COND_EXEC
)
2968 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2969 sub
= COND_EXEC_CODE (sub
);
2970 code
= GET_CODE (sub
);
2972 if (code
== SET
|| code
== CLOBBER
)
2973 sched_analyze_1 (deps
, sub
, insn
);
2975 sched_analyze_2 (deps
, sub
, insn
);
2979 sched_analyze_2 (deps
, x
, insn
);
2981 /* Mark registers CLOBBERED or used by called function. */
2984 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2986 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2987 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2988 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2989 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2991 /* Don't schedule anything after a tail call, tail call needs
2992 to use at least all call-saved registers. */
2993 if (SIBLING_CALL_P (insn
))
2994 reg_pending_barrier
= TRUE_BARRIER
;
2995 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2996 reg_pending_barrier
= MOVE_BARRIER
;
3002 next
= next_nonnote_nondebug_insn (insn
);
3003 if (next
&& BARRIER_P (next
))
3004 reg_pending_barrier
= MOVE_BARRIER
;
3007 rtx_insn_list
*pending
;
3008 rtx_expr_list
*pending_mem
;
3010 if (sched_deps_info
->compute_jump_reg_dependencies
)
3012 (*sched_deps_info
->compute_jump_reg_dependencies
)
3013 (insn
, reg_pending_control_uses
);
3015 /* Make latency of jump equal to 0 by using anti-dependence. */
3016 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3018 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3019 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
3021 add_dependence_list (insn
, reg_last
->implicit_sets
,
3022 0, REG_DEP_ANTI
, false);
3023 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3024 REG_DEP_ANTI
, false);
3028 /* All memory writes and volatile reads must happen before the
3029 jump. Non-volatile reads must happen before the jump iff
3030 the result is needed by the above register used mask. */
3032 pending
= deps
->pending_write_insns
;
3033 pending_mem
= deps
->pending_write_mems
;
3036 if (! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3037 add_dependence (insn
, pending
->insn (),
3039 pending
= pending
->next ();
3040 pending_mem
= pending_mem
->next ();
3043 pending
= deps
->pending_read_insns
;
3044 pending_mem
= deps
->pending_read_mems
;
3047 if (MEM_VOLATILE_P (pending_mem
->element ())
3048 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3049 add_dependence (insn
, pending
->insn (),
3051 pending
= pending
->next ();
3052 pending_mem
= pending_mem
->next ();
3055 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
3056 REG_DEP_ANTI
, true);
3057 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
3058 REG_DEP_ANTI
, true);
3062 /* If this instruction can throw an exception, then moving it changes
3063 where block boundaries fall. This is mighty confusing elsewhere.
3064 Therefore, prevent such an instruction from being moved. Same for
3065 non-jump instructions that define block boundaries.
3066 ??? Unclear whether this is still necessary in EBB mode. If not,
3067 add_branch_dependences should be adjusted for RGN mode instead. */
3068 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
3069 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
3070 reg_pending_barrier
= MOVE_BARRIER
;
3072 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
3074 setup_insn_reg_uses (deps
, insn
);
3075 init_insn_reg_pressure_info (insn
);
3078 /* Add register dependencies for insn. */
3079 if (DEBUG_INSN_P (insn
))
3081 rtx_insn
*prev
= deps
->last_debug_insn
;
3084 if (!deps
->readonly
)
3085 deps
->last_debug_insn
= insn
;
3088 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3090 add_dependence_list (insn
, deps
->last_function_call
, 1,
3091 REG_DEP_ANTI
, false);
3093 if (!sel_sched_p ())
3094 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3095 add_dependence (insn
, as_a
<rtx_insn
*> (XEXP (u
, 0)), REG_DEP_ANTI
);
3097 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3099 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3100 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3101 /* There's no point in making REG_DEP_CONTROL dependencies for
3103 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3106 if (!deps
->readonly
)
3107 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3109 CLEAR_REG_SET (reg_pending_uses
);
3111 /* Quite often, a debug insn will refer to stuff in the
3112 previous instruction, but the reason we want this
3113 dependency here is to make sure the scheduler doesn't
3114 gratuitously move a debug insn ahead. This could dirty
3115 DF flags and cause additional analysis that wouldn't have
3116 occurred in compilation without debug insns, and such
3117 additional analysis can modify the generated code. */
3118 prev
= PREV_INSN (insn
);
3120 if (prev
&& NONDEBUG_INSN_P (prev
))
3121 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3125 regset_head set_or_clobbered
;
3127 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3129 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3130 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3131 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3133 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3136 if (!deps
->readonly
)
3138 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3139 reg_last
->uses_length
++;
3143 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3144 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3146 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3147 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3148 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3149 REG_DEP_ANTI
, false);
3150 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3153 if (!deps
->readonly
)
3155 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3156 reg_last
->uses_length
++;
3160 if (targetm
.sched
.exposed_pipeline
)
3162 INIT_REG_SET (&set_or_clobbered
);
3163 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3165 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3167 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3169 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3171 rtx other
= XEXP (list
, 0);
3172 if (INSN_CACHED_COND (other
) != const_true_rtx
3173 && refers_to_regno_p (i
, i
+ 1, INSN_CACHED_COND (other
), NULL
))
3174 INSN_CACHED_COND (other
) = const_true_rtx
;
3179 /* If the current insn is conditional, we can't free any
3181 if (sched_has_condition_p (insn
))
3183 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3185 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3186 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3188 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3189 REG_DEP_ANTI
, false);
3190 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3192 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3193 REG_DEP_CONTROL
, false);
3195 if (!deps
->readonly
)
3198 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3199 reg_last
->clobbers_length
++;
3202 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3204 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3205 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3207 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3208 REG_DEP_ANTI
, false);
3209 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3211 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3213 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3214 REG_DEP_CONTROL
, false);
3216 if (!deps
->readonly
)
3217 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3222 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3224 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3225 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
3226 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
3228 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3229 REG_DEP_OUTPUT
, false);
3230 add_dependence_list_and_free (deps
, insn
,
3231 ®_last
->implicit_sets
, 0,
3232 REG_DEP_ANTI
, false);
3233 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3234 REG_DEP_ANTI
, false);
3235 add_dependence_list_and_free (deps
, insn
,
3236 ®_last
->control_uses
, 0,
3237 REG_DEP_ANTI
, false);
3238 add_dependence_list_and_free (deps
, insn
,
3239 ®_last
->clobbers
, 0,
3240 REG_DEP_OUTPUT
, false);
3242 if (!deps
->readonly
)
3244 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3245 reg_last
->clobbers_length
= 0;
3246 reg_last
->uses_length
= 0;
3251 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3253 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3254 REG_DEP_ANTI
, false);
3255 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3257 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3258 REG_DEP_CONTROL
, false);
3261 if (!deps
->readonly
)
3263 reg_last
->clobbers_length
++;
3265 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3268 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3270 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3272 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3273 REG_DEP_OUTPUT
, false);
3274 add_dependence_list_and_free (deps
, insn
,
3275 ®_last
->implicit_sets
,
3276 0, REG_DEP_ANTI
, false);
3277 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3278 REG_DEP_OUTPUT
, false);
3279 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3280 REG_DEP_ANTI
, false);
3281 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3282 REG_DEP_CONTROL
, false);
3284 if (!deps
->readonly
)
3286 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3287 reg_last
->uses_length
= 0;
3288 reg_last
->clobbers_length
= 0;
3292 if (!deps
->readonly
)
3294 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3296 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3297 reg_last
->control_uses
3298 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3303 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3304 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3306 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3307 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3308 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3309 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3310 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3313 if (!deps
->readonly
)
3314 reg_last
->implicit_sets
3315 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3318 if (!deps
->readonly
)
3320 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3321 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3322 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3323 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3324 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3325 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3326 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3328 /* Set up the pending barrier found. */
3329 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3332 CLEAR_REG_SET (reg_pending_uses
);
3333 CLEAR_REG_SET (reg_pending_clobbers
);
3334 CLEAR_REG_SET (reg_pending_sets
);
3335 CLEAR_REG_SET (reg_pending_control_uses
);
3336 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3337 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3339 /* Add dependencies if a scheduling barrier was found. */
3340 if (reg_pending_barrier
)
3342 /* In the case of barrier the most added dependencies are not
3343 real, so we use anti-dependence here. */
3344 if (sched_has_condition_p (insn
))
3346 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3348 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3349 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3351 add_dependence_list (insn
, reg_last
->sets
, 0,
3352 reg_pending_barrier
== TRUE_BARRIER
3353 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3354 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3355 REG_DEP_ANTI
, true);
3356 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3357 reg_pending_barrier
== TRUE_BARRIER
3358 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3363 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3365 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3366 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3367 REG_DEP_ANTI
, true);
3368 add_dependence_list_and_free (deps
, insn
,
3369 ®_last
->control_uses
, 0,
3370 REG_DEP_CONTROL
, true);
3371 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3372 reg_pending_barrier
== TRUE_BARRIER
3373 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3375 add_dependence_list_and_free (deps
, insn
,
3376 ®_last
->implicit_sets
, 0,
3377 REG_DEP_ANTI
, true);
3378 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3379 reg_pending_barrier
== TRUE_BARRIER
3380 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3383 if (!deps
->readonly
)
3385 reg_last
->uses_length
= 0;
3386 reg_last
->clobbers_length
= 0;
3391 if (!deps
->readonly
)
3392 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3394 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3395 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3396 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3399 /* Don't flush pending lists on speculative checks for
3400 selective scheduling. */
3401 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn
))
3402 flush_pending_lists (deps
, insn
, true, true);
3404 reg_pending_barrier
= NOT_A_BARRIER
;
3407 /* If a post-call group is still open, see if it should remain so.
3408 This insn must be a simple move of a hard reg to a pseudo or
3411 We must avoid moving these insns for correctness on targets
3412 with small register classes, and for special registers like
3413 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3414 hard regs for all targets. */
3416 if (deps
->in_post_call_group_p
)
3418 rtx tmp
, set
= single_set (insn
);
3419 int src_regno
, dest_regno
;
3423 if (DEBUG_INSN_P (insn
))
3424 /* We don't want to mark debug insns as part of the same
3425 sched group. We know they really aren't, but if we use
3426 debug insns to tell that a call group is over, we'll
3427 get different code if debug insns are not there and
3428 instructions that follow seem like they should be part
3431 Also, if we did, chain_to_prev_insn would move the
3432 deps of the debug insn to the call insn, modifying
3433 non-debug post-dependency counts of the debug insn
3434 dependencies and otherwise messing with the scheduling
3437 Instead, let such debug insns be scheduled freely, but
3438 keep the call group open in case there are insns that
3439 should be part of it afterwards. Since we grant debug
3440 insns higher priority than even sched group insns, it
3441 will all turn out all right. */
3442 goto debug_dont_end_call_group
;
3444 goto end_call_group
;
3447 tmp
= SET_DEST (set
);
3448 if (GET_CODE (tmp
) == SUBREG
)
3449 tmp
= SUBREG_REG (tmp
);
3451 dest_regno
= REGNO (tmp
);
3453 goto end_call_group
;
3455 tmp
= SET_SRC (set
);
3456 if (GET_CODE (tmp
) == SUBREG
)
3457 tmp
= SUBREG_REG (tmp
);
3458 if ((GET_CODE (tmp
) == PLUS
3459 || GET_CODE (tmp
) == MINUS
)
3460 && REG_P (XEXP (tmp
, 0))
3461 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3462 && dest_regno
== STACK_POINTER_REGNUM
)
3463 src_regno
= STACK_POINTER_REGNUM
;
3464 else if (REG_P (tmp
))
3465 src_regno
= REGNO (tmp
);
3467 goto end_call_group
;
3469 if (src_regno
< FIRST_PSEUDO_REGISTER
3470 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3473 && deps
->in_post_call_group_p
== post_call_initial
)
3474 deps
->in_post_call_group_p
= post_call
;
3476 if (!sel_sched_p () || sched_emulate_haifa_p
)
3478 SCHED_GROUP_P (insn
) = 1;
3479 CANT_MOVE (insn
) = 1;
3485 if (!deps
->readonly
)
3486 deps
->in_post_call_group_p
= not_post_call
;
3490 debug_dont_end_call_group
:
3491 if ((current_sched_info
->flags
& DO_SPECULATION
)
3492 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3493 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3497 sel_mark_hard_insn (insn
);
3500 sd_iterator_def sd_it
;
3503 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3504 sd_iterator_cond (&sd_it
, &dep
);)
3505 change_spec_dep_to_hard (sd_it
);
3509 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3510 honor their original ordering. */
3511 if (find_reg_note (insn
, REG_ARGS_SIZE
, NULL
))
3513 if (deps
->last_args_size
)
3514 add_dependence (insn
, deps
->last_args_size
, REG_DEP_OUTPUT
);
3515 deps
->last_args_size
= insn
;
3519 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3520 longjmp, loop forever, ...). */
3521 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3522 test for ECF_NORETURN? */
3524 call_may_noreturn_p (rtx insn
)
3528 /* const or pure calls that aren't looping will always return. */
3529 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3530 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3533 call
= get_call_rtx_from (insn
);
3534 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3536 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3537 if (SYMBOL_REF_DECL (symbol
)
3538 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3540 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3542 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3545 case BUILT_IN_BCOPY
:
3546 case BUILT_IN_BZERO
:
3547 case BUILT_IN_INDEX
:
3548 case BUILT_IN_MEMCHR
:
3549 case BUILT_IN_MEMCMP
:
3550 case BUILT_IN_MEMCPY
:
3551 case BUILT_IN_MEMMOVE
:
3552 case BUILT_IN_MEMPCPY
:
3553 case BUILT_IN_MEMSET
:
3554 case BUILT_IN_RINDEX
:
3555 case BUILT_IN_STPCPY
:
3556 case BUILT_IN_STPNCPY
:
3557 case BUILT_IN_STRCAT
:
3558 case BUILT_IN_STRCHR
:
3559 case BUILT_IN_STRCMP
:
3560 case BUILT_IN_STRCPY
:
3561 case BUILT_IN_STRCSPN
:
3562 case BUILT_IN_STRLEN
:
3563 case BUILT_IN_STRNCAT
:
3564 case BUILT_IN_STRNCMP
:
3565 case BUILT_IN_STRNCPY
:
3566 case BUILT_IN_STRPBRK
:
3567 case BUILT_IN_STRRCHR
:
3568 case BUILT_IN_STRSPN
:
3569 case BUILT_IN_STRSTR
:
3570 /* Assume certain string/memory builtins always return. */
3578 /* For all other calls assume that they might not always return. */
3582 /* Return true if INSN should be made dependent on the previous instruction
3583 group, and if all INSN's dependencies should be moved to the first
3584 instruction of that group. */
3587 chain_to_prev_insn_p (rtx insn
)
3591 /* INSN forms a group with the previous instruction. */
3592 if (SCHED_GROUP_P (insn
))
3595 /* If the previous instruction clobbers a register R and this one sets
3596 part of R, the clobber was added specifically to help us track the
3597 liveness of R. There's no point scheduling the clobber and leaving
3598 INSN behind, especially if we move the clobber to another block. */
3599 prev
= prev_nonnote_nondebug_insn (insn
);
3602 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3603 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3605 x
= XEXP (PATTERN (prev
), 0);
3606 if (set_of (x
, insn
))
3613 /* Analyze INSN with DEPS as a context. */
3615 deps_analyze_insn (struct deps_desc
*deps
, rtx_insn
*insn
)
3617 if (sched_deps_info
->start_insn
)
3618 sched_deps_info
->start_insn (insn
);
3620 /* Record the condition for this insn. */
3621 if (NONDEBUG_INSN_P (insn
))
3624 sched_get_condition_with_rev (insn
, NULL
);
3625 t
= INSN_CACHED_COND (insn
);
3626 INSN_COND_DEPS (insn
) = NULL
;
3627 if (reload_completed
3628 && (current_sched_info
->flags
& DO_PREDICATION
)
3630 && REG_P (XEXP (t
, 0))
3631 && CONSTANT_P (XEXP (t
, 1)))
3635 rtx_insn_list
*cond_deps
= NULL
;
3638 nregs
= hard_regno_nregs
[regno
][GET_MODE (t
)];
3641 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3642 cond_deps
= concat_INSN_LIST (reg_last
->sets
, cond_deps
);
3643 cond_deps
= concat_INSN_LIST (reg_last
->clobbers
, cond_deps
);
3644 cond_deps
= concat_INSN_LIST (reg_last
->implicit_sets
, cond_deps
);
3646 INSN_COND_DEPS (insn
) = cond_deps
;
3652 /* Make each JUMP_INSN (but not a speculative check)
3653 a scheduling barrier for memory references. */
3656 && sel_insn_is_speculation_check (insn
)))
3658 /* Keep the list a reasonable size. */
3659 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3660 flush_pending_lists (deps
, insn
, true, true);
3662 deps
->pending_jump_insns
3663 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3666 /* For each insn which shouldn't cross a jump, add a dependence. */
3667 add_dependence_list_and_free (deps
, insn
,
3668 &deps
->sched_before_next_jump
, 1,
3669 REG_DEP_ANTI
, true);
3671 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3673 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3675 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3677 else if (CALL_P (insn
))
3681 CANT_MOVE (insn
) = 1;
3683 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3685 /* This is setjmp. Assume that all registers, not just
3686 hard registers, may be clobbered by this call. */
3687 reg_pending_barrier
= MOVE_BARRIER
;
3691 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3692 /* A call may read and modify global register variables. */
3695 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3696 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3698 /* Other call-clobbered hard regs may be clobbered.
3699 Since we only have a choice between 'might be clobbered'
3700 and 'definitely not clobbered', we must include all
3701 partly call-clobbered registers here. */
3702 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3703 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3704 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3705 /* We don't know what set of fixed registers might be used
3706 by the function, but it is certain that the stack pointer
3707 is among them, but be conservative. */
3708 else if (fixed_regs
[i
])
3709 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3710 /* The frame pointer is normally not used by the function
3711 itself, but by the debugger. */
3712 /* ??? MIPS o32 is an exception. It uses the frame pointer
3713 in the macro expansion of jal but does not represent this
3714 fact in the call_insn rtl. */
3715 else if (i
== FRAME_POINTER_REGNUM
3716 || (i
== HARD_FRAME_POINTER_REGNUM
3717 && (! reload_completed
|| frame_pointer_needed
)))
3718 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3721 /* For each insn which shouldn't cross a call, add a dependence
3722 between that insn and this call insn. */
3723 add_dependence_list_and_free (deps
, insn
,
3724 &deps
->sched_before_next_call
, 1,
3725 REG_DEP_ANTI
, true);
3727 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3729 /* If CALL would be in a sched group, then this will violate
3730 convention that sched group insns have dependencies only on the
3731 previous instruction.
3733 Of course one can say: "Hey! What about head of the sched group?"
3734 And I will answer: "Basic principles (one dep per insn) are always
3736 gcc_assert (!SCHED_GROUP_P (insn
));
3738 /* In the absence of interprocedural alias analysis, we must flush
3739 all pending reads and writes, and start new dependencies starting
3740 from here. But only flush writes for constant calls (which may
3741 be passed a pointer to something we haven't written yet). */
3742 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3744 if (!deps
->readonly
)
3746 /* Remember the last function call for limiting lifetimes. */
3747 free_INSN_LIST_list (&deps
->last_function_call
);
3748 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3750 if (call_may_noreturn_p (insn
))
3752 /* Remember the last function call that might not always return
3753 normally for limiting moves of trapping insns. */
3754 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3755 deps
->last_function_call_may_noreturn
3756 = alloc_INSN_LIST (insn
, NULL_RTX
);
3759 /* Before reload, begin a post-call group, so as to keep the
3760 lifetimes of hard registers correct. */
3761 if (! reload_completed
)
3762 deps
->in_post_call_group_p
= post_call
;
3766 if (sched_deps_info
->use_cselib
)
3767 cselib_process_insn (insn
);
3769 if (sched_deps_info
->finish_insn
)
3770 sched_deps_info
->finish_insn ();
3772 /* Fixup the dependencies in the sched group. */
3773 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3774 && chain_to_prev_insn_p (insn
)
3776 chain_to_prev_insn (insn
);
3779 /* Initialize DEPS for the new block beginning with HEAD. */
3781 deps_start_bb (struct deps_desc
*deps
, rtx_insn
*head
)
3783 gcc_assert (!deps
->readonly
);
3785 /* Before reload, if the previous block ended in a call, show that
3786 we are inside a post-call group, so as to keep the lifetimes of
3787 hard registers correct. */
3788 if (! reload_completed
&& !LABEL_P (head
))
3790 rtx_insn
*insn
= prev_nonnote_nondebug_insn (head
);
3792 if (insn
&& CALL_P (insn
))
3793 deps
->in_post_call_group_p
= post_call_initial
;
3797 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3798 dependencies for each insn. */
3800 sched_analyze (struct deps_desc
*deps
, rtx_insn
*head
, rtx_insn
*tail
)
3804 if (sched_deps_info
->use_cselib
)
3805 cselib_init (CSELIB_RECORD_MEMORY
);
3807 deps_start_bb (deps
, head
);
3809 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3814 /* And initialize deps_lists. */
3815 sd_init_insn (insn
);
3816 /* Clean up SCHED_GROUP_P which may be set by last
3818 if (SCHED_GROUP_P (insn
))
3819 SCHED_GROUP_P (insn
) = 0;
3822 deps_analyze_insn (deps
, insn
);
3826 if (sched_deps_info
->use_cselib
)
3834 /* Helper for sched_free_deps ().
3835 Delete INSN's (RESOLVED_P) backward dependencies. */
3837 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3839 sd_iterator_def sd_it
;
3841 sd_list_types_def types
;
3844 types
= SD_LIST_RES_BACK
;
3846 types
= SD_LIST_BACK
;
3848 for (sd_it
= sd_iterator_start (insn
, types
);
3849 sd_iterator_cond (&sd_it
, &dep
);)
3851 dep_link_t link
= *sd_it
.linkp
;
3852 dep_node_t node
= DEP_LINK_NODE (link
);
3853 deps_list_t back_list
;
3854 deps_list_t forw_list
;
3856 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3857 remove_from_deps_list (link
, back_list
);
3858 delete_dep_node (node
);
3862 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3865 sched_free_deps (rtx_insn
*head
, rtx_insn
*tail
, bool resolved_p
)
3868 rtx_insn
*next_tail
= NEXT_INSN (tail
);
3870 /* We make two passes since some insns may be scheduled before their
3871 dependencies are resolved. */
3872 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3873 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3875 /* Clear forward deps and leave the dep_nodes to the
3876 corresponding back_deps list. */
3878 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3880 clear_deps_list (INSN_FORW_DEPS (insn
));
3882 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3883 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3885 /* Clear resolved back deps together with its dep_nodes. */
3886 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3888 sd_finish_insn (insn
);
3892 /* Initialize variables for region data dependence analysis.
3893 When LAZY_REG_LAST is true, do not allocate reg_last array
3894 of struct deps_desc immediately. */
3897 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3899 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3901 deps
->max_reg
= max_reg
;
3903 deps
->reg_last
= NULL
;
3905 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3906 INIT_REG_SET (&deps
->reg_last_in_use
);
3908 deps
->pending_read_insns
= 0;
3909 deps
->pending_read_mems
= 0;
3910 deps
->pending_write_insns
= 0;
3911 deps
->pending_write_mems
= 0;
3912 deps
->pending_jump_insns
= 0;
3913 deps
->pending_read_list_length
= 0;
3914 deps
->pending_write_list_length
= 0;
3915 deps
->pending_flush_length
= 0;
3916 deps
->last_pending_memory_flush
= 0;
3917 deps
->last_function_call
= 0;
3918 deps
->last_function_call_may_noreturn
= 0;
3919 deps
->sched_before_next_call
= 0;
3920 deps
->sched_before_next_jump
= 0;
3921 deps
->in_post_call_group_p
= not_post_call
;
3922 deps
->last_debug_insn
= 0;
3923 deps
->last_args_size
= 0;
3924 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3928 /* Init only reg_last field of DEPS, which was not allocated before as
3929 we inited DEPS lazily. */
3931 init_deps_reg_last (struct deps_desc
*deps
)
3933 gcc_assert (deps
&& deps
->max_reg
> 0);
3934 gcc_assert (deps
->reg_last
== NULL
);
3936 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3940 /* Free insn lists found in DEPS. */
3943 free_deps (struct deps_desc
*deps
)
3946 reg_set_iterator rsi
;
3948 /* We set max_reg to 0 when this context was already freed. */
3949 if (deps
->max_reg
== 0)
3951 gcc_assert (deps
->reg_last
== NULL
);
3956 free_INSN_LIST_list (&deps
->pending_read_insns
);
3957 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3958 free_INSN_LIST_list (&deps
->pending_write_insns
);
3959 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3960 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3962 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3963 times. For a testcase with 42000 regs and 8000 small basic blocks,
3964 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3965 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3967 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3969 free_INSN_LIST_list (®_last
->uses
);
3971 free_INSN_LIST_list (®_last
->sets
);
3972 if (reg_last
->implicit_sets
)
3973 free_INSN_LIST_list (®_last
->implicit_sets
);
3974 if (reg_last
->control_uses
)
3975 free_INSN_LIST_list (®_last
->control_uses
);
3976 if (reg_last
->clobbers
)
3977 free_INSN_LIST_list (®_last
->clobbers
);
3979 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3981 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3983 free (deps
->reg_last
);
3984 deps
->reg_last
= NULL
;
3989 /* Remove INSN from dependence contexts DEPS. */
3991 remove_from_deps (struct deps_desc
*deps
, rtx_insn
*insn
)
3995 reg_set_iterator rsi
;
3997 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3998 &deps
->pending_read_mems
);
3999 if (!DEBUG_INSN_P (insn
))
4000 deps
->pending_read_list_length
-= removed
;
4001 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
4002 &deps
->pending_write_mems
);
4003 deps
->pending_write_list_length
-= removed
;
4005 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
4006 deps
->pending_flush_length
-= removed
;
4007 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
4008 deps
->pending_flush_length
-= removed
;
4010 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
4012 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
4014 remove_from_dependence_list (insn
, ®_last
->uses
);
4016 remove_from_dependence_list (insn
, ®_last
->sets
);
4017 if (reg_last
->implicit_sets
)
4018 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
4019 if (reg_last
->clobbers
)
4020 remove_from_dependence_list (insn
, ®_last
->clobbers
);
4021 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
4022 && !reg_last
->clobbers
)
4023 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
4028 remove_from_dependence_list (insn
, &deps
->last_function_call
);
4029 remove_from_dependence_list (insn
,
4030 &deps
->last_function_call_may_noreturn
);
4032 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
4035 /* Init deps data vector. */
4037 init_deps_data_vector (void)
4039 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
4040 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
4041 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
4044 /* If it is profitable to use them, initialize or extend (depending on
4045 GLOBAL_P) dependency data. */
4047 sched_deps_init (bool global_p
)
4049 /* Average number of insns in the basic block.
4050 '+ 1' is used to make it nonzero. */
4051 int insns_in_block
= sched_max_luid
/ n_basic_blocks_for_fn (cfun
) + 1;
4053 init_deps_data_vector ();
4055 /* We use another caching mechanism for selective scheduling, so
4056 we don't use this one. */
4057 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
4059 /* ?!? We could save some memory by computing a per-region luid mapping
4060 which could reduce both the number of vectors in the cache and the
4061 size of each vector. Instead we just avoid the cache entirely unless
4062 the average number of instructions in a basic block is very high. See
4063 the comment before the declaration of true_dependency_cache for
4064 what we consider "very high". */
4066 extend_dependency_caches (sched_max_luid
, true);
4071 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
4072 /* Allocate lists for one block at a time. */
4074 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
4075 /* Allocate nodes for one block at a time.
4076 We assume that average insn has
4078 5 * insns_in_block
);
4083 /* Create or extend (depending on CREATE_P) dependency caches to
4086 extend_dependency_caches (int n
, bool create_p
)
4088 if (create_p
|| true_dependency_cache
)
4090 int i
, luid
= cache_size
+ n
;
4092 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4094 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4095 output_dependency_cache
, luid
);
4096 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4098 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4101 if (current_sched_info
->flags
& DO_SPECULATION
)
4102 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4105 for (i
= cache_size
; i
< luid
; i
++)
4107 bitmap_initialize (&true_dependency_cache
[i
], 0);
4108 bitmap_initialize (&output_dependency_cache
[i
], 0);
4109 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4110 bitmap_initialize (&control_dependency_cache
[i
], 0);
4112 if (current_sched_info
->flags
& DO_SPECULATION
)
4113 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4119 /* Finalize dependency information for the whole function. */
4121 sched_deps_finish (void)
4123 gcc_assert (deps_pools_are_empty_p ());
4124 free_alloc_pool_if_empty (&dn_pool
);
4125 free_alloc_pool_if_empty (&dl_pool
);
4126 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
4131 if (true_dependency_cache
)
4135 for (i
= 0; i
< cache_size
; i
++)
4137 bitmap_clear (&true_dependency_cache
[i
]);
4138 bitmap_clear (&output_dependency_cache
[i
]);
4139 bitmap_clear (&anti_dependency_cache
[i
]);
4140 bitmap_clear (&control_dependency_cache
[i
]);
4142 if (sched_deps_info
->generate_spec_deps
)
4143 bitmap_clear (&spec_dependency_cache
[i
]);
4145 free (true_dependency_cache
);
4146 true_dependency_cache
= NULL
;
4147 free (output_dependency_cache
);
4148 output_dependency_cache
= NULL
;
4149 free (anti_dependency_cache
);
4150 anti_dependency_cache
= NULL
;
4151 free (control_dependency_cache
);
4152 control_dependency_cache
= NULL
;
4154 if (sched_deps_info
->generate_spec_deps
)
4156 free (spec_dependency_cache
);
4157 spec_dependency_cache
= NULL
;
4163 /* Initialize some global variables needed by the dependency analysis
4167 init_deps_global (void)
4169 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4170 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4171 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4172 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4173 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4174 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4175 reg_pending_barrier
= NOT_A_BARRIER
;
4177 if (!sel_sched_p () || sched_emulate_haifa_p
)
4179 sched_deps_info
->start_insn
= haifa_start_insn
;
4180 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4182 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4183 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4184 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4186 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4187 sched_deps_info
->note_dep
= haifa_note_dep
;
4191 /* Free everything used by the dependency analysis code. */
4194 finish_deps_global (void)
4196 FREE_REG_SET (reg_pending_sets
);
4197 FREE_REG_SET (reg_pending_clobbers
);
4198 FREE_REG_SET (reg_pending_uses
);
4199 FREE_REG_SET (reg_pending_control_uses
);
4202 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4204 estimate_dep_weak (rtx mem1
, rtx mem2
)
4209 /* MEMs are the same - don't speculate. */
4210 return MIN_DEP_WEAK
;
4212 r1
= XEXP (mem1
, 0);
4213 r2
= XEXP (mem2
, 0);
4216 || (REG_P (r1
) && REG_P (r2
)
4217 && REGNO (r1
) == REGNO (r2
)))
4218 /* Again, MEMs are the same. */
4219 return MIN_DEP_WEAK
;
4220 else if ((REG_P (r1
) && !REG_P (r2
))
4221 || (!REG_P (r1
) && REG_P (r2
)))
4222 /* Different addressing modes - reason to be more speculative,
4224 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4226 /* We can't say anything about the dependence. */
4227 return UNCERTAIN_DEP_WEAK
;
4230 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4231 This function can handle same INSN and ELEM (INSN == ELEM).
4232 It is a convenience wrapper. */
4234 add_dependence_1 (rtx_insn
*insn
, rtx_insn
*elem
, enum reg_note dep_type
)
4239 if (dep_type
== REG_DEP_TRUE
)
4241 else if (dep_type
== REG_DEP_OUTPUT
)
4243 else if (dep_type
== REG_DEP_CONTROL
)
4247 gcc_assert (dep_type
== REG_DEP_ANTI
);
4251 /* When add_dependence is called from inside sched-deps.c, we expect
4252 cur_insn to be non-null. */
4253 internal
= cur_insn
!= NULL
;
4255 gcc_assert (insn
== cur_insn
);
4259 note_dep (elem
, ds
);
4264 /* Return weakness of speculative type TYPE in the dep_status DS,
4265 without checking to prevent ICEs on malformed input. */
4267 get_dep_weak_1 (ds_t ds
, ds_t type
)
4273 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4274 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4275 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4276 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4277 default: gcc_unreachable ();
4283 /* Return weakness of speculative type TYPE in the dep_status DS. */
4285 get_dep_weak (ds_t ds
, ds_t type
)
4287 dw_t dw
= get_dep_weak_1 (ds
, type
);
4289 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4293 /* Return the dep_status, which has the same parameters as DS, except for
4294 speculative type TYPE, that will have weakness DW. */
4296 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4298 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4303 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4304 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4305 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4306 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4307 default: gcc_unreachable ();
4312 /* Return the join of two dep_statuses DS1 and DS2.
4313 If MAX_P is true then choose the greater probability,
4314 otherwise multiply probabilities.
4315 This function assumes that both DS1 and DS2 contain speculative bits. */
4317 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4321 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4323 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4325 t
= FIRST_SPEC_TYPE
;
4328 if ((ds1
& t
) && !(ds2
& t
))
4330 else if (!(ds1
& t
) && (ds2
& t
))
4332 else if ((ds1
& t
) && (ds2
& t
))
4334 dw_t dw1
= get_dep_weak (ds1
, t
);
4335 dw_t dw2
= get_dep_weak (ds2
, t
);
4340 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4342 if (dw
< MIN_DEP_WEAK
)
4353 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4356 if (t
== LAST_SPEC_TYPE
)
4358 t
<<= SPEC_TYPE_SHIFT
;
4365 /* Return the join of two dep_statuses DS1 and DS2.
4366 This function assumes that both DS1 and DS2 contain speculative bits. */
4368 ds_merge (ds_t ds1
, ds_t ds2
)
4370 return ds_merge_1 (ds1
, ds2
, false);
4373 /* Return the join of two dep_statuses DS1 and DS2. */
4375 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4377 ds_t new_status
= ds
| ds2
;
4379 if (new_status
& SPECULATIVE
)
4381 if ((ds
&& !(ds
& SPECULATIVE
))
4382 || (ds2
&& !(ds2
& SPECULATIVE
)))
4383 /* Then this dep can't be speculative. */
4384 new_status
&= ~SPECULATIVE
;
4387 /* Both are speculative. Merging probabilities. */
4392 dw
= estimate_dep_weak (mem1
, mem2
);
4393 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4401 new_status
= ds_merge (ds2
, ds
);
4408 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4411 ds_max_merge (ds_t ds1
, ds_t ds2
)
4413 if (ds1
== 0 && ds2
== 0)
4416 if (ds1
== 0 && ds2
!= 0)
4419 if (ds1
!= 0 && ds2
== 0)
4422 return ds_merge_1 (ds1
, ds2
, true);
4425 /* Return the probability of speculation success for the speculation
4433 dt
= FIRST_SPEC_TYPE
;
4438 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4442 if (dt
== LAST_SPEC_TYPE
)
4444 dt
<<= SPEC_TYPE_SHIFT
;
4450 res
/= MAX_DEP_WEAK
;
4452 if (res
< MIN_DEP_WEAK
)
4455 gcc_assert (res
<= MAX_DEP_WEAK
);
4460 /* Return a dep status that contains all speculation types of DS. */
4462 ds_get_speculation_types (ds_t ds
)
4464 if (ds
& BEGIN_DATA
)
4466 if (ds
& BE_IN_DATA
)
4468 if (ds
& BEGIN_CONTROL
)
4469 ds
|= BEGIN_CONTROL
;
4470 if (ds
& BE_IN_CONTROL
)
4471 ds
|= BE_IN_CONTROL
;
4473 return ds
& SPECULATIVE
;
4476 /* Return a dep status that contains maximal weakness for each speculation
4477 type present in DS. */
4479 ds_get_max_dep_weak (ds_t ds
)
4481 if (ds
& BEGIN_DATA
)
4482 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4483 if (ds
& BE_IN_DATA
)
4484 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4485 if (ds
& BEGIN_CONTROL
)
4486 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4487 if (ds
& BE_IN_CONTROL
)
4488 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4493 /* Dump information about the dependence status S. */
4495 dump_ds (FILE *f
, ds_t s
)
4500 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4502 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4503 if (s
& BEGIN_CONTROL
)
4504 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4505 if (s
& BE_IN_CONTROL
)
4506 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4509 fprintf (f
, "HARD_DEP; ");
4512 fprintf (f
, "DEP_TRUE; ");
4514 fprintf (f
, "DEP_OUTPUT; ");
4516 fprintf (f
, "DEP_ANTI; ");
4517 if (s
& DEP_CONTROL
)
4518 fprintf (f
, "DEP_CONTROL; ");
4526 dump_ds (stderr
, s
);
4527 fprintf (stderr
, "\n");
4530 #ifdef ENABLE_CHECKING
4531 /* Verify that dependence type and status are consistent.
4532 If RELAXED_P is true, then skip dep_weakness checks. */
4534 check_dep (dep_t dep
, bool relaxed_p
)
4536 enum reg_note dt
= DEP_TYPE (dep
);
4537 ds_t ds
= DEP_STATUS (dep
);
4539 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4541 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4543 gcc_assert (ds
== 0);
4547 /* Check that dependence type contains the same bits as the status. */
4548 if (dt
== REG_DEP_TRUE
)
4549 gcc_assert (ds
& DEP_TRUE
);
4550 else if (dt
== REG_DEP_OUTPUT
)
4551 gcc_assert ((ds
& DEP_OUTPUT
)
4552 && !(ds
& DEP_TRUE
));
4553 else if (dt
== REG_DEP_ANTI
)
4554 gcc_assert ((ds
& DEP_ANTI
)
4555 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4557 gcc_assert (dt
== REG_DEP_CONTROL
4558 && (ds
& DEP_CONTROL
)
4559 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4561 /* HARD_DEP can not appear in dep_status of a link. */
4562 gcc_assert (!(ds
& HARD_DEP
));
4564 /* Check that dependence status is set correctly when speculation is not
4566 if (!sched_deps_info
->generate_spec_deps
)
4567 gcc_assert (!(ds
& SPECULATIVE
));
4568 else if (ds
& SPECULATIVE
)
4572 ds_t type
= FIRST_SPEC_TYPE
;
4574 /* Check that dependence weakness is in proper range. */
4578 get_dep_weak (ds
, type
);
4580 if (type
== LAST_SPEC_TYPE
)
4582 type
<<= SPEC_TYPE_SHIFT
;
4587 if (ds
& BEGIN_SPEC
)
4589 /* Only true dependence can be data speculative. */
4590 if (ds
& BEGIN_DATA
)
4591 gcc_assert (ds
& DEP_TRUE
);
4593 /* Control dependencies in the insn scheduler are represented by
4594 anti-dependencies, therefore only anti dependence can be
4595 control speculative. */
4596 if (ds
& BEGIN_CONTROL
)
4597 gcc_assert (ds
& DEP_ANTI
);
4601 /* Subsequent speculations should resolve true dependencies. */
4602 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4605 /* Check that true and anti dependencies can't have other speculative
4608 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4609 /* An output dependence can't be speculative at all. */
4610 gcc_assert (!(ds
& DEP_OUTPUT
));
4612 gcc_assert (ds
& BEGIN_CONTROL
);
4615 #endif /* ENABLE_CHECKING */
4617 /* The following code discovers opportunities to switch a memory reference
4618 and an increment by modifying the address. We ensure that this is done
4619 only for dependencies that are only used to show a single register
4620 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4621 instruction involved is subject to only one dep that can cause a pattern
4624 When we discover a suitable dependency, we fill in the dep_replacement
4625 structure to show how to modify the memory reference. */
4627 /* Holds information about a pair of memory reference and register increment
4628 insns which depend on each other, but could possibly be interchanged. */
4635 /* A register occurring in the memory address for which we wish to break
4636 the dependence. This must be identical to the destination register of
4639 /* Any kind of index that is added to that register. */
4641 /* The constant offset used in the memory address. */
4642 HOST_WIDE_INT mem_constant
;
4643 /* The constant added in the increment insn. Negated if the increment is
4644 after the memory address. */
4645 HOST_WIDE_INT inc_constant
;
4646 /* The source register used in the increment. May be different from mem_reg0
4647 if the increment occurs before the memory address. */
4651 /* Verify that the memory location described in MII can be replaced with
4652 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4653 insn remains unchanged by this function. */
4656 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4658 rtx mem
= *mii
->mem_loc
;
4661 /* Jump through a lot of hoops to keep the attributes up to date. We
4662 do not want to call one of the change address variants that take
4663 an offset even though we know the offset in many cases. These
4664 assume you are changing where the address is pointing by the
4666 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4667 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4669 if (sched_verbose
>= 5)
4670 fprintf (sched_dump
, "validation failure\n");
4674 /* Put back the old one. */
4675 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4680 /* Return true if INSN is of a form "a = b op c" where a and b are
4681 regs. op is + if c is a reg and +|- if c is a const. Fill in
4682 informantion in MII about what is found.
4683 BEFORE_MEM indicates whether the increment is found before or after
4684 a corresponding memory reference. */
4687 parse_add_or_inc (struct mem_inc_info
*mii
, rtx_insn
*insn
, bool before_mem
)
4689 rtx pat
= single_set (insn
);
4693 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4696 /* Result must be single reg. */
4697 if (!REG_P (SET_DEST (pat
)))
4700 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4703 mii
->inc_insn
= insn
;
4704 src
= SET_SRC (pat
);
4705 mii
->inc_input
= XEXP (src
, 0);
4707 if (!REG_P (XEXP (src
, 0)))
4710 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4713 cst
= XEXP (src
, 1);
4714 if (!CONST_INT_P (cst
))
4716 mii
->inc_constant
= INTVAL (cst
);
4718 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4722 mii
->inc_constant
= -mii
->inc_constant
;
4727 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4729 /* Note that the sign has already been reversed for !before_mem. */
4730 #ifdef STACK_GROWS_DOWNWARD
4731 return mii
->inc_constant
> 0;
4733 return mii
->inc_constant
< 0;
4739 /* Once a suitable mem reference has been found and the corresponding data
4740 in MII has been filled in, this function is called to find a suitable
4741 add or inc insn involving the register we found in the memory
4745 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4747 sd_iterator_def sd_it
;
4750 sd_it
= sd_iterator_start (mii
->mem_insn
,
4751 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4752 while (sd_iterator_cond (&sd_it
, &dep
))
4754 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4755 rtx_insn
*pro
= DEP_PRO (dep
);
4756 rtx_insn
*con
= DEP_CON (dep
);
4757 rtx_insn
*inc_cand
= backwards
? pro
: con
;
4758 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4760 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4762 struct dep_replacement
*desc
;
4764 rtx newaddr
, newmem
;
4766 if (sched_verbose
>= 5)
4767 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4768 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4770 /* Need to assure that none of the operands of the inc
4771 instruction are assigned to by the mem insn. */
4772 FOR_EACH_INSN_DEF (def
, mii
->mem_insn
)
4773 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4774 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4776 if (sched_verbose
>= 5)
4777 fprintf (sched_dump
,
4778 "inc conflicts with store failure.\n");
4782 newaddr
= mii
->inc_input
;
4783 if (mii
->mem_index
!= NULL_RTX
)
4784 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4786 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4787 mii
->mem_constant
+ mii
->inc_constant
);
4788 newmem
= attempt_change (mii
, newaddr
);
4789 if (newmem
== NULL_RTX
)
4791 if (sched_verbose
>= 5)
4792 fprintf (sched_dump
, "successful address replacement\n");
4793 desc
= XCNEW (struct dep_replacement
);
4794 DEP_REPLACE (dep
) = desc
;
4795 desc
->loc
= mii
->mem_loc
;
4796 desc
->newval
= newmem
;
4797 desc
->orig
= *desc
->loc
;
4798 desc
->insn
= mii
->mem_insn
;
4799 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4800 INSN_SPEC_BACK_DEPS (con
));
4803 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4804 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4809 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4810 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4816 sd_iterator_next (&sd_it
);
4821 /* A recursive function that walks ADDRESS_OF_X to find memory references
4822 which could be modified during scheduling. We call find_inc for each
4823 one we find that has a recognizable form. MII holds information about
4824 the pair of memory/increment instructions.
4825 We ensure that every instruction with a memory reference (which will be
4826 the location of the replacement) is assigned at most one breakable
4830 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4832 rtx x
= *address_of_x
;
4833 enum rtx_code code
= GET_CODE (x
);
4834 const char *const fmt
= GET_RTX_FORMAT (code
);
4839 rtx reg0
= XEXP (x
, 0);
4841 mii
->mem_loc
= address_of_x
;
4842 mii
->mem_index
= NULL_RTX
;
4843 mii
->mem_constant
= 0;
4844 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4846 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4847 reg0
= XEXP (reg0
, 0);
4849 if (GET_CODE (reg0
) == PLUS
)
4851 mii
->mem_index
= XEXP (reg0
, 1);
4852 reg0
= XEXP (reg0
, 0);
4857 int occurrences
= 0;
4859 /* Make sure this reg appears only once in this insn. Can't use
4860 count_occurrences since that only works for pseudos. */
4861 FOR_EACH_INSN_USE (use
, mii
->mem_insn
)
4862 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (use
)))
4863 if (++occurrences
> 1)
4865 if (sched_verbose
>= 5)
4866 fprintf (sched_dump
, "mem count failure\n");
4870 mii
->mem_reg0
= reg0
;
4871 return find_inc (mii
, true) || find_inc (mii
, false);
4876 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4878 /* If REG occurs inside a MEM used in a bit-field reference,
4879 that is unacceptable. */
4883 /* Time for some deep diving. */
4884 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4888 if (find_mem (mii
, &XEXP (x
, i
)))
4891 else if (fmt
[i
] == 'E')
4894 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4895 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4903 /* Examine the instructions between HEAD and TAIL and try to find
4904 dependencies that can be broken by modifying one of the patterns. */
4907 find_modifiable_mems (rtx_insn
*head
, rtx_insn
*tail
)
4909 rtx_insn
*insn
, *next_tail
= NEXT_INSN (tail
);
4910 int success_in_block
= 0;
4912 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4914 struct mem_inc_info mii
;
4916 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4919 mii
.mem_insn
= insn
;
4920 if (find_mem (&mii
, &PATTERN (insn
)))
4923 if (success_in_block
&& sched_verbose
>= 5)
4924 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4928 #endif /* INSN_SCHEDULING */