1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992-2015 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"
30 #include "diagnostic-core.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "alloc-pool.h"
48 #ifdef INSN_SCHEDULING
50 /* Holds current parameters for the dependency analyzer. */
51 struct sched_deps_info_def
*sched_deps_info
;
53 /* The data is specific to the Haifa scheduler. */
54 vec
<haifa_deps_insn_data_def
>
57 /* Return the major type present in the DS. */
65 return REG_DEP_OUTPUT
;
68 return REG_DEP_CONTROL
;
70 gcc_assert (ds
& DEP_ANTI
);
75 /* Return equivalent dep_status. */
77 dk_to_ds (enum reg_note dk
)
91 gcc_assert (dk
== REG_DEP_ANTI
);
96 /* Functions to operate with dependence information container - dep_t. */
98 /* Init DEP with the arguments. */
100 init_dep_1 (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note type
, ds_t ds
)
104 DEP_TYPE (dep
) = type
;
105 DEP_STATUS (dep
) = ds
;
106 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
107 DEP_NONREG (dep
) = 0;
108 DEP_MULTIPLE (dep
) = 0;
109 DEP_REPLACE (dep
) = NULL
;
112 /* Init DEP with the arguments.
113 While most of the scheduler (including targets) only need the major type
114 of the dependency, it is convenient to hide full dep_status from them. */
116 init_dep (dep_t dep
, rtx_insn
*pro
, rtx_insn
*con
, enum reg_note kind
)
120 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
121 ds
= dk_to_ds (kind
);
125 init_dep_1 (dep
, pro
, con
, kind
, ds
);
128 /* Make a copy of FROM in TO. */
130 copy_dep (dep_t to
, dep_t from
)
132 memcpy (to
, from
, sizeof (*to
));
135 static void dump_ds (FILE *, ds_t
);
137 /* Define flags for dump_dep (). */
139 /* Dump producer of the dependence. */
140 #define DUMP_DEP_PRO (2)
142 /* Dump consumer of the dependence. */
143 #define DUMP_DEP_CON (4)
145 /* Dump type of the dependence. */
146 #define DUMP_DEP_TYPE (8)
148 /* Dump status of the dependence. */
149 #define DUMP_DEP_STATUS (16)
151 /* Dump all information about the dependence. */
152 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
156 FLAGS is a bit mask specifying what information about DEP needs
158 If FLAGS has the very first bit set, then dump all information about DEP
159 and propagate this bit into the callee dump functions. */
161 dump_dep (FILE *dump
, dep_t dep
, int flags
)
164 flags
|= DUMP_DEP_ALL
;
168 if (flags
& DUMP_DEP_PRO
)
169 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
171 if (flags
& DUMP_DEP_CON
)
172 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
174 if (flags
& DUMP_DEP_TYPE
)
177 enum reg_note type
= DEP_TYPE (dep
);
189 case REG_DEP_CONTROL
:
202 fprintf (dump
, "%c; ", t
);
205 if (flags
& DUMP_DEP_STATUS
)
207 if (current_sched_info
->flags
& USE_DEPS_LIST
)
208 dump_ds (dump
, DEP_STATUS (dep
));
214 /* Default flags for dump_dep (). */
215 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
217 /* Dump all fields of DEP to STDERR. */
219 sd_debug_dep (dep_t dep
)
221 dump_dep (stderr
, dep
, 1);
222 fprintf (stderr
, "\n");
225 /* Determine whether DEP is a dependency link of a non-debug insn on a
229 depl_on_debug_p (dep_link_t dep
)
231 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
232 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
235 /* Functions to operate with a single link from the dependencies lists -
238 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
241 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
243 dep_link_t next
= *prev_nextp
;
245 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
246 && DEP_LINK_NEXT (l
) == NULL
);
248 /* Init node being inserted. */
249 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
250 DEP_LINK_NEXT (l
) = next
;
255 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
257 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
264 /* Add dep_link LINK to deps_list L. */
266 add_to_deps_list (dep_link_t link
, deps_list_t l
)
268 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
270 /* Don't count debug deps. */
271 if (!depl_on_debug_p (link
))
272 ++DEPS_LIST_N_LINKS (l
);
275 /* Detach dep_link L from the list. */
277 detach_dep_link (dep_link_t l
)
279 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
280 dep_link_t next
= DEP_LINK_NEXT (l
);
285 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
287 DEP_LINK_PREV_NEXTP (l
) = NULL
;
288 DEP_LINK_NEXT (l
) = NULL
;
291 /* Remove link LINK from list LIST. */
293 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
295 detach_dep_link (link
);
297 /* Don't count debug deps. */
298 if (!depl_on_debug_p (link
))
299 --DEPS_LIST_N_LINKS (list
);
302 /* Move link LINK from list FROM to list TO. */
304 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
306 remove_from_deps_list (link
, from
);
307 add_to_deps_list (link
, to
);
310 /* Return true of LINK is not attached to any list. */
312 dep_link_is_detached_p (dep_link_t link
)
314 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
317 /* Pool to hold all dependency nodes (dep_node_t). */
318 static object_allocator
<_dep_node
> *dn_pool
;
320 /* Number of dep_nodes out there. */
321 static int dn_pool_diff
= 0;
323 /* Create a dep_node. */
325 create_dep_node (void)
327 dep_node_t n
= dn_pool
->allocate ();
328 dep_link_t back
= DEP_NODE_BACK (n
);
329 dep_link_t forw
= DEP_NODE_FORW (n
);
331 DEP_LINK_NODE (back
) = n
;
332 DEP_LINK_NEXT (back
) = NULL
;
333 DEP_LINK_PREV_NEXTP (back
) = NULL
;
335 DEP_LINK_NODE (forw
) = n
;
336 DEP_LINK_NEXT (forw
) = NULL
;
337 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
344 /* Delete dep_node N. N must not be connected to any deps_list. */
346 delete_dep_node (dep_node_t n
)
348 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
349 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
351 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n
)));
358 /* Pool to hold dependencies lists (deps_list_t). */
359 static object_allocator
<_deps_list
> *dl_pool
;
361 /* Number of deps_lists out there. */
362 static int dl_pool_diff
= 0;
364 /* Functions to operate with dependences lists - deps_list_t. */
366 /* Return true if list L is empty. */
368 deps_list_empty_p (deps_list_t l
)
370 return DEPS_LIST_N_LINKS (l
) == 0;
373 /* Create a new deps_list. */
375 create_deps_list (void)
377 deps_list_t l
= dl_pool
->allocate ();
379 DEPS_LIST_FIRST (l
) = NULL
;
380 DEPS_LIST_N_LINKS (l
) = 0;
386 /* Free deps_list L. */
388 free_deps_list (deps_list_t l
)
390 gcc_assert (deps_list_empty_p (l
));
397 /* Return true if there is no dep_nodes and deps_lists out there.
398 After the region is scheduled all the dependency nodes and lists
399 should [generally] be returned to pool. */
401 deps_pools_are_empty_p (void)
403 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
406 /* Remove all elements from L. */
408 clear_deps_list (deps_list_t l
)
412 dep_link_t link
= DEPS_LIST_FIRST (l
);
417 remove_from_deps_list (link
, l
);
422 /* Decide whether a dependency should be treated as a hard or a speculative
425 dep_spec_p (dep_t dep
)
427 if (current_sched_info
->flags
& DO_SPECULATION
)
429 if (DEP_STATUS (dep
) & SPECULATIVE
)
432 if (current_sched_info
->flags
& DO_PREDICATION
)
434 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
437 if (DEP_REPLACE (dep
) != NULL
)
442 static regset reg_pending_sets
;
443 static regset reg_pending_clobbers
;
444 static regset reg_pending_uses
;
445 static regset reg_pending_control_uses
;
446 static enum reg_pending_barrier_mode reg_pending_barrier
;
448 /* Hard registers implicitly clobbered or used (or may be implicitly
449 clobbered or used) by the currently analyzed insn. For example,
450 insn in its constraint has one register class. Even if there is
451 currently no hard register in the insn, the particular hard
452 register will be in the insn after reload pass because the
453 constraint requires it. */
454 static HARD_REG_SET implicit_reg_pending_clobbers
;
455 static HARD_REG_SET implicit_reg_pending_uses
;
457 /* To speed up the test for duplicate dependency links we keep a
458 record of dependencies created by add_dependence when the average
459 number of instructions in a basic block is very large.
461 Studies have shown that there is typically around 5 instructions between
462 branches for typical C code. So we can make a guess that the average
463 basic block is approximately 5 instructions long; we will choose 100X
464 the average size as a very large basic block.
466 Each insn has associated bitmaps for its dependencies. Each bitmap
467 has enough entries to represent a dependency on any other insn in
468 the insn chain. All bitmap for true dependencies cache is
469 allocated then the rest two ones are also allocated. */
470 static bitmap_head
*true_dependency_cache
= NULL
;
471 static bitmap_head
*output_dependency_cache
= NULL
;
472 static bitmap_head
*anti_dependency_cache
= NULL
;
473 static bitmap_head
*control_dependency_cache
= NULL
;
474 static bitmap_head
*spec_dependency_cache
= NULL
;
475 static int cache_size
;
477 /* True if we should mark added dependencies as a non-register deps. */
478 static bool mark_as_hard
;
480 static int deps_may_trap_p (const_rtx
);
481 static void add_dependence_1 (rtx_insn
*, rtx_insn
*, enum reg_note
);
482 static void add_dependence_list (rtx_insn
*, rtx_insn_list
*, int,
483 enum reg_note
, bool);
484 static void add_dependence_list_and_free (struct deps_desc
*, rtx_insn
*,
485 rtx_insn_list
**, int, enum reg_note
,
487 static void delete_all_dependences (rtx_insn
*);
488 static void chain_to_prev_insn (rtx_insn
*);
490 static void flush_pending_lists (struct deps_desc
*, rtx_insn
*, int, int);
491 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx_insn
*);
492 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx_insn
*);
493 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx_insn
*);
495 static bool sched_has_condition_p (const rtx_insn
*);
496 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
498 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
500 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
502 static void check_dep (dep_t
, bool);
505 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
508 deps_may_trap_p (const_rtx mem
)
510 const_rtx addr
= XEXP (mem
, 0);
512 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
514 const_rtx t
= get_reg_known_value (REGNO (addr
));
518 return rtx_addr_can_trap_p (addr
);
522 /* Find the condition under which INSN is executed. If REV is not NULL,
523 it is set to TRUE when the returned comparison should be reversed
524 to get the actual condition. */
526 sched_get_condition_with_rev_uncached (const rtx_insn
*insn
, bool *rev
)
528 rtx pat
= PATTERN (insn
);
534 if (GET_CODE (pat
) == COND_EXEC
)
535 return COND_EXEC_TEST (pat
);
537 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
540 src
= SET_SRC (pc_set (insn
));
542 if (XEXP (src
, 2) == pc_rtx
)
543 return XEXP (src
, 0);
544 else if (XEXP (src
, 1) == pc_rtx
)
546 rtx cond
= XEXP (src
, 0);
547 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
549 if (revcode
== UNKNOWN
)
560 /* Return the condition under which INSN does not execute (i.e. the
561 not-taken condition for a conditional branch), or NULL if we cannot
562 find such a condition. The caller should make a copy of the condition
565 sched_get_reverse_condition_uncached (const rtx_insn
*insn
)
568 rtx cond
= sched_get_condition_with_rev_uncached (insn
, &rev
);
569 if (cond
== NULL_RTX
)
573 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
574 cond
= gen_rtx_fmt_ee (revcode
, GET_MODE (cond
),
581 /* Caching variant of sched_get_condition_with_rev_uncached.
582 We only do actual work the first time we come here for an insn; the
583 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
585 sched_get_condition_with_rev (const rtx_insn
*insn
, bool *rev
)
589 if (INSN_LUID (insn
) == 0)
590 return sched_get_condition_with_rev_uncached (insn
, rev
);
592 if (INSN_CACHED_COND (insn
) == const_true_rtx
)
595 if (INSN_CACHED_COND (insn
) != NULL_RTX
)
598 *rev
= INSN_REVERSE_COND (insn
);
599 return INSN_CACHED_COND (insn
);
602 INSN_CACHED_COND (insn
) = sched_get_condition_with_rev_uncached (insn
, &tmp
);
603 INSN_REVERSE_COND (insn
) = tmp
;
605 if (INSN_CACHED_COND (insn
) == NULL_RTX
)
607 INSN_CACHED_COND (insn
) = const_true_rtx
;
612 *rev
= INSN_REVERSE_COND (insn
);
613 return INSN_CACHED_COND (insn
);
616 /* True when we can find a condition under which INSN is executed. */
618 sched_has_condition_p (const rtx_insn
*insn
)
620 return !! sched_get_condition_with_rev (insn
, NULL
);
625 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
627 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
629 if (COMPARISON_P (cond1
)
630 && COMPARISON_P (cond2
)
631 && GET_CODE (cond1
) ==
633 ? reversed_comparison_code (cond2
, NULL
)
635 && rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
636 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
641 /* Return true if insn1 and insn2 can never depend on one another because
642 the conditions under which they are executed are mutually exclusive. */
644 sched_insns_conditions_mutex_p (const rtx_insn
*insn1
, const rtx_insn
*insn2
)
647 bool rev1
= false, rev2
= false;
649 /* df doesn't handle conditional lifetimes entirely correctly;
650 calls mess up the conditional lifetimes. */
651 if (!CALL_P (insn1
) && !CALL_P (insn2
))
653 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
654 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
656 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
657 /* Make sure first instruction doesn't affect condition of second
658 instruction if switched. */
659 && !modified_in_p (cond1
, insn2
)
660 /* Make sure second instruction doesn't affect condition of first
661 instruction if switched. */
662 && !modified_in_p (cond2
, insn1
))
669 /* Return true if INSN can potentially be speculated with type DS. */
671 sched_insn_is_legitimate_for_speculation_p (const rtx_insn
*insn
, ds_t ds
)
673 if (HAS_INTERNAL_DEP (insn
))
676 if (!NONJUMP_INSN_P (insn
))
679 if (SCHED_GROUP_P (insn
))
682 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn
)))
685 if (side_effects_p (PATTERN (insn
)))
689 /* The following instructions, which depend on a speculatively scheduled
690 instruction, cannot be speculatively scheduled along. */
692 if (may_trap_or_fault_p (PATTERN (insn
)))
693 /* If instruction might fault, it cannot be speculatively scheduled.
694 For control speculation it's obvious why and for data speculation
695 it's because the insn might get wrong input if speculation
696 wasn't successful. */
699 if ((ds
& BE_IN_DATA
)
700 && sched_has_condition_p (insn
))
701 /* If this is a predicated instruction, then it cannot be
702 speculatively scheduled. See PR35659. */
709 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
710 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
711 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
712 This function is used to switch sd_iterator to the next list.
713 !!! For internal use only. Might consider moving it to sched-int.h. */
715 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
716 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
718 sd_list_types_def types
= *types_ptr
;
720 if (types
& SD_LIST_HARD_BACK
)
722 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
723 *resolved_p_ptr
= false;
724 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
726 else if (types
& SD_LIST_SPEC_BACK
)
728 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
729 *resolved_p_ptr
= false;
730 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
732 else if (types
& SD_LIST_FORW
)
734 *list_ptr
= INSN_FORW_DEPS (insn
);
735 *resolved_p_ptr
= false;
736 *types_ptr
= types
& ~SD_LIST_FORW
;
738 else if (types
& SD_LIST_RES_BACK
)
740 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
741 *resolved_p_ptr
= true;
742 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
744 else if (types
& SD_LIST_RES_FORW
)
746 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
747 *resolved_p_ptr
= true;
748 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
753 *resolved_p_ptr
= false;
754 *types_ptr
= SD_LIST_NONE
;
758 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
760 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
764 while (list_types
!= SD_LIST_NONE
)
769 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
771 size
+= DEPS_LIST_N_LINKS (list
);
777 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
780 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
782 while (list_types
!= SD_LIST_NONE
)
787 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
788 if (!deps_list_empty_p (list
))
795 /* Initialize data for INSN. */
797 sd_init_insn (rtx_insn
*insn
)
799 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
800 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
801 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
802 INSN_FORW_DEPS (insn
) = create_deps_list ();
803 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
805 /* ??? It would be nice to allocate dependency caches here. */
808 /* Free data for INSN. */
810 sd_finish_insn (rtx_insn
*insn
)
812 /* ??? It would be nice to deallocate dependency caches here. */
814 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
815 INSN_HARD_BACK_DEPS (insn
) = NULL
;
817 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
818 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
820 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
821 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
823 free_deps_list (INSN_FORW_DEPS (insn
));
824 INSN_FORW_DEPS (insn
) = NULL
;
826 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
827 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
830 /* Find a dependency between producer PRO and consumer CON.
831 Search through resolved dependency lists if RESOLVED_P is true.
832 If no such dependency is found return NULL,
833 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
834 with an iterator pointing to it. */
836 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
837 sd_iterator_def
*sd_it_ptr
)
839 sd_list_types_def pro_list_type
;
840 sd_list_types_def con_list_type
;
841 sd_iterator_def sd_it
;
843 bool found_p
= false;
847 pro_list_type
= SD_LIST_RES_FORW
;
848 con_list_type
= SD_LIST_RES_BACK
;
852 pro_list_type
= SD_LIST_FORW
;
853 con_list_type
= SD_LIST_BACK
;
856 /* Walk through either back list of INSN or forw list of ELEM
857 depending on which one is shorter. */
858 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
860 /* Find the dep_link with producer PRO in consumer's back_deps. */
861 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
862 if (DEP_PRO (dep
) == pro
)
870 /* Find the dep_link with consumer CON in producer's forw_deps. */
871 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
872 if (DEP_CON (dep
) == con
)
881 if (sd_it_ptr
!= NULL
)
890 /* Find a dependency between producer PRO and consumer CON.
891 Use dependency [if available] to check if dependency is present at all.
892 Search through resolved dependency lists if RESOLVED_P is true.
893 If the dependency or NULL if none found. */
895 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
897 if (true_dependency_cache
!= NULL
)
898 /* Avoiding the list walk below can cut compile times dramatically
901 int elem_luid
= INSN_LUID (pro
);
902 int insn_luid
= INSN_LUID (con
);
904 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
905 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
906 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
)
907 && !bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
911 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
914 /* Add or update a dependence described by DEP.
915 MEM1 and MEM2, if non-null, correspond to memory locations in case of
918 The function returns a value indicating if an old entry has been changed
919 or a new entry has been added to insn's backward deps.
921 This function merely checks if producer and consumer is the same insn
922 and doesn't create a dep in this case. Actual manipulation of
923 dependence data structures is performed in add_or_update_dep_1. */
924 static enum DEPS_ADJUST_RESULT
925 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
927 rtx_insn
*elem
= DEP_PRO (dep
);
928 rtx_insn
*insn
= DEP_CON (dep
);
930 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
932 /* Don't depend an insn on itself. */
935 if (sched_deps_info
->generate_spec_deps
)
936 /* INSN has an internal dependence, which we can't overcome. */
937 HAS_INTERNAL_DEP (insn
) = 1;
942 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
945 /* Ask dependency caches what needs to be done for dependence DEP.
946 Return DEP_CREATED if new dependence should be created and there is no
947 need to try to find one searching the dependencies lists.
948 Return DEP_PRESENT if there already is a dependence described by DEP and
949 hence nothing is to be done.
950 Return DEP_CHANGED if there already is a dependence, but it should be
951 updated to incorporate additional information from DEP. */
952 static enum DEPS_ADJUST_RESULT
953 ask_dependency_caches (dep_t dep
)
955 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
956 int insn_luid
= INSN_LUID (DEP_CON (dep
));
958 gcc_assert (true_dependency_cache
!= NULL
959 && output_dependency_cache
!= NULL
960 && anti_dependency_cache
!= NULL
961 && control_dependency_cache
!= NULL
);
963 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
965 enum reg_note present_dep_type
;
967 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
968 present_dep_type
= REG_DEP_TRUE
;
969 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
970 present_dep_type
= REG_DEP_OUTPUT
;
971 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
972 present_dep_type
= REG_DEP_ANTI
;
973 else if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
974 present_dep_type
= REG_DEP_CONTROL
;
976 /* There is no existing dep so it should be created. */
979 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
980 /* DEP does not add anything to the existing dependence. */
985 ds_t present_dep_types
= 0;
987 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
988 present_dep_types
|= DEP_TRUE
;
989 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
990 present_dep_types
|= DEP_OUTPUT
;
991 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
992 present_dep_types
|= DEP_ANTI
;
993 if (bitmap_bit_p (&control_dependency_cache
[insn_luid
], elem_luid
))
994 present_dep_types
|= DEP_CONTROL
;
996 if (present_dep_types
== 0)
997 /* There is no existing dep so it should be created. */
1000 if (!(current_sched_info
->flags
& DO_SPECULATION
)
1001 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
1003 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
1004 == present_dep_types
)
1005 /* DEP does not add anything to the existing dependence. */
1010 /* Only true dependencies can be data speculative and
1011 only anti dependencies can be control speculative. */
1012 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
1013 == present_dep_types
);
1015 /* if (DEP is SPECULATIVE) then
1016 ..we should update DEP_STATUS
1018 ..we should reset existing dep to non-speculative. */
1025 /* Set dependency caches according to DEP. */
1027 set_dependency_caches (dep_t dep
)
1029 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1030 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1032 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1034 switch (DEP_TYPE (dep
))
1037 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1040 case REG_DEP_OUTPUT
:
1041 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1045 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1048 case REG_DEP_CONTROL
:
1049 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1058 ds_t ds
= DEP_STATUS (dep
);
1061 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1062 if (ds
& DEP_OUTPUT
)
1063 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1065 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1066 if (ds
& DEP_CONTROL
)
1067 bitmap_set_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1069 if (ds
& SPECULATIVE
)
1071 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
1072 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1077 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1078 caches accordingly. */
1080 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
1082 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
1083 int insn_luid
= INSN_LUID (DEP_CON (dep
));
1085 /* Clear corresponding cache entry because type of the link
1086 may have changed. Keep them if we use_deps_list. */
1087 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1091 case REG_DEP_OUTPUT
:
1092 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1096 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1099 case REG_DEP_CONTROL
:
1100 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1108 set_dependency_caches (dep
);
1111 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1113 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1115 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1116 dep_link_t link
= DEP_NODE_BACK (node
);
1117 dep_t dep
= DEP_NODE_DEP (node
);
1118 rtx_insn
*elem
= DEP_PRO (dep
);
1119 rtx_insn
*insn
= DEP_CON (dep
);
1121 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1123 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1125 if (true_dependency_cache
!= NULL
)
1126 /* Clear the cache entry. */
1127 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1131 /* Update DEP to incorporate information from NEW_DEP.
1132 SD_IT points to DEP in case it should be moved to another list.
1133 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1134 data-speculative dependence should be updated. */
1135 static enum DEPS_ADJUST_RESULT
1136 update_dep (dep_t dep
, dep_t new_dep
,
1137 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1138 rtx mem1 ATTRIBUTE_UNUSED
,
1139 rtx mem2 ATTRIBUTE_UNUSED
)
1141 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1142 enum reg_note old_type
= DEP_TYPE (dep
);
1143 bool was_spec
= dep_spec_p (dep
);
1145 DEP_NONREG (dep
) |= DEP_NONREG (new_dep
);
1146 DEP_MULTIPLE (dep
) = 1;
1148 /* If this is a more restrictive type of dependence than the
1149 existing one, then change the existing dependence to this
1151 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1153 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1157 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1158 /* Update DEP_STATUS. */
1160 ds_t dep_status
= DEP_STATUS (dep
);
1161 ds_t ds
= DEP_STATUS (new_dep
);
1162 ds_t new_status
= ds
| dep_status
;
1164 if (new_status
& SPECULATIVE
)
1166 /* Either existing dep or a dep we're adding or both are
1168 if (!(ds
& SPECULATIVE
)
1169 || !(dep_status
& SPECULATIVE
))
1170 /* The new dep can't be speculative. */
1171 new_status
&= ~SPECULATIVE
;
1174 /* Both are speculative. Merge probabilities. */
1179 dw
= estimate_dep_weak (mem1
, mem2
);
1180 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1183 new_status
= ds_merge (dep_status
, ds
);
1189 if (dep_status
!= ds
)
1191 DEP_STATUS (dep
) = ds
;
1196 if (was_spec
&& !dep_spec_p (dep
))
1197 /* The old dep was speculative, but now it isn't. */
1198 change_spec_dep_to_hard (sd_it
);
1200 if (true_dependency_cache
!= NULL
1201 && res
== DEP_CHANGED
)
1202 update_dependency_caches (dep
, old_type
);
1207 /* Add or update a dependence described by DEP.
1208 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1211 The function returns a value indicating if an old entry has been changed
1212 or a new entry has been added to insn's backward deps or nothing has
1213 been updated at all. */
1214 static enum DEPS_ADJUST_RESULT
1215 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1216 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1218 bool maybe_present_p
= true;
1219 bool present_p
= false;
1221 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1222 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1225 check_dep (new_dep
, mem1
!= NULL
);
1227 if (true_dependency_cache
!= NULL
)
1229 switch (ask_dependency_caches (new_dep
))
1233 sd_iterator_def sd_it
;
1235 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1237 resolved_p
, &sd_it
);
1238 DEP_MULTIPLE (present_dep
) = 1;
1242 maybe_present_p
= true;
1247 maybe_present_p
= false;
1257 /* Check that we don't already have this dependence. */
1258 if (maybe_present_p
)
1261 sd_iterator_def sd_it
;
1263 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1265 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1267 resolved_p
, &sd_it
);
1269 if (present_dep
!= NULL
)
1270 /* We found an existing dependency between ELEM and INSN. */
1271 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1273 /* We didn't find a dep, it shouldn't present in the cache. */
1274 gcc_assert (!present_p
);
1277 /* Might want to check one level of transitivity to save conses.
1278 This check should be done in maybe_add_or_update_dep_1.
1279 Since we made it to add_or_update_dep_1, we must create
1280 (or update) a link. */
1282 if (mem1
!= NULL_RTX
)
1284 gcc_assert (sched_deps_info
->generate_spec_deps
);
1285 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1286 estimate_dep_weak (mem1
, mem2
));
1289 sd_add_dep (new_dep
, resolved_p
);
1294 /* Initialize BACK_LIST_PTR with consumer's backward list and
1295 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1296 initialize with lists that hold resolved deps. */
1298 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1299 deps_list_t
*back_list_ptr
,
1300 deps_list_t
*forw_list_ptr
)
1302 rtx_insn
*con
= DEP_CON (dep
);
1306 if (dep_spec_p (dep
))
1307 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1309 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1311 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1315 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1316 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1320 /* Add dependence described by DEP.
1321 If RESOLVED_P is true treat the dependence as a resolved one. */
1323 sd_add_dep (dep_t dep
, bool resolved_p
)
1325 dep_node_t n
= create_dep_node ();
1326 deps_list_t con_back_deps
;
1327 deps_list_t pro_forw_deps
;
1328 rtx_insn
*elem
= DEP_PRO (dep
);
1329 rtx_insn
*insn
= DEP_CON (dep
);
1331 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1333 if ((current_sched_info
->flags
& DO_SPECULATION
) == 0
1334 || !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1335 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1337 copy_dep (DEP_NODE_DEP (n
), dep
);
1339 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1341 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1344 check_dep (dep
, false);
1346 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1348 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1349 in the bitmap caches of dependency information. */
1350 if (true_dependency_cache
!= NULL
)
1351 set_dependency_caches (dep
);
1354 /* Add or update backward dependence between INSN and ELEM
1355 with given type DEP_TYPE and dep_status DS.
1356 This function is a convenience wrapper. */
1357 enum DEPS_ADJUST_RESULT
1358 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1360 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1363 /* Resolved dependence pointed to by SD_IT.
1364 SD_IT will advance to the next element. */
1366 sd_resolve_dep (sd_iterator_def sd_it
)
1368 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1369 dep_t dep
= DEP_NODE_DEP (node
);
1370 rtx_insn
*pro
= DEP_PRO (dep
);
1371 rtx_insn
*con
= DEP_CON (dep
);
1373 if (dep_spec_p (dep
))
1374 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1375 INSN_RESOLVED_BACK_DEPS (con
));
1377 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1378 INSN_RESOLVED_BACK_DEPS (con
));
1380 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1381 INSN_RESOLVED_FORW_DEPS (pro
));
1384 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1385 pointed to by SD_IT to unresolved state. */
1387 sd_unresolve_dep (sd_iterator_def sd_it
)
1389 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1390 dep_t dep
= DEP_NODE_DEP (node
);
1391 rtx_insn
*pro
= DEP_PRO (dep
);
1392 rtx_insn
*con
= DEP_CON (dep
);
1394 if (dep_spec_p (dep
))
1395 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1396 INSN_SPEC_BACK_DEPS (con
));
1398 move_dep_link (DEP_NODE_BACK (node
), INSN_RESOLVED_BACK_DEPS (con
),
1399 INSN_HARD_BACK_DEPS (con
));
1401 move_dep_link (DEP_NODE_FORW (node
), INSN_RESOLVED_FORW_DEPS (pro
),
1402 INSN_FORW_DEPS (pro
));
1405 /* Make TO depend on all the FROM's producers.
1406 If RESOLVED_P is true add dependencies to the resolved lists. */
1408 sd_copy_back_deps (rtx_insn
*to
, rtx_insn
*from
, bool resolved_p
)
1410 sd_list_types_def list_type
;
1411 sd_iterator_def sd_it
;
1414 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1416 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1418 dep_def _new_dep
, *new_dep
= &_new_dep
;
1420 copy_dep (new_dep
, dep
);
1421 DEP_CON (new_dep
) = to
;
1422 sd_add_dep (new_dep
, resolved_p
);
1426 /* Remove a dependency referred to by SD_IT.
1427 SD_IT will point to the next dependence after removal. */
1429 sd_delete_dep (sd_iterator_def sd_it
)
1431 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1432 dep_t dep
= DEP_NODE_DEP (n
);
1433 rtx_insn
*pro
= DEP_PRO (dep
);
1434 rtx_insn
*con
= DEP_CON (dep
);
1435 deps_list_t con_back_deps
;
1436 deps_list_t pro_forw_deps
;
1438 if (true_dependency_cache
!= NULL
)
1440 int elem_luid
= INSN_LUID (pro
);
1441 int insn_luid
= INSN_LUID (con
);
1443 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1444 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1445 bitmap_clear_bit (&control_dependency_cache
[insn_luid
], elem_luid
);
1446 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1448 if (current_sched_info
->flags
& DO_SPECULATION
)
1449 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1452 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1453 &con_back_deps
, &pro_forw_deps
);
1455 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1456 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1458 delete_dep_node (n
);
1461 /* Dump size of the lists. */
1462 #define DUMP_LISTS_SIZE (2)
1464 /* Dump dependencies of the lists. */
1465 #define DUMP_LISTS_DEPS (4)
1467 /* Dump all information about the lists. */
1468 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1470 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1471 FLAGS is a bit mask specifying what information about the lists needs
1473 If FLAGS has the very first bit set, then dump all information about
1474 the lists and propagate this bit into the callee dump functions. */
1476 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1478 sd_iterator_def sd_it
;
1485 flags
|= DUMP_LISTS_ALL
;
1487 fprintf (dump
, "[");
1489 if (flags
& DUMP_LISTS_SIZE
)
1490 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1492 if (flags
& DUMP_LISTS_DEPS
)
1494 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1496 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1497 fprintf (dump
, " ");
1502 /* Dump all information about deps_lists of INSN specified by TYPES
1505 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1507 dump_lists (stderr
, insn
, types
, 1);
1508 fprintf (stderr
, "\n");
1511 /* A wrapper around add_dependence_1, to add a dependence of CON on
1512 PRO, with type DEP_TYPE. This function implements special handling
1513 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1514 the type to REG_DEP_ANTI if we can determine that predication is
1515 impossible; otherwise we add additional true dependencies on the
1516 INSN_COND_DEPS list of the jump (which PRO must be). */
1518 add_dependence (rtx_insn
*con
, rtx_insn
*pro
, enum reg_note dep_type
)
1520 if (dep_type
== REG_DEP_CONTROL
1521 && !(current_sched_info
->flags
& DO_PREDICATION
))
1522 dep_type
= REG_DEP_ANTI
;
1524 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1525 so we must also make the insn dependent on the setter of the
1527 if (dep_type
== REG_DEP_CONTROL
)
1529 rtx_insn
*real_pro
= pro
;
1530 rtx_insn
*other
= real_insn_for_shadow (real_pro
);
1533 if (other
!= NULL_RTX
)
1535 cond
= sched_get_reverse_condition_uncached (real_pro
);
1536 /* Verify that the insn does not use a different value in
1537 the condition register than the one that was present at
1539 if (cond
== NULL_RTX
)
1540 dep_type
= REG_DEP_ANTI
;
1541 else if (INSN_CACHED_COND (real_pro
) == const_true_rtx
)
1544 CLEAR_HARD_REG_SET (uses
);
1545 note_uses (&PATTERN (con
), record_hard_reg_uses
, &uses
);
1546 if (TEST_HARD_REG_BIT (uses
, REGNO (XEXP (cond
, 0))))
1547 dep_type
= REG_DEP_ANTI
;
1549 if (dep_type
== REG_DEP_CONTROL
)
1551 if (sched_verbose
>= 5)
1552 fprintf (sched_dump
, "making DEP_CONTROL for %d\n",
1553 INSN_UID (real_pro
));
1554 add_dependence_list (con
, INSN_COND_DEPS (real_pro
), 0,
1555 REG_DEP_TRUE
, false);
1559 add_dependence_1 (con
, pro
, dep_type
);
1562 /* A convenience wrapper to operate on an entire list. HARD should be
1563 true if DEP_NONREG should be set on newly created dependencies. */
1566 add_dependence_list (rtx_insn
*insn
, rtx_insn_list
*list
, int uncond
,
1567 enum reg_note dep_type
, bool hard
)
1569 mark_as_hard
= hard
;
1570 for (; list
; list
= list
->next ())
1572 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, list
->insn ()))
1573 add_dependence (insn
, list
->insn (), dep_type
);
1575 mark_as_hard
= false;
1578 /* Similar, but free *LISTP at the same time, when the context
1579 is not readonly. HARD should be true if DEP_NONREG should be set on
1580 newly created dependencies. */
1583 add_dependence_list_and_free (struct deps_desc
*deps
, rtx_insn
*insn
,
1584 rtx_insn_list
**listp
,
1585 int uncond
, enum reg_note dep_type
, bool hard
)
1587 add_dependence_list (insn
, *listp
, uncond
, dep_type
, hard
);
1589 /* We don't want to short-circuit dependencies involving debug
1590 insns, because they may cause actual dependencies to be
1592 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1595 free_INSN_LIST_list (listp
);
1598 /* Remove all occurrences of INSN from LIST. Return the number of
1599 occurrences removed. */
1602 remove_from_dependence_list (rtx_insn
*insn
, rtx_insn_list
**listp
)
1608 if ((*listp
)->insn () == insn
)
1610 remove_free_INSN_LIST_node (listp
);
1615 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1621 /* Same as above, but process two lists at once. */
1623 remove_from_both_dependence_lists (rtx_insn
*insn
,
1624 rtx_insn_list
**listp
,
1625 rtx_expr_list
**exprp
)
1631 if (XEXP (*listp
, 0) == insn
)
1633 remove_free_INSN_LIST_node (listp
);
1634 remove_free_EXPR_LIST_node (exprp
);
1639 listp
= (rtx_insn_list
**)&XEXP (*listp
, 1);
1640 exprp
= (rtx_expr_list
**)&XEXP (*exprp
, 1);
1646 /* Clear all dependencies for an insn. */
1648 delete_all_dependences (rtx_insn
*insn
)
1650 sd_iterator_def sd_it
;
1653 /* The below cycle can be optimized to clear the caches and back_deps
1654 in one call but that would provoke duplication of code from
1657 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1658 sd_iterator_cond (&sd_it
, &dep
);)
1659 sd_delete_dep (sd_it
);
1662 /* All insns in a scheduling group except the first should only have
1663 dependencies on the previous insn in the group. So we find the
1664 first instruction in the scheduling group by walking the dependence
1665 chains backwards. Then we add the dependencies for the group to
1666 the previous nonnote insn. */
1669 chain_to_prev_insn (rtx_insn
*insn
)
1671 sd_iterator_def sd_it
;
1673 rtx_insn
*prev_nonnote
;
1675 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1678 rtx_insn
*pro
= DEP_PRO (dep
);
1682 i
= prev_nonnote_insn (i
);
1686 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1688 if (! sched_insns_conditions_mutex_p (i
, pro
))
1689 add_dependence (i
, pro
, DEP_TYPE (dep
));
1693 delete_all_dependences (insn
);
1695 prev_nonnote
= prev_nonnote_nondebug_insn (insn
);
1696 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1697 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1698 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1701 /* Process an insn's memory dependencies. There are four kinds of
1704 (0) read dependence: read follows read
1705 (1) true dependence: read follows write
1706 (2) output dependence: write follows write
1707 (3) anti dependence: write follows read
1709 We are careful to build only dependencies which actually exist, and
1710 use transitivity to avoid building too many links. */
1712 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1713 The MEM is a memory reference contained within INSN, which we are saving
1714 so that we can do memory aliasing on it. */
1717 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1718 rtx_insn
*insn
, rtx mem
)
1720 rtx_insn_list
**insn_list
;
1721 rtx_insn_list
*insn_node
;
1722 rtx_expr_list
**mem_list
;
1723 rtx_expr_list
*mem_node
;
1725 gcc_assert (!deps
->readonly
);
1728 insn_list
= &deps
->pending_read_insns
;
1729 mem_list
= &deps
->pending_read_mems
;
1730 if (!DEBUG_INSN_P (insn
))
1731 deps
->pending_read_list_length
++;
1735 insn_list
= &deps
->pending_write_insns
;
1736 mem_list
= &deps
->pending_write_mems
;
1737 deps
->pending_write_list_length
++;
1740 insn_node
= alloc_INSN_LIST (insn
, *insn_list
);
1741 *insn_list
= insn_node
;
1743 if (sched_deps_info
->use_cselib
)
1745 mem
= shallow_copy_rtx (mem
);
1746 XEXP (mem
, 0) = cselib_subst_to_values_from_insn (XEXP (mem
, 0),
1747 GET_MODE (mem
), insn
);
1749 mem_node
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1750 *mem_list
= mem_node
;
1753 /* Make a dependency between every memory reference on the pending lists
1754 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1755 dependencies for a read operation, similarly with FOR_WRITE. */
1758 flush_pending_lists (struct deps_desc
*deps
, rtx_insn
*insn
, int for_read
,
1763 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1764 1, REG_DEP_ANTI
, true);
1765 if (!deps
->readonly
)
1767 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1768 deps
->pending_read_list_length
= 0;
1772 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1773 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1776 add_dependence_list_and_free (deps
, insn
,
1777 &deps
->last_pending_memory_flush
, 1,
1778 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
,
1781 add_dependence_list_and_free (deps
, insn
, &deps
->pending_jump_insns
, 1,
1782 REG_DEP_ANTI
, true);
1784 if (DEBUG_INSN_P (insn
))
1787 free_INSN_LIST_list (&deps
->pending_read_insns
);
1788 free_INSN_LIST_list (&deps
->pending_write_insns
);
1789 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
1790 free_INSN_LIST_list (&deps
->pending_jump_insns
);
1793 if (!deps
->readonly
)
1795 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1796 deps
->pending_write_list_length
= 0;
1798 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1799 deps
->pending_flush_length
= 1;
1801 mark_as_hard
= false;
1804 /* Instruction which dependencies we are analyzing. */
1805 static rtx_insn
*cur_insn
= NULL
;
1807 /* Implement hooks for haifa scheduler. */
1810 haifa_start_insn (rtx_insn
*insn
)
1812 gcc_assert (insn
&& !cur_insn
);
1818 haifa_finish_insn (void)
1824 haifa_note_reg_set (int regno
)
1826 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1830 haifa_note_reg_clobber (int regno
)
1832 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1836 haifa_note_reg_use (int regno
)
1838 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1842 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx_insn
*pending_insn
, ds_t ds
)
1844 if (!(ds
& SPECULATIVE
))
1847 pending_mem
= NULL_RTX
;
1850 gcc_assert (ds
& BEGIN_DATA
);
1853 dep_def _dep
, *dep
= &_dep
;
1855 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1856 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: 0);
1857 DEP_NONREG (dep
) = 1;
1858 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1864 haifa_note_dep (rtx_insn
*elem
, ds_t ds
)
1869 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1871 DEP_NONREG (dep
) = 1;
1872 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1876 note_reg_use (int r
)
1878 if (sched_deps_info
->note_reg_use
)
1879 sched_deps_info
->note_reg_use (r
);
1883 note_reg_set (int r
)
1885 if (sched_deps_info
->note_reg_set
)
1886 sched_deps_info
->note_reg_set (r
);
1890 note_reg_clobber (int r
)
1892 if (sched_deps_info
->note_reg_clobber
)
1893 sched_deps_info
->note_reg_clobber (r
);
1897 note_mem_dep (rtx m1
, rtx m2
, rtx_insn
*e
, ds_t ds
)
1899 if (sched_deps_info
->note_mem_dep
)
1900 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1904 note_dep (rtx_insn
*e
, ds_t ds
)
1906 if (sched_deps_info
->note_dep
)
1907 sched_deps_info
->note_dep (e
, ds
);
1910 /* Return corresponding to DS reg_note. */
1915 return REG_DEP_TRUE
;
1916 else if (ds
& DEP_OUTPUT
)
1917 return REG_DEP_OUTPUT
;
1918 else if (ds
& DEP_ANTI
)
1919 return REG_DEP_ANTI
;
1922 gcc_assert (ds
& DEP_CONTROL
);
1923 return REG_DEP_CONTROL
;
1929 /* Functions for computation of info needed for register pressure
1930 sensitive insn scheduling. */
1933 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1934 static struct reg_use_data
*
1935 create_insn_reg_use (int regno
, rtx_insn
*insn
)
1937 struct reg_use_data
*use
;
1939 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1942 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1943 INSN_REG_USE_LIST (insn
) = use
;
1947 /* Allocate reg_set_data structure for REGNO and INSN. */
1949 create_insn_reg_set (int regno
, rtx insn
)
1951 struct reg_set_data
*set
;
1953 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1956 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1957 INSN_REG_SET_LIST (insn
) = set
;
1960 /* Set up insn register uses for INSN and dependency context DEPS. */
1962 setup_insn_reg_uses (struct deps_desc
*deps
, rtx_insn
*insn
)
1965 reg_set_iterator rsi
;
1966 struct reg_use_data
*use
, *use2
, *next
;
1967 struct deps_reg
*reg_last
;
1969 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1971 if (i
< FIRST_PSEUDO_REGISTER
1972 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1975 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1976 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1977 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1978 /* Ignore use which is not dying. */
1981 use
= create_insn_reg_use (i
, insn
);
1982 use
->next_regno_use
= use
;
1983 reg_last
= &deps
->reg_last
[i
];
1985 /* Create the cycle list of uses. */
1986 for (rtx_insn_list
*list
= reg_last
->uses
; list
; list
= list
->next ())
1988 use2
= create_insn_reg_use (i
, list
->insn ());
1989 next
= use
->next_regno_use
;
1990 use
->next_regno_use
= use2
;
1991 use2
->next_regno_use
= next
;
1996 /* Register pressure info for the currently processed insn. */
1997 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1999 /* Return TRUE if INSN has the use structure for REGNO. */
2001 insn_use_p (rtx insn
, int regno
)
2003 struct reg_use_data
*use
;
2005 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2006 if (use
->regno
== regno
)
2011 /* Update the register pressure info after birth of pseudo register REGNO
2012 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2013 the register is in clobber or unused after the insn. */
2015 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
2020 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2021 cl
= sched_regno_pressure_class
[regno
];
2024 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2027 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
2028 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2032 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
2033 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2037 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
2038 reg_pressure_info
[cl
].set_increase
= new_incr
;
2039 if (! insn_use_p (insn
, regno
))
2040 reg_pressure_info
[cl
].change
+= incr
;
2041 create_insn_reg_set (regno
, insn
);
2043 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2047 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2048 hard registers involved in the birth. */
2050 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
2051 bool clobber_p
, bool unused_p
)
2054 int new_incr
, last
= regno
+ nregs
;
2056 while (regno
< last
)
2058 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2059 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2061 cl
= sched_regno_pressure_class
[regno
];
2066 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
2067 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
2071 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
2072 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
2076 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
2077 reg_pressure_info
[cl
].set_increase
= new_incr
;
2078 if (! insn_use_p (insn
, regno
))
2079 reg_pressure_info
[cl
].change
+= 1;
2080 create_insn_reg_set (regno
, insn
);
2082 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
2089 /* Update the register pressure info after birth of pseudo or hard
2090 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2091 correspondingly that the register is in clobber or unused after the
2094 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
2098 if (GET_CODE (reg
) == SUBREG
)
2099 reg
= SUBREG_REG (reg
);
2104 regno
= REGNO (reg
);
2105 if (regno
< FIRST_PSEUDO_REGISTER
)
2106 mark_insn_hard_regno_birth (insn
, regno
, REG_NREGS (reg
),
2107 clobber_p
, unused_p
);
2109 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
2112 /* Update the register pressure info after death of pseudo register
2115 mark_pseudo_death (int regno
)
2120 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
2121 cl
= sched_regno_pressure_class
[regno
];
2124 incr
= ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
2125 reg_pressure_info
[cl
].change
-= incr
;
2129 /* Like mark_pseudo_death except that NREGS saying how many hard
2130 registers involved in the death. */
2132 mark_hard_regno_death (int regno
, int nregs
)
2135 int last
= regno
+ nregs
;
2137 while (regno
< last
)
2139 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2140 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
2142 cl
= sched_regno_pressure_class
[regno
];
2144 reg_pressure_info
[cl
].change
-= 1;
2150 /* Update the register pressure info after death of pseudo or hard
2153 mark_reg_death (rtx reg
)
2157 if (GET_CODE (reg
) == SUBREG
)
2158 reg
= SUBREG_REG (reg
);
2163 regno
= REGNO (reg
);
2164 if (regno
< FIRST_PSEUDO_REGISTER
)
2165 mark_hard_regno_death (regno
, REG_NREGS (reg
));
2167 mark_pseudo_death (regno
);
2170 /* Process SETTER of REG. DATA is an insn containing the setter. */
2172 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
2174 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
2177 ((rtx
) data
, reg
, false,
2178 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
2181 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2183 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
2185 if (GET_CODE (setter
) == CLOBBER
)
2186 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2189 /* Set up reg pressure info related to INSN. */
2191 init_insn_reg_pressure_info (rtx_insn
*insn
)
2195 static struct reg_pressure_data
*pressure_info
;
2198 gcc_assert (sched_pressure
!= SCHED_PRESSURE_NONE
);
2200 if (! INSN_P (insn
))
2203 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2205 cl
= ira_pressure_classes
[i
];
2206 reg_pressure_info
[cl
].clobber_increase
= 0;
2207 reg_pressure_info
[cl
].set_increase
= 0;
2208 reg_pressure_info
[cl
].unused_set_increase
= 0;
2209 reg_pressure_info
[cl
].change
= 0;
2212 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2214 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2217 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2218 if (REG_NOTE_KIND (link
) == REG_INC
)
2219 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2221 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2222 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2223 mark_reg_death (XEXP (link
, 0));
2225 len
= sizeof (struct reg_pressure_data
) * ira_pressure_classes_num
;
2227 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2228 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2229 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_pressure_classes_num
2231 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2233 cl
= ira_pressure_classes
[i
];
2234 pressure_info
[i
].clobber_increase
2235 = reg_pressure_info
[cl
].clobber_increase
;
2236 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2237 pressure_info
[i
].unused_set_increase
2238 = reg_pressure_info
[cl
].unused_set_increase
;
2239 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2246 /* Internal variable for sched_analyze_[12] () functions.
2247 If it is nonzero, this means that sched_analyze_[12] looks
2248 at the most toplevel SET. */
2249 static bool can_start_lhs_rhs_p
;
2251 /* Extend reg info for the deps context DEPS given that
2252 we have just generated a register numbered REGNO. */
2254 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2256 int max_regno
= regno
+ 1;
2258 gcc_assert (!reload_completed
);
2260 /* In a readonly context, it would not hurt to extend info,
2261 but it should not be needed. */
2262 if (reload_completed
&& deps
->readonly
)
2264 deps
->max_reg
= max_regno
;
2268 if (max_regno
> deps
->max_reg
)
2270 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2272 memset (&deps
->reg_last
[deps
->max_reg
],
2273 0, (max_regno
- deps
->max_reg
)
2274 * sizeof (struct deps_reg
));
2275 deps
->max_reg
= max_regno
;
2279 /* Extends REG_INFO_P if needed. */
2281 maybe_extend_reg_info_p (void)
2283 /* Extend REG_INFO_P, if needed. */
2284 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2286 size_t new_reg_info_p_size
= max_regno
+ 128;
2288 gcc_assert (!reload_completed
&& sel_sched_p ());
2290 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2291 new_reg_info_p_size
,
2293 sizeof (*reg_info_p
));
2294 reg_info_p_size
= new_reg_info_p_size
;
2298 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2299 The type of the reference is specified by REF and can be SET,
2300 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2303 sched_analyze_reg (struct deps_desc
*deps
, int regno
, machine_mode mode
,
2304 enum rtx_code ref
, rtx_insn
*insn
)
2306 /* We could emit new pseudos in renaming. Extend the reg structures. */
2307 if (!reload_completed
&& sel_sched_p ()
2308 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2309 extend_deps_reg_info (deps
, regno
);
2311 maybe_extend_reg_info_p ();
2313 /* A hard reg in a wide mode may really be multiple registers.
2314 If so, mark all of them just like the first. */
2315 if (regno
< FIRST_PSEUDO_REGISTER
)
2317 int i
= hard_regno_nregs
[regno
][mode
];
2321 note_reg_set (regno
+ i
);
2323 else if (ref
== USE
)
2326 note_reg_use (regno
+ i
);
2331 note_reg_clobber (regno
+ i
);
2335 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2336 it does not reload. Ignore these as they have served their
2338 else if (regno
>= deps
->max_reg
)
2340 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2341 gcc_assert (code
== USE
|| code
== CLOBBER
);
2347 note_reg_set (regno
);
2348 else if (ref
== USE
)
2349 note_reg_use (regno
);
2351 note_reg_clobber (regno
);
2353 /* Pseudos that are REG_EQUIV to something may be replaced
2354 by that during reloading. We need only add dependencies for
2355 the address in the REG_EQUIV note. */
2356 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2358 rtx t
= get_reg_known_value (regno
);
2360 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2363 /* Don't let it cross a call after scheduling if it doesn't
2364 already cross one. */
2365 if (REG_N_CALLS_CROSSED (regno
) == 0)
2367 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2368 deps
->sched_before_next_call
2369 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2371 add_dependence_list (insn
, deps
->last_function_call
, 1,
2372 REG_DEP_ANTI
, false);
2377 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2378 rtx, X, creating all dependencies generated by the write to the
2379 destination of X, and reads of everything mentioned. */
2382 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2384 rtx dest
= XEXP (x
, 0);
2385 enum rtx_code code
= GET_CODE (x
);
2386 bool cslr_p
= can_start_lhs_rhs_p
;
2388 can_start_lhs_rhs_p
= false;
2394 if (cslr_p
&& sched_deps_info
->start_lhs
)
2395 sched_deps_info
->start_lhs (dest
);
2397 if (GET_CODE (dest
) == PARALLEL
)
2401 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2402 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2403 sched_analyze_1 (deps
,
2404 gen_rtx_CLOBBER (VOIDmode
,
2405 XEXP (XVECEXP (dest
, 0, i
), 0)),
2408 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2409 sched_deps_info
->finish_lhs ();
2413 can_start_lhs_rhs_p
= cslr_p
;
2415 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2417 can_start_lhs_rhs_p
= false;
2423 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2424 || GET_CODE (dest
) == ZERO_EXTRACT
)
2426 if (GET_CODE (dest
) == STRICT_LOW_PART
2427 || GET_CODE (dest
) == ZERO_EXTRACT
2428 || df_read_modify_subreg_p (dest
))
2430 /* These both read and modify the result. We must handle
2431 them as writes to get proper dependencies for following
2432 instructions. We must handle them as reads to get proper
2433 dependencies from this to previous instructions.
2434 Thus we need to call sched_analyze_2. */
2436 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2438 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2440 /* The second and third arguments are values read by this insn. */
2441 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2442 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2444 dest
= XEXP (dest
, 0);
2449 int regno
= REGNO (dest
);
2450 machine_mode mode
= GET_MODE (dest
);
2452 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2455 /* Treat all writes to a stack register as modifying the TOS. */
2456 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2458 /* Avoid analyzing the same register twice. */
2459 if (regno
!= FIRST_STACK_REG
)
2460 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2462 add_to_hard_reg_set (&implicit_reg_pending_uses
, mode
,
2467 else if (MEM_P (dest
))
2469 /* Writing memory. */
2472 if (sched_deps_info
->use_cselib
)
2474 machine_mode address_mode
= get_address_mode (dest
);
2476 t
= shallow_copy_rtx (dest
);
2477 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2478 GET_MODE (t
), insn
);
2480 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2485 /* Pending lists can't get larger with a readonly context. */
2487 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2488 >= MAX_PENDING_LIST_LENGTH
))
2490 /* Flush all pending reads and writes to prevent the pending lists
2491 from getting any larger. Insn scheduling runs too slowly when
2492 these lists get long. When compiling GCC with itself,
2493 this flush occurs 8 times for sparc, and 10 times for m88k using
2494 the default value of 32. */
2495 flush_pending_lists (deps
, insn
, false, true);
2499 rtx_insn_list
*pending
;
2500 rtx_expr_list
*pending_mem
;
2502 pending
= deps
->pending_read_insns
;
2503 pending_mem
= deps
->pending_read_mems
;
2506 if (anti_dependence (pending_mem
->element (), t
)
2507 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2508 note_mem_dep (t
, pending_mem
->element (), pending
->insn (),
2511 pending
= pending
->next ();
2512 pending_mem
= pending_mem
->next ();
2515 pending
= deps
->pending_write_insns
;
2516 pending_mem
= deps
->pending_write_mems
;
2519 if (output_dependence (pending_mem
->element (), t
)
2520 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
2521 note_mem_dep (t
, pending_mem
->element (),
2525 pending
= pending
->next ();
2526 pending_mem
= pending_mem
-> next ();
2529 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2530 REG_DEP_ANTI
, true);
2531 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
2532 REG_DEP_CONTROL
, true);
2534 if (!deps
->readonly
)
2535 add_insn_mem_dependence (deps
, false, insn
, dest
);
2537 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2540 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2541 sched_deps_info
->finish_lhs ();
2543 /* Analyze reads. */
2544 if (GET_CODE (x
) == SET
)
2546 can_start_lhs_rhs_p
= cslr_p
;
2548 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2550 can_start_lhs_rhs_p
= false;
2554 /* Analyze the uses of memory and registers in rtx X in INSN. */
2556 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2562 bool cslr_p
= can_start_lhs_rhs_p
;
2564 can_start_lhs_rhs_p
= false;
2570 if (cslr_p
&& sched_deps_info
->start_rhs
)
2571 sched_deps_info
->start_rhs (x
);
2573 code
= GET_CODE (x
);
2581 /* Ignore constants. */
2582 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2583 sched_deps_info
->finish_rhs ();
2591 /* User of CC0 depends on immediately preceding insn. */
2592 SCHED_GROUP_P (insn
) = 1;
2593 /* Don't move CC0 setter to another block (it can set up the
2594 same flag for previous CC0 users which is safe). */
2595 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2597 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2598 sched_deps_info
->finish_rhs ();
2604 int regno
= REGNO (x
);
2605 machine_mode mode
= GET_MODE (x
);
2607 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2610 /* Treat all reads of a stack register as modifying the TOS. */
2611 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2613 /* Avoid analyzing the same register twice. */
2614 if (regno
!= FIRST_STACK_REG
)
2615 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2616 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2620 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2621 sched_deps_info
->finish_rhs ();
2628 /* Reading memory. */
2630 rtx_insn_list
*pending
;
2631 rtx_expr_list
*pending_mem
;
2634 if (sched_deps_info
->use_cselib
)
2636 machine_mode address_mode
= get_address_mode (t
);
2638 t
= shallow_copy_rtx (t
);
2639 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1,
2640 GET_MODE (t
), insn
);
2642 = cselib_subst_to_values_from_insn (XEXP (t
, 0), GET_MODE (t
),
2646 if (!DEBUG_INSN_P (insn
))
2649 pending
= deps
->pending_read_insns
;
2650 pending_mem
= deps
->pending_read_mems
;
2653 if (read_dependence (pending_mem
->element (), t
)
2654 && ! sched_insns_conditions_mutex_p (insn
,
2656 note_mem_dep (t
, pending_mem
->element (),
2660 pending
= pending
->next ();
2661 pending_mem
= pending_mem
->next ();
2664 pending
= deps
->pending_write_insns
;
2665 pending_mem
= deps
->pending_write_mems
;
2668 if (true_dependence (pending_mem
->element (), VOIDmode
, t
)
2669 && ! sched_insns_conditions_mutex_p (insn
,
2671 note_mem_dep (t
, pending_mem
->element (),
2673 sched_deps_info
->generate_spec_deps
2674 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2676 pending
= pending
->next ();
2677 pending_mem
= pending_mem
->next ();
2680 for (u
= deps
->last_pending_memory_flush
; u
; u
= u
->next ())
2681 add_dependence (insn
, u
->insn (), REG_DEP_ANTI
);
2683 for (u
= deps
->pending_jump_insns
; u
; u
= u
->next ())
2684 if (deps_may_trap_p (x
))
2686 if ((sched_deps_info
->generate_spec_deps
)
2687 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2689 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2692 note_dep (u
->insn (), ds
);
2695 add_dependence (insn
, u
->insn (), REG_DEP_CONTROL
);
2699 /* Always add these dependencies to pending_reads, since
2700 this insn may be followed by a write. */
2701 if (!deps
->readonly
)
2703 if ((deps
->pending_read_list_length
2704 + deps
->pending_write_list_length
)
2705 >= MAX_PENDING_LIST_LENGTH
2706 && !DEBUG_INSN_P (insn
))
2707 flush_pending_lists (deps
, insn
, true, true);
2708 add_insn_mem_dependence (deps
, true, insn
, x
);
2711 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2713 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2714 sched_deps_info
->finish_rhs ();
2719 /* Force pending stores to memory in case a trap handler needs them. */
2721 flush_pending_lists (deps
, insn
, true, false);
2725 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2726 reg_pending_barrier
= TRUE_BARRIER
;
2727 /* Prefetch insn contains addresses only. So if the prefetch
2728 address has no registers, there will be no dependencies on
2729 the prefetch insn. This is wrong with result code
2730 correctness point of view as such prefetch can be moved below
2731 a jump insn which usually generates MOVE_BARRIER preventing
2732 to move insns containing registers or memories through the
2733 barrier. It is also wrong with generated code performance
2734 point of view as prefetch withouth dependecies will have a
2735 tendency to be issued later instead of earlier. It is hard
2736 to generate accurate dependencies for prefetch insns as
2737 prefetch has only the start address but it is better to have
2738 something than nothing. */
2739 if (!deps
->readonly
)
2741 rtx x
= gen_rtx_MEM (Pmode
, XEXP (PATTERN (insn
), 0));
2742 if (sched_deps_info
->use_cselib
)
2743 cselib_lookup_from_insn (x
, Pmode
, true, VOIDmode
, insn
);
2744 add_insn_mem_dependence (deps
, true, insn
, x
);
2748 case UNSPEC_VOLATILE
:
2749 flush_pending_lists (deps
, insn
, true, true);
2755 /* Traditional and volatile asm instructions must be considered to use
2756 and clobber all hard registers, all pseudo-registers and all of
2757 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2759 Consider for instance a volatile asm that changes the fpu rounding
2760 mode. An insn should not be moved across this even if it only uses
2761 pseudo-regs because it might give an incorrectly rounded result. */
2762 if ((code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2763 && !DEBUG_INSN_P (insn
))
2764 reg_pending_barrier
= TRUE_BARRIER
;
2766 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2767 We can not just fall through here since then we would be confused
2768 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2769 traditional asms unlike their normal usage. */
2771 if (code
== ASM_OPERANDS
)
2773 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2774 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2776 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2777 sched_deps_info
->finish_rhs ();
2788 /* These both read and modify the result. We must handle them as writes
2789 to get proper dependencies for following instructions. We must handle
2790 them as reads to get proper dependencies from this to previous
2791 instructions. Thus we need to pass them to both sched_analyze_1
2792 and sched_analyze_2. We must call sched_analyze_2 first in order
2793 to get the proper antecedent for the read. */
2794 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2795 sched_analyze_1 (deps
, x
, insn
);
2797 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2798 sched_deps_info
->finish_rhs ();
2804 /* op0 = op0 + op1 */
2805 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2806 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2807 sched_analyze_1 (deps
, x
, insn
);
2809 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2810 sched_deps_info
->finish_rhs ();
2818 /* Other cases: walk the insn. */
2819 fmt
= GET_RTX_FORMAT (code
);
2820 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2823 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2824 else if (fmt
[i
] == 'E')
2825 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2826 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2829 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2830 sched_deps_info
->finish_rhs ();
2833 /* Try to group two fusible insns together to prevent scheduler
2834 from scheduling them apart. */
2837 sched_macro_fuse_insns (rtx_insn
*insn
)
2841 if (any_condjump_p (insn
))
2843 unsigned int condreg1
, condreg2
;
2845 targetm
.fixed_condition_code_regs (&condreg1
, &condreg2
);
2846 cc_reg_1
= gen_rtx_REG (CCmode
, condreg1
);
2847 prev
= prev_nonnote_nondebug_insn (insn
);
2848 if (!reg_referenced_p (cc_reg_1
, PATTERN (insn
))
2850 || !modified_in_p (cc_reg_1
, prev
))
2855 rtx insn_set
= single_set (insn
);
2857 prev
= prev_nonnote_nondebug_insn (insn
);
2860 || !single_set (prev
))
2865 if (targetm
.sched
.macro_fusion_pair_p (prev
, insn
))
2866 SCHED_GROUP_P (insn
) = 1;
2870 /* Analyze an INSN with pattern X to find all dependencies. */
2872 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx_insn
*insn
)
2874 RTX_CODE code
= GET_CODE (x
);
2877 reg_set_iterator rsi
;
2879 if (! reload_completed
)
2883 extract_insn (insn
);
2884 preprocess_constraints (insn
);
2885 alternative_mask prefrred
= get_preferred_alternatives (insn
);
2886 ira_implicitly_set_insn_hard_regs (&temp
, prefrred
);
2887 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2888 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2891 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2894 /* Group compare and branch insns for macro-fusion. */
2895 if (targetm
.sched
.macro_fusion_p
2896 && targetm
.sched
.macro_fusion_p ())
2897 sched_macro_fuse_insns (insn
);
2900 /* Avoid moving trapping instructions across function calls that might
2901 not always return. */
2902 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2903 1, REG_DEP_ANTI
, true);
2905 /* We must avoid creating a situation in which two successors of the
2906 current block have different unwind info after scheduling. If at any
2907 point the two paths re-join this leads to incorrect unwind info. */
2908 /* ??? There are certain situations involving a forced frame pointer in
2909 which, with extra effort, we could fix up the unwind info at a later
2910 CFG join. However, it seems better to notice these cases earlier
2911 during prologue generation and avoid marking the frame pointer setup
2912 as frame-related at all. */
2913 if (RTX_FRAME_RELATED_P (insn
))
2915 /* Make sure prologue insn is scheduled before next jump. */
2916 deps
->sched_before_next_jump
2917 = alloc_INSN_LIST (insn
, deps
->sched_before_next_jump
);
2919 /* Make sure epilogue insn is scheduled after preceding jumps. */
2920 add_dependence_list (insn
, deps
->pending_jump_insns
, 1, REG_DEP_ANTI
,
2924 if (code
== COND_EXEC
)
2926 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2928 /* ??? Should be recording conditions so we reduce the number of
2929 false dependencies. */
2930 x
= COND_EXEC_CODE (x
);
2931 code
= GET_CODE (x
);
2933 if (code
== SET
|| code
== CLOBBER
)
2935 sched_analyze_1 (deps
, x
, insn
);
2937 /* Bare clobber insns are used for letting life analysis, reg-stack
2938 and others know that a value is dead. Depend on the last call
2939 instruction so that reg-stack won't get confused. */
2940 if (code
== CLOBBER
)
2941 add_dependence_list (insn
, deps
->last_function_call
, 1,
2942 REG_DEP_OUTPUT
, true);
2944 else if (code
== PARALLEL
)
2946 for (i
= XVECLEN (x
, 0); i
--;)
2948 rtx sub
= XVECEXP (x
, 0, i
);
2949 code
= GET_CODE (sub
);
2951 if (code
== COND_EXEC
)
2953 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2954 sub
= COND_EXEC_CODE (sub
);
2955 code
= GET_CODE (sub
);
2957 if (code
== SET
|| code
== CLOBBER
)
2958 sched_analyze_1 (deps
, sub
, insn
);
2960 sched_analyze_2 (deps
, sub
, insn
);
2964 sched_analyze_2 (deps
, x
, insn
);
2966 /* Mark registers CLOBBERED or used by called function. */
2969 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2971 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2972 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2973 else if (GET_CODE (XEXP (link
, 0)) != SET
)
2974 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2976 /* Don't schedule anything after a tail call, tail call needs
2977 to use at least all call-saved registers. */
2978 if (SIBLING_CALL_P (insn
))
2979 reg_pending_barrier
= TRUE_BARRIER
;
2980 else if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2981 reg_pending_barrier
= MOVE_BARRIER
;
2986 rtx_insn
*next
= next_nonnote_nondebug_insn (insn
);
2987 if (next
&& BARRIER_P (next
))
2988 reg_pending_barrier
= MOVE_BARRIER
;
2991 rtx_insn_list
*pending
;
2992 rtx_expr_list
*pending_mem
;
2994 if (sched_deps_info
->compute_jump_reg_dependencies
)
2996 (*sched_deps_info
->compute_jump_reg_dependencies
)
2997 (insn
, reg_pending_control_uses
);
2999 /* Make latency of jump equal to 0 by using anti-dependence. */
3000 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3002 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3003 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
,
3005 add_dependence_list (insn
, reg_last
->implicit_sets
,
3006 0, REG_DEP_ANTI
, false);
3007 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3008 REG_DEP_ANTI
, false);
3012 /* All memory writes and volatile reads must happen before the
3013 jump. Non-volatile reads must happen before the jump iff
3014 the result is needed by the above register used mask. */
3016 pending
= deps
->pending_write_insns
;
3017 pending_mem
= deps
->pending_write_mems
;
3020 if (! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3021 add_dependence (insn
, pending
->insn (),
3023 pending
= pending
->next ();
3024 pending_mem
= pending_mem
->next ();
3027 pending
= deps
->pending_read_insns
;
3028 pending_mem
= deps
->pending_read_mems
;
3031 if (MEM_VOLATILE_P (pending_mem
->element ())
3032 && ! sched_insns_conditions_mutex_p (insn
, pending
->insn ()))
3033 add_dependence (insn
, pending
->insn (),
3035 pending
= pending
->next ();
3036 pending_mem
= pending_mem
->next ();
3039 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
3040 REG_DEP_ANTI
, true);
3041 add_dependence_list (insn
, deps
->pending_jump_insns
, 1,
3042 REG_DEP_ANTI
, true);
3046 /* If this instruction can throw an exception, then moving it changes
3047 where block boundaries fall. This is mighty confusing elsewhere.
3048 Therefore, prevent such an instruction from being moved. Same for
3049 non-jump instructions that define block boundaries.
3050 ??? Unclear whether this is still necessary in EBB mode. If not,
3051 add_branch_dependences should be adjusted for RGN mode instead. */
3052 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
3053 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
3054 reg_pending_barrier
= MOVE_BARRIER
;
3056 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
3058 setup_insn_reg_uses (deps
, insn
);
3059 init_insn_reg_pressure_info (insn
);
3062 /* Add register dependencies for insn. */
3063 if (DEBUG_INSN_P (insn
))
3065 rtx_insn
*prev
= deps
->last_debug_insn
;
3068 if (!deps
->readonly
)
3069 deps
->last_debug_insn
= insn
;
3072 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3074 add_dependence_list (insn
, deps
->last_function_call
, 1,
3075 REG_DEP_ANTI
, false);
3077 if (!sel_sched_p ())
3078 for (u
= deps
->last_pending_memory_flush
; u
; u
= u
->next ())
3079 add_dependence (insn
, u
->insn (), REG_DEP_ANTI
);
3081 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3083 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3084 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
, false);
3085 /* There's no point in making REG_DEP_CONTROL dependencies for
3087 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
,
3090 if (!deps
->readonly
)
3091 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3093 CLEAR_REG_SET (reg_pending_uses
);
3095 /* Quite often, a debug insn will refer to stuff in the
3096 previous instruction, but the reason we want this
3097 dependency here is to make sure the scheduler doesn't
3098 gratuitously move a debug insn ahead. This could dirty
3099 DF flags and cause additional analysis that wouldn't have
3100 occurred in compilation without debug insns, and such
3101 additional analysis can modify the generated code. */
3102 prev
= PREV_INSN (insn
);
3104 if (prev
&& NONDEBUG_INSN_P (prev
))
3105 add_dependence (insn
, prev
, REG_DEP_ANTI
);
3109 regset_head set_or_clobbered
;
3111 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
3113 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3114 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3115 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
,
3117 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3120 if (!deps
->readonly
)
3122 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3123 reg_last
->uses_length
++;
3127 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3128 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
3130 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3131 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
, false);
3132 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3133 REG_DEP_ANTI
, false);
3134 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
,
3137 if (!deps
->readonly
)
3139 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
3140 reg_last
->uses_length
++;
3144 if (targetm
.sched
.exposed_pipeline
)
3146 INIT_REG_SET (&set_or_clobbered
);
3147 bitmap_ior (&set_or_clobbered
, reg_pending_clobbers
,
3149 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered
, 0, i
, rsi
)
3151 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3153 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
3155 rtx other
= XEXP (list
, 0);
3156 if (INSN_CACHED_COND (other
) != const_true_rtx
3157 && refers_to_regno_p (i
, INSN_CACHED_COND (other
)))
3158 INSN_CACHED_COND (other
) = const_true_rtx
;
3163 /* If the current insn is conditional, we can't free any
3165 if (sched_has_condition_p (insn
))
3167 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3169 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3170 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3172 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3173 REG_DEP_ANTI
, false);
3174 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3176 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3177 REG_DEP_CONTROL
, false);
3179 if (!deps
->readonly
)
3182 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3183 reg_last
->clobbers_length
++;
3186 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3188 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3189 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3191 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3192 REG_DEP_ANTI
, false);
3193 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
,
3195 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3197 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3198 REG_DEP_CONTROL
, false);
3200 if (!deps
->readonly
)
3201 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3206 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
3208 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3209 if (reg_last
->uses_length
>= MAX_PENDING_LIST_LENGTH
3210 || reg_last
->clobbers_length
>= MAX_PENDING_LIST_LENGTH
)
3212 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3213 REG_DEP_OUTPUT
, false);
3214 add_dependence_list_and_free (deps
, insn
,
3215 ®_last
->implicit_sets
, 0,
3216 REG_DEP_ANTI
, false);
3217 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3218 REG_DEP_ANTI
, false);
3219 add_dependence_list_and_free (deps
, insn
,
3220 ®_last
->control_uses
, 0,
3221 REG_DEP_ANTI
, false);
3222 add_dependence_list_and_free (deps
, insn
,
3223 ®_last
->clobbers
, 0,
3224 REG_DEP_OUTPUT
, false);
3226 if (!deps
->readonly
)
3228 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3229 reg_last
->clobbers_length
= 0;
3230 reg_last
->uses_length
= 0;
3235 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
,
3237 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3238 REG_DEP_ANTI
, false);
3239 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3241 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3242 REG_DEP_CONTROL
, false);
3245 if (!deps
->readonly
)
3247 reg_last
->clobbers_length
++;
3249 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
3252 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
3254 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3256 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3257 REG_DEP_OUTPUT
, false);
3258 add_dependence_list_and_free (deps
, insn
,
3259 ®_last
->implicit_sets
,
3260 0, REG_DEP_ANTI
, false);
3261 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3262 REG_DEP_OUTPUT
, false);
3263 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3264 REG_DEP_ANTI
, false);
3265 add_dependence_list (insn
, reg_last
->control_uses
, 0,
3266 REG_DEP_CONTROL
, false);
3268 if (!deps
->readonly
)
3270 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3271 reg_last
->uses_length
= 0;
3272 reg_last
->clobbers_length
= 0;
3276 if (!deps
->readonly
)
3278 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses
, 0, i
, rsi
)
3280 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3281 reg_last
->control_uses
3282 = alloc_INSN_LIST (insn
, reg_last
->control_uses
);
3287 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3288 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3290 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3291 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
, false);
3292 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
, false);
3293 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
, false);
3294 add_dependence_list (insn
, reg_last
->control_uses
, 0, REG_DEP_ANTI
,
3297 if (!deps
->readonly
)
3298 reg_last
->implicit_sets
3299 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
3302 if (!deps
->readonly
)
3304 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
3305 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
3306 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
3307 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3308 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
3309 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
3310 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3312 /* Set up the pending barrier found. */
3313 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
3316 CLEAR_REG_SET (reg_pending_uses
);
3317 CLEAR_REG_SET (reg_pending_clobbers
);
3318 CLEAR_REG_SET (reg_pending_sets
);
3319 CLEAR_REG_SET (reg_pending_control_uses
);
3320 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3321 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3323 /* Add dependencies if a scheduling barrier was found. */
3324 if (reg_pending_barrier
)
3326 /* In the case of barrier the most added dependencies are not
3327 real, so we use anti-dependence here. */
3328 if (sched_has_condition_p (insn
))
3330 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3332 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3333 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
,
3335 add_dependence_list (insn
, reg_last
->sets
, 0,
3336 reg_pending_barrier
== TRUE_BARRIER
3337 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3338 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3339 REG_DEP_ANTI
, true);
3340 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3341 reg_pending_barrier
== TRUE_BARRIER
3342 ? REG_DEP_TRUE
: REG_DEP_ANTI
, true);
3347 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3349 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3350 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3351 REG_DEP_ANTI
, true);
3352 add_dependence_list_and_free (deps
, insn
,
3353 ®_last
->control_uses
, 0,
3354 REG_DEP_CONTROL
, true);
3355 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3356 reg_pending_barrier
== TRUE_BARRIER
3357 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3359 add_dependence_list_and_free (deps
, insn
,
3360 ®_last
->implicit_sets
, 0,
3361 REG_DEP_ANTI
, true);
3362 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3363 reg_pending_barrier
== TRUE_BARRIER
3364 ? REG_DEP_TRUE
: REG_DEP_ANTI
,
3367 if (!deps
->readonly
)
3369 reg_last
->uses_length
= 0;
3370 reg_last
->clobbers_length
= 0;
3375 if (!deps
->readonly
)
3376 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3378 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3379 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3380 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3383 /* Don't flush pending lists on speculative checks for
3384 selective scheduling. */
3385 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn
))
3386 flush_pending_lists (deps
, insn
, true, true);
3388 reg_pending_barrier
= NOT_A_BARRIER
;
3391 /* If a post-call group is still open, see if it should remain so.
3392 This insn must be a simple move of a hard reg to a pseudo or
3395 We must avoid moving these insns for correctness on targets
3396 with small register classes, and for special registers like
3397 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3398 hard regs for all targets. */
3400 if (deps
->in_post_call_group_p
)
3402 rtx tmp
, set
= single_set (insn
);
3403 int src_regno
, dest_regno
;
3407 if (DEBUG_INSN_P (insn
))
3408 /* We don't want to mark debug insns as part of the same
3409 sched group. We know they really aren't, but if we use
3410 debug insns to tell that a call group is over, we'll
3411 get different code if debug insns are not there and
3412 instructions that follow seem like they should be part
3415 Also, if we did, chain_to_prev_insn would move the
3416 deps of the debug insn to the call insn, modifying
3417 non-debug post-dependency counts of the debug insn
3418 dependencies and otherwise messing with the scheduling
3421 Instead, let such debug insns be scheduled freely, but
3422 keep the call group open in case there are insns that
3423 should be part of it afterwards. Since we grant debug
3424 insns higher priority than even sched group insns, it
3425 will all turn out all right. */
3426 goto debug_dont_end_call_group
;
3428 goto end_call_group
;
3431 tmp
= SET_DEST (set
);
3432 if (GET_CODE (tmp
) == SUBREG
)
3433 tmp
= SUBREG_REG (tmp
);
3435 dest_regno
= REGNO (tmp
);
3437 goto end_call_group
;
3439 tmp
= SET_SRC (set
);
3440 if (GET_CODE (tmp
) == SUBREG
)
3441 tmp
= SUBREG_REG (tmp
);
3442 if ((GET_CODE (tmp
) == PLUS
3443 || GET_CODE (tmp
) == MINUS
)
3444 && REG_P (XEXP (tmp
, 0))
3445 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3446 && dest_regno
== STACK_POINTER_REGNUM
)
3447 src_regno
= STACK_POINTER_REGNUM
;
3448 else if (REG_P (tmp
))
3449 src_regno
= REGNO (tmp
);
3451 goto end_call_group
;
3453 if (src_regno
< FIRST_PSEUDO_REGISTER
3454 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3457 && deps
->in_post_call_group_p
== post_call_initial
)
3458 deps
->in_post_call_group_p
= post_call
;
3460 if (!sel_sched_p () || sched_emulate_haifa_p
)
3462 SCHED_GROUP_P (insn
) = 1;
3463 CANT_MOVE (insn
) = 1;
3469 if (!deps
->readonly
)
3470 deps
->in_post_call_group_p
= not_post_call
;
3474 debug_dont_end_call_group
:
3475 if ((current_sched_info
->flags
& DO_SPECULATION
)
3476 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3477 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3481 sel_mark_hard_insn (insn
);
3484 sd_iterator_def sd_it
;
3487 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3488 sd_iterator_cond (&sd_it
, &dep
);)
3489 change_spec_dep_to_hard (sd_it
);
3493 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3494 honor their original ordering. */
3495 if (find_reg_note (insn
, REG_ARGS_SIZE
, NULL
))
3497 if (deps
->last_args_size
)
3498 add_dependence (insn
, deps
->last_args_size
, REG_DEP_OUTPUT
);
3499 deps
->last_args_size
= insn
;
3503 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3504 longjmp, loop forever, ...). */
3505 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3506 test for ECF_NORETURN? */
3508 call_may_noreturn_p (rtx_insn
*insn
)
3512 /* const or pure calls that aren't looping will always return. */
3513 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3514 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3517 call
= get_call_rtx_from (insn
);
3518 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3520 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3521 if (SYMBOL_REF_DECL (symbol
)
3522 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3524 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3526 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3529 case BUILT_IN_BCOPY
:
3530 case BUILT_IN_BZERO
:
3531 case BUILT_IN_INDEX
:
3532 case BUILT_IN_MEMCHR
:
3533 case BUILT_IN_MEMCMP
:
3534 case BUILT_IN_MEMCPY
:
3535 case BUILT_IN_MEMMOVE
:
3536 case BUILT_IN_MEMPCPY
:
3537 case BUILT_IN_MEMSET
:
3538 case BUILT_IN_RINDEX
:
3539 case BUILT_IN_STPCPY
:
3540 case BUILT_IN_STPNCPY
:
3541 case BUILT_IN_STRCAT
:
3542 case BUILT_IN_STRCHR
:
3543 case BUILT_IN_STRCMP
:
3544 case BUILT_IN_STRCPY
:
3545 case BUILT_IN_STRCSPN
:
3546 case BUILT_IN_STRLEN
:
3547 case BUILT_IN_STRNCAT
:
3548 case BUILT_IN_STRNCMP
:
3549 case BUILT_IN_STRNCPY
:
3550 case BUILT_IN_STRPBRK
:
3551 case BUILT_IN_STRRCHR
:
3552 case BUILT_IN_STRSPN
:
3553 case BUILT_IN_STRSTR
:
3554 /* Assume certain string/memory builtins always return. */
3562 /* For all other calls assume that they might not always return. */
3566 /* Return true if INSN should be made dependent on the previous instruction
3567 group, and if all INSN's dependencies should be moved to the first
3568 instruction of that group. */
3571 chain_to_prev_insn_p (rtx_insn
*insn
)
3573 /* INSN forms a group with the previous instruction. */
3574 if (SCHED_GROUP_P (insn
))
3577 /* If the previous instruction clobbers a register R and this one sets
3578 part of R, the clobber was added specifically to help us track the
3579 liveness of R. There's no point scheduling the clobber and leaving
3580 INSN behind, especially if we move the clobber to another block. */
3581 rtx_insn
*prev
= prev_nonnote_nondebug_insn (insn
);
3584 && BLOCK_FOR_INSN (prev
) == BLOCK_FOR_INSN (insn
)
3585 && GET_CODE (PATTERN (prev
)) == CLOBBER
)
3587 rtx x
= XEXP (PATTERN (prev
), 0);
3588 if (set_of (x
, insn
))
3595 /* Analyze INSN with DEPS as a context. */
3597 deps_analyze_insn (struct deps_desc
*deps
, rtx_insn
*insn
)
3599 if (sched_deps_info
->start_insn
)
3600 sched_deps_info
->start_insn (insn
);
3602 /* Record the condition for this insn. */
3603 if (NONDEBUG_INSN_P (insn
))
3606 sched_get_condition_with_rev (insn
, NULL
);
3607 t
= INSN_CACHED_COND (insn
);
3608 INSN_COND_DEPS (insn
) = NULL
;
3609 if (reload_completed
3610 && (current_sched_info
->flags
& DO_PREDICATION
)
3612 && REG_P (XEXP (t
, 0))
3613 && CONSTANT_P (XEXP (t
, 1)))
3617 rtx_insn_list
*cond_deps
= NULL
;
3620 nregs
= REG_NREGS (t
);
3623 struct deps_reg
*reg_last
= &deps
->reg_last
[regno
+ nregs
];
3624 cond_deps
= concat_INSN_LIST (reg_last
->sets
, cond_deps
);
3625 cond_deps
= concat_INSN_LIST (reg_last
->clobbers
, cond_deps
);
3626 cond_deps
= concat_INSN_LIST (reg_last
->implicit_sets
, cond_deps
);
3628 INSN_COND_DEPS (insn
) = cond_deps
;
3634 /* Make each JUMP_INSN (but not a speculative check)
3635 a scheduling barrier for memory references. */
3638 && sel_insn_is_speculation_check (insn
)))
3640 /* Keep the list a reasonable size. */
3641 if (deps
->pending_flush_length
++ >= MAX_PENDING_LIST_LENGTH
)
3642 flush_pending_lists (deps
, insn
, true, true);
3644 deps
->pending_jump_insns
3645 = alloc_INSN_LIST (insn
, deps
->pending_jump_insns
);
3648 /* For each insn which shouldn't cross a jump, add a dependence. */
3649 add_dependence_list_and_free (deps
, insn
,
3650 &deps
->sched_before_next_jump
, 1,
3651 REG_DEP_ANTI
, true);
3653 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3655 else if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
))
3657 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3659 else if (CALL_P (insn
))
3663 CANT_MOVE (insn
) = 1;
3665 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3667 /* This is setjmp. Assume that all registers, not just
3668 hard registers, may be clobbered by this call. */
3669 reg_pending_barrier
= MOVE_BARRIER
;
3673 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3674 /* A call may read and modify global register variables. */
3677 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3678 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3680 /* Other call-clobbered hard regs may be clobbered.
3681 Since we only have a choice between 'might be clobbered'
3682 and 'definitely not clobbered', we must include all
3683 partly call-clobbered registers here. */
3684 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3685 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3686 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3687 /* We don't know what set of fixed registers might be used
3688 by the function, but it is certain that the stack pointer
3689 is among them, but be conservative. */
3690 else if (fixed_regs
[i
])
3691 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3692 /* The frame pointer is normally not used by the function
3693 itself, but by the debugger. */
3694 /* ??? MIPS o32 is an exception. It uses the frame pointer
3695 in the macro expansion of jal but does not represent this
3696 fact in the call_insn rtl. */
3697 else if (i
== FRAME_POINTER_REGNUM
3698 || (i
== HARD_FRAME_POINTER_REGNUM
3699 && (! reload_completed
|| frame_pointer_needed
)))
3700 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3703 /* For each insn which shouldn't cross a call, add a dependence
3704 between that insn and this call insn. */
3705 add_dependence_list_and_free (deps
, insn
,
3706 &deps
->sched_before_next_call
, 1,
3707 REG_DEP_ANTI
, true);
3709 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3711 /* If CALL would be in a sched group, then this will violate
3712 convention that sched group insns have dependencies only on the
3713 previous instruction.
3715 Of course one can say: "Hey! What about head of the sched group?"
3716 And I will answer: "Basic principles (one dep per insn) are always
3718 gcc_assert (!SCHED_GROUP_P (insn
));
3720 /* In the absence of interprocedural alias analysis, we must flush
3721 all pending reads and writes, and start new dependencies starting
3722 from here. But only flush writes for constant calls (which may
3723 be passed a pointer to something we haven't written yet). */
3724 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3726 if (!deps
->readonly
)
3728 /* Remember the last function call for limiting lifetimes. */
3729 free_INSN_LIST_list (&deps
->last_function_call
);
3730 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3732 if (call_may_noreturn_p (insn
))
3734 /* Remember the last function call that might not always return
3735 normally for limiting moves of trapping insns. */
3736 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3737 deps
->last_function_call_may_noreturn
3738 = alloc_INSN_LIST (insn
, NULL_RTX
);
3741 /* Before reload, begin a post-call group, so as to keep the
3742 lifetimes of hard registers correct. */
3743 if (! reload_completed
)
3744 deps
->in_post_call_group_p
= post_call
;
3748 if (sched_deps_info
->use_cselib
)
3749 cselib_process_insn (insn
);
3751 if (sched_deps_info
->finish_insn
)
3752 sched_deps_info
->finish_insn ();
3754 /* Fixup the dependencies in the sched group. */
3755 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3756 && chain_to_prev_insn_p (insn
)
3758 chain_to_prev_insn (insn
);
3761 /* Initialize DEPS for the new block beginning with HEAD. */
3763 deps_start_bb (struct deps_desc
*deps
, rtx_insn
*head
)
3765 gcc_assert (!deps
->readonly
);
3767 /* Before reload, if the previous block ended in a call, show that
3768 we are inside a post-call group, so as to keep the lifetimes of
3769 hard registers correct. */
3770 if (! reload_completed
&& !LABEL_P (head
))
3772 rtx_insn
*insn
= prev_nonnote_nondebug_insn (head
);
3774 if (insn
&& CALL_P (insn
))
3775 deps
->in_post_call_group_p
= post_call_initial
;
3779 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3780 dependencies for each insn. */
3782 sched_analyze (struct deps_desc
*deps
, rtx_insn
*head
, rtx_insn
*tail
)
3786 if (sched_deps_info
->use_cselib
)
3787 cselib_init (CSELIB_RECORD_MEMORY
);
3789 deps_start_bb (deps
, head
);
3791 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3796 /* And initialize deps_lists. */
3797 sd_init_insn (insn
);
3798 /* Clean up SCHED_GROUP_P which may be set by last
3800 if (SCHED_GROUP_P (insn
))
3801 SCHED_GROUP_P (insn
) = 0;
3804 deps_analyze_insn (deps
, insn
);
3808 if (sched_deps_info
->use_cselib
)
3816 /* Helper for sched_free_deps ().
3817 Delete INSN's (RESOLVED_P) backward dependencies. */
3819 delete_dep_nodes_in_back_deps (rtx_insn
*insn
, bool resolved_p
)
3821 sd_iterator_def sd_it
;
3823 sd_list_types_def types
;
3826 types
= SD_LIST_RES_BACK
;
3828 types
= SD_LIST_BACK
;
3830 for (sd_it
= sd_iterator_start (insn
, types
);
3831 sd_iterator_cond (&sd_it
, &dep
);)
3833 dep_link_t link
= *sd_it
.linkp
;
3834 dep_node_t node
= DEP_LINK_NODE (link
);
3835 deps_list_t back_list
;
3836 deps_list_t forw_list
;
3838 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3839 remove_from_deps_list (link
, back_list
);
3840 delete_dep_node (node
);
3844 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3847 sched_free_deps (rtx_insn
*head
, rtx_insn
*tail
, bool resolved_p
)
3850 rtx_insn
*next_tail
= NEXT_INSN (tail
);
3852 /* We make two passes since some insns may be scheduled before their
3853 dependencies are resolved. */
3854 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3855 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3857 /* Clear forward deps and leave the dep_nodes to the
3858 corresponding back_deps list. */
3860 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3862 clear_deps_list (INSN_FORW_DEPS (insn
));
3864 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3865 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3867 /* Clear resolved back deps together with its dep_nodes. */
3868 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3870 sd_finish_insn (insn
);
3874 /* Initialize variables for region data dependence analysis.
3875 When LAZY_REG_LAST is true, do not allocate reg_last array
3876 of struct deps_desc immediately. */
3879 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3881 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3883 deps
->max_reg
= max_reg
;
3885 deps
->reg_last
= NULL
;
3887 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3888 INIT_REG_SET (&deps
->reg_last_in_use
);
3890 deps
->pending_read_insns
= 0;
3891 deps
->pending_read_mems
= 0;
3892 deps
->pending_write_insns
= 0;
3893 deps
->pending_write_mems
= 0;
3894 deps
->pending_jump_insns
= 0;
3895 deps
->pending_read_list_length
= 0;
3896 deps
->pending_write_list_length
= 0;
3897 deps
->pending_flush_length
= 0;
3898 deps
->last_pending_memory_flush
= 0;
3899 deps
->last_function_call
= 0;
3900 deps
->last_function_call_may_noreturn
= 0;
3901 deps
->sched_before_next_call
= 0;
3902 deps
->sched_before_next_jump
= 0;
3903 deps
->in_post_call_group_p
= not_post_call
;
3904 deps
->last_debug_insn
= 0;
3905 deps
->last_args_size
= 0;
3906 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3910 /* Init only reg_last field of DEPS, which was not allocated before as
3911 we inited DEPS lazily. */
3913 init_deps_reg_last (struct deps_desc
*deps
)
3915 gcc_assert (deps
&& deps
->max_reg
> 0);
3916 gcc_assert (deps
->reg_last
== NULL
);
3918 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3922 /* Free insn lists found in DEPS. */
3925 free_deps (struct deps_desc
*deps
)
3928 reg_set_iterator rsi
;
3930 /* We set max_reg to 0 when this context was already freed. */
3931 if (deps
->max_reg
== 0)
3933 gcc_assert (deps
->reg_last
== NULL
);
3938 free_INSN_LIST_list (&deps
->pending_read_insns
);
3939 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3940 free_INSN_LIST_list (&deps
->pending_write_insns
);
3941 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3942 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3944 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3945 times. For a testcase with 42000 regs and 8000 small basic blocks,
3946 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3947 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3949 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3951 free_INSN_LIST_list (®_last
->uses
);
3953 free_INSN_LIST_list (®_last
->sets
);
3954 if (reg_last
->implicit_sets
)
3955 free_INSN_LIST_list (®_last
->implicit_sets
);
3956 if (reg_last
->control_uses
)
3957 free_INSN_LIST_list (®_last
->control_uses
);
3958 if (reg_last
->clobbers
)
3959 free_INSN_LIST_list (®_last
->clobbers
);
3961 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3963 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3965 free (deps
->reg_last
);
3966 deps
->reg_last
= NULL
;
3971 /* Remove INSN from dependence contexts DEPS. */
3973 remove_from_deps (struct deps_desc
*deps
, rtx_insn
*insn
)
3977 reg_set_iterator rsi
;
3979 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3980 &deps
->pending_read_mems
);
3981 if (!DEBUG_INSN_P (insn
))
3982 deps
->pending_read_list_length
-= removed
;
3983 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3984 &deps
->pending_write_mems
);
3985 deps
->pending_write_list_length
-= removed
;
3987 removed
= remove_from_dependence_list (insn
, &deps
->pending_jump_insns
);
3988 deps
->pending_flush_length
-= removed
;
3989 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3990 deps
->pending_flush_length
-= removed
;
3992 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3994 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3996 remove_from_dependence_list (insn
, ®_last
->uses
);
3998 remove_from_dependence_list (insn
, ®_last
->sets
);
3999 if (reg_last
->implicit_sets
)
4000 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
4001 if (reg_last
->clobbers
)
4002 remove_from_dependence_list (insn
, ®_last
->clobbers
);
4003 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
4004 && !reg_last
->clobbers
)
4005 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
4010 remove_from_dependence_list (insn
, &deps
->last_function_call
);
4011 remove_from_dependence_list (insn
,
4012 &deps
->last_function_call_may_noreturn
);
4014 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
4017 /* Init deps data vector. */
4019 init_deps_data_vector (void)
4021 int reserve
= (sched_max_luid
+ 1 - h_d_i_d
.length ());
4022 if (reserve
> 0 && ! h_d_i_d
.space (reserve
))
4023 h_d_i_d
.safe_grow_cleared (3 * sched_max_luid
/ 2);
4026 /* If it is profitable to use them, initialize or extend (depending on
4027 GLOBAL_P) dependency data. */
4029 sched_deps_init (bool global_p
)
4031 /* Average number of insns in the basic block.
4032 '+ 1' is used to make it nonzero. */
4033 int insns_in_block
= sched_max_luid
/ n_basic_blocks_for_fn (cfun
) + 1;
4035 init_deps_data_vector ();
4037 /* We use another caching mechanism for selective scheduling, so
4038 we don't use this one. */
4039 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
4041 /* ?!? We could save some memory by computing a per-region luid mapping
4042 which could reduce both the number of vectors in the cache and the
4043 size of each vector. Instead we just avoid the cache entirely unless
4044 the average number of instructions in a basic block is very high. See
4045 the comment before the declaration of true_dependency_cache for
4046 what we consider "very high". */
4048 extend_dependency_caches (sched_max_luid
, true);
4053 dl_pool
= new object_allocator
<_deps_list
> ("deps_list");
4054 /* Allocate lists for one block at a time. */
4055 dn_pool
= new object_allocator
<_dep_node
> ("dep_node");
4056 /* Allocate nodes for one block at a time. */
4061 /* Create or extend (depending on CREATE_P) dependency caches to
4064 extend_dependency_caches (int n
, bool create_p
)
4066 if (create_p
|| true_dependency_cache
)
4068 int i
, luid
= cache_size
+ n
;
4070 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
4072 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
4073 output_dependency_cache
, luid
);
4074 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
4076 control_dependency_cache
= XRESIZEVEC (bitmap_head
, control_dependency_cache
,
4079 if (current_sched_info
->flags
& DO_SPECULATION
)
4080 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
4083 for (i
= cache_size
; i
< luid
; i
++)
4085 bitmap_initialize (&true_dependency_cache
[i
], 0);
4086 bitmap_initialize (&output_dependency_cache
[i
], 0);
4087 bitmap_initialize (&anti_dependency_cache
[i
], 0);
4088 bitmap_initialize (&control_dependency_cache
[i
], 0);
4090 if (current_sched_info
->flags
& DO_SPECULATION
)
4091 bitmap_initialize (&spec_dependency_cache
[i
], 0);
4097 /* Finalize dependency information for the whole function. */
4099 sched_deps_finish (void)
4101 gcc_assert (deps_pools_are_empty_p ());
4102 dn_pool
->release_if_empty ();
4104 dl_pool
->release_if_empty ();
4110 if (true_dependency_cache
)
4114 for (i
= 0; i
< cache_size
; i
++)
4116 bitmap_clear (&true_dependency_cache
[i
]);
4117 bitmap_clear (&output_dependency_cache
[i
]);
4118 bitmap_clear (&anti_dependency_cache
[i
]);
4119 bitmap_clear (&control_dependency_cache
[i
]);
4121 if (sched_deps_info
->generate_spec_deps
)
4122 bitmap_clear (&spec_dependency_cache
[i
]);
4124 free (true_dependency_cache
);
4125 true_dependency_cache
= NULL
;
4126 free (output_dependency_cache
);
4127 output_dependency_cache
= NULL
;
4128 free (anti_dependency_cache
);
4129 anti_dependency_cache
= NULL
;
4130 free (control_dependency_cache
);
4131 control_dependency_cache
= NULL
;
4133 if (sched_deps_info
->generate_spec_deps
)
4135 free (spec_dependency_cache
);
4136 spec_dependency_cache
= NULL
;
4142 /* Initialize some global variables needed by the dependency analysis
4146 init_deps_global (void)
4148 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
4149 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
4150 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
4151 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
4152 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
4153 reg_pending_control_uses
= ALLOC_REG_SET (®_obstack
);
4154 reg_pending_barrier
= NOT_A_BARRIER
;
4156 if (!sel_sched_p () || sched_emulate_haifa_p
)
4158 sched_deps_info
->start_insn
= haifa_start_insn
;
4159 sched_deps_info
->finish_insn
= haifa_finish_insn
;
4161 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
4162 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
4163 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
4165 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
4166 sched_deps_info
->note_dep
= haifa_note_dep
;
4170 /* Free everything used by the dependency analysis code. */
4173 finish_deps_global (void)
4175 FREE_REG_SET (reg_pending_sets
);
4176 FREE_REG_SET (reg_pending_clobbers
);
4177 FREE_REG_SET (reg_pending_uses
);
4178 FREE_REG_SET (reg_pending_control_uses
);
4181 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4183 estimate_dep_weak (rtx mem1
, rtx mem2
)
4188 /* MEMs are the same - don't speculate. */
4189 return MIN_DEP_WEAK
;
4191 r1
= XEXP (mem1
, 0);
4192 r2
= XEXP (mem2
, 0);
4195 || (REG_P (r1
) && REG_P (r2
)
4196 && REGNO (r1
) == REGNO (r2
)))
4197 /* Again, MEMs are the same. */
4198 return MIN_DEP_WEAK
;
4199 else if ((REG_P (r1
) && !REG_P (r2
))
4200 || (!REG_P (r1
) && REG_P (r2
)))
4201 /* Different addressing modes - reason to be more speculative,
4203 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
4205 /* We can't say anything about the dependence. */
4206 return UNCERTAIN_DEP_WEAK
;
4209 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4210 This function can handle same INSN and ELEM (INSN == ELEM).
4211 It is a convenience wrapper. */
4213 add_dependence_1 (rtx_insn
*insn
, rtx_insn
*elem
, enum reg_note dep_type
)
4218 if (dep_type
== REG_DEP_TRUE
)
4220 else if (dep_type
== REG_DEP_OUTPUT
)
4222 else if (dep_type
== REG_DEP_CONTROL
)
4226 gcc_assert (dep_type
== REG_DEP_ANTI
);
4230 /* When add_dependence is called from inside sched-deps.c, we expect
4231 cur_insn to be non-null. */
4232 internal
= cur_insn
!= NULL
;
4234 gcc_assert (insn
== cur_insn
);
4238 note_dep (elem
, ds
);
4243 /* Return weakness of speculative type TYPE in the dep_status DS,
4244 without checking to prevent ICEs on malformed input. */
4246 get_dep_weak_1 (ds_t ds
, ds_t type
)
4252 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
4253 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
4254 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
4255 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
4256 default: gcc_unreachable ();
4262 /* Return weakness of speculative type TYPE in the dep_status DS. */
4264 get_dep_weak (ds_t ds
, ds_t type
)
4266 dw_t dw
= get_dep_weak_1 (ds
, type
);
4268 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4272 /* Return the dep_status, which has the same parameters as DS, except for
4273 speculative type TYPE, that will have weakness DW. */
4275 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
4277 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
4282 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
4283 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
4284 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
4285 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
4286 default: gcc_unreachable ();
4291 /* Return the join of two dep_statuses DS1 and DS2.
4292 If MAX_P is true then choose the greater probability,
4293 otherwise multiply probabilities.
4294 This function assumes that both DS1 and DS2 contain speculative bits. */
4296 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
4300 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
4302 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
4304 t
= FIRST_SPEC_TYPE
;
4307 if ((ds1
& t
) && !(ds2
& t
))
4309 else if (!(ds1
& t
) && (ds2
& t
))
4311 else if ((ds1
& t
) && (ds2
& t
))
4313 dw_t dw1
= get_dep_weak (ds1
, t
);
4314 dw_t dw2
= get_dep_weak (ds2
, t
);
4319 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
4321 if (dw
< MIN_DEP_WEAK
)
4332 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
4335 if (t
== LAST_SPEC_TYPE
)
4337 t
<<= SPEC_TYPE_SHIFT
;
4344 /* Return the join of two dep_statuses DS1 and DS2.
4345 This function assumes that both DS1 and DS2 contain speculative bits. */
4347 ds_merge (ds_t ds1
, ds_t ds2
)
4349 return ds_merge_1 (ds1
, ds2
, false);
4352 /* Return the join of two dep_statuses DS1 and DS2. */
4354 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
4356 ds_t new_status
= ds
| ds2
;
4358 if (new_status
& SPECULATIVE
)
4360 if ((ds
&& !(ds
& SPECULATIVE
))
4361 || (ds2
&& !(ds2
& SPECULATIVE
)))
4362 /* Then this dep can't be speculative. */
4363 new_status
&= ~SPECULATIVE
;
4366 /* Both are speculative. Merging probabilities. */
4371 dw
= estimate_dep_weak (mem1
, mem2
);
4372 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
4380 new_status
= ds_merge (ds2
, ds
);
4387 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4390 ds_max_merge (ds_t ds1
, ds_t ds2
)
4392 if (ds1
== 0 && ds2
== 0)
4395 if (ds1
== 0 && ds2
!= 0)
4398 if (ds1
!= 0 && ds2
== 0)
4401 return ds_merge_1 (ds1
, ds2
, true);
4404 /* Return the probability of speculation success for the speculation
4412 dt
= FIRST_SPEC_TYPE
;
4417 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4421 if (dt
== LAST_SPEC_TYPE
)
4423 dt
<<= SPEC_TYPE_SHIFT
;
4429 res
/= MAX_DEP_WEAK
;
4431 if (res
< MIN_DEP_WEAK
)
4434 gcc_assert (res
<= MAX_DEP_WEAK
);
4439 /* Return a dep status that contains all speculation types of DS. */
4441 ds_get_speculation_types (ds_t ds
)
4443 if (ds
& BEGIN_DATA
)
4445 if (ds
& BE_IN_DATA
)
4447 if (ds
& BEGIN_CONTROL
)
4448 ds
|= BEGIN_CONTROL
;
4449 if (ds
& BE_IN_CONTROL
)
4450 ds
|= BE_IN_CONTROL
;
4452 return ds
& SPECULATIVE
;
4455 /* Return a dep status that contains maximal weakness for each speculation
4456 type present in DS. */
4458 ds_get_max_dep_weak (ds_t ds
)
4460 if (ds
& BEGIN_DATA
)
4461 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4462 if (ds
& BE_IN_DATA
)
4463 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4464 if (ds
& BEGIN_CONTROL
)
4465 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4466 if (ds
& BE_IN_CONTROL
)
4467 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4472 /* Dump information about the dependence status S. */
4474 dump_ds (FILE *f
, ds_t s
)
4479 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4481 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4482 if (s
& BEGIN_CONTROL
)
4483 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4484 if (s
& BE_IN_CONTROL
)
4485 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4488 fprintf (f
, "HARD_DEP; ");
4491 fprintf (f
, "DEP_TRUE; ");
4493 fprintf (f
, "DEP_OUTPUT; ");
4495 fprintf (f
, "DEP_ANTI; ");
4496 if (s
& DEP_CONTROL
)
4497 fprintf (f
, "DEP_CONTROL; ");
4505 dump_ds (stderr
, s
);
4506 fprintf (stderr
, "\n");
4509 /* Verify that dependence type and status are consistent.
4510 If RELAXED_P is true, then skip dep_weakness checks. */
4512 check_dep (dep_t dep
, bool relaxed_p
)
4514 enum reg_note dt
= DEP_TYPE (dep
);
4515 ds_t ds
= DEP_STATUS (dep
);
4517 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4519 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4521 gcc_assert (ds
== 0);
4525 /* Check that dependence type contains the same bits as the status. */
4526 if (dt
== REG_DEP_TRUE
)
4527 gcc_assert (ds
& DEP_TRUE
);
4528 else if (dt
== REG_DEP_OUTPUT
)
4529 gcc_assert ((ds
& DEP_OUTPUT
)
4530 && !(ds
& DEP_TRUE
));
4531 else if (dt
== REG_DEP_ANTI
)
4532 gcc_assert ((ds
& DEP_ANTI
)
4533 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4535 gcc_assert (dt
== REG_DEP_CONTROL
4536 && (ds
& DEP_CONTROL
)
4537 && !(ds
& (DEP_OUTPUT
| DEP_ANTI
| DEP_TRUE
)));
4539 /* HARD_DEP can not appear in dep_status of a link. */
4540 gcc_assert (!(ds
& HARD_DEP
));
4542 /* Check that dependence status is set correctly when speculation is not
4544 if (!sched_deps_info
->generate_spec_deps
)
4545 gcc_assert (!(ds
& SPECULATIVE
));
4546 else if (ds
& SPECULATIVE
)
4550 ds_t type
= FIRST_SPEC_TYPE
;
4552 /* Check that dependence weakness is in proper range. */
4556 get_dep_weak (ds
, type
);
4558 if (type
== LAST_SPEC_TYPE
)
4560 type
<<= SPEC_TYPE_SHIFT
;
4565 if (ds
& BEGIN_SPEC
)
4567 /* Only true dependence can be data speculative. */
4568 if (ds
& BEGIN_DATA
)
4569 gcc_assert (ds
& DEP_TRUE
);
4571 /* Control dependencies in the insn scheduler are represented by
4572 anti-dependencies, therefore only anti dependence can be
4573 control speculative. */
4574 if (ds
& BEGIN_CONTROL
)
4575 gcc_assert (ds
& DEP_ANTI
);
4579 /* Subsequent speculations should resolve true dependencies. */
4580 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4583 /* Check that true and anti dependencies can't have other speculative
4586 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4587 /* An output dependence can't be speculative at all. */
4588 gcc_assert (!(ds
& DEP_OUTPUT
));
4590 gcc_assert (ds
& BEGIN_CONTROL
);
4594 /* The following code discovers opportunities to switch a memory reference
4595 and an increment by modifying the address. We ensure that this is done
4596 only for dependencies that are only used to show a single register
4597 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4598 instruction involved is subject to only one dep that can cause a pattern
4601 When we discover a suitable dependency, we fill in the dep_replacement
4602 structure to show how to modify the memory reference. */
4604 /* Holds information about a pair of memory reference and register increment
4605 insns which depend on each other, but could possibly be interchanged. */
4612 /* A register occurring in the memory address for which we wish to break
4613 the dependence. This must be identical to the destination register of
4616 /* Any kind of index that is added to that register. */
4618 /* The constant offset used in the memory address. */
4619 HOST_WIDE_INT mem_constant
;
4620 /* The constant added in the increment insn. Negated if the increment is
4621 after the memory address. */
4622 HOST_WIDE_INT inc_constant
;
4623 /* The source register used in the increment. May be different from mem_reg0
4624 if the increment occurs before the memory address. */
4628 /* Verify that the memory location described in MII can be replaced with
4629 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4630 insn remains unchanged by this function. */
4633 attempt_change (struct mem_inc_info
*mii
, rtx new_addr
)
4635 rtx mem
= *mii
->mem_loc
;
4638 /* Jump through a lot of hoops to keep the attributes up to date. We
4639 do not want to call one of the change address variants that take
4640 an offset even though we know the offset in many cases. These
4641 assume you are changing where the address is pointing by the
4643 new_mem
= replace_equiv_address_nv (mem
, new_addr
);
4644 if (! validate_change (mii
->mem_insn
, mii
->mem_loc
, new_mem
, 0))
4646 if (sched_verbose
>= 5)
4647 fprintf (sched_dump
, "validation failure\n");
4651 /* Put back the old one. */
4652 validate_change (mii
->mem_insn
, mii
->mem_loc
, mem
, 0);
4657 /* Return true if INSN is of a form "a = b op c" where a and b are
4658 regs. op is + if c is a reg and +|- if c is a const. Fill in
4659 informantion in MII about what is found.
4660 BEFORE_MEM indicates whether the increment is found before or after
4661 a corresponding memory reference. */
4664 parse_add_or_inc (struct mem_inc_info
*mii
, rtx_insn
*insn
, bool before_mem
)
4666 rtx pat
= single_set (insn
);
4670 if (RTX_FRAME_RELATED_P (insn
) || !pat
)
4673 /* Result must be single reg. */
4674 if (!REG_P (SET_DEST (pat
)))
4677 if (GET_CODE (SET_SRC (pat
)) != PLUS
)
4680 mii
->inc_insn
= insn
;
4681 src
= SET_SRC (pat
);
4682 mii
->inc_input
= XEXP (src
, 0);
4684 if (!REG_P (XEXP (src
, 0)))
4687 if (!rtx_equal_p (SET_DEST (pat
), mii
->mem_reg0
))
4690 cst
= XEXP (src
, 1);
4691 if (!CONST_INT_P (cst
))
4693 mii
->inc_constant
= INTVAL (cst
);
4695 regs_equal
= rtx_equal_p (mii
->inc_input
, mii
->mem_reg0
);
4699 mii
->inc_constant
= -mii
->inc_constant
;
4704 if (regs_equal
&& REGNO (SET_DEST (pat
)) == STACK_POINTER_REGNUM
)
4706 /* Note that the sign has already been reversed for !before_mem. */
4707 if (STACK_GROWS_DOWNWARD
)
4708 return mii
->inc_constant
> 0;
4710 return mii
->inc_constant
< 0;
4715 /* Once a suitable mem reference has been found and the corresponding data
4716 in MII has been filled in, this function is called to find a suitable
4717 add or inc insn involving the register we found in the memory
4721 find_inc (struct mem_inc_info
*mii
, bool backwards
)
4723 sd_iterator_def sd_it
;
4726 sd_it
= sd_iterator_start (mii
->mem_insn
,
4727 backwards
? SD_LIST_HARD_BACK
: SD_LIST_FORW
);
4728 while (sd_iterator_cond (&sd_it
, &dep
))
4730 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
4731 rtx_insn
*pro
= DEP_PRO (dep
);
4732 rtx_insn
*con
= DEP_CON (dep
);
4733 rtx_insn
*inc_cand
= backwards
? pro
: con
;
4734 if (DEP_NONREG (dep
) || DEP_MULTIPLE (dep
))
4736 if (parse_add_or_inc (mii
, inc_cand
, backwards
))
4738 struct dep_replacement
*desc
;
4740 rtx newaddr
, newmem
;
4742 if (sched_verbose
>= 5)
4743 fprintf (sched_dump
, "candidate mem/inc pair: %d %d\n",
4744 INSN_UID (mii
->mem_insn
), INSN_UID (inc_cand
));
4746 /* Need to assure that none of the operands of the inc
4747 instruction are assigned to by the mem insn. */
4748 FOR_EACH_INSN_DEF (def
, mii
->mem_insn
)
4749 if (reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->inc_input
)
4750 || reg_overlap_mentioned_p (DF_REF_REG (def
), mii
->mem_reg0
))
4752 if (sched_verbose
>= 5)
4753 fprintf (sched_dump
,
4754 "inc conflicts with store failure.\n");
4758 newaddr
= mii
->inc_input
;
4759 if (mii
->mem_index
!= NULL_RTX
)
4760 newaddr
= gen_rtx_PLUS (GET_MODE (newaddr
), newaddr
,
4762 newaddr
= plus_constant (GET_MODE (newaddr
), newaddr
,
4763 mii
->mem_constant
+ mii
->inc_constant
);
4764 newmem
= attempt_change (mii
, newaddr
);
4765 if (newmem
== NULL_RTX
)
4767 if (sched_verbose
>= 5)
4768 fprintf (sched_dump
, "successful address replacement\n");
4769 desc
= XCNEW (struct dep_replacement
);
4770 DEP_REPLACE (dep
) = desc
;
4771 desc
->loc
= mii
->mem_loc
;
4772 desc
->newval
= newmem
;
4773 desc
->orig
= *desc
->loc
;
4774 desc
->insn
= mii
->mem_insn
;
4775 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
4776 INSN_SPEC_BACK_DEPS (con
));
4779 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_BACK
, sd_it
, dep
)
4780 add_dependence_1 (mii
->mem_insn
, DEP_PRO (dep
),
4785 FOR_EACH_DEP (mii
->inc_insn
, SD_LIST_FORW
, sd_it
, dep
)
4786 add_dependence_1 (DEP_CON (dep
), mii
->mem_insn
,
4792 sd_iterator_next (&sd_it
);
4797 /* A recursive function that walks ADDRESS_OF_X to find memory references
4798 which could be modified during scheduling. We call find_inc for each
4799 one we find that has a recognizable form. MII holds information about
4800 the pair of memory/increment instructions.
4801 We ensure that every instruction with a memory reference (which will be
4802 the location of the replacement) is assigned at most one breakable
4806 find_mem (struct mem_inc_info
*mii
, rtx
*address_of_x
)
4808 rtx x
= *address_of_x
;
4809 enum rtx_code code
= GET_CODE (x
);
4810 const char *const fmt
= GET_RTX_FORMAT (code
);
4815 rtx reg0
= XEXP (x
, 0);
4817 mii
->mem_loc
= address_of_x
;
4818 mii
->mem_index
= NULL_RTX
;
4819 mii
->mem_constant
= 0;
4820 if (GET_CODE (reg0
) == PLUS
&& CONST_INT_P (XEXP (reg0
, 1)))
4822 mii
->mem_constant
= INTVAL (XEXP (reg0
, 1));
4823 reg0
= XEXP (reg0
, 0);
4825 if (GET_CODE (reg0
) == PLUS
)
4827 mii
->mem_index
= XEXP (reg0
, 1);
4828 reg0
= XEXP (reg0
, 0);
4833 int occurrences
= 0;
4835 /* Make sure this reg appears only once in this insn. Can't use
4836 count_occurrences since that only works for pseudos. */
4837 FOR_EACH_INSN_USE (use
, mii
->mem_insn
)
4838 if (reg_overlap_mentioned_p (reg0
, DF_REF_REG (use
)))
4839 if (++occurrences
> 1)
4841 if (sched_verbose
>= 5)
4842 fprintf (sched_dump
, "mem count failure\n");
4846 mii
->mem_reg0
= reg0
;
4847 return find_inc (mii
, true) || find_inc (mii
, false);
4852 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
4854 /* If REG occurs inside a MEM used in a bit-field reference,
4855 that is unacceptable. */
4859 /* Time for some deep diving. */
4860 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4864 if (find_mem (mii
, &XEXP (x
, i
)))
4867 else if (fmt
[i
] == 'E')
4870 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4871 if (find_mem (mii
, &XVECEXP (x
, i
, j
)))
4879 /* Examine the instructions between HEAD and TAIL and try to find
4880 dependencies that can be broken by modifying one of the patterns. */
4883 find_modifiable_mems (rtx_insn
*head
, rtx_insn
*tail
)
4885 rtx_insn
*insn
, *next_tail
= NEXT_INSN (tail
);
4886 int success_in_block
= 0;
4888 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4890 struct mem_inc_info mii
;
4892 if (!NONDEBUG_INSN_P (insn
) || RTX_FRAME_RELATED_P (insn
))
4895 mii
.mem_insn
= insn
;
4896 if (find_mem (&mii
, &PATTERN (insn
)))
4899 if (success_in_block
&& sched_verbose
>= 5)
4900 fprintf (sched_dump
, "%d candidates for address modification found.\n",
4904 #endif /* INSN_SCHEDULING */