1 /* Instruction scheduling pass. This file computes dependencies between
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
5 Free Software Foundation, Inc.
6 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
7 and currently maintained by, Jim Wilson (wilson@cygnus.com)
9 This file is part of GCC.
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3. If not see
23 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
29 #include "diagnostic-core.h"
33 #include "hard-reg-set.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
42 #include "sched-int.h"
48 #ifdef INSN_SCHEDULING
50 #ifdef ENABLE_CHECKING
56 /* Holds current parameters for the dependency analyzer. */
57 struct sched_deps_info_def
*sched_deps_info
;
59 /* The data is specific to the Haifa scheduler. */
60 VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
= NULL
;
62 /* Return the major type present in the DS. */
70 return REG_DEP_OUTPUT
;
72 gcc_assert (ds
& DEP_ANTI
);
77 /* Return equivalent dep_status. */
79 dk_to_ds (enum reg_note dk
)
90 gcc_assert (dk
== REG_DEP_ANTI
);
95 /* Functions to operate with dependence information container - dep_t. */
97 /* Init DEP with the arguments. */
99 init_dep_1 (dep_t dep
, rtx pro
, rtx con
, enum reg_note type
, ds_t ds
)
103 DEP_TYPE (dep
) = type
;
104 DEP_STATUS (dep
) = ds
;
107 /* Init DEP with the arguments.
108 While most of the scheduler (including targets) only need the major type
109 of the dependency, it is convenient to hide full dep_status from them. */
111 init_dep (dep_t dep
, rtx pro
, rtx con
, enum reg_note kind
)
115 if ((current_sched_info
->flags
& USE_DEPS_LIST
))
116 ds
= dk_to_ds (kind
);
120 init_dep_1 (dep
, pro
, con
, kind
, ds
);
123 /* Make a copy of FROM in TO. */
125 copy_dep (dep_t to
, dep_t from
)
127 memcpy (to
, from
, sizeof (*to
));
130 static void dump_ds (FILE *, ds_t
);
132 /* Define flags for dump_dep (). */
134 /* Dump producer of the dependence. */
135 #define DUMP_DEP_PRO (2)
137 /* Dump consumer of the dependence. */
138 #define DUMP_DEP_CON (4)
140 /* Dump type of the dependence. */
141 #define DUMP_DEP_TYPE (8)
143 /* Dump status of the dependence. */
144 #define DUMP_DEP_STATUS (16)
146 /* Dump all information about the dependence. */
147 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
151 FLAGS is a bit mask specifying what information about DEP needs
153 If FLAGS has the very first bit set, then dump all information about DEP
154 and propagate this bit into the callee dump functions. */
156 dump_dep (FILE *dump
, dep_t dep
, int flags
)
159 flags
|= DUMP_DEP_ALL
;
163 if (flags
& DUMP_DEP_PRO
)
164 fprintf (dump
, "%d; ", INSN_UID (DEP_PRO (dep
)));
166 if (flags
& DUMP_DEP_CON
)
167 fprintf (dump
, "%d; ", INSN_UID (DEP_CON (dep
)));
169 if (flags
& DUMP_DEP_TYPE
)
172 enum reg_note type
= DEP_TYPE (dep
);
193 fprintf (dump
, "%c; ", t
);
196 if (flags
& DUMP_DEP_STATUS
)
198 if (current_sched_info
->flags
& USE_DEPS_LIST
)
199 dump_ds (dump
, DEP_STATUS (dep
));
205 /* Default flags for dump_dep (). */
206 static int dump_dep_flags
= (DUMP_DEP_PRO
| DUMP_DEP_CON
);
208 /* Dump all fields of DEP to STDERR. */
210 sd_debug_dep (dep_t dep
)
212 dump_dep (stderr
, dep
, 1);
213 fprintf (stderr
, "\n");
216 /* Determine whether DEP is a dependency link of a non-debug insn on a
220 depl_on_debug_p (dep_link_t dep
)
222 return (DEBUG_INSN_P (DEP_LINK_PRO (dep
))
223 && !DEBUG_INSN_P (DEP_LINK_CON (dep
)));
226 /* Functions to operate with a single link from the dependencies lists -
229 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
232 attach_dep_link (dep_link_t l
, dep_link_t
*prev_nextp
)
234 dep_link_t next
= *prev_nextp
;
236 gcc_assert (DEP_LINK_PREV_NEXTP (l
) == NULL
237 && DEP_LINK_NEXT (l
) == NULL
);
239 /* Init node being inserted. */
240 DEP_LINK_PREV_NEXTP (l
) = prev_nextp
;
241 DEP_LINK_NEXT (l
) = next
;
246 gcc_assert (DEP_LINK_PREV_NEXTP (next
) == prev_nextp
);
248 DEP_LINK_PREV_NEXTP (next
) = &DEP_LINK_NEXT (l
);
255 /* Add dep_link LINK to deps_list L. */
257 add_to_deps_list (dep_link_t link
, deps_list_t l
)
259 attach_dep_link (link
, &DEPS_LIST_FIRST (l
));
261 /* Don't count debug deps. */
262 if (!depl_on_debug_p (link
))
263 ++DEPS_LIST_N_LINKS (l
);
266 /* Detach dep_link L from the list. */
268 detach_dep_link (dep_link_t l
)
270 dep_link_t
*prev_nextp
= DEP_LINK_PREV_NEXTP (l
);
271 dep_link_t next
= DEP_LINK_NEXT (l
);
276 DEP_LINK_PREV_NEXTP (next
) = prev_nextp
;
278 DEP_LINK_PREV_NEXTP (l
) = NULL
;
279 DEP_LINK_NEXT (l
) = NULL
;
282 /* Remove link LINK from list LIST. */
284 remove_from_deps_list (dep_link_t link
, deps_list_t list
)
286 detach_dep_link (link
);
288 /* Don't count debug deps. */
289 if (!depl_on_debug_p (link
))
290 --DEPS_LIST_N_LINKS (list
);
293 /* Move link LINK from list FROM to list TO. */
295 move_dep_link (dep_link_t link
, deps_list_t from
, deps_list_t to
)
297 remove_from_deps_list (link
, from
);
298 add_to_deps_list (link
, to
);
301 /* Return true of LINK is not attached to any list. */
303 dep_link_is_detached_p (dep_link_t link
)
305 return DEP_LINK_PREV_NEXTP (link
) == NULL
;
308 /* Pool to hold all dependency nodes (dep_node_t). */
309 static alloc_pool dn_pool
;
311 /* Number of dep_nodes out there. */
312 static int dn_pool_diff
= 0;
314 /* Create a dep_node. */
316 create_dep_node (void)
318 dep_node_t n
= (dep_node_t
) pool_alloc (dn_pool
);
319 dep_link_t back
= DEP_NODE_BACK (n
);
320 dep_link_t forw
= DEP_NODE_FORW (n
);
322 DEP_LINK_NODE (back
) = n
;
323 DEP_LINK_NEXT (back
) = NULL
;
324 DEP_LINK_PREV_NEXTP (back
) = NULL
;
326 DEP_LINK_NODE (forw
) = n
;
327 DEP_LINK_NEXT (forw
) = NULL
;
328 DEP_LINK_PREV_NEXTP (forw
) = NULL
;
335 /* Delete dep_node N. N must not be connected to any deps_list. */
337 delete_dep_node (dep_node_t n
)
339 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n
))
340 && dep_link_is_detached_p (DEP_NODE_FORW (n
)));
344 pool_free (dn_pool
, n
);
347 /* Pool to hold dependencies lists (deps_list_t). */
348 static alloc_pool dl_pool
;
350 /* Number of deps_lists out there. */
351 static int dl_pool_diff
= 0;
353 /* Functions to operate with dependences lists - deps_list_t. */
355 /* Return true if list L is empty. */
357 deps_list_empty_p (deps_list_t l
)
359 return DEPS_LIST_N_LINKS (l
) == 0;
362 /* Create a new deps_list. */
364 create_deps_list (void)
366 deps_list_t l
= (deps_list_t
) pool_alloc (dl_pool
);
368 DEPS_LIST_FIRST (l
) = NULL
;
369 DEPS_LIST_N_LINKS (l
) = 0;
375 /* Free deps_list L. */
377 free_deps_list (deps_list_t l
)
379 gcc_assert (deps_list_empty_p (l
));
383 pool_free (dl_pool
, l
);
386 /* Return true if there is no dep_nodes and deps_lists out there.
387 After the region is scheduled all the dependency nodes and lists
388 should [generally] be returned to pool. */
390 deps_pools_are_empty_p (void)
392 return dn_pool_diff
== 0 && dl_pool_diff
== 0;
395 /* Remove all elements from L. */
397 clear_deps_list (deps_list_t l
)
401 dep_link_t link
= DEPS_LIST_FIRST (l
);
406 remove_from_deps_list (link
, l
);
411 static regset reg_pending_sets
;
412 static regset reg_pending_clobbers
;
413 static regset reg_pending_uses
;
414 static enum reg_pending_barrier_mode reg_pending_barrier
;
416 /* Hard registers implicitly clobbered or used (or may be implicitly
417 clobbered or used) by the currently analyzed insn. For example,
418 insn in its constraint has one register class. Even if there is
419 currently no hard register in the insn, the particular hard
420 register will be in the insn after reload pass because the
421 constraint requires it. */
422 static HARD_REG_SET implicit_reg_pending_clobbers
;
423 static HARD_REG_SET implicit_reg_pending_uses
;
425 /* To speed up the test for duplicate dependency links we keep a
426 record of dependencies created by add_dependence when the average
427 number of instructions in a basic block is very large.
429 Studies have shown that there is typically around 5 instructions between
430 branches for typical C code. So we can make a guess that the average
431 basic block is approximately 5 instructions long; we will choose 100X
432 the average size as a very large basic block.
434 Each insn has associated bitmaps for its dependencies. Each bitmap
435 has enough entries to represent a dependency on any other insn in
436 the insn chain. All bitmap for true dependencies cache is
437 allocated then the rest two ones are also allocated. */
438 static bitmap_head
*true_dependency_cache
= NULL
;
439 static bitmap_head
*output_dependency_cache
= NULL
;
440 static bitmap_head
*anti_dependency_cache
= NULL
;
441 static bitmap_head
*spec_dependency_cache
= NULL
;
442 static int cache_size
;
444 static int deps_may_trap_p (const_rtx
);
445 static void add_dependence_list (rtx
, rtx
, int, enum reg_note
);
446 static void add_dependence_list_and_free (struct deps_desc
*, rtx
,
447 rtx
*, int, enum reg_note
);
448 static void delete_all_dependences (rtx
);
449 static void fixup_sched_groups (rtx
);
451 static void flush_pending_lists (struct deps_desc
*, rtx
, int, int);
452 static void sched_analyze_1 (struct deps_desc
*, rtx
, rtx
);
453 static void sched_analyze_2 (struct deps_desc
*, rtx
, rtx
);
454 static void sched_analyze_insn (struct deps_desc
*, rtx
, rtx
);
456 static bool sched_has_condition_p (const_rtx
);
457 static int conditions_mutex_p (const_rtx
, const_rtx
, bool, bool);
459 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_dep_1 (dep_t
, bool,
461 static enum DEPS_ADJUST_RESULT
add_or_update_dep_1 (dep_t
, bool, rtx
, rtx
);
463 #ifdef ENABLE_CHECKING
464 static void check_dep (dep_t
, bool);
467 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
470 deps_may_trap_p (const_rtx mem
)
472 const_rtx addr
= XEXP (mem
, 0);
474 if (REG_P (addr
) && REGNO (addr
) >= FIRST_PSEUDO_REGISTER
)
476 const_rtx t
= get_reg_known_value (REGNO (addr
));
480 return rtx_addr_can_trap_p (addr
);
484 /* Find the condition under which INSN is executed. If REV is not NULL,
485 it is set to TRUE when the returned comparison should be reversed
486 to get the actual condition. */
488 sched_get_condition_with_rev (const_rtx insn
, bool *rev
)
490 rtx pat
= PATTERN (insn
);
499 if (GET_CODE (pat
) == COND_EXEC
)
500 return COND_EXEC_TEST (pat
);
502 if (!any_condjump_p (insn
) || !onlyjump_p (insn
))
505 src
= SET_SRC (pc_set (insn
));
507 if (XEXP (src
, 2) == pc_rtx
)
508 return XEXP (src
, 0);
509 else if (XEXP (src
, 1) == pc_rtx
)
511 rtx cond
= XEXP (src
, 0);
512 enum rtx_code revcode
= reversed_comparison_code (cond
, insn
);
514 if (revcode
== UNKNOWN
)
525 /* True when we can find a condition under which INSN is executed. */
527 sched_has_condition_p (const_rtx insn
)
529 return !! sched_get_condition_with_rev (insn
, NULL
);
534 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
536 conditions_mutex_p (const_rtx cond1
, const_rtx cond2
, bool rev1
, bool rev2
)
538 if (COMPARISON_P (cond1
)
539 && COMPARISON_P (cond2
)
540 && GET_CODE (cond1
) ==
542 ? reversed_comparison_code (cond2
, NULL
)
544 && XEXP (cond1
, 0) == XEXP (cond2
, 0)
545 && XEXP (cond1
, 1) == XEXP (cond2
, 1))
550 /* Return true if insn1 and insn2 can never depend on one another because
551 the conditions under which they are executed are mutually exclusive. */
553 sched_insns_conditions_mutex_p (const_rtx insn1
, const_rtx insn2
)
556 bool rev1
= false, rev2
= false;
558 /* df doesn't handle conditional lifetimes entirely correctly;
559 calls mess up the conditional lifetimes. */
560 if (!CALL_P (insn1
) && !CALL_P (insn2
))
562 cond1
= sched_get_condition_with_rev (insn1
, &rev1
);
563 cond2
= sched_get_condition_with_rev (insn2
, &rev2
);
565 && conditions_mutex_p (cond1
, cond2
, rev1
, rev2
)
566 /* Make sure first instruction doesn't affect condition of second
567 instruction if switched. */
568 && !modified_in_p (cond1
, insn2
)
569 /* Make sure second instruction doesn't affect condition of first
570 instruction if switched. */
571 && !modified_in_p (cond2
, insn1
))
578 /* Return true if INSN can potentially be speculated with type DS. */
580 sched_insn_is_legitimate_for_speculation_p (const_rtx insn
, ds_t ds
)
582 if (HAS_INTERNAL_DEP (insn
))
585 if (!NONJUMP_INSN_P (insn
))
588 if (SCHED_GROUP_P (insn
))
591 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn
)))
594 if (side_effects_p (PATTERN (insn
)))
598 /* The following instructions, which depend on a speculatively scheduled
599 instruction, cannot be speculatively scheduled along. */
601 if (may_trap_p (PATTERN (insn
)))
602 /* If instruction might trap, it cannot be speculatively scheduled.
603 For control speculation it's obvious why and for data speculation
604 it's because the insn might get wrong input if speculation
605 wasn't successful. */
608 if ((ds
& BE_IN_DATA
)
609 && sched_has_condition_p (insn
))
610 /* If this is a predicated instruction, then it cannot be
611 speculatively scheduled. See PR35659. */
618 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
619 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
620 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
621 This function is used to switch sd_iterator to the next list.
622 !!! For internal use only. Might consider moving it to sched-int.h. */
624 sd_next_list (const_rtx insn
, sd_list_types_def
*types_ptr
,
625 deps_list_t
*list_ptr
, bool *resolved_p_ptr
)
627 sd_list_types_def types
= *types_ptr
;
629 if (types
& SD_LIST_HARD_BACK
)
631 *list_ptr
= INSN_HARD_BACK_DEPS (insn
);
632 *resolved_p_ptr
= false;
633 *types_ptr
= types
& ~SD_LIST_HARD_BACK
;
635 else if (types
& SD_LIST_SPEC_BACK
)
637 *list_ptr
= INSN_SPEC_BACK_DEPS (insn
);
638 *resolved_p_ptr
= false;
639 *types_ptr
= types
& ~SD_LIST_SPEC_BACK
;
641 else if (types
& SD_LIST_FORW
)
643 *list_ptr
= INSN_FORW_DEPS (insn
);
644 *resolved_p_ptr
= false;
645 *types_ptr
= types
& ~SD_LIST_FORW
;
647 else if (types
& SD_LIST_RES_BACK
)
649 *list_ptr
= INSN_RESOLVED_BACK_DEPS (insn
);
650 *resolved_p_ptr
= true;
651 *types_ptr
= types
& ~SD_LIST_RES_BACK
;
653 else if (types
& SD_LIST_RES_FORW
)
655 *list_ptr
= INSN_RESOLVED_FORW_DEPS (insn
);
656 *resolved_p_ptr
= true;
657 *types_ptr
= types
& ~SD_LIST_RES_FORW
;
662 *resolved_p_ptr
= false;
663 *types_ptr
= SD_LIST_NONE
;
667 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
669 sd_lists_size (const_rtx insn
, sd_list_types_def list_types
)
673 while (list_types
!= SD_LIST_NONE
)
678 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
680 size
+= DEPS_LIST_N_LINKS (list
);
686 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
689 sd_lists_empty_p (const_rtx insn
, sd_list_types_def list_types
)
691 while (list_types
!= SD_LIST_NONE
)
696 sd_next_list (insn
, &list_types
, &list
, &resolved_p
);
697 if (!deps_list_empty_p (list
))
704 /* Initialize data for INSN. */
706 sd_init_insn (rtx insn
)
708 INSN_HARD_BACK_DEPS (insn
) = create_deps_list ();
709 INSN_SPEC_BACK_DEPS (insn
) = create_deps_list ();
710 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list ();
711 INSN_FORW_DEPS (insn
) = create_deps_list ();
712 INSN_RESOLVED_FORW_DEPS (insn
) = create_deps_list ();
714 if (DEBUG_INSN_P (insn
))
715 DEBUG_INSN_SCHED_P (insn
) = TRUE
;
717 /* ??? It would be nice to allocate dependency caches here. */
720 /* Free data for INSN. */
722 sd_finish_insn (rtx insn
)
724 /* ??? It would be nice to deallocate dependency caches here. */
726 if (DEBUG_INSN_P (insn
))
728 gcc_assert (DEBUG_INSN_SCHED_P (insn
));
729 DEBUG_INSN_SCHED_P (insn
) = FALSE
;
732 free_deps_list (INSN_HARD_BACK_DEPS (insn
));
733 INSN_HARD_BACK_DEPS (insn
) = NULL
;
735 free_deps_list (INSN_SPEC_BACK_DEPS (insn
));
736 INSN_SPEC_BACK_DEPS (insn
) = NULL
;
738 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
739 INSN_RESOLVED_BACK_DEPS (insn
) = NULL
;
741 free_deps_list (INSN_FORW_DEPS (insn
));
742 INSN_FORW_DEPS (insn
) = NULL
;
744 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
745 INSN_RESOLVED_FORW_DEPS (insn
) = NULL
;
748 /* Find a dependency between producer PRO and consumer CON.
749 Search through resolved dependency lists if RESOLVED_P is true.
750 If no such dependency is found return NULL,
751 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
752 with an iterator pointing to it. */
754 sd_find_dep_between_no_cache (rtx pro
, rtx con
, bool resolved_p
,
755 sd_iterator_def
*sd_it_ptr
)
757 sd_list_types_def pro_list_type
;
758 sd_list_types_def con_list_type
;
759 sd_iterator_def sd_it
;
761 bool found_p
= false;
765 pro_list_type
= SD_LIST_RES_FORW
;
766 con_list_type
= SD_LIST_RES_BACK
;
770 pro_list_type
= SD_LIST_FORW
;
771 con_list_type
= SD_LIST_BACK
;
774 /* Walk through either back list of INSN or forw list of ELEM
775 depending on which one is shorter. */
776 if (sd_lists_size (con
, con_list_type
) < sd_lists_size (pro
, pro_list_type
))
778 /* Find the dep_link with producer PRO in consumer's back_deps. */
779 FOR_EACH_DEP (con
, con_list_type
, sd_it
, dep
)
780 if (DEP_PRO (dep
) == pro
)
788 /* Find the dep_link with consumer CON in producer's forw_deps. */
789 FOR_EACH_DEP (pro
, pro_list_type
, sd_it
, dep
)
790 if (DEP_CON (dep
) == con
)
799 if (sd_it_ptr
!= NULL
)
808 /* Find a dependency between producer PRO and consumer CON.
809 Use dependency [if available] to check if dependency is present at all.
810 Search through resolved dependency lists if RESOLVED_P is true.
811 If the dependency or NULL if none found. */
813 sd_find_dep_between (rtx pro
, rtx con
, bool resolved_p
)
815 if (true_dependency_cache
!= NULL
)
816 /* Avoiding the list walk below can cut compile times dramatically
819 int elem_luid
= INSN_LUID (pro
);
820 int insn_luid
= INSN_LUID (con
);
822 gcc_assert (output_dependency_cache
!= NULL
823 && anti_dependency_cache
!= NULL
);
825 if (!bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
)
826 && !bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
)
827 && !bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
831 return sd_find_dep_between_no_cache (pro
, con
, resolved_p
, NULL
);
834 /* Add or update a dependence described by DEP.
835 MEM1 and MEM2, if non-null, correspond to memory locations in case of
838 The function returns a value indicating if an old entry has been changed
839 or a new entry has been added to insn's backward deps.
841 This function merely checks if producer and consumer is the same insn
842 and doesn't create a dep in this case. Actual manipulation of
843 dependence data structures is performed in add_or_update_dep_1. */
844 static enum DEPS_ADJUST_RESULT
845 maybe_add_or_update_dep_1 (dep_t dep
, bool resolved_p
, rtx mem1
, rtx mem2
)
847 rtx elem
= DEP_PRO (dep
);
848 rtx insn
= DEP_CON (dep
);
850 gcc_assert (INSN_P (insn
) && INSN_P (elem
));
852 /* Don't depend an insn on itself. */
855 if (sched_deps_info
->generate_spec_deps
)
856 /* INSN has an internal dependence, which we can't overcome. */
857 HAS_INTERNAL_DEP (insn
) = 1;
862 return add_or_update_dep_1 (dep
, resolved_p
, mem1
, mem2
);
865 /* Ask dependency caches what needs to be done for dependence DEP.
866 Return DEP_CREATED if new dependence should be created and there is no
867 need to try to find one searching the dependencies lists.
868 Return DEP_PRESENT if there already is a dependence described by DEP and
869 hence nothing is to be done.
870 Return DEP_CHANGED if there already is a dependence, but it should be
871 updated to incorporate additional information from DEP. */
872 static enum DEPS_ADJUST_RESULT
873 ask_dependency_caches (dep_t dep
)
875 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
876 int insn_luid
= INSN_LUID (DEP_CON (dep
));
878 gcc_assert (true_dependency_cache
!= NULL
879 && output_dependency_cache
!= NULL
880 && anti_dependency_cache
!= NULL
);
882 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
884 enum reg_note present_dep_type
;
886 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
887 present_dep_type
= REG_DEP_TRUE
;
888 else if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
889 present_dep_type
= REG_DEP_OUTPUT
;
890 else if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
891 present_dep_type
= REG_DEP_ANTI
;
893 /* There is no existing dep so it should be created. */
896 if ((int) DEP_TYPE (dep
) >= (int) present_dep_type
)
897 /* DEP does not add anything to the existing dependence. */
902 ds_t present_dep_types
= 0;
904 if (bitmap_bit_p (&true_dependency_cache
[insn_luid
], elem_luid
))
905 present_dep_types
|= DEP_TRUE
;
906 if (bitmap_bit_p (&output_dependency_cache
[insn_luid
], elem_luid
))
907 present_dep_types
|= DEP_OUTPUT
;
908 if (bitmap_bit_p (&anti_dependency_cache
[insn_luid
], elem_luid
))
909 present_dep_types
|= DEP_ANTI
;
911 if (present_dep_types
== 0)
912 /* There is no existing dep so it should be created. */
915 if (!(current_sched_info
->flags
& DO_SPECULATION
)
916 || !bitmap_bit_p (&spec_dependency_cache
[insn_luid
], elem_luid
))
918 if ((present_dep_types
| (DEP_STATUS (dep
) & DEP_TYPES
))
919 == present_dep_types
)
920 /* DEP does not add anything to the existing dependence. */
925 /* Only true dependencies can be data speculative and
926 only anti dependencies can be control speculative. */
927 gcc_assert ((present_dep_types
& (DEP_TRUE
| DEP_ANTI
))
928 == present_dep_types
);
930 /* if (DEP is SPECULATIVE) then
931 ..we should update DEP_STATUS
933 ..we should reset existing dep to non-speculative. */
940 /* Set dependency caches according to DEP. */
942 set_dependency_caches (dep_t dep
)
944 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
945 int insn_luid
= INSN_LUID (DEP_CON (dep
));
947 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
949 switch (DEP_TYPE (dep
))
952 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
956 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
960 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
969 ds_t ds
= DEP_STATUS (dep
);
972 bitmap_set_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
974 bitmap_set_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
976 bitmap_set_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
978 if (ds
& SPECULATIVE
)
980 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
);
981 bitmap_set_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
986 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
987 caches accordingly. */
989 update_dependency_caches (dep_t dep
, enum reg_note old_type
)
991 int elem_luid
= INSN_LUID (DEP_PRO (dep
));
992 int insn_luid
= INSN_LUID (DEP_CON (dep
));
994 /* Clear corresponding cache entry because type of the link
995 may have changed. Keep them if we use_deps_list. */
996 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
1000 case REG_DEP_OUTPUT
:
1001 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1005 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1013 set_dependency_caches (dep
);
1016 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1018 change_spec_dep_to_hard (sd_iterator_def sd_it
)
1020 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1021 dep_link_t link
= DEP_NODE_BACK (node
);
1022 dep_t dep
= DEP_NODE_DEP (node
);
1023 rtx elem
= DEP_PRO (dep
);
1024 rtx insn
= DEP_CON (dep
);
1026 move_dep_link (link
, INSN_SPEC_BACK_DEPS (insn
), INSN_HARD_BACK_DEPS (insn
));
1028 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1030 if (true_dependency_cache
!= NULL
)
1031 /* Clear the cache entry. */
1032 bitmap_clear_bit (&spec_dependency_cache
[INSN_LUID (insn
)],
1036 /* Update DEP to incorporate information from NEW_DEP.
1037 SD_IT points to DEP in case it should be moved to another list.
1038 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1039 data-speculative dependence should be updated. */
1040 static enum DEPS_ADJUST_RESULT
1041 update_dep (dep_t dep
, dep_t new_dep
,
1042 sd_iterator_def sd_it ATTRIBUTE_UNUSED
,
1043 rtx mem1 ATTRIBUTE_UNUSED
,
1044 rtx mem2 ATTRIBUTE_UNUSED
)
1046 enum DEPS_ADJUST_RESULT res
= DEP_PRESENT
;
1047 enum reg_note old_type
= DEP_TYPE (dep
);
1049 /* If this is a more restrictive type of dependence than the
1050 existing one, then change the existing dependence to this
1052 if ((int) DEP_TYPE (new_dep
) < (int) old_type
)
1054 DEP_TYPE (dep
) = DEP_TYPE (new_dep
);
1058 if (current_sched_info
->flags
& USE_DEPS_LIST
)
1059 /* Update DEP_STATUS. */
1061 ds_t dep_status
= DEP_STATUS (dep
);
1062 ds_t ds
= DEP_STATUS (new_dep
);
1063 ds_t new_status
= ds
| dep_status
;
1065 if (new_status
& SPECULATIVE
)
1066 /* Either existing dep or a dep we're adding or both are
1069 if (!(ds
& SPECULATIVE
)
1070 || !(dep_status
& SPECULATIVE
))
1071 /* The new dep can't be speculative. */
1073 new_status
&= ~SPECULATIVE
;
1075 if (dep_status
& SPECULATIVE
)
1076 /* The old dep was speculative, but now it
1078 change_spec_dep_to_hard (sd_it
);
1082 /* Both are speculative. Merge probabilities. */
1087 dw
= estimate_dep_weak (mem1
, mem2
);
1088 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
1091 new_status
= ds_merge (dep_status
, ds
);
1097 if (dep_status
!= ds
)
1099 DEP_STATUS (dep
) = ds
;
1104 if (true_dependency_cache
!= NULL
1105 && res
== DEP_CHANGED
)
1106 update_dependency_caches (dep
, old_type
);
1111 /* Add or update a dependence described by DEP.
1112 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1115 The function returns a value indicating if an old entry has been changed
1116 or a new entry has been added to insn's backward deps or nothing has
1117 been updated at all. */
1118 static enum DEPS_ADJUST_RESULT
1119 add_or_update_dep_1 (dep_t new_dep
, bool resolved_p
,
1120 rtx mem1 ATTRIBUTE_UNUSED
, rtx mem2 ATTRIBUTE_UNUSED
)
1122 bool maybe_present_p
= true;
1123 bool present_p
= false;
1125 gcc_assert (INSN_P (DEP_PRO (new_dep
)) && INSN_P (DEP_CON (new_dep
))
1126 && DEP_PRO (new_dep
) != DEP_CON (new_dep
));
1128 #ifdef ENABLE_CHECKING
1129 check_dep (new_dep
, mem1
!= NULL
);
1132 if (true_dependency_cache
!= NULL
)
1134 switch (ask_dependency_caches (new_dep
))
1140 maybe_present_p
= true;
1145 maybe_present_p
= false;
1155 /* Check that we don't already have this dependence. */
1156 if (maybe_present_p
)
1159 sd_iterator_def sd_it
;
1161 gcc_assert (true_dependency_cache
== NULL
|| present_p
);
1163 present_dep
= sd_find_dep_between_no_cache (DEP_PRO (new_dep
),
1165 resolved_p
, &sd_it
);
1167 if (present_dep
!= NULL
)
1168 /* We found an existing dependency between ELEM and INSN. */
1169 return update_dep (present_dep
, new_dep
, sd_it
, mem1
, mem2
);
1171 /* We didn't find a dep, it shouldn't present in the cache. */
1172 gcc_assert (!present_p
);
1175 /* Might want to check one level of transitivity to save conses.
1176 This check should be done in maybe_add_or_update_dep_1.
1177 Since we made it to add_or_update_dep_1, we must create
1178 (or update) a link. */
1180 if (mem1
!= NULL_RTX
)
1182 gcc_assert (sched_deps_info
->generate_spec_deps
);
1183 DEP_STATUS (new_dep
) = set_dep_weak (DEP_STATUS (new_dep
), BEGIN_DATA
,
1184 estimate_dep_weak (mem1
, mem2
));
1187 sd_add_dep (new_dep
, resolved_p
);
1192 /* Initialize BACK_LIST_PTR with consumer's backward list and
1193 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1194 initialize with lists that hold resolved deps. */
1196 get_back_and_forw_lists (dep_t dep
, bool resolved_p
,
1197 deps_list_t
*back_list_ptr
,
1198 deps_list_t
*forw_list_ptr
)
1200 rtx con
= DEP_CON (dep
);
1204 if ((current_sched_info
->flags
& DO_SPECULATION
)
1205 && (DEP_STATUS (dep
) & SPECULATIVE
))
1206 *back_list_ptr
= INSN_SPEC_BACK_DEPS (con
);
1208 *back_list_ptr
= INSN_HARD_BACK_DEPS (con
);
1210 *forw_list_ptr
= INSN_FORW_DEPS (DEP_PRO (dep
));
1214 *back_list_ptr
= INSN_RESOLVED_BACK_DEPS (con
);
1215 *forw_list_ptr
= INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep
));
1219 /* Add dependence described by DEP.
1220 If RESOLVED_P is true treat the dependence as a resolved one. */
1222 sd_add_dep (dep_t dep
, bool resolved_p
)
1224 dep_node_t n
= create_dep_node ();
1225 deps_list_t con_back_deps
;
1226 deps_list_t pro_forw_deps
;
1227 rtx elem
= DEP_PRO (dep
);
1228 rtx insn
= DEP_CON (dep
);
1230 gcc_assert (INSN_P (insn
) && INSN_P (elem
) && insn
!= elem
);
1232 if ((current_sched_info
->flags
& DO_SPECULATION
)
1233 && !sched_insn_is_legitimate_for_speculation_p (insn
, DEP_STATUS (dep
)))
1234 DEP_STATUS (dep
) &= ~SPECULATIVE
;
1236 copy_dep (DEP_NODE_DEP (n
), dep
);
1238 get_back_and_forw_lists (dep
, resolved_p
, &con_back_deps
, &pro_forw_deps
);
1240 add_to_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1242 #ifdef ENABLE_CHECKING
1243 check_dep (dep
, false);
1246 add_to_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1248 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1249 in the bitmap caches of dependency information. */
1250 if (true_dependency_cache
!= NULL
)
1251 set_dependency_caches (dep
);
1254 /* Add or update backward dependence between INSN and ELEM
1255 with given type DEP_TYPE and dep_status DS.
1256 This function is a convenience wrapper. */
1257 enum DEPS_ADJUST_RESULT
1258 sd_add_or_update_dep (dep_t dep
, bool resolved_p
)
1260 return add_or_update_dep_1 (dep
, resolved_p
, NULL_RTX
, NULL_RTX
);
1263 /* Resolved dependence pointed to by SD_IT.
1264 SD_IT will advance to the next element. */
1266 sd_resolve_dep (sd_iterator_def sd_it
)
1268 dep_node_t node
= DEP_LINK_NODE (*sd_it
.linkp
);
1269 dep_t dep
= DEP_NODE_DEP (node
);
1270 rtx pro
= DEP_PRO (dep
);
1271 rtx con
= DEP_CON (dep
);
1273 if ((current_sched_info
->flags
& DO_SPECULATION
)
1274 && (DEP_STATUS (dep
) & SPECULATIVE
))
1275 move_dep_link (DEP_NODE_BACK (node
), INSN_SPEC_BACK_DEPS (con
),
1276 INSN_RESOLVED_BACK_DEPS (con
));
1278 move_dep_link (DEP_NODE_BACK (node
), INSN_HARD_BACK_DEPS (con
),
1279 INSN_RESOLVED_BACK_DEPS (con
));
1281 move_dep_link (DEP_NODE_FORW (node
), INSN_FORW_DEPS (pro
),
1282 INSN_RESOLVED_FORW_DEPS (pro
));
1285 /* Make TO depend on all the FROM's producers.
1286 If RESOLVED_P is true add dependencies to the resolved lists. */
1288 sd_copy_back_deps (rtx to
, rtx from
, bool resolved_p
)
1290 sd_list_types_def list_type
;
1291 sd_iterator_def sd_it
;
1294 list_type
= resolved_p
? SD_LIST_RES_BACK
: SD_LIST_BACK
;
1296 FOR_EACH_DEP (from
, list_type
, sd_it
, dep
)
1298 dep_def _new_dep
, *new_dep
= &_new_dep
;
1300 copy_dep (new_dep
, dep
);
1301 DEP_CON (new_dep
) = to
;
1302 sd_add_dep (new_dep
, resolved_p
);
1306 /* Remove a dependency referred to by SD_IT.
1307 SD_IT will point to the next dependence after removal. */
1309 sd_delete_dep (sd_iterator_def sd_it
)
1311 dep_node_t n
= DEP_LINK_NODE (*sd_it
.linkp
);
1312 dep_t dep
= DEP_NODE_DEP (n
);
1313 rtx pro
= DEP_PRO (dep
);
1314 rtx con
= DEP_CON (dep
);
1315 deps_list_t con_back_deps
;
1316 deps_list_t pro_forw_deps
;
1318 if (true_dependency_cache
!= NULL
)
1320 int elem_luid
= INSN_LUID (pro
);
1321 int insn_luid
= INSN_LUID (con
);
1323 bitmap_clear_bit (&true_dependency_cache
[insn_luid
], elem_luid
);
1324 bitmap_clear_bit (&anti_dependency_cache
[insn_luid
], elem_luid
);
1325 bitmap_clear_bit (&output_dependency_cache
[insn_luid
], elem_luid
);
1327 if (current_sched_info
->flags
& DO_SPECULATION
)
1328 bitmap_clear_bit (&spec_dependency_cache
[insn_luid
], elem_luid
);
1331 get_back_and_forw_lists (dep
, sd_it
.resolved_p
,
1332 &con_back_deps
, &pro_forw_deps
);
1334 remove_from_deps_list (DEP_NODE_BACK (n
), con_back_deps
);
1335 remove_from_deps_list (DEP_NODE_FORW (n
), pro_forw_deps
);
1337 delete_dep_node (n
);
1340 /* Dump size of the lists. */
1341 #define DUMP_LISTS_SIZE (2)
1343 /* Dump dependencies of the lists. */
1344 #define DUMP_LISTS_DEPS (4)
1346 /* Dump all information about the lists. */
1347 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1349 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1350 FLAGS is a bit mask specifying what information about the lists needs
1352 If FLAGS has the very first bit set, then dump all information about
1353 the lists and propagate this bit into the callee dump functions. */
1355 dump_lists (FILE *dump
, rtx insn
, sd_list_types_def types
, int flags
)
1357 sd_iterator_def sd_it
;
1364 flags
|= DUMP_LISTS_ALL
;
1366 fprintf (dump
, "[");
1368 if (flags
& DUMP_LISTS_SIZE
)
1369 fprintf (dump
, "%d; ", sd_lists_size (insn
, types
));
1371 if (flags
& DUMP_LISTS_DEPS
)
1373 FOR_EACH_DEP (insn
, types
, sd_it
, dep
)
1375 dump_dep (dump
, dep
, dump_dep_flags
| all
);
1376 fprintf (dump
, " ");
1381 /* Dump all information about deps_lists of INSN specified by TYPES
1384 sd_debug_lists (rtx insn
, sd_list_types_def types
)
1386 dump_lists (stderr
, insn
, types
, 1);
1387 fprintf (stderr
, "\n");
1390 /* A convenience wrapper to operate on an entire list. */
1393 add_dependence_list (rtx insn
, rtx list
, int uncond
, enum reg_note dep_type
)
1395 for (; list
; list
= XEXP (list
, 1))
1397 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1398 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1402 /* Similar, but free *LISTP at the same time, when the context
1406 add_dependence_list_and_free (struct deps_desc
*deps
, rtx insn
, rtx
*listp
,
1407 int uncond
, enum reg_note dep_type
)
1411 /* We don't want to short-circuit dependencies involving debug
1412 insns, because they may cause actual dependencies to be
1414 if (deps
->readonly
|| DEBUG_INSN_P (insn
))
1416 add_dependence_list (insn
, *listp
, uncond
, dep_type
);
1420 for (list
= *listp
, *listp
= NULL
; list
; list
= next
)
1422 next
= XEXP (list
, 1);
1423 if (uncond
|| ! sched_insns_conditions_mutex_p (insn
, XEXP (list
, 0)))
1424 add_dependence (insn
, XEXP (list
, 0), dep_type
);
1425 free_INSN_LIST_node (list
);
1429 /* Remove all occurences of INSN from LIST. Return the number of
1430 occurences removed. */
1433 remove_from_dependence_list (rtx insn
, rtx
* listp
)
1439 if (XEXP (*listp
, 0) == insn
)
1441 remove_free_INSN_LIST_node (listp
);
1446 listp
= &XEXP (*listp
, 1);
1452 /* Same as above, but process two lists at once. */
1454 remove_from_both_dependence_lists (rtx insn
, rtx
*listp
, rtx
*exprp
)
1460 if (XEXP (*listp
, 0) == insn
)
1462 remove_free_INSN_LIST_node (listp
);
1463 remove_free_EXPR_LIST_node (exprp
);
1468 listp
= &XEXP (*listp
, 1);
1469 exprp
= &XEXP (*exprp
, 1);
1475 /* Clear all dependencies for an insn. */
1477 delete_all_dependences (rtx insn
)
1479 sd_iterator_def sd_it
;
1482 /* The below cycle can be optimized to clear the caches and back_deps
1483 in one call but that would provoke duplication of code from
1486 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1487 sd_iterator_cond (&sd_it
, &dep
);)
1488 sd_delete_dep (sd_it
);
1491 /* All insns in a scheduling group except the first should only have
1492 dependencies on the previous insn in the group. So we find the
1493 first instruction in the scheduling group by walking the dependence
1494 chains backwards. Then we add the dependencies for the group to
1495 the previous nonnote insn. */
1498 fixup_sched_groups (rtx insn
)
1500 sd_iterator_def sd_it
;
1504 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1507 rtx pro
= DEP_PRO (dep
);
1511 i
= prev_nonnote_insn (i
);
1515 } while (SCHED_GROUP_P (i
) || DEBUG_INSN_P (i
));
1517 if (! sched_insns_conditions_mutex_p (i
, pro
))
1518 add_dependence (i
, pro
, DEP_TYPE (dep
));
1522 delete_all_dependences (insn
);
1524 prev_nonnote
= prev_nonnote_insn (insn
);
1525 while (DEBUG_INSN_P (prev_nonnote
))
1526 prev_nonnote
= prev_nonnote_insn (prev_nonnote
);
1527 if (BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (prev_nonnote
)
1528 && ! sched_insns_conditions_mutex_p (insn
, prev_nonnote
))
1529 add_dependence (insn
, prev_nonnote
, REG_DEP_ANTI
);
1532 /* Process an insn's memory dependencies. There are four kinds of
1535 (0) read dependence: read follows read
1536 (1) true dependence: read follows write
1537 (2) output dependence: write follows write
1538 (3) anti dependence: write follows read
1540 We are careful to build only dependencies which actually exist, and
1541 use transitivity to avoid building too many links. */
1543 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1544 The MEM is a memory reference contained within INSN, which we are saving
1545 so that we can do memory aliasing on it. */
1548 add_insn_mem_dependence (struct deps_desc
*deps
, bool read_p
,
1555 gcc_assert (!deps
->readonly
);
1558 insn_list
= &deps
->pending_read_insns
;
1559 mem_list
= &deps
->pending_read_mems
;
1560 if (!DEBUG_INSN_P (insn
))
1561 deps
->pending_read_list_length
++;
1565 insn_list
= &deps
->pending_write_insns
;
1566 mem_list
= &deps
->pending_write_mems
;
1567 deps
->pending_write_list_length
++;
1570 link
= alloc_INSN_LIST (insn
, *insn_list
);
1573 if (sched_deps_info
->use_cselib
)
1575 mem
= shallow_copy_rtx (mem
);
1576 XEXP (mem
, 0) = cselib_subst_to_values (XEXP (mem
, 0));
1578 link
= alloc_EXPR_LIST (VOIDmode
, canon_rtx (mem
), *mem_list
);
1582 /* Make a dependency between every memory reference on the pending lists
1583 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1584 dependencies for a read operation, similarly with FOR_WRITE. */
1587 flush_pending_lists (struct deps_desc
*deps
, rtx insn
, int for_read
,
1592 add_dependence_list_and_free (deps
, insn
, &deps
->pending_read_insns
,
1594 if (!deps
->readonly
)
1596 free_EXPR_LIST_list (&deps
->pending_read_mems
);
1597 deps
->pending_read_list_length
= 0;
1601 add_dependence_list_and_free (deps
, insn
, &deps
->pending_write_insns
, 1,
1602 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1604 add_dependence_list_and_free (deps
, insn
,
1605 &deps
->last_pending_memory_flush
, 1,
1606 for_read
? REG_DEP_ANTI
: REG_DEP_OUTPUT
);
1607 if (!deps
->readonly
)
1609 free_EXPR_LIST_list (&deps
->pending_write_mems
);
1610 deps
->pending_write_list_length
= 0;
1612 deps
->last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
1613 deps
->pending_flush_length
= 1;
1617 /* Instruction which dependencies we are analyzing. */
1618 static rtx cur_insn
= NULL_RTX
;
1620 /* Implement hooks for haifa scheduler. */
1623 haifa_start_insn (rtx insn
)
1625 gcc_assert (insn
&& !cur_insn
);
1631 haifa_finish_insn (void)
1637 haifa_note_reg_set (int regno
)
1639 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
1643 haifa_note_reg_clobber (int regno
)
1645 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
1649 haifa_note_reg_use (int regno
)
1651 SET_REGNO_REG_SET (reg_pending_uses
, regno
);
1655 haifa_note_mem_dep (rtx mem
, rtx pending_mem
, rtx pending_insn
, ds_t ds
)
1657 if (!(ds
& SPECULATIVE
))
1660 pending_mem
= NULL_RTX
;
1663 gcc_assert (ds
& BEGIN_DATA
);
1666 dep_def _dep
, *dep
= &_dep
;
1668 init_dep_1 (dep
, pending_insn
, cur_insn
, ds_to_dt (ds
),
1669 current_sched_info
->flags
& USE_DEPS_LIST
? ds
: -1);
1670 maybe_add_or_update_dep_1 (dep
, false, pending_mem
, mem
);
1676 haifa_note_dep (rtx elem
, ds_t ds
)
1681 init_dep (dep
, elem
, cur_insn
, ds_to_dt (ds
));
1682 maybe_add_or_update_dep_1 (dep
, false, NULL_RTX
, NULL_RTX
);
1686 note_reg_use (int r
)
1688 if (sched_deps_info
->note_reg_use
)
1689 sched_deps_info
->note_reg_use (r
);
1693 note_reg_set (int r
)
1695 if (sched_deps_info
->note_reg_set
)
1696 sched_deps_info
->note_reg_set (r
);
1700 note_reg_clobber (int r
)
1702 if (sched_deps_info
->note_reg_clobber
)
1703 sched_deps_info
->note_reg_clobber (r
);
1707 note_mem_dep (rtx m1
, rtx m2
, rtx e
, ds_t ds
)
1709 if (sched_deps_info
->note_mem_dep
)
1710 sched_deps_info
->note_mem_dep (m1
, m2
, e
, ds
);
1714 note_dep (rtx e
, ds_t ds
)
1716 if (sched_deps_info
->note_dep
)
1717 sched_deps_info
->note_dep (e
, ds
);
1720 /* Return corresponding to DS reg_note. */
1725 return REG_DEP_TRUE
;
1726 else if (ds
& DEP_OUTPUT
)
1727 return REG_DEP_OUTPUT
;
1730 gcc_assert (ds
& DEP_ANTI
);
1731 return REG_DEP_ANTI
;
1737 /* Functions for computation of info needed for register pressure
1738 sensitive insn scheduling. */
1741 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1742 static struct reg_use_data
*
1743 create_insn_reg_use (int regno
, rtx insn
)
1745 struct reg_use_data
*use
;
1747 use
= (struct reg_use_data
*) xmalloc (sizeof (struct reg_use_data
));
1750 use
->next_insn_use
= INSN_REG_USE_LIST (insn
);
1751 INSN_REG_USE_LIST (insn
) = use
;
1755 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1756 static struct reg_set_data
*
1757 create_insn_reg_set (int regno
, rtx insn
)
1759 struct reg_set_data
*set
;
1761 set
= (struct reg_set_data
*) xmalloc (sizeof (struct reg_set_data
));
1764 set
->next_insn_set
= INSN_REG_SET_LIST (insn
);
1765 INSN_REG_SET_LIST (insn
) = set
;
1769 /* Set up insn register uses for INSN and dependency context DEPS. */
1771 setup_insn_reg_uses (struct deps_desc
*deps
, rtx insn
)
1774 reg_set_iterator rsi
;
1776 struct reg_use_data
*use
, *use2
, *next
;
1777 struct deps_reg
*reg_last
;
1779 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
1781 if (i
< FIRST_PSEUDO_REGISTER
1782 && TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
1785 if (find_regno_note (insn
, REG_DEAD
, i
) == NULL_RTX
1786 && ! REGNO_REG_SET_P (reg_pending_sets
, i
)
1787 && ! REGNO_REG_SET_P (reg_pending_clobbers
, i
))
1788 /* Ignore use which is not dying. */
1791 use
= create_insn_reg_use (i
, insn
);
1792 use
->next_regno_use
= use
;
1793 reg_last
= &deps
->reg_last
[i
];
1795 /* Create the cycle list of uses. */
1796 for (list
= reg_last
->uses
; list
; list
= XEXP (list
, 1))
1798 use2
= create_insn_reg_use (i
, XEXP (list
, 0));
1799 next
= use
->next_regno_use
;
1800 use
->next_regno_use
= use2
;
1801 use2
->next_regno_use
= next
;
1806 /* Register pressure info for the currently processed insn. */
1807 static struct reg_pressure_data reg_pressure_info
[N_REG_CLASSES
];
1809 /* Return TRUE if INSN has the use structure for REGNO. */
1811 insn_use_p (rtx insn
, int regno
)
1813 struct reg_use_data
*use
;
1815 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1816 if (use
->regno
== regno
)
1821 /* Update the register pressure info after birth of pseudo register REGNO
1822 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
1823 the register is in clobber or unused after the insn. */
1825 mark_insn_pseudo_birth (rtx insn
, int regno
, bool clobber_p
, bool unused_p
)
1830 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1831 cl
= sched_regno_cover_class
[regno
];
1834 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1837 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ incr
;
1838 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1842 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ incr
;
1843 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1847 new_incr
= reg_pressure_info
[cl
].set_increase
+ incr
;
1848 reg_pressure_info
[cl
].set_increase
= new_incr
;
1849 if (! insn_use_p (insn
, regno
))
1850 reg_pressure_info
[cl
].change
+= incr
;
1851 create_insn_reg_set (regno
, insn
);
1853 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1857 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
1858 hard registers involved in the birth. */
1860 mark_insn_hard_regno_birth (rtx insn
, int regno
, int nregs
,
1861 bool clobber_p
, bool unused_p
)
1864 int new_incr
, last
= regno
+ nregs
;
1866 while (regno
< last
)
1868 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1869 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1871 cl
= sched_regno_cover_class
[regno
];
1876 new_incr
= reg_pressure_info
[cl
].clobber_increase
+ 1;
1877 reg_pressure_info
[cl
].clobber_increase
= new_incr
;
1881 new_incr
= reg_pressure_info
[cl
].unused_set_increase
+ 1;
1882 reg_pressure_info
[cl
].unused_set_increase
= new_incr
;
1886 new_incr
= reg_pressure_info
[cl
].set_increase
+ 1;
1887 reg_pressure_info
[cl
].set_increase
= new_incr
;
1888 if (! insn_use_p (insn
, regno
))
1889 reg_pressure_info
[cl
].change
+= 1;
1890 create_insn_reg_set (regno
, insn
);
1892 gcc_assert (new_incr
< (1 << INCREASE_BITS
));
1899 /* Update the register pressure info after birth of pseudo or hard
1900 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
1901 correspondingly that the register is in clobber or unused after the
1904 mark_insn_reg_birth (rtx insn
, rtx reg
, bool clobber_p
, bool unused_p
)
1908 if (GET_CODE (reg
) == SUBREG
)
1909 reg
= SUBREG_REG (reg
);
1914 regno
= REGNO (reg
);
1915 if (regno
< FIRST_PSEUDO_REGISTER
)
1916 mark_insn_hard_regno_birth (insn
, regno
,
1917 hard_regno_nregs
[regno
][GET_MODE (reg
)],
1918 clobber_p
, unused_p
);
1920 mark_insn_pseudo_birth (insn
, regno
, clobber_p
, unused_p
);
1923 /* Update the register pressure info after death of pseudo register
1926 mark_pseudo_death (int regno
)
1931 gcc_assert (regno
>= FIRST_PSEUDO_REGISTER
);
1932 cl
= sched_regno_cover_class
[regno
];
1935 incr
= ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (regno
)];
1936 reg_pressure_info
[cl
].change
-= incr
;
1940 /* Like mark_pseudo_death except that NREGS saying how many hard
1941 registers involved in the death. */
1943 mark_hard_regno_death (int regno
, int nregs
)
1946 int last
= regno
+ nregs
;
1948 while (regno
< last
)
1950 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
1951 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
1953 cl
= sched_regno_cover_class
[regno
];
1955 reg_pressure_info
[cl
].change
-= 1;
1961 /* Update the register pressure info after death of pseudo or hard
1964 mark_reg_death (rtx reg
)
1968 if (GET_CODE (reg
) == SUBREG
)
1969 reg
= SUBREG_REG (reg
);
1974 regno
= REGNO (reg
);
1975 if (regno
< FIRST_PSEUDO_REGISTER
)
1976 mark_hard_regno_death (regno
, hard_regno_nregs
[regno
][GET_MODE (reg
)]);
1978 mark_pseudo_death (regno
);
1981 /* Process SETTER of REG. DATA is an insn containing the setter. */
1983 mark_insn_reg_store (rtx reg
, const_rtx setter
, void *data
)
1985 if (setter
!= NULL_RTX
&& GET_CODE (setter
) != SET
)
1988 ((rtx
) data
, reg
, false,
1989 find_reg_note ((const_rtx
) data
, REG_UNUSED
, reg
) != NULL_RTX
);
1992 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
1994 mark_insn_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1996 if (GET_CODE (setter
) == CLOBBER
)
1997 mark_insn_reg_birth ((rtx
) data
, reg
, true, false);
2000 /* Set up reg pressure info related to INSN. */
2002 setup_insn_reg_pressure_info (rtx insn
)
2006 static struct reg_pressure_data
*pressure_info
;
2009 gcc_assert (sched_pressure_p
);
2011 if (! INSN_P (insn
))
2014 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2016 cl
= ira_reg_class_cover
[i
];
2017 reg_pressure_info
[cl
].clobber_increase
= 0;
2018 reg_pressure_info
[cl
].set_increase
= 0;
2019 reg_pressure_info
[cl
].unused_set_increase
= 0;
2020 reg_pressure_info
[cl
].change
= 0;
2023 note_stores (PATTERN (insn
), mark_insn_reg_clobber
, insn
);
2025 note_stores (PATTERN (insn
), mark_insn_reg_store
, insn
);
2028 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2029 if (REG_NOTE_KIND (link
) == REG_INC
)
2030 mark_insn_reg_store (XEXP (link
, 0), NULL_RTX
, insn
);
2033 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2034 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2035 mark_reg_death (XEXP (link
, 0));
2037 len
= sizeof (struct reg_pressure_data
) * ira_reg_class_cover_size
;
2039 = INSN_REG_PRESSURE (insn
) = (struct reg_pressure_data
*) xmalloc (len
);
2040 INSN_MAX_REG_PRESSURE (insn
) = (int *) xcalloc (ira_reg_class_cover_size
2042 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2044 cl
= ira_reg_class_cover
[i
];
2045 pressure_info
[i
].clobber_increase
2046 = reg_pressure_info
[cl
].clobber_increase
;
2047 pressure_info
[i
].set_increase
= reg_pressure_info
[cl
].set_increase
;
2048 pressure_info
[i
].unused_set_increase
2049 = reg_pressure_info
[cl
].unused_set_increase
;
2050 pressure_info
[i
].change
= reg_pressure_info
[cl
].change
;
2057 /* Internal variable for sched_analyze_[12] () functions.
2058 If it is nonzero, this means that sched_analyze_[12] looks
2059 at the most toplevel SET. */
2060 static bool can_start_lhs_rhs_p
;
2062 /* Extend reg info for the deps context DEPS given that
2063 we have just generated a register numbered REGNO. */
2065 extend_deps_reg_info (struct deps_desc
*deps
, int regno
)
2067 int max_regno
= regno
+ 1;
2069 gcc_assert (!reload_completed
);
2071 /* In a readonly context, it would not hurt to extend info,
2072 but it should not be needed. */
2073 if (reload_completed
&& deps
->readonly
)
2075 deps
->max_reg
= max_regno
;
2079 if (max_regno
> deps
->max_reg
)
2081 deps
->reg_last
= XRESIZEVEC (struct deps_reg
, deps
->reg_last
,
2083 memset (&deps
->reg_last
[deps
->max_reg
],
2084 0, (max_regno
- deps
->max_reg
)
2085 * sizeof (struct deps_reg
));
2086 deps
->max_reg
= max_regno
;
2090 /* Extends REG_INFO_P if needed. */
2092 maybe_extend_reg_info_p (void)
2094 /* Extend REG_INFO_P, if needed. */
2095 if ((unsigned int)max_regno
- 1 >= reg_info_p_size
)
2097 size_t new_reg_info_p_size
= max_regno
+ 128;
2099 gcc_assert (!reload_completed
&& sel_sched_p ());
2101 reg_info_p
= (struct reg_info_t
*) xrecalloc (reg_info_p
,
2102 new_reg_info_p_size
,
2104 sizeof (*reg_info_p
));
2105 reg_info_p_size
= new_reg_info_p_size
;
2109 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2110 The type of the reference is specified by REF and can be SET,
2111 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2114 sched_analyze_reg (struct deps_desc
*deps
, int regno
, enum machine_mode mode
,
2115 enum rtx_code ref
, rtx insn
)
2117 /* We could emit new pseudos in renaming. Extend the reg structures. */
2118 if (!reload_completed
&& sel_sched_p ()
2119 && (regno
>= max_reg_num () - 1 || regno
>= deps
->max_reg
))
2120 extend_deps_reg_info (deps
, regno
);
2122 maybe_extend_reg_info_p ();
2124 /* A hard reg in a wide mode may really be multiple registers.
2125 If so, mark all of them just like the first. */
2126 if (regno
< FIRST_PSEUDO_REGISTER
)
2128 int i
= hard_regno_nregs
[regno
][mode
];
2132 note_reg_set (regno
+ i
);
2134 else if (ref
== USE
)
2137 note_reg_use (regno
+ i
);
2142 note_reg_clobber (regno
+ i
);
2146 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2147 it does not reload. Ignore these as they have served their
2149 else if (regno
>= deps
->max_reg
)
2151 enum rtx_code code
= GET_CODE (PATTERN (insn
));
2152 gcc_assert (code
== USE
|| code
== CLOBBER
);
2158 note_reg_set (regno
);
2159 else if (ref
== USE
)
2160 note_reg_use (regno
);
2162 note_reg_clobber (regno
);
2164 /* Pseudos that are REG_EQUIV to something may be replaced
2165 by that during reloading. We need only add dependencies for
2166 the address in the REG_EQUIV note. */
2167 if (!reload_completed
&& get_reg_known_equiv_p (regno
))
2169 rtx t
= get_reg_known_value (regno
);
2171 sched_analyze_2 (deps
, XEXP (t
, 0), insn
);
2174 /* Don't let it cross a call after scheduling if it doesn't
2175 already cross one. */
2176 if (REG_N_CALLS_CROSSED (regno
) == 0)
2178 if (!deps
->readonly
&& ref
== USE
&& !DEBUG_INSN_P (insn
))
2179 deps
->sched_before_next_call
2180 = alloc_INSN_LIST (insn
, deps
->sched_before_next_call
);
2182 add_dependence_list (insn
, deps
->last_function_call
, 1,
2188 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2189 rtx, X, creating all dependencies generated by the write to the
2190 destination of X, and reads of everything mentioned. */
2193 sched_analyze_1 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2195 rtx dest
= XEXP (x
, 0);
2196 enum rtx_code code
= GET_CODE (x
);
2197 bool cslr_p
= can_start_lhs_rhs_p
;
2199 can_start_lhs_rhs_p
= false;
2205 if (cslr_p
&& sched_deps_info
->start_lhs
)
2206 sched_deps_info
->start_lhs (dest
);
2208 if (GET_CODE (dest
) == PARALLEL
)
2212 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
2213 if (XEXP (XVECEXP (dest
, 0, i
), 0) != 0)
2214 sched_analyze_1 (deps
,
2215 gen_rtx_CLOBBER (VOIDmode
,
2216 XEXP (XVECEXP (dest
, 0, i
), 0)),
2219 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2220 sched_deps_info
->finish_lhs ();
2224 can_start_lhs_rhs_p
= cslr_p
;
2226 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2228 can_start_lhs_rhs_p
= false;
2234 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
2235 || GET_CODE (dest
) == ZERO_EXTRACT
)
2237 if (GET_CODE (dest
) == STRICT_LOW_PART
2238 || GET_CODE (dest
) == ZERO_EXTRACT
2239 || df_read_modify_subreg_p (dest
))
2241 /* These both read and modify the result. We must handle
2242 them as writes to get proper dependencies for following
2243 instructions. We must handle them as reads to get proper
2244 dependencies from this to previous instructions.
2245 Thus we need to call sched_analyze_2. */
2247 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2249 if (GET_CODE (dest
) == ZERO_EXTRACT
)
2251 /* The second and third arguments are values read by this insn. */
2252 sched_analyze_2 (deps
, XEXP (dest
, 1), insn
);
2253 sched_analyze_2 (deps
, XEXP (dest
, 2), insn
);
2255 dest
= XEXP (dest
, 0);
2260 int regno
= REGNO (dest
);
2261 enum machine_mode mode
= GET_MODE (dest
);
2263 sched_analyze_reg (deps
, regno
, mode
, code
, insn
);
2266 /* Treat all writes to a stack register as modifying the TOS. */
2267 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2271 /* Avoid analyzing the same register twice. */
2272 if (regno
!= FIRST_STACK_REG
)
2273 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, code
, insn
);
2275 nregs
= hard_regno_nregs
[FIRST_STACK_REG
][mode
];
2276 while (--nregs
>= 0)
2277 SET_HARD_REG_BIT (implicit_reg_pending_uses
,
2278 FIRST_STACK_REG
+ nregs
);
2282 else if (MEM_P (dest
))
2284 /* Writing memory. */
2287 if (sched_deps_info
->use_cselib
)
2289 enum machine_mode address_mode
2290 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (dest
));
2292 t
= shallow_copy_rtx (dest
);
2293 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1, insn
);
2294 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2298 /* Pending lists can't get larger with a readonly context. */
2300 && ((deps
->pending_read_list_length
+ deps
->pending_write_list_length
)
2301 > MAX_PENDING_LIST_LENGTH
))
2303 /* Flush all pending reads and writes to prevent the pending lists
2304 from getting any larger. Insn scheduling runs too slowly when
2305 these lists get long. When compiling GCC with itself,
2306 this flush occurs 8 times for sparc, and 10 times for m88k using
2307 the default value of 32. */
2308 flush_pending_lists (deps
, insn
, false, true);
2312 rtx pending
, pending_mem
;
2314 pending
= deps
->pending_read_insns
;
2315 pending_mem
= deps
->pending_read_mems
;
2318 if (anti_dependence (XEXP (pending_mem
, 0), t
)
2319 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2320 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2323 pending
= XEXP (pending
, 1);
2324 pending_mem
= XEXP (pending_mem
, 1);
2327 pending
= deps
->pending_write_insns
;
2328 pending_mem
= deps
->pending_write_mems
;
2331 if (output_dependence (XEXP (pending_mem
, 0), t
)
2332 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2333 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2336 pending
= XEXP (pending
, 1);
2337 pending_mem
= XEXP (pending_mem
, 1);
2340 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2343 if (!deps
->readonly
)
2344 add_insn_mem_dependence (deps
, false, insn
, dest
);
2346 sched_analyze_2 (deps
, XEXP (dest
, 0), insn
);
2349 if (cslr_p
&& sched_deps_info
->finish_lhs
)
2350 sched_deps_info
->finish_lhs ();
2352 /* Analyze reads. */
2353 if (GET_CODE (x
) == SET
)
2355 can_start_lhs_rhs_p
= cslr_p
;
2357 sched_analyze_2 (deps
, SET_SRC (x
), insn
);
2359 can_start_lhs_rhs_p
= false;
2363 /* Analyze the uses of memory and registers in rtx X in INSN. */
2365 sched_analyze_2 (struct deps_desc
*deps
, rtx x
, rtx insn
)
2371 bool cslr_p
= can_start_lhs_rhs_p
;
2373 can_start_lhs_rhs_p
= false;
2379 if (cslr_p
&& sched_deps_info
->start_rhs
)
2380 sched_deps_info
->start_rhs (x
);
2382 code
= GET_CODE (x
);
2393 /* Ignore constants. */
2394 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2395 sched_deps_info
->finish_rhs ();
2401 /* User of CC0 depends on immediately preceding insn. */
2402 SCHED_GROUP_P (insn
) = 1;
2403 /* Don't move CC0 setter to another block (it can set up the
2404 same flag for previous CC0 users which is safe). */
2405 CANT_MOVE (prev_nonnote_insn (insn
)) = 1;
2407 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2408 sched_deps_info
->finish_rhs ();
2415 int regno
= REGNO (x
);
2416 enum machine_mode mode
= GET_MODE (x
);
2418 sched_analyze_reg (deps
, regno
, mode
, USE
, insn
);
2421 /* Treat all reads of a stack register as modifying the TOS. */
2422 if (regno
>= FIRST_STACK_REG
&& regno
<= LAST_STACK_REG
)
2424 /* Avoid analyzing the same register twice. */
2425 if (regno
!= FIRST_STACK_REG
)
2426 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, USE
, insn
);
2427 sched_analyze_reg (deps
, FIRST_STACK_REG
, mode
, SET
, insn
);
2431 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2432 sched_deps_info
->finish_rhs ();
2439 /* Reading memory. */
2441 rtx pending
, pending_mem
;
2444 if (sched_deps_info
->use_cselib
)
2446 enum machine_mode address_mode
2447 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (t
));
2449 t
= shallow_copy_rtx (t
);
2450 cselib_lookup_from_insn (XEXP (t
, 0), address_mode
, 1, insn
);
2451 XEXP (t
, 0) = cselib_subst_to_values (XEXP (t
, 0));
2454 if (!DEBUG_INSN_P (insn
))
2457 pending
= deps
->pending_read_insns
;
2458 pending_mem
= deps
->pending_read_mems
;
2461 if (read_dependence (XEXP (pending_mem
, 0), t
)
2462 && ! sched_insns_conditions_mutex_p (insn
,
2464 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2467 pending
= XEXP (pending
, 1);
2468 pending_mem
= XEXP (pending_mem
, 1);
2471 pending
= deps
->pending_write_insns
;
2472 pending_mem
= deps
->pending_write_mems
;
2475 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
2477 && ! sched_insns_conditions_mutex_p (insn
,
2479 note_mem_dep (t
, XEXP (pending_mem
, 0), XEXP (pending
, 0),
2480 sched_deps_info
->generate_spec_deps
2481 ? BEGIN_DATA
| DEP_TRUE
: DEP_TRUE
);
2483 pending
= XEXP (pending
, 1);
2484 pending_mem
= XEXP (pending_mem
, 1);
2487 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2489 if (! JUMP_P (XEXP (u
, 0)))
2490 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2491 else if (deps_may_trap_p (x
))
2493 if ((sched_deps_info
->generate_spec_deps
)
2494 && sel_sched_p () && (spec_info
->mask
& BEGIN_CONTROL
))
2496 ds_t ds
= set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
2499 note_dep (XEXP (u
, 0), ds
);
2502 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2507 /* Always add these dependencies to pending_reads, since
2508 this insn may be followed by a write. */
2509 if (!deps
->readonly
)
2510 add_insn_mem_dependence (deps
, true, insn
, x
);
2512 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2514 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2515 sched_deps_info
->finish_rhs ();
2520 /* Force pending stores to memory in case a trap handler needs them. */
2522 flush_pending_lists (deps
, insn
, true, false);
2526 if (PREFETCH_SCHEDULE_BARRIER_P (x
))
2527 reg_pending_barrier
= TRUE_BARRIER
;
2530 case UNSPEC_VOLATILE
:
2531 flush_pending_lists (deps
, insn
, true, true);
2537 /* Traditional and volatile asm instructions must be considered to use
2538 and clobber all hard registers, all pseudo-registers and all of
2539 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2541 Consider for instance a volatile asm that changes the fpu rounding
2542 mode. An insn should not be moved across this even if it only uses
2543 pseudo-regs because it might give an incorrectly rounded result. */
2544 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
2545 reg_pending_barrier
= TRUE_BARRIER
;
2547 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2548 We can not just fall through here since then we would be confused
2549 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2550 traditional asms unlike their normal usage. */
2552 if (code
== ASM_OPERANDS
)
2554 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
2555 sched_analyze_2 (deps
, ASM_OPERANDS_INPUT (x
, j
), insn
);
2557 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2558 sched_deps_info
->finish_rhs ();
2569 /* These both read and modify the result. We must handle them as writes
2570 to get proper dependencies for following instructions. We must handle
2571 them as reads to get proper dependencies from this to previous
2572 instructions. Thus we need to pass them to both sched_analyze_1
2573 and sched_analyze_2. We must call sched_analyze_2 first in order
2574 to get the proper antecedent for the read. */
2575 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2576 sched_analyze_1 (deps
, x
, insn
);
2578 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2579 sched_deps_info
->finish_rhs ();
2585 /* op0 = op0 + op1 */
2586 sched_analyze_2 (deps
, XEXP (x
, 0), insn
);
2587 sched_analyze_2 (deps
, XEXP (x
, 1), insn
);
2588 sched_analyze_1 (deps
, x
, insn
);
2590 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2591 sched_deps_info
->finish_rhs ();
2599 /* Other cases: walk the insn. */
2600 fmt
= GET_RTX_FORMAT (code
);
2601 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2604 sched_analyze_2 (deps
, XEXP (x
, i
), insn
);
2605 else if (fmt
[i
] == 'E')
2606 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2607 sched_analyze_2 (deps
, XVECEXP (x
, i
, j
), insn
);
2610 if (cslr_p
&& sched_deps_info
->finish_rhs
)
2611 sched_deps_info
->finish_rhs ();
2614 /* Analyze an INSN with pattern X to find all dependencies. */
2616 sched_analyze_insn (struct deps_desc
*deps
, rtx x
, rtx insn
)
2618 RTX_CODE code
= GET_CODE (x
);
2621 reg_set_iterator rsi
;
2623 if (! reload_completed
)
2627 extract_insn (insn
);
2628 preprocess_constraints ();
2629 ira_implicitly_set_insn_hard_regs (&temp
);
2630 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
2631 IOR_HARD_REG_SET (implicit_reg_pending_clobbers
, temp
);
2634 can_start_lhs_rhs_p
= (NONJUMP_INSN_P (insn
)
2638 /* Avoid moving trapping instructions accross function calls that might
2639 not always return. */
2640 add_dependence_list (insn
, deps
->last_function_call_may_noreturn
,
2643 if (code
== COND_EXEC
)
2645 sched_analyze_2 (deps
, COND_EXEC_TEST (x
), insn
);
2647 /* ??? Should be recording conditions so we reduce the number of
2648 false dependencies. */
2649 x
= COND_EXEC_CODE (x
);
2650 code
= GET_CODE (x
);
2652 if (code
== SET
|| code
== CLOBBER
)
2654 sched_analyze_1 (deps
, x
, insn
);
2656 /* Bare clobber insns are used for letting life analysis, reg-stack
2657 and others know that a value is dead. Depend on the last call
2658 instruction so that reg-stack won't get confused. */
2659 if (code
== CLOBBER
)
2660 add_dependence_list (insn
, deps
->last_function_call
, 1,
2663 else if (code
== PARALLEL
)
2665 for (i
= XVECLEN (x
, 0); i
--;)
2667 rtx sub
= XVECEXP (x
, 0, i
);
2668 code
= GET_CODE (sub
);
2670 if (code
== COND_EXEC
)
2672 sched_analyze_2 (deps
, COND_EXEC_TEST (sub
), insn
);
2673 sub
= COND_EXEC_CODE (sub
);
2674 code
= GET_CODE (sub
);
2676 if (code
== SET
|| code
== CLOBBER
)
2677 sched_analyze_1 (deps
, sub
, insn
);
2679 sched_analyze_2 (deps
, sub
, insn
);
2683 sched_analyze_2 (deps
, x
, insn
);
2685 /* Mark registers CLOBBERED or used by called function. */
2688 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
2690 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
2691 sched_analyze_1 (deps
, XEXP (link
, 0), insn
);
2693 sched_analyze_2 (deps
, XEXP (link
, 0), insn
);
2695 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
2696 reg_pending_barrier
= MOVE_BARRIER
;
2702 next
= next_nonnote_insn (insn
);
2703 while (next
&& DEBUG_INSN_P (next
))
2704 next
= next_nonnote_insn (next
);
2705 if (next
&& BARRIER_P (next
))
2706 reg_pending_barrier
= MOVE_BARRIER
;
2709 rtx pending
, pending_mem
;
2711 if (sched_deps_info
->compute_jump_reg_dependencies
)
2713 regset_head tmp_uses
, tmp_sets
;
2714 INIT_REG_SET (&tmp_uses
);
2715 INIT_REG_SET (&tmp_sets
);
2717 (*sched_deps_info
->compute_jump_reg_dependencies
)
2718 (insn
, &deps
->reg_conditional_sets
, &tmp_uses
, &tmp_sets
);
2719 /* Make latency of jump equal to 0 by using anti-dependence. */
2720 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses
, 0, i
, rsi
)
2722 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2723 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2724 add_dependence_list (insn
, reg_last
->implicit_sets
,
2726 add_dependence_list (insn
, reg_last
->clobbers
, 0,
2729 if (!deps
->readonly
)
2731 reg_last
->uses_length
++;
2732 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2735 IOR_REG_SET (reg_pending_sets
, &tmp_sets
);
2737 CLEAR_REG_SET (&tmp_uses
);
2738 CLEAR_REG_SET (&tmp_sets
);
2741 /* All memory writes and volatile reads must happen before the
2742 jump. Non-volatile reads must happen before the jump iff
2743 the result is needed by the above register used mask. */
2745 pending
= deps
->pending_write_insns
;
2746 pending_mem
= deps
->pending_write_mems
;
2749 if (! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2750 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2751 pending
= XEXP (pending
, 1);
2752 pending_mem
= XEXP (pending_mem
, 1);
2755 pending
= deps
->pending_read_insns
;
2756 pending_mem
= deps
->pending_read_mems
;
2759 if (MEM_VOLATILE_P (XEXP (pending_mem
, 0))
2760 && ! sched_insns_conditions_mutex_p (insn
, XEXP (pending
, 0)))
2761 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
2762 pending
= XEXP (pending
, 1);
2763 pending_mem
= XEXP (pending_mem
, 1);
2766 add_dependence_list (insn
, deps
->last_pending_memory_flush
, 1,
2771 /* If this instruction can throw an exception, then moving it changes
2772 where block boundaries fall. This is mighty confusing elsewhere.
2773 Therefore, prevent such an instruction from being moved. Same for
2774 non-jump instructions that define block boundaries.
2775 ??? Unclear whether this is still necessary in EBB mode. If not,
2776 add_branch_dependences should be adjusted for RGN mode instead. */
2777 if (((CALL_P (insn
) || JUMP_P (insn
)) && can_throw_internal (insn
))
2778 || (NONJUMP_INSN_P (insn
) && control_flow_insn_p (insn
)))
2779 reg_pending_barrier
= MOVE_BARRIER
;
2781 if (sched_pressure_p
)
2783 setup_insn_reg_uses (deps
, insn
);
2784 setup_insn_reg_pressure_info (insn
);
2787 /* Add register dependencies for insn. */
2788 if (DEBUG_INSN_P (insn
))
2790 rtx prev
= deps
->last_debug_insn
;
2793 if (!deps
->readonly
)
2794 deps
->last_debug_insn
= insn
;
2797 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2799 add_dependence_list (insn
, deps
->last_function_call
, 1,
2802 for (u
= deps
->last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
2803 if (! JUMP_P (XEXP (u
, 0))
2805 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
2807 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2809 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2810 add_dependence_list (insn
, reg_last
->sets
, 1, REG_DEP_ANTI
);
2811 add_dependence_list (insn
, reg_last
->clobbers
, 1, REG_DEP_ANTI
);
2813 if (!deps
->readonly
)
2814 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2816 CLEAR_REG_SET (reg_pending_uses
);
2818 /* Quite often, a debug insn will refer to stuff in the
2819 previous instruction, but the reason we want this
2820 dependency here is to make sure the scheduler doesn't
2821 gratuitously move a debug insn ahead. This could dirty
2822 DF flags and cause additional analysis that wouldn't have
2823 occurred in compilation without debug insns, and such
2824 additional analysis can modify the generated code. */
2825 prev
= PREV_INSN (insn
);
2827 if (prev
&& NONDEBUG_INSN_P (prev
))
2828 add_dependence (insn
, prev
, REG_DEP_ANTI
);
2832 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses
, 0, i
, rsi
)
2834 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2835 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2836 add_dependence_list (insn
, reg_last
->implicit_sets
, 0, REG_DEP_ANTI
);
2837 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2839 if (!deps
->readonly
)
2841 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2842 reg_last
->uses_length
++;
2846 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2847 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
))
2849 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2850 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_TRUE
);
2851 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2853 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_TRUE
);
2855 if (!deps
->readonly
)
2857 reg_last
->uses
= alloc_INSN_LIST (insn
, reg_last
->uses
);
2858 reg_last
->uses_length
++;
2862 /* If the current insn is conditional, we can't free any
2864 if (sched_has_condition_p (insn
))
2866 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2868 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2869 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2870 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2872 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2874 if (!deps
->readonly
)
2877 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2878 reg_last
->clobbers_length
++;
2881 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2883 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2884 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2885 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2887 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2888 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2890 if (!deps
->readonly
)
2892 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2893 SET_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2899 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
, rsi
)
2901 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2902 if (reg_last
->uses_length
> MAX_PENDING_LIST_LENGTH
2903 || reg_last
->clobbers_length
> MAX_PENDING_LIST_LENGTH
)
2905 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2907 add_dependence_list_and_free (deps
, insn
,
2908 ®_last
->implicit_sets
, 0,
2910 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2912 add_dependence_list_and_free
2913 (deps
, insn
, ®_last
->clobbers
, 0, REG_DEP_OUTPUT
);
2915 if (!deps
->readonly
)
2917 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2918 reg_last
->clobbers_length
= 0;
2919 reg_last
->uses_length
= 0;
2924 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_OUTPUT
);
2925 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
2927 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2930 if (!deps
->readonly
)
2932 reg_last
->clobbers_length
++;
2934 = alloc_INSN_LIST (insn
, reg_last
->clobbers
);
2937 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
, rsi
)
2939 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2941 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
2943 add_dependence_list_and_free (deps
, insn
,
2944 ®_last
->implicit_sets
,
2946 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
2948 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
2951 if (!deps
->readonly
)
2953 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
2954 reg_last
->uses_length
= 0;
2955 reg_last
->clobbers_length
= 0;
2956 CLEAR_REGNO_REG_SET (&deps
->reg_conditional_sets
, i
);
2962 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2963 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2965 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
2966 add_dependence_list (insn
, reg_last
->sets
, 0, REG_DEP_ANTI
);
2967 add_dependence_list (insn
, reg_last
->clobbers
, 0, REG_DEP_ANTI
);
2968 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
2970 if (!deps
->readonly
)
2971 reg_last
->implicit_sets
2972 = alloc_INSN_LIST (insn
, reg_last
->implicit_sets
);
2975 if (!deps
->readonly
)
2977 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_uses
);
2978 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_clobbers
);
2979 IOR_REG_SET (&deps
->reg_last_in_use
, reg_pending_sets
);
2980 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2981 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses
, i
)
2982 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers
, i
))
2983 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
2985 /* Set up the pending barrier found. */
2986 deps
->last_reg_pending_barrier
= reg_pending_barrier
;
2989 CLEAR_REG_SET (reg_pending_uses
);
2990 CLEAR_REG_SET (reg_pending_clobbers
);
2991 CLEAR_REG_SET (reg_pending_sets
);
2992 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
2993 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
2995 /* Add dependencies if a scheduling barrier was found. */
2996 if (reg_pending_barrier
)
2998 /* In the case of barrier the most added dependencies are not
2999 real, so we use anti-dependence here. */
3000 if (sched_has_condition_p (insn
))
3002 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3004 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3005 add_dependence_list (insn
, reg_last
->uses
, 0, REG_DEP_ANTI
);
3006 add_dependence_list (insn
, reg_last
->sets
, 0,
3007 reg_pending_barrier
== TRUE_BARRIER
3008 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3009 add_dependence_list (insn
, reg_last
->implicit_sets
, 0,
3011 add_dependence_list (insn
, reg_last
->clobbers
, 0,
3012 reg_pending_barrier
== TRUE_BARRIER
3013 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3018 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3020 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3021 add_dependence_list_and_free (deps
, insn
, ®_last
->uses
, 0,
3023 add_dependence_list_and_free (deps
, insn
, ®_last
->sets
, 0,
3024 reg_pending_barrier
== TRUE_BARRIER
3025 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3026 add_dependence_list_and_free (deps
, insn
,
3027 ®_last
->implicit_sets
, 0,
3029 add_dependence_list_and_free (deps
, insn
, ®_last
->clobbers
, 0,
3030 reg_pending_barrier
== TRUE_BARRIER
3031 ? REG_DEP_TRUE
: REG_DEP_ANTI
);
3033 if (!deps
->readonly
)
3035 reg_last
->uses_length
= 0;
3036 reg_last
->clobbers_length
= 0;
3041 if (!deps
->readonly
)
3042 for (i
= 0; i
< (unsigned)deps
->max_reg
; i
++)
3044 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3045 reg_last
->sets
= alloc_INSN_LIST (insn
, reg_last
->sets
);
3046 SET_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3049 /* Flush pending lists on jumps, but not on speculative checks. */
3050 if (JUMP_P (insn
) && !(sel_sched_p ()
3051 && sel_insn_is_speculation_check (insn
)))
3052 flush_pending_lists (deps
, insn
, true, true);
3054 if (!deps
->readonly
)
3055 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3056 reg_pending_barrier
= NOT_A_BARRIER
;
3059 /* If a post-call group is still open, see if it should remain so.
3060 This insn must be a simple move of a hard reg to a pseudo or
3063 We must avoid moving these insns for correctness on targets
3064 with small register classes, and for special registers like
3065 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3066 hard regs for all targets. */
3068 if (deps
->in_post_call_group_p
)
3070 rtx tmp
, set
= single_set (insn
);
3071 int src_regno
, dest_regno
;
3075 if (DEBUG_INSN_P (insn
))
3076 /* We don't want to mark debug insns as part of the same
3077 sched group. We know they really aren't, but if we use
3078 debug insns to tell that a call group is over, we'll
3079 get different code if debug insns are not there and
3080 instructions that follow seem like they should be part
3083 Also, if we did, fixup_sched_groups() would move the
3084 deps of the debug insn to the call insn, modifying
3085 non-debug post-dependency counts of the debug insn
3086 dependencies and otherwise messing with the scheduling
3089 Instead, let such debug insns be scheduled freely, but
3090 keep the call group open in case there are insns that
3091 should be part of it afterwards. Since we grant debug
3092 insns higher priority than even sched group insns, it
3093 will all turn out all right. */
3094 goto debug_dont_end_call_group
;
3096 goto end_call_group
;
3099 tmp
= SET_DEST (set
);
3100 if (GET_CODE (tmp
) == SUBREG
)
3101 tmp
= SUBREG_REG (tmp
);
3103 dest_regno
= REGNO (tmp
);
3105 goto end_call_group
;
3107 tmp
= SET_SRC (set
);
3108 if (GET_CODE (tmp
) == SUBREG
)
3109 tmp
= SUBREG_REG (tmp
);
3110 if ((GET_CODE (tmp
) == PLUS
3111 || GET_CODE (tmp
) == MINUS
)
3112 && REG_P (XEXP (tmp
, 0))
3113 && REGNO (XEXP (tmp
, 0)) == STACK_POINTER_REGNUM
3114 && dest_regno
== STACK_POINTER_REGNUM
)
3115 src_regno
= STACK_POINTER_REGNUM
;
3116 else if (REG_P (tmp
))
3117 src_regno
= REGNO (tmp
);
3119 goto end_call_group
;
3121 if (src_regno
< FIRST_PSEUDO_REGISTER
3122 || dest_regno
< FIRST_PSEUDO_REGISTER
)
3125 && deps
->in_post_call_group_p
== post_call_initial
)
3126 deps
->in_post_call_group_p
= post_call
;
3128 if (!sel_sched_p () || sched_emulate_haifa_p
)
3130 SCHED_GROUP_P (insn
) = 1;
3131 CANT_MOVE (insn
) = 1;
3137 if (!deps
->readonly
)
3138 deps
->in_post_call_group_p
= not_post_call
;
3142 debug_dont_end_call_group
:
3143 if ((current_sched_info
->flags
& DO_SPECULATION
)
3144 && !sched_insn_is_legitimate_for_speculation_p (insn
, 0))
3145 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3149 sel_mark_hard_insn (insn
);
3152 sd_iterator_def sd_it
;
3155 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3156 sd_iterator_cond (&sd_it
, &dep
);)
3157 change_spec_dep_to_hard (sd_it
);
3162 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3163 longjmp, loop forever, ...). */
3165 call_may_noreturn_p (rtx insn
)
3169 /* const or pure calls that aren't looping will always return. */
3170 if (RTL_CONST_OR_PURE_CALL_P (insn
)
3171 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
3174 call
= PATTERN (insn
);
3175 if (GET_CODE (call
) == PARALLEL
)
3176 call
= XVECEXP (call
, 0, 0);
3177 if (GET_CODE (call
) == SET
)
3178 call
= SET_SRC (call
);
3179 if (GET_CODE (call
) == CALL
3180 && MEM_P (XEXP (call
, 0))
3181 && GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
3183 rtx symbol
= XEXP (XEXP (call
, 0), 0);
3184 if (SYMBOL_REF_DECL (symbol
)
3185 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
3187 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
3189 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
)))
3192 case BUILT_IN_BCOPY
:
3193 case BUILT_IN_BZERO
:
3194 case BUILT_IN_INDEX
:
3195 case BUILT_IN_MEMCHR
:
3196 case BUILT_IN_MEMCMP
:
3197 case BUILT_IN_MEMCPY
:
3198 case BUILT_IN_MEMMOVE
:
3199 case BUILT_IN_MEMPCPY
:
3200 case BUILT_IN_MEMSET
:
3201 case BUILT_IN_RINDEX
:
3202 case BUILT_IN_STPCPY
:
3203 case BUILT_IN_STPNCPY
:
3204 case BUILT_IN_STRCAT
:
3205 case BUILT_IN_STRCHR
:
3206 case BUILT_IN_STRCMP
:
3207 case BUILT_IN_STRCPY
:
3208 case BUILT_IN_STRCSPN
:
3209 case BUILT_IN_STRLEN
:
3210 case BUILT_IN_STRNCAT
:
3211 case BUILT_IN_STRNCMP
:
3212 case BUILT_IN_STRNCPY
:
3213 case BUILT_IN_STRPBRK
:
3214 case BUILT_IN_STRRCHR
:
3215 case BUILT_IN_STRSPN
:
3216 case BUILT_IN_STRSTR
:
3217 /* Assume certain string/memory builtins always return. */
3225 /* For all other calls assume that they might not always return. */
3229 /* Analyze INSN with DEPS as a context. */
3231 deps_analyze_insn (struct deps_desc
*deps
, rtx insn
)
3233 if (sched_deps_info
->start_insn
)
3234 sched_deps_info
->start_insn (insn
);
3236 if (NONJUMP_INSN_P (insn
) || DEBUG_INSN_P (insn
) || JUMP_P (insn
))
3238 /* Make each JUMP_INSN (but not a speculative check)
3239 a scheduling barrier for memory references. */
3243 && sel_insn_is_speculation_check (insn
)))
3245 /* Keep the list a reasonable size. */
3246 if (deps
->pending_flush_length
++ > MAX_PENDING_LIST_LENGTH
)
3247 flush_pending_lists (deps
, insn
, true, true);
3249 deps
->last_pending_memory_flush
3250 = alloc_INSN_LIST (insn
, deps
->last_pending_memory_flush
);
3253 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3255 else if (CALL_P (insn
))
3259 CANT_MOVE (insn
) = 1;
3261 if (find_reg_note (insn
, REG_SETJMP
, NULL
))
3263 /* This is setjmp. Assume that all registers, not just
3264 hard registers, may be clobbered by this call. */
3265 reg_pending_barrier
= MOVE_BARRIER
;
3269 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3270 /* A call may read and modify global register variables. */
3273 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3274 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3276 /* Other call-clobbered hard regs may be clobbered.
3277 Since we only have a choice between 'might be clobbered'
3278 and 'definitely not clobbered', we must include all
3279 partly call-clobbered registers here. */
3280 else if (HARD_REGNO_CALL_PART_CLOBBERED (i
, reg_raw_mode
[i
])
3281 || TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3282 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3283 /* We don't know what set of fixed registers might be used
3284 by the function, but it is certain that the stack pointer
3285 is among them, but be conservative. */
3286 else if (fixed_regs
[i
])
3287 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3288 /* The frame pointer is normally not used by the function
3289 itself, but by the debugger. */
3290 /* ??? MIPS o32 is an exception. It uses the frame pointer
3291 in the macro expansion of jal but does not represent this
3292 fact in the call_insn rtl. */
3293 else if (i
== FRAME_POINTER_REGNUM
3294 || (i
== HARD_FRAME_POINTER_REGNUM
3295 && (! reload_completed
|| frame_pointer_needed
)))
3296 SET_HARD_REG_BIT (implicit_reg_pending_uses
, i
);
3299 /* For each insn which shouldn't cross a call, add a dependence
3300 between that insn and this call insn. */
3301 add_dependence_list_and_free (deps
, insn
,
3302 &deps
->sched_before_next_call
, 1,
3305 sched_analyze_insn (deps
, PATTERN (insn
), insn
);
3307 /* If CALL would be in a sched group, then this will violate
3308 convention that sched group insns have dependencies only on the
3309 previous instruction.
3311 Of course one can say: "Hey! What about head of the sched group?"
3312 And I will answer: "Basic principles (one dep per insn) are always
3314 gcc_assert (!SCHED_GROUP_P (insn
));
3316 /* In the absence of interprocedural alias analysis, we must flush
3317 all pending reads and writes, and start new dependencies starting
3318 from here. But only flush writes for constant calls (which may
3319 be passed a pointer to something we haven't written yet). */
3320 flush_pending_lists (deps
, insn
, true, ! RTL_CONST_OR_PURE_CALL_P (insn
));
3322 if (!deps
->readonly
)
3324 /* Remember the last function call for limiting lifetimes. */
3325 free_INSN_LIST_list (&deps
->last_function_call
);
3326 deps
->last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3328 if (call_may_noreturn_p (insn
))
3330 /* Remember the last function call that might not always return
3331 normally for limiting moves of trapping insns. */
3332 free_INSN_LIST_list (&deps
->last_function_call_may_noreturn
);
3333 deps
->last_function_call_may_noreturn
3334 = alloc_INSN_LIST (insn
, NULL_RTX
);
3337 /* Before reload, begin a post-call group, so as to keep the
3338 lifetimes of hard registers correct. */
3339 if (! reload_completed
)
3340 deps
->in_post_call_group_p
= post_call
;
3344 if (sched_deps_info
->use_cselib
)
3345 cselib_process_insn (insn
);
3347 /* EH_REGION insn notes can not appear until well after we complete
3350 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
3351 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
);
3353 if (sched_deps_info
->finish_insn
)
3354 sched_deps_info
->finish_insn ();
3356 /* Fixup the dependencies in the sched group. */
3357 if ((NONJUMP_INSN_P (insn
) || JUMP_P (insn
))
3358 && SCHED_GROUP_P (insn
) && !sel_sched_p ())
3359 fixup_sched_groups (insn
);
3362 /* Initialize DEPS for the new block beginning with HEAD. */
3364 deps_start_bb (struct deps_desc
*deps
, rtx head
)
3366 gcc_assert (!deps
->readonly
);
3368 /* Before reload, if the previous block ended in a call, show that
3369 we are inside a post-call group, so as to keep the lifetimes of
3370 hard registers correct. */
3371 if (! reload_completed
&& !LABEL_P (head
))
3373 rtx insn
= prev_nonnote_insn (head
);
3375 while (insn
&& DEBUG_INSN_P (insn
))
3376 insn
= prev_nonnote_insn (insn
);
3377 if (insn
&& CALL_P (insn
))
3378 deps
->in_post_call_group_p
= post_call_initial
;
3382 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3383 dependencies for each insn. */
3385 sched_analyze (struct deps_desc
*deps
, rtx head
, rtx tail
)
3389 if (sched_deps_info
->use_cselib
)
3390 cselib_init (CSELIB_RECORD_MEMORY
);
3392 deps_start_bb (deps
, head
);
3394 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3399 /* And initialize deps_lists. */
3400 sd_init_insn (insn
);
3403 deps_analyze_insn (deps
, insn
);
3407 if (sched_deps_info
->use_cselib
)
3415 /* Helper for sched_free_deps ().
3416 Delete INSN's (RESOLVED_P) backward dependencies. */
3418 delete_dep_nodes_in_back_deps (rtx insn
, bool resolved_p
)
3420 sd_iterator_def sd_it
;
3422 sd_list_types_def types
;
3425 types
= SD_LIST_RES_BACK
;
3427 types
= SD_LIST_BACK
;
3429 for (sd_it
= sd_iterator_start (insn
, types
);
3430 sd_iterator_cond (&sd_it
, &dep
);)
3432 dep_link_t link
= *sd_it
.linkp
;
3433 dep_node_t node
= DEP_LINK_NODE (link
);
3434 deps_list_t back_list
;
3435 deps_list_t forw_list
;
3437 get_back_and_forw_lists (dep
, resolved_p
, &back_list
, &forw_list
);
3438 remove_from_deps_list (link
, back_list
);
3439 delete_dep_node (node
);
3443 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3446 sched_free_deps (rtx head
, rtx tail
, bool resolved_p
)
3449 rtx next_tail
= NEXT_INSN (tail
);
3451 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3452 if (INSN_P (insn
) && INSN_LUID (insn
) > 0)
3454 /* Clear resolved back deps together with its dep_nodes. */
3455 delete_dep_nodes_in_back_deps (insn
, resolved_p
);
3457 /* Clear forward deps and leave the dep_nodes to the
3458 corresponding back_deps list. */
3460 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn
));
3462 clear_deps_list (INSN_FORW_DEPS (insn
));
3464 sd_finish_insn (insn
);
3468 /* Initialize variables for region data dependence analysis.
3469 When LAZY_REG_LAST is true, do not allocate reg_last array
3470 of struct deps_desc immediately. */
3473 init_deps (struct deps_desc
*deps
, bool lazy_reg_last
)
3475 int max_reg
= (reload_completed
? FIRST_PSEUDO_REGISTER
: max_reg_num ());
3477 deps
->max_reg
= max_reg
;
3479 deps
->reg_last
= NULL
;
3481 deps
->reg_last
= XCNEWVEC (struct deps_reg
, max_reg
);
3482 INIT_REG_SET (&deps
->reg_last_in_use
);
3483 INIT_REG_SET (&deps
->reg_conditional_sets
);
3485 deps
->pending_read_insns
= 0;
3486 deps
->pending_read_mems
= 0;
3487 deps
->pending_write_insns
= 0;
3488 deps
->pending_write_mems
= 0;
3489 deps
->pending_read_list_length
= 0;
3490 deps
->pending_write_list_length
= 0;
3491 deps
->pending_flush_length
= 0;
3492 deps
->last_pending_memory_flush
= 0;
3493 deps
->last_function_call
= 0;
3494 deps
->last_function_call_may_noreturn
= 0;
3495 deps
->sched_before_next_call
= 0;
3496 deps
->in_post_call_group_p
= not_post_call
;
3497 deps
->last_debug_insn
= 0;
3498 deps
->last_reg_pending_barrier
= NOT_A_BARRIER
;
3502 /* Init only reg_last field of DEPS, which was not allocated before as
3503 we inited DEPS lazily. */
3505 init_deps_reg_last (struct deps_desc
*deps
)
3507 gcc_assert (deps
&& deps
->max_reg
> 0);
3508 gcc_assert (deps
->reg_last
== NULL
);
3510 deps
->reg_last
= XCNEWVEC (struct deps_reg
, deps
->max_reg
);
3514 /* Free insn lists found in DEPS. */
3517 free_deps (struct deps_desc
*deps
)
3520 reg_set_iterator rsi
;
3522 /* We set max_reg to 0 when this context was already freed. */
3523 if (deps
->max_reg
== 0)
3525 gcc_assert (deps
->reg_last
== NULL
);
3530 free_INSN_LIST_list (&deps
->pending_read_insns
);
3531 free_EXPR_LIST_list (&deps
->pending_read_mems
);
3532 free_INSN_LIST_list (&deps
->pending_write_insns
);
3533 free_EXPR_LIST_list (&deps
->pending_write_mems
);
3534 free_INSN_LIST_list (&deps
->last_pending_memory_flush
);
3536 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3537 times. For a testcase with 42000 regs and 8000 small basic blocks,
3538 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3539 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3541 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3543 free_INSN_LIST_list (®_last
->uses
);
3545 free_INSN_LIST_list (®_last
->sets
);
3546 if (reg_last
->implicit_sets
)
3547 free_INSN_LIST_list (®_last
->implicit_sets
);
3548 if (reg_last
->clobbers
)
3549 free_INSN_LIST_list (®_last
->clobbers
);
3551 CLEAR_REG_SET (&deps
->reg_last_in_use
);
3552 CLEAR_REG_SET (&deps
->reg_conditional_sets
);
3554 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3557 free (deps
->reg_last
);
3558 deps
->reg_last
= NULL
;
3563 /* Remove INSN from dependence contexts DEPS. Caution: reg_conditional_sets
3566 remove_from_deps (struct deps_desc
*deps
, rtx insn
)
3570 reg_set_iterator rsi
;
3572 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_read_insns
,
3573 &deps
->pending_read_mems
);
3574 if (!DEBUG_INSN_P (insn
))
3575 deps
->pending_read_list_length
-= removed
;
3576 removed
= remove_from_both_dependence_lists (insn
, &deps
->pending_write_insns
,
3577 &deps
->pending_write_mems
);
3578 deps
->pending_write_list_length
-= removed
;
3579 removed
= remove_from_dependence_list (insn
, &deps
->last_pending_memory_flush
);
3580 deps
->pending_flush_length
-= removed
;
3582 EXECUTE_IF_SET_IN_REG_SET (&deps
->reg_last_in_use
, 0, i
, rsi
)
3584 struct deps_reg
*reg_last
= &deps
->reg_last
[i
];
3586 remove_from_dependence_list (insn
, ®_last
->uses
);
3588 remove_from_dependence_list (insn
, ®_last
->sets
);
3589 if (reg_last
->implicit_sets
)
3590 remove_from_dependence_list (insn
, ®_last
->implicit_sets
);
3591 if (reg_last
->clobbers
)
3592 remove_from_dependence_list (insn
, ®_last
->clobbers
);
3593 if (!reg_last
->uses
&& !reg_last
->sets
&& !reg_last
->implicit_sets
3594 && !reg_last
->clobbers
)
3595 CLEAR_REGNO_REG_SET (&deps
->reg_last_in_use
, i
);
3600 remove_from_dependence_list (insn
, &deps
->last_function_call
);
3601 remove_from_dependence_list (insn
,
3602 &deps
->last_function_call_may_noreturn
);
3604 remove_from_dependence_list (insn
, &deps
->sched_before_next_call
);
3607 /* Init deps data vector. */
3609 init_deps_data_vector (void)
3611 int reserve
= (sched_max_luid
+ 1
3612 - VEC_length (haifa_deps_insn_data_def
, h_d_i_d
));
3614 && ! VEC_space (haifa_deps_insn_data_def
, h_d_i_d
, reserve
))
3615 VEC_safe_grow_cleared (haifa_deps_insn_data_def
, heap
, h_d_i_d
,
3616 3 * sched_max_luid
/ 2);
3619 /* If it is profitable to use them, initialize or extend (depending on
3620 GLOBAL_P) dependency data. */
3622 sched_deps_init (bool global_p
)
3624 /* Average number of insns in the basic block.
3625 '+ 1' is used to make it nonzero. */
3626 int insns_in_block
= sched_max_luid
/ n_basic_blocks
+ 1;
3628 init_deps_data_vector ();
3630 /* We use another caching mechanism for selective scheduling, so
3631 we don't use this one. */
3632 if (!sel_sched_p () && global_p
&& insns_in_block
> 100 * 5)
3634 /* ?!? We could save some memory by computing a per-region luid mapping
3635 which could reduce both the number of vectors in the cache and the
3636 size of each vector. Instead we just avoid the cache entirely unless
3637 the average number of instructions in a basic block is very high. See
3638 the comment before the declaration of true_dependency_cache for
3639 what we consider "very high". */
3641 extend_dependency_caches (sched_max_luid
, true);
3646 dl_pool
= create_alloc_pool ("deps_list", sizeof (struct _deps_list
),
3647 /* Allocate lists for one block at a time. */
3649 dn_pool
= create_alloc_pool ("dep_node", sizeof (struct _dep_node
),
3650 /* Allocate nodes for one block at a time.
3651 We assume that average insn has
3653 5 * insns_in_block
);
3658 /* Create or extend (depending on CREATE_P) dependency caches to
3661 extend_dependency_caches (int n
, bool create_p
)
3663 if (create_p
|| true_dependency_cache
)
3665 int i
, luid
= cache_size
+ n
;
3667 true_dependency_cache
= XRESIZEVEC (bitmap_head
, true_dependency_cache
,
3669 output_dependency_cache
= XRESIZEVEC (bitmap_head
,
3670 output_dependency_cache
, luid
);
3671 anti_dependency_cache
= XRESIZEVEC (bitmap_head
, anti_dependency_cache
,
3674 if (current_sched_info
->flags
& DO_SPECULATION
)
3675 spec_dependency_cache
= XRESIZEVEC (bitmap_head
, spec_dependency_cache
,
3678 for (i
= cache_size
; i
< luid
; i
++)
3680 bitmap_initialize (&true_dependency_cache
[i
], 0);
3681 bitmap_initialize (&output_dependency_cache
[i
], 0);
3682 bitmap_initialize (&anti_dependency_cache
[i
], 0);
3684 if (current_sched_info
->flags
& DO_SPECULATION
)
3685 bitmap_initialize (&spec_dependency_cache
[i
], 0);
3691 /* Finalize dependency information for the whole function. */
3693 sched_deps_finish (void)
3695 gcc_assert (deps_pools_are_empty_p ());
3696 free_alloc_pool_if_empty (&dn_pool
);
3697 free_alloc_pool_if_empty (&dl_pool
);
3698 gcc_assert (dn_pool
== NULL
&& dl_pool
== NULL
);
3700 VEC_free (haifa_deps_insn_data_def
, heap
, h_d_i_d
);
3703 if (true_dependency_cache
)
3707 for (i
= 0; i
< cache_size
; i
++)
3709 bitmap_clear (&true_dependency_cache
[i
]);
3710 bitmap_clear (&output_dependency_cache
[i
]);
3711 bitmap_clear (&anti_dependency_cache
[i
]);
3713 if (sched_deps_info
->generate_spec_deps
)
3714 bitmap_clear (&spec_dependency_cache
[i
]);
3716 free (true_dependency_cache
);
3717 true_dependency_cache
= NULL
;
3718 free (output_dependency_cache
);
3719 output_dependency_cache
= NULL
;
3720 free (anti_dependency_cache
);
3721 anti_dependency_cache
= NULL
;
3723 if (sched_deps_info
->generate_spec_deps
)
3725 free (spec_dependency_cache
);
3726 spec_dependency_cache
= NULL
;
3732 /* Initialize some global variables needed by the dependency analysis
3736 init_deps_global (void)
3738 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers
);
3739 CLEAR_HARD_REG_SET (implicit_reg_pending_uses
);
3740 reg_pending_sets
= ALLOC_REG_SET (®_obstack
);
3741 reg_pending_clobbers
= ALLOC_REG_SET (®_obstack
);
3742 reg_pending_uses
= ALLOC_REG_SET (®_obstack
);
3743 reg_pending_barrier
= NOT_A_BARRIER
;
3745 if (!sel_sched_p () || sched_emulate_haifa_p
)
3747 sched_deps_info
->start_insn
= haifa_start_insn
;
3748 sched_deps_info
->finish_insn
= haifa_finish_insn
;
3750 sched_deps_info
->note_reg_set
= haifa_note_reg_set
;
3751 sched_deps_info
->note_reg_clobber
= haifa_note_reg_clobber
;
3752 sched_deps_info
->note_reg_use
= haifa_note_reg_use
;
3754 sched_deps_info
->note_mem_dep
= haifa_note_mem_dep
;
3755 sched_deps_info
->note_dep
= haifa_note_dep
;
3759 /* Free everything used by the dependency analysis code. */
3762 finish_deps_global (void)
3764 FREE_REG_SET (reg_pending_sets
);
3765 FREE_REG_SET (reg_pending_clobbers
);
3766 FREE_REG_SET (reg_pending_uses
);
3769 /* Estimate the weakness of dependence between MEM1 and MEM2. */
3771 estimate_dep_weak (rtx mem1
, rtx mem2
)
3776 /* MEMs are the same - don't speculate. */
3777 return MIN_DEP_WEAK
;
3779 r1
= XEXP (mem1
, 0);
3780 r2
= XEXP (mem2
, 0);
3783 || (REG_P (r1
) && REG_P (r2
)
3784 && REGNO (r1
) == REGNO (r2
)))
3785 /* Again, MEMs are the same. */
3786 return MIN_DEP_WEAK
;
3787 else if ((REG_P (r1
) && !REG_P (r2
))
3788 || (!REG_P (r1
) && REG_P (r2
)))
3789 /* Different addressing modes - reason to be more speculative,
3791 return NO_DEP_WEAK
- (NO_DEP_WEAK
- UNCERTAIN_DEP_WEAK
) / 2;
3793 /* We can't say anything about the dependence. */
3794 return UNCERTAIN_DEP_WEAK
;
3797 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3798 This function can handle same INSN and ELEM (INSN == ELEM).
3799 It is a convenience wrapper. */
3801 add_dependence (rtx insn
, rtx elem
, enum reg_note dep_type
)
3806 if (dep_type
== REG_DEP_TRUE
)
3808 else if (dep_type
== REG_DEP_OUTPUT
)
3812 gcc_assert (dep_type
== REG_DEP_ANTI
);
3816 /* When add_dependence is called from inside sched-deps.c, we expect
3817 cur_insn to be non-null. */
3818 internal
= cur_insn
!= NULL
;
3820 gcc_assert (insn
== cur_insn
);
3824 note_dep (elem
, ds
);
3829 /* Return weakness of speculative type TYPE in the dep_status DS. */
3831 get_dep_weak_1 (ds_t ds
, ds_t type
)
3837 case BEGIN_DATA
: ds
>>= BEGIN_DATA_BITS_OFFSET
; break;
3838 case BE_IN_DATA
: ds
>>= BE_IN_DATA_BITS_OFFSET
; break;
3839 case BEGIN_CONTROL
: ds
>>= BEGIN_CONTROL_BITS_OFFSET
; break;
3840 case BE_IN_CONTROL
: ds
>>= BE_IN_CONTROL_BITS_OFFSET
; break;
3841 default: gcc_unreachable ();
3848 get_dep_weak (ds_t ds
, ds_t type
)
3850 dw_t dw
= get_dep_weak_1 (ds
, type
);
3852 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3856 /* Return the dep_status, which has the same parameters as DS, except for
3857 speculative type TYPE, that will have weakness DW. */
3859 set_dep_weak (ds_t ds
, ds_t type
, dw_t dw
)
3861 gcc_assert (MIN_DEP_WEAK
<= dw
&& dw
<= MAX_DEP_WEAK
);
3866 case BEGIN_DATA
: ds
|= ((ds_t
) dw
) << BEGIN_DATA_BITS_OFFSET
; break;
3867 case BE_IN_DATA
: ds
|= ((ds_t
) dw
) << BE_IN_DATA_BITS_OFFSET
; break;
3868 case BEGIN_CONTROL
: ds
|= ((ds_t
) dw
) << BEGIN_CONTROL_BITS_OFFSET
; break;
3869 case BE_IN_CONTROL
: ds
|= ((ds_t
) dw
) << BE_IN_CONTROL_BITS_OFFSET
; break;
3870 default: gcc_unreachable ();
3875 /* Return the join of two dep_statuses DS1 and DS2.
3876 If MAX_P is true then choose the greater probability,
3877 otherwise multiply probabilities.
3878 This function assumes that both DS1 and DS2 contain speculative bits. */
3880 ds_merge_1 (ds_t ds1
, ds_t ds2
, bool max_p
)
3884 gcc_assert ((ds1
& SPECULATIVE
) && (ds2
& SPECULATIVE
));
3886 ds
= (ds1
& DEP_TYPES
) | (ds2
& DEP_TYPES
);
3888 t
= FIRST_SPEC_TYPE
;
3891 if ((ds1
& t
) && !(ds2
& t
))
3893 else if (!(ds1
& t
) && (ds2
& t
))
3895 else if ((ds1
& t
) && (ds2
& t
))
3897 dw_t dw1
= get_dep_weak (ds1
, t
);
3898 dw_t dw2
= get_dep_weak (ds2
, t
);
3903 dw
= ((ds_t
) dw1
) * ((ds_t
) dw2
);
3905 if (dw
< MIN_DEP_WEAK
)
3916 ds
= set_dep_weak (ds
, t
, (dw_t
) dw
);
3919 if (t
== LAST_SPEC_TYPE
)
3921 t
<<= SPEC_TYPE_SHIFT
;
3928 /* Return the join of two dep_statuses DS1 and DS2.
3929 This function assumes that both DS1 and DS2 contain speculative bits. */
3931 ds_merge (ds_t ds1
, ds_t ds2
)
3933 return ds_merge_1 (ds1
, ds2
, false);
3936 /* Return the join of two dep_statuses DS1 and DS2. */
3938 ds_full_merge (ds_t ds
, ds_t ds2
, rtx mem1
, rtx mem2
)
3940 ds_t new_status
= ds
| ds2
;
3942 if (new_status
& SPECULATIVE
)
3944 if ((ds
&& !(ds
& SPECULATIVE
))
3945 || (ds2
&& !(ds2
& SPECULATIVE
)))
3946 /* Then this dep can't be speculative. */
3947 new_status
&= ~SPECULATIVE
;
3950 /* Both are speculative. Merging probabilities. */
3955 dw
= estimate_dep_weak (mem1
, mem2
);
3956 ds
= set_dep_weak (ds
, BEGIN_DATA
, dw
);
3964 new_status
= ds_merge (ds2
, ds
);
3971 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
3974 ds_max_merge (ds_t ds1
, ds_t ds2
)
3976 if (ds1
== 0 && ds2
== 0)
3979 if (ds1
== 0 && ds2
!= 0)
3982 if (ds1
!= 0 && ds2
== 0)
3985 return ds_merge_1 (ds1
, ds2
, true);
3988 /* Return the probability of speculation success for the speculation
3996 dt
= FIRST_SPEC_TYPE
;
4001 res
*= (ds_t
) get_dep_weak (ds
, dt
);
4005 if (dt
== LAST_SPEC_TYPE
)
4007 dt
<<= SPEC_TYPE_SHIFT
;
4013 res
/= MAX_DEP_WEAK
;
4015 if (res
< MIN_DEP_WEAK
)
4018 gcc_assert (res
<= MAX_DEP_WEAK
);
4023 /* Return a dep status that contains all speculation types of DS. */
4025 ds_get_speculation_types (ds_t ds
)
4027 if (ds
& BEGIN_DATA
)
4029 if (ds
& BE_IN_DATA
)
4031 if (ds
& BEGIN_CONTROL
)
4032 ds
|= BEGIN_CONTROL
;
4033 if (ds
& BE_IN_CONTROL
)
4034 ds
|= BE_IN_CONTROL
;
4036 return ds
& SPECULATIVE
;
4039 /* Return a dep status that contains maximal weakness for each speculation
4040 type present in DS. */
4042 ds_get_max_dep_weak (ds_t ds
)
4044 if (ds
& BEGIN_DATA
)
4045 ds
= set_dep_weak (ds
, BEGIN_DATA
, MAX_DEP_WEAK
);
4046 if (ds
& BE_IN_DATA
)
4047 ds
= set_dep_weak (ds
, BE_IN_DATA
, MAX_DEP_WEAK
);
4048 if (ds
& BEGIN_CONTROL
)
4049 ds
= set_dep_weak (ds
, BEGIN_CONTROL
, MAX_DEP_WEAK
);
4050 if (ds
& BE_IN_CONTROL
)
4051 ds
= set_dep_weak (ds
, BE_IN_CONTROL
, MAX_DEP_WEAK
);
4056 /* Dump information about the dependence status S. */
4058 dump_ds (FILE *f
, ds_t s
)
4063 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak_1 (s
, BEGIN_DATA
));
4065 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak_1 (s
, BE_IN_DATA
));
4066 if (s
& BEGIN_CONTROL
)
4067 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s
, BEGIN_CONTROL
));
4068 if (s
& BE_IN_CONTROL
)
4069 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s
, BE_IN_CONTROL
));
4072 fprintf (f
, "HARD_DEP; ");
4075 fprintf (f
, "DEP_TRUE; ");
4077 fprintf (f
, "DEP_ANTI; ");
4079 fprintf (f
, "DEP_OUTPUT; ");
4087 dump_ds (stderr
, s
);
4088 fprintf (stderr
, "\n");
4091 #ifdef ENABLE_CHECKING
4092 /* Verify that dependence type and status are consistent.
4093 If RELAXED_P is true, then skip dep_weakness checks. */
4095 check_dep (dep_t dep
, bool relaxed_p
)
4097 enum reg_note dt
= DEP_TYPE (dep
);
4098 ds_t ds
= DEP_STATUS (dep
);
4100 gcc_assert (DEP_PRO (dep
) != DEP_CON (dep
));
4102 if (!(current_sched_info
->flags
& USE_DEPS_LIST
))
4104 gcc_assert (ds
== -1);
4108 /* Check that dependence type contains the same bits as the status. */
4109 if (dt
== REG_DEP_TRUE
)
4110 gcc_assert (ds
& DEP_TRUE
);
4111 else if (dt
== REG_DEP_OUTPUT
)
4112 gcc_assert ((ds
& DEP_OUTPUT
)
4113 && !(ds
& DEP_TRUE
));
4115 gcc_assert ((dt
== REG_DEP_ANTI
)
4117 && !(ds
& (DEP_OUTPUT
| DEP_TRUE
)));
4119 /* HARD_DEP can not appear in dep_status of a link. */
4120 gcc_assert (!(ds
& HARD_DEP
));
4122 /* Check that dependence status is set correctly when speculation is not
4124 if (!sched_deps_info
->generate_spec_deps
)
4125 gcc_assert (!(ds
& SPECULATIVE
));
4126 else if (ds
& SPECULATIVE
)
4130 ds_t type
= FIRST_SPEC_TYPE
;
4132 /* Check that dependence weakness is in proper range. */
4136 get_dep_weak (ds
, type
);
4138 if (type
== LAST_SPEC_TYPE
)
4140 type
<<= SPEC_TYPE_SHIFT
;
4145 if (ds
& BEGIN_SPEC
)
4147 /* Only true dependence can be data speculative. */
4148 if (ds
& BEGIN_DATA
)
4149 gcc_assert (ds
& DEP_TRUE
);
4151 /* Control dependencies in the insn scheduler are represented by
4152 anti-dependencies, therefore only anti dependence can be
4153 control speculative. */
4154 if (ds
& BEGIN_CONTROL
)
4155 gcc_assert (ds
& DEP_ANTI
);
4159 /* Subsequent speculations should resolve true dependencies. */
4160 gcc_assert ((ds
& DEP_TYPES
) == DEP_TRUE
);
4163 /* Check that true and anti dependencies can't have other speculative
4166 gcc_assert (ds
& (BEGIN_DATA
| BE_IN_SPEC
));
4167 /* An output dependence can't be speculative at all. */
4168 gcc_assert (!(ds
& DEP_OUTPUT
));
4170 gcc_assert (ds
& BEGIN_CONTROL
);
4173 #endif /* ENABLE_CHECKING */
4175 #endif /* INSN_SCHEDULING */