Daily bump.
[official-gcc.git] / gcc / sched-deps.c
blobee534b02ef8ab8c1e4818c799359522d68001298
1 /* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992-2014 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "diagnostic-core.h"
28 #include "rtl.h"
29 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "regs.h"
33 #include "hashtab.h"
34 #include "hash-set.h"
35 #include "vec.h"
36 #include "machmode.h"
37 #include "input.h"
38 #include "function.h"
39 #include "flags.h"
40 #include "insn-config.h"
41 #include "insn-attr.h"
42 #include "except.h"
43 #include "recog.h"
44 #include "emit-rtl.h"
45 #include "dominance.h"
46 #include "cfg.h"
47 #include "cfgbuild.h"
48 #include "predict.h"
49 #include "basic-block.h"
50 #include "sched-int.h"
51 #include "params.h"
52 #include "cselib.h"
53 #include "ira.h"
54 #include "target.h"
56 #ifdef INSN_SCHEDULING
58 #ifdef ENABLE_CHECKING
59 #define CHECK (true)
60 #else
61 #define CHECK (false)
62 #endif
64 /* Holds current parameters for the dependency analyzer. */
65 struct sched_deps_info_def *sched_deps_info;
67 /* The data is specific to the Haifa scheduler. */
68 vec<haifa_deps_insn_data_def>
69 h_d_i_d = vNULL;
71 /* Return the major type present in the DS. */
72 enum reg_note
73 ds_to_dk (ds_t ds)
75 if (ds & DEP_TRUE)
76 return REG_DEP_TRUE;
78 if (ds & DEP_OUTPUT)
79 return REG_DEP_OUTPUT;
81 if (ds & DEP_CONTROL)
82 return REG_DEP_CONTROL;
84 gcc_assert (ds & DEP_ANTI);
86 return REG_DEP_ANTI;
89 /* Return equivalent dep_status. */
90 ds_t
91 dk_to_ds (enum reg_note dk)
93 switch (dk)
95 case REG_DEP_TRUE:
96 return DEP_TRUE;
98 case REG_DEP_OUTPUT:
99 return DEP_OUTPUT;
101 case REG_DEP_CONTROL:
102 return DEP_CONTROL;
104 default:
105 gcc_assert (dk == REG_DEP_ANTI);
106 return DEP_ANTI;
110 /* Functions to operate with dependence information container - dep_t. */
112 /* Init DEP with the arguments. */
113 void
114 init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
116 DEP_PRO (dep) = pro;
117 DEP_CON (dep) = con;
118 DEP_TYPE (dep) = type;
119 DEP_STATUS (dep) = ds;
120 DEP_COST (dep) = UNKNOWN_DEP_COST;
121 DEP_NONREG (dep) = 0;
122 DEP_MULTIPLE (dep) = 0;
123 DEP_REPLACE (dep) = NULL;
126 /* Init DEP with the arguments.
127 While most of the scheduler (including targets) only need the major type
128 of the dependency, it is convenient to hide full dep_status from them. */
129 void
130 init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
132 ds_t ds;
134 if ((current_sched_info->flags & USE_DEPS_LIST))
135 ds = dk_to_ds (kind);
136 else
137 ds = 0;
139 init_dep_1 (dep, pro, con, kind, ds);
142 /* Make a copy of FROM in TO. */
143 static void
144 copy_dep (dep_t to, dep_t from)
146 memcpy (to, from, sizeof (*to));
149 static void dump_ds (FILE *, ds_t);
151 /* Define flags for dump_dep (). */
153 /* Dump producer of the dependence. */
154 #define DUMP_DEP_PRO (2)
156 /* Dump consumer of the dependence. */
157 #define DUMP_DEP_CON (4)
159 /* Dump type of the dependence. */
160 #define DUMP_DEP_TYPE (8)
162 /* Dump status of the dependence. */
163 #define DUMP_DEP_STATUS (16)
165 /* Dump all information about the dependence. */
166 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
167 |DUMP_DEP_STATUS)
169 /* Dump DEP to DUMP.
170 FLAGS is a bit mask specifying what information about DEP needs
171 to be printed.
172 If FLAGS has the very first bit set, then dump all information about DEP
173 and propagate this bit into the callee dump functions. */
174 static void
175 dump_dep (FILE *dump, dep_t dep, int flags)
177 if (flags & 1)
178 flags |= DUMP_DEP_ALL;
180 fprintf (dump, "<");
182 if (flags & DUMP_DEP_PRO)
183 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
185 if (flags & DUMP_DEP_CON)
186 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
188 if (flags & DUMP_DEP_TYPE)
190 char t;
191 enum reg_note type = DEP_TYPE (dep);
193 switch (type)
195 case REG_DEP_TRUE:
196 t = 't';
197 break;
199 case REG_DEP_OUTPUT:
200 t = 'o';
201 break;
203 case REG_DEP_CONTROL:
204 t = 'c';
205 break;
207 case REG_DEP_ANTI:
208 t = 'a';
209 break;
211 default:
212 gcc_unreachable ();
213 break;
216 fprintf (dump, "%c; ", t);
219 if (flags & DUMP_DEP_STATUS)
221 if (current_sched_info->flags & USE_DEPS_LIST)
222 dump_ds (dump, DEP_STATUS (dep));
225 fprintf (dump, ">");
228 /* Default flags for dump_dep (). */
229 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
231 /* Dump all fields of DEP to STDERR. */
232 void
233 sd_debug_dep (dep_t dep)
235 dump_dep (stderr, dep, 1);
236 fprintf (stderr, "\n");
239 /* Determine whether DEP is a dependency link of a non-debug insn on a
240 debug insn. */
242 static inline bool
243 depl_on_debug_p (dep_link_t dep)
245 return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
246 && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
249 /* Functions to operate with a single link from the dependencies lists -
250 dep_link_t. */
252 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
253 PREV_NEXT_P. */
254 static void
255 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
257 dep_link_t next = *prev_nextp;
259 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
260 && DEP_LINK_NEXT (l) == NULL);
262 /* Init node being inserted. */
263 DEP_LINK_PREV_NEXTP (l) = prev_nextp;
264 DEP_LINK_NEXT (l) = next;
266 /* Fix next node. */
267 if (next != NULL)
269 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
271 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
274 /* Fix prev node. */
275 *prev_nextp = l;
278 /* Add dep_link LINK to deps_list L. */
279 static void
280 add_to_deps_list (dep_link_t link, deps_list_t l)
282 attach_dep_link (link, &DEPS_LIST_FIRST (l));
284 /* Don't count debug deps. */
285 if (!depl_on_debug_p (link))
286 ++DEPS_LIST_N_LINKS (l);
289 /* Detach dep_link L from the list. */
290 static void
291 detach_dep_link (dep_link_t l)
293 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
294 dep_link_t next = DEP_LINK_NEXT (l);
296 *prev_nextp = next;
298 if (next != NULL)
299 DEP_LINK_PREV_NEXTP (next) = prev_nextp;
301 DEP_LINK_PREV_NEXTP (l) = NULL;
302 DEP_LINK_NEXT (l) = NULL;
305 /* Remove link LINK from list LIST. */
306 static void
307 remove_from_deps_list (dep_link_t link, deps_list_t list)
309 detach_dep_link (link);
311 /* Don't count debug deps. */
312 if (!depl_on_debug_p (link))
313 --DEPS_LIST_N_LINKS (list);
316 /* Move link LINK from list FROM to list TO. */
317 static void
318 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
320 remove_from_deps_list (link, from);
321 add_to_deps_list (link, to);
324 /* Return true of LINK is not attached to any list. */
325 static bool
326 dep_link_is_detached_p (dep_link_t link)
328 return DEP_LINK_PREV_NEXTP (link) == NULL;
331 /* Pool to hold all dependency nodes (dep_node_t). */
332 static alloc_pool dn_pool;
334 /* Number of dep_nodes out there. */
335 static int dn_pool_diff = 0;
337 /* Create a dep_node. */
338 static dep_node_t
339 create_dep_node (void)
341 dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
342 dep_link_t back = DEP_NODE_BACK (n);
343 dep_link_t forw = DEP_NODE_FORW (n);
345 DEP_LINK_NODE (back) = n;
346 DEP_LINK_NEXT (back) = NULL;
347 DEP_LINK_PREV_NEXTP (back) = NULL;
349 DEP_LINK_NODE (forw) = n;
350 DEP_LINK_NEXT (forw) = NULL;
351 DEP_LINK_PREV_NEXTP (forw) = NULL;
353 ++dn_pool_diff;
355 return n;
358 /* Delete dep_node N. N must not be connected to any deps_list. */
359 static void
360 delete_dep_node (dep_node_t n)
362 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
363 && dep_link_is_detached_p (DEP_NODE_FORW (n)));
365 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
367 --dn_pool_diff;
369 pool_free (dn_pool, n);
372 /* Pool to hold dependencies lists (deps_list_t). */
373 static alloc_pool dl_pool;
375 /* Number of deps_lists out there. */
376 static int dl_pool_diff = 0;
378 /* Functions to operate with dependences lists - deps_list_t. */
380 /* Return true if list L is empty. */
381 static bool
382 deps_list_empty_p (deps_list_t l)
384 return DEPS_LIST_N_LINKS (l) == 0;
387 /* Create a new deps_list. */
388 static deps_list_t
389 create_deps_list (void)
391 deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
393 DEPS_LIST_FIRST (l) = NULL;
394 DEPS_LIST_N_LINKS (l) = 0;
396 ++dl_pool_diff;
397 return l;
400 /* Free deps_list L. */
401 static void
402 free_deps_list (deps_list_t l)
404 gcc_assert (deps_list_empty_p (l));
406 --dl_pool_diff;
408 pool_free (dl_pool, l);
411 /* Return true if there is no dep_nodes and deps_lists out there.
412 After the region is scheduled all the dependency nodes and lists
413 should [generally] be returned to pool. */
414 bool
415 deps_pools_are_empty_p (void)
417 return dn_pool_diff == 0 && dl_pool_diff == 0;
420 /* Remove all elements from L. */
421 static void
422 clear_deps_list (deps_list_t l)
426 dep_link_t link = DEPS_LIST_FIRST (l);
428 if (link == NULL)
429 break;
431 remove_from_deps_list (link, l);
433 while (1);
436 /* Decide whether a dependency should be treated as a hard or a speculative
437 dependency. */
438 static bool
439 dep_spec_p (dep_t dep)
441 if (current_sched_info->flags & DO_SPECULATION)
443 if (DEP_STATUS (dep) & SPECULATIVE)
444 return true;
446 if (current_sched_info->flags & DO_PREDICATION)
448 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
449 return true;
451 if (DEP_REPLACE (dep) != NULL)
452 return true;
453 return false;
456 static regset reg_pending_sets;
457 static regset reg_pending_clobbers;
458 static regset reg_pending_uses;
459 static regset reg_pending_control_uses;
460 static enum reg_pending_barrier_mode reg_pending_barrier;
462 /* Hard registers implicitly clobbered or used (or may be implicitly
463 clobbered or used) by the currently analyzed insn. For example,
464 insn in its constraint has one register class. Even if there is
465 currently no hard register in the insn, the particular hard
466 register will be in the insn after reload pass because the
467 constraint requires it. */
468 static HARD_REG_SET implicit_reg_pending_clobbers;
469 static HARD_REG_SET implicit_reg_pending_uses;
471 /* To speed up the test for duplicate dependency links we keep a
472 record of dependencies created by add_dependence when the average
473 number of instructions in a basic block is very large.
475 Studies have shown that there is typically around 5 instructions between
476 branches for typical C code. So we can make a guess that the average
477 basic block is approximately 5 instructions long; we will choose 100X
478 the average size as a very large basic block.
480 Each insn has associated bitmaps for its dependencies. Each bitmap
481 has enough entries to represent a dependency on any other insn in
482 the insn chain. All bitmap for true dependencies cache is
483 allocated then the rest two ones are also allocated. */
484 static bitmap_head *true_dependency_cache = NULL;
485 static bitmap_head *output_dependency_cache = NULL;
486 static bitmap_head *anti_dependency_cache = NULL;
487 static bitmap_head *control_dependency_cache = NULL;
488 static bitmap_head *spec_dependency_cache = NULL;
489 static int cache_size;
491 /* True if we should mark added dependencies as a non-register deps. */
492 static bool mark_as_hard;
494 static int deps_may_trap_p (const_rtx);
495 static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note);
496 static void add_dependence_list (rtx_insn *, rtx_insn_list *, int,
497 enum reg_note, bool);
498 static void add_dependence_list_and_free (struct deps_desc *, rtx_insn *,
499 rtx_insn_list **, int, enum reg_note,
500 bool);
501 static void delete_all_dependences (rtx);
502 static void chain_to_prev_insn (rtx_insn *);
504 static void flush_pending_lists (struct deps_desc *, rtx_insn *, int, int);
505 static void sched_analyze_1 (struct deps_desc *, rtx, rtx_insn *);
506 static void sched_analyze_2 (struct deps_desc *, rtx, rtx_insn *);
507 static void sched_analyze_insn (struct deps_desc *, rtx, rtx_insn *);
509 static bool sched_has_condition_p (const rtx_insn *);
510 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
512 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
513 rtx, rtx);
514 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
516 #ifdef ENABLE_CHECKING
517 static void check_dep (dep_t, bool);
518 #endif
520 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
522 static int
523 deps_may_trap_p (const_rtx mem)
525 const_rtx addr = XEXP (mem, 0);
527 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
529 const_rtx t = get_reg_known_value (REGNO (addr));
530 if (t)
531 addr = t;
533 return rtx_addr_can_trap_p (addr);
537 /* Find the condition under which INSN is executed. If REV is not NULL,
538 it is set to TRUE when the returned comparison should be reversed
539 to get the actual condition. */
540 static rtx
541 sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
543 rtx pat = PATTERN (insn);
544 rtx src;
546 if (rev)
547 *rev = false;
549 if (GET_CODE (pat) == COND_EXEC)
550 return COND_EXEC_TEST (pat);
552 if (!any_condjump_p (insn) || !onlyjump_p (insn))
553 return 0;
555 src = SET_SRC (pc_set (insn));
557 if (XEXP (src, 2) == pc_rtx)
558 return XEXP (src, 0);
559 else if (XEXP (src, 1) == pc_rtx)
561 rtx cond = XEXP (src, 0);
562 enum rtx_code revcode = reversed_comparison_code (cond, insn);
564 if (revcode == UNKNOWN)
565 return 0;
567 if (rev)
568 *rev = true;
569 return cond;
572 return 0;
575 /* Return the condition under which INSN does not execute (i.e. the
576 not-taken condition for a conditional branch), or NULL if we cannot
577 find such a condition. The caller should make a copy of the condition
578 before using it. */
580 sched_get_reverse_condition_uncached (const rtx_insn *insn)
582 bool rev;
583 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
584 if (cond == NULL_RTX)
585 return cond;
586 if (!rev)
588 enum rtx_code revcode = reversed_comparison_code (cond, insn);
589 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
590 XEXP (cond, 0),
591 XEXP (cond, 1));
593 return cond;
596 /* Caching variant of sched_get_condition_with_rev_uncached.
597 We only do actual work the first time we come here for an insn; the
598 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
599 static rtx
600 sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
602 bool tmp;
604 if (INSN_LUID (insn) == 0)
605 return sched_get_condition_with_rev_uncached (insn, rev);
607 if (INSN_CACHED_COND (insn) == const_true_rtx)
608 return NULL_RTX;
610 if (INSN_CACHED_COND (insn) != NULL_RTX)
612 if (rev)
613 *rev = INSN_REVERSE_COND (insn);
614 return INSN_CACHED_COND (insn);
617 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
618 INSN_REVERSE_COND (insn) = tmp;
620 if (INSN_CACHED_COND (insn) == NULL_RTX)
622 INSN_CACHED_COND (insn) = const_true_rtx;
623 return NULL_RTX;
626 if (rev)
627 *rev = INSN_REVERSE_COND (insn);
628 return INSN_CACHED_COND (insn);
631 /* True when we can find a condition under which INSN is executed. */
632 static bool
633 sched_has_condition_p (const rtx_insn *insn)
635 return !! sched_get_condition_with_rev (insn, NULL);
640 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
641 static int
642 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
644 if (COMPARISON_P (cond1)
645 && COMPARISON_P (cond2)
646 && GET_CODE (cond1) ==
647 (rev1==rev2
648 ? reversed_comparison_code (cond2, NULL)
649 : GET_CODE (cond2))
650 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
651 && XEXP (cond1, 1) == XEXP (cond2, 1))
652 return 1;
653 return 0;
656 /* Return true if insn1 and insn2 can never depend on one another because
657 the conditions under which they are executed are mutually exclusive. */
658 bool
659 sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
661 rtx cond1, cond2;
662 bool rev1 = false, rev2 = false;
664 /* df doesn't handle conditional lifetimes entirely correctly;
665 calls mess up the conditional lifetimes. */
666 if (!CALL_P (insn1) && !CALL_P (insn2))
668 cond1 = sched_get_condition_with_rev (insn1, &rev1);
669 cond2 = sched_get_condition_with_rev (insn2, &rev2);
670 if (cond1 && cond2
671 && conditions_mutex_p (cond1, cond2, rev1, rev2)
672 /* Make sure first instruction doesn't affect condition of second
673 instruction if switched. */
674 && !modified_in_p (cond1, insn2)
675 /* Make sure second instruction doesn't affect condition of first
676 instruction if switched. */
677 && !modified_in_p (cond2, insn1))
678 return true;
680 return false;
684 /* Return true if INSN can potentially be speculated with type DS. */
685 bool
686 sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
688 if (HAS_INTERNAL_DEP (insn))
689 return false;
691 if (!NONJUMP_INSN_P (insn))
692 return false;
694 if (SCHED_GROUP_P (insn))
695 return false;
697 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn)))
698 return false;
700 if (side_effects_p (PATTERN (insn)))
701 return false;
703 if (ds & BE_IN_SPEC)
704 /* The following instructions, which depend on a speculatively scheduled
705 instruction, cannot be speculatively scheduled along. */
707 if (may_trap_or_fault_p (PATTERN (insn)))
708 /* If instruction might fault, it cannot be speculatively scheduled.
709 For control speculation it's obvious why and for data speculation
710 it's because the insn might get wrong input if speculation
711 wasn't successful. */
712 return false;
714 if ((ds & BE_IN_DATA)
715 && sched_has_condition_p (insn))
716 /* If this is a predicated instruction, then it cannot be
717 speculatively scheduled. See PR35659. */
718 return false;
721 return true;
724 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
725 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
726 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
727 This function is used to switch sd_iterator to the next list.
728 !!! For internal use only. Might consider moving it to sched-int.h. */
729 void
730 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
731 deps_list_t *list_ptr, bool *resolved_p_ptr)
733 sd_list_types_def types = *types_ptr;
735 if (types & SD_LIST_HARD_BACK)
737 *list_ptr = INSN_HARD_BACK_DEPS (insn);
738 *resolved_p_ptr = false;
739 *types_ptr = types & ~SD_LIST_HARD_BACK;
741 else if (types & SD_LIST_SPEC_BACK)
743 *list_ptr = INSN_SPEC_BACK_DEPS (insn);
744 *resolved_p_ptr = false;
745 *types_ptr = types & ~SD_LIST_SPEC_BACK;
747 else if (types & SD_LIST_FORW)
749 *list_ptr = INSN_FORW_DEPS (insn);
750 *resolved_p_ptr = false;
751 *types_ptr = types & ~SD_LIST_FORW;
753 else if (types & SD_LIST_RES_BACK)
755 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
756 *resolved_p_ptr = true;
757 *types_ptr = types & ~SD_LIST_RES_BACK;
759 else if (types & SD_LIST_RES_FORW)
761 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
762 *resolved_p_ptr = true;
763 *types_ptr = types & ~SD_LIST_RES_FORW;
765 else
767 *list_ptr = NULL;
768 *resolved_p_ptr = false;
769 *types_ptr = SD_LIST_NONE;
773 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
775 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
777 int size = 0;
779 while (list_types != SD_LIST_NONE)
781 deps_list_t list;
782 bool resolved_p;
784 sd_next_list (insn, &list_types, &list, &resolved_p);
785 if (list)
786 size += DEPS_LIST_N_LINKS (list);
789 return size;
792 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
794 bool
795 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
797 while (list_types != SD_LIST_NONE)
799 deps_list_t list;
800 bool resolved_p;
802 sd_next_list (insn, &list_types, &list, &resolved_p);
803 if (!deps_list_empty_p (list))
804 return false;
807 return true;
810 /* Initialize data for INSN. */
811 void
812 sd_init_insn (rtx insn)
814 INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
815 INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
816 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
817 INSN_FORW_DEPS (insn) = create_deps_list ();
818 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
820 /* ??? It would be nice to allocate dependency caches here. */
823 /* Free data for INSN. */
824 void
825 sd_finish_insn (rtx insn)
827 /* ??? It would be nice to deallocate dependency caches here. */
829 free_deps_list (INSN_HARD_BACK_DEPS (insn));
830 INSN_HARD_BACK_DEPS (insn) = NULL;
832 free_deps_list (INSN_SPEC_BACK_DEPS (insn));
833 INSN_SPEC_BACK_DEPS (insn) = NULL;
835 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
836 INSN_RESOLVED_BACK_DEPS (insn) = NULL;
838 free_deps_list (INSN_FORW_DEPS (insn));
839 INSN_FORW_DEPS (insn) = NULL;
841 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
842 INSN_RESOLVED_FORW_DEPS (insn) = NULL;
845 /* Find a dependency between producer PRO and consumer CON.
846 Search through resolved dependency lists if RESOLVED_P is true.
847 If no such dependency is found return NULL,
848 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
849 with an iterator pointing to it. */
850 static dep_t
851 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
852 sd_iterator_def *sd_it_ptr)
854 sd_list_types_def pro_list_type;
855 sd_list_types_def con_list_type;
856 sd_iterator_def sd_it;
857 dep_t dep;
858 bool found_p = false;
860 if (resolved_p)
862 pro_list_type = SD_LIST_RES_FORW;
863 con_list_type = SD_LIST_RES_BACK;
865 else
867 pro_list_type = SD_LIST_FORW;
868 con_list_type = SD_LIST_BACK;
871 /* Walk through either back list of INSN or forw list of ELEM
872 depending on which one is shorter. */
873 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
875 /* Find the dep_link with producer PRO in consumer's back_deps. */
876 FOR_EACH_DEP (con, con_list_type, sd_it, dep)
877 if (DEP_PRO (dep) == pro)
879 found_p = true;
880 break;
883 else
885 /* Find the dep_link with consumer CON in producer's forw_deps. */
886 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
887 if (DEP_CON (dep) == con)
889 found_p = true;
890 break;
894 if (found_p)
896 if (sd_it_ptr != NULL)
897 *sd_it_ptr = sd_it;
899 return dep;
902 return NULL;
905 /* Find a dependency between producer PRO and consumer CON.
906 Use dependency [if available] to check if dependency is present at all.
907 Search through resolved dependency lists if RESOLVED_P is true.
908 If the dependency or NULL if none found. */
909 dep_t
910 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
912 if (true_dependency_cache != NULL)
913 /* Avoiding the list walk below can cut compile times dramatically
914 for some code. */
916 int elem_luid = INSN_LUID (pro);
917 int insn_luid = INSN_LUID (con);
919 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
920 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
921 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
922 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
923 return NULL;
926 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
929 /* Add or update a dependence described by DEP.
930 MEM1 and MEM2, if non-null, correspond to memory locations in case of
931 data speculation.
933 The function returns a value indicating if an old entry has been changed
934 or a new entry has been added to insn's backward deps.
936 This function merely checks if producer and consumer is the same insn
937 and doesn't create a dep in this case. Actual manipulation of
938 dependence data structures is performed in add_or_update_dep_1. */
939 static enum DEPS_ADJUST_RESULT
940 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
942 rtx_insn *elem = DEP_PRO (dep);
943 rtx_insn *insn = DEP_CON (dep);
945 gcc_assert (INSN_P (insn) && INSN_P (elem));
947 /* Don't depend an insn on itself. */
948 if (insn == elem)
950 if (sched_deps_info->generate_spec_deps)
951 /* INSN has an internal dependence, which we can't overcome. */
952 HAS_INTERNAL_DEP (insn) = 1;
954 return DEP_NODEP;
957 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
960 /* Ask dependency caches what needs to be done for dependence DEP.
961 Return DEP_CREATED if new dependence should be created and there is no
962 need to try to find one searching the dependencies lists.
963 Return DEP_PRESENT if there already is a dependence described by DEP and
964 hence nothing is to be done.
965 Return DEP_CHANGED if there already is a dependence, but it should be
966 updated to incorporate additional information from DEP. */
967 static enum DEPS_ADJUST_RESULT
968 ask_dependency_caches (dep_t dep)
970 int elem_luid = INSN_LUID (DEP_PRO (dep));
971 int insn_luid = INSN_LUID (DEP_CON (dep));
973 gcc_assert (true_dependency_cache != NULL
974 && output_dependency_cache != NULL
975 && anti_dependency_cache != NULL
976 && control_dependency_cache != NULL);
978 if (!(current_sched_info->flags & USE_DEPS_LIST))
980 enum reg_note present_dep_type;
982 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
983 present_dep_type = REG_DEP_TRUE;
984 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
985 present_dep_type = REG_DEP_OUTPUT;
986 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
987 present_dep_type = REG_DEP_ANTI;
988 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
989 present_dep_type = REG_DEP_CONTROL;
990 else
991 /* There is no existing dep so it should be created. */
992 return DEP_CREATED;
994 if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
995 /* DEP does not add anything to the existing dependence. */
996 return DEP_PRESENT;
998 else
1000 ds_t present_dep_types = 0;
1002 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
1003 present_dep_types |= DEP_TRUE;
1004 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
1005 present_dep_types |= DEP_OUTPUT;
1006 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
1007 present_dep_types |= DEP_ANTI;
1008 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
1009 present_dep_types |= DEP_CONTROL;
1011 if (present_dep_types == 0)
1012 /* There is no existing dep so it should be created. */
1013 return DEP_CREATED;
1015 if (!(current_sched_info->flags & DO_SPECULATION)
1016 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
1018 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
1019 == present_dep_types)
1020 /* DEP does not add anything to the existing dependence. */
1021 return DEP_PRESENT;
1023 else
1025 /* Only true dependencies can be data speculative and
1026 only anti dependencies can be control speculative. */
1027 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1028 == present_dep_types);
1030 /* if (DEP is SPECULATIVE) then
1031 ..we should update DEP_STATUS
1032 else
1033 ..we should reset existing dep to non-speculative. */
1037 return DEP_CHANGED;
1040 /* Set dependency caches according to DEP. */
1041 static void
1042 set_dependency_caches (dep_t dep)
1044 int elem_luid = INSN_LUID (DEP_PRO (dep));
1045 int insn_luid = INSN_LUID (DEP_CON (dep));
1047 if (!(current_sched_info->flags & USE_DEPS_LIST))
1049 switch (DEP_TYPE (dep))
1051 case REG_DEP_TRUE:
1052 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1053 break;
1055 case REG_DEP_OUTPUT:
1056 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1057 break;
1059 case REG_DEP_ANTI:
1060 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1061 break;
1063 case REG_DEP_CONTROL:
1064 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1065 break;
1067 default:
1068 gcc_unreachable ();
1071 else
1073 ds_t ds = DEP_STATUS (dep);
1075 if (ds & DEP_TRUE)
1076 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1077 if (ds & DEP_OUTPUT)
1078 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1079 if (ds & DEP_ANTI)
1080 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1081 if (ds & DEP_CONTROL)
1082 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1084 if (ds & SPECULATIVE)
1086 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1087 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1092 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1093 caches accordingly. */
1094 static void
1095 update_dependency_caches (dep_t dep, enum reg_note old_type)
1097 int elem_luid = INSN_LUID (DEP_PRO (dep));
1098 int insn_luid = INSN_LUID (DEP_CON (dep));
1100 /* Clear corresponding cache entry because type of the link
1101 may have changed. Keep them if we use_deps_list. */
1102 if (!(current_sched_info->flags & USE_DEPS_LIST))
1104 switch (old_type)
1106 case REG_DEP_OUTPUT:
1107 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1108 break;
1110 case REG_DEP_ANTI:
1111 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1112 break;
1114 case REG_DEP_CONTROL:
1115 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1116 break;
1118 default:
1119 gcc_unreachable ();
1123 set_dependency_caches (dep);
1126 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1127 static void
1128 change_spec_dep_to_hard (sd_iterator_def sd_it)
1130 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1131 dep_link_t link = DEP_NODE_BACK (node);
1132 dep_t dep = DEP_NODE_DEP (node);
1133 rtx_insn *elem = DEP_PRO (dep);
1134 rtx_insn *insn = DEP_CON (dep);
1136 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1138 DEP_STATUS (dep) &= ~SPECULATIVE;
1140 if (true_dependency_cache != NULL)
1141 /* Clear the cache entry. */
1142 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1143 INSN_LUID (elem));
1146 /* Update DEP to incorporate information from NEW_DEP.
1147 SD_IT points to DEP in case it should be moved to another list.
1148 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1149 data-speculative dependence should be updated. */
1150 static enum DEPS_ADJUST_RESULT
1151 update_dep (dep_t dep, dep_t new_dep,
1152 sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1153 rtx mem1 ATTRIBUTE_UNUSED,
1154 rtx mem2 ATTRIBUTE_UNUSED)
1156 enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1157 enum reg_note old_type = DEP_TYPE (dep);
1158 bool was_spec = dep_spec_p (dep);
1160 DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1161 DEP_MULTIPLE (dep) = 1;
1163 /* If this is a more restrictive type of dependence than the
1164 existing one, then change the existing dependence to this
1165 type. */
1166 if ((int) DEP_TYPE (new_dep) < (int) old_type)
1168 DEP_TYPE (dep) = DEP_TYPE (new_dep);
1169 res = DEP_CHANGED;
1172 if (current_sched_info->flags & USE_DEPS_LIST)
1173 /* Update DEP_STATUS. */
1175 ds_t dep_status = DEP_STATUS (dep);
1176 ds_t ds = DEP_STATUS (new_dep);
1177 ds_t new_status = ds | dep_status;
1179 if (new_status & SPECULATIVE)
1181 /* Either existing dep or a dep we're adding or both are
1182 speculative. */
1183 if (!(ds & SPECULATIVE)
1184 || !(dep_status & SPECULATIVE))
1185 /* The new dep can't be speculative. */
1186 new_status &= ~SPECULATIVE;
1187 else
1189 /* Both are speculative. Merge probabilities. */
1190 if (mem1 != NULL)
1192 dw_t dw;
1194 dw = estimate_dep_weak (mem1, mem2);
1195 ds = set_dep_weak (ds, BEGIN_DATA, dw);
1198 new_status = ds_merge (dep_status, ds);
1202 ds = new_status;
1204 if (dep_status != ds)
1206 DEP_STATUS (dep) = ds;
1207 res = DEP_CHANGED;
1211 if (was_spec && !dep_spec_p (dep))
1212 /* The old dep was speculative, but now it isn't. */
1213 change_spec_dep_to_hard (sd_it);
1215 if (true_dependency_cache != NULL
1216 && res == DEP_CHANGED)
1217 update_dependency_caches (dep, old_type);
1219 return res;
1222 /* Add or update a dependence described by DEP.
1223 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1224 data speculation.
1226 The function returns a value indicating if an old entry has been changed
1227 or a new entry has been added to insn's backward deps or nothing has
1228 been updated at all. */
1229 static enum DEPS_ADJUST_RESULT
1230 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1231 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1233 bool maybe_present_p = true;
1234 bool present_p = false;
1236 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1237 && DEP_PRO (new_dep) != DEP_CON (new_dep));
1239 #ifdef ENABLE_CHECKING
1240 check_dep (new_dep, mem1 != NULL);
1241 #endif
1243 if (true_dependency_cache != NULL)
1245 switch (ask_dependency_caches (new_dep))
1247 case DEP_PRESENT:
1248 dep_t present_dep;
1249 sd_iterator_def sd_it;
1251 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1252 DEP_CON (new_dep),
1253 resolved_p, &sd_it);
1254 DEP_MULTIPLE (present_dep) = 1;
1255 return DEP_PRESENT;
1257 case DEP_CHANGED:
1258 maybe_present_p = true;
1259 present_p = true;
1260 break;
1262 case DEP_CREATED:
1263 maybe_present_p = false;
1264 present_p = false;
1265 break;
1267 default:
1268 gcc_unreachable ();
1269 break;
1273 /* Check that we don't already have this dependence. */
1274 if (maybe_present_p)
1276 dep_t present_dep;
1277 sd_iterator_def sd_it;
1279 gcc_assert (true_dependency_cache == NULL || present_p);
1281 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1282 DEP_CON (new_dep),
1283 resolved_p, &sd_it);
1285 if (present_dep != NULL)
1286 /* We found an existing dependency between ELEM and INSN. */
1287 return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1288 else
1289 /* We didn't find a dep, it shouldn't present in the cache. */
1290 gcc_assert (!present_p);
1293 /* Might want to check one level of transitivity to save conses.
1294 This check should be done in maybe_add_or_update_dep_1.
1295 Since we made it to add_or_update_dep_1, we must create
1296 (or update) a link. */
1298 if (mem1 != NULL_RTX)
1300 gcc_assert (sched_deps_info->generate_spec_deps);
1301 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1302 estimate_dep_weak (mem1, mem2));
1305 sd_add_dep (new_dep, resolved_p);
1307 return DEP_CREATED;
1310 /* Initialize BACK_LIST_PTR with consumer's backward list and
1311 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1312 initialize with lists that hold resolved deps. */
1313 static void
1314 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1315 deps_list_t *back_list_ptr,
1316 deps_list_t *forw_list_ptr)
1318 rtx_insn *con = DEP_CON (dep);
1320 if (!resolved_p)
1322 if (dep_spec_p (dep))
1323 *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1324 else
1325 *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1327 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1329 else
1331 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1332 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1336 /* Add dependence described by DEP.
1337 If RESOLVED_P is true treat the dependence as a resolved one. */
1338 void
1339 sd_add_dep (dep_t dep, bool resolved_p)
1341 dep_node_t n = create_dep_node ();
1342 deps_list_t con_back_deps;
1343 deps_list_t pro_forw_deps;
1344 rtx_insn *elem = DEP_PRO (dep);
1345 rtx_insn *insn = DEP_CON (dep);
1347 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1349 if ((current_sched_info->flags & DO_SPECULATION) == 0
1350 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1351 DEP_STATUS (dep) &= ~SPECULATIVE;
1353 copy_dep (DEP_NODE_DEP (n), dep);
1355 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1357 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1359 #ifdef ENABLE_CHECKING
1360 check_dep (dep, false);
1361 #endif
1363 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1365 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1366 in the bitmap caches of dependency information. */
1367 if (true_dependency_cache != NULL)
1368 set_dependency_caches (dep);
1371 /* Add or update backward dependence between INSN and ELEM
1372 with given type DEP_TYPE and dep_status DS.
1373 This function is a convenience wrapper. */
1374 enum DEPS_ADJUST_RESULT
1375 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1377 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1380 /* Resolved dependence pointed to by SD_IT.
1381 SD_IT will advance to the next element. */
1382 void
1383 sd_resolve_dep (sd_iterator_def sd_it)
1385 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1386 dep_t dep = DEP_NODE_DEP (node);
1387 rtx_insn *pro = DEP_PRO (dep);
1388 rtx_insn *con = DEP_CON (dep);
1390 if (dep_spec_p (dep))
1391 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1392 INSN_RESOLVED_BACK_DEPS (con));
1393 else
1394 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1395 INSN_RESOLVED_BACK_DEPS (con));
1397 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1398 INSN_RESOLVED_FORW_DEPS (pro));
1401 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1402 pointed to by SD_IT to unresolved state. */
1403 void
1404 sd_unresolve_dep (sd_iterator_def sd_it)
1406 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1407 dep_t dep = DEP_NODE_DEP (node);
1408 rtx_insn *pro = DEP_PRO (dep);
1409 rtx_insn *con = DEP_CON (dep);
1411 if (dep_spec_p (dep))
1412 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1413 INSN_SPEC_BACK_DEPS (con));
1414 else
1415 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1416 INSN_HARD_BACK_DEPS (con));
1418 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1419 INSN_FORW_DEPS (pro));
1422 /* Make TO depend on all the FROM's producers.
1423 If RESOLVED_P is true add dependencies to the resolved lists. */
1424 void
1425 sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p)
1427 sd_list_types_def list_type;
1428 sd_iterator_def sd_it;
1429 dep_t dep;
1431 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1433 FOR_EACH_DEP (from, list_type, sd_it, dep)
1435 dep_def _new_dep, *new_dep = &_new_dep;
1437 copy_dep (new_dep, dep);
1438 DEP_CON (new_dep) = to;
1439 sd_add_dep (new_dep, resolved_p);
1443 /* Remove a dependency referred to by SD_IT.
1444 SD_IT will point to the next dependence after removal. */
1445 void
1446 sd_delete_dep (sd_iterator_def sd_it)
1448 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1449 dep_t dep = DEP_NODE_DEP (n);
1450 rtx_insn *pro = DEP_PRO (dep);
1451 rtx_insn *con = DEP_CON (dep);
1452 deps_list_t con_back_deps;
1453 deps_list_t pro_forw_deps;
1455 if (true_dependency_cache != NULL)
1457 int elem_luid = INSN_LUID (pro);
1458 int insn_luid = INSN_LUID (con);
1460 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1461 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1462 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1463 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1465 if (current_sched_info->flags & DO_SPECULATION)
1466 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1469 get_back_and_forw_lists (dep, sd_it.resolved_p,
1470 &con_back_deps, &pro_forw_deps);
1472 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1473 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1475 delete_dep_node (n);
1478 /* Dump size of the lists. */
1479 #define DUMP_LISTS_SIZE (2)
1481 /* Dump dependencies of the lists. */
1482 #define DUMP_LISTS_DEPS (4)
1484 /* Dump all information about the lists. */
1485 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1487 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1488 FLAGS is a bit mask specifying what information about the lists needs
1489 to be printed.
1490 If FLAGS has the very first bit set, then dump all information about
1491 the lists and propagate this bit into the callee dump functions. */
1492 static void
1493 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1495 sd_iterator_def sd_it;
1496 dep_t dep;
1497 int all;
1499 all = (flags & 1);
1501 if (all)
1502 flags |= DUMP_LISTS_ALL;
1504 fprintf (dump, "[");
1506 if (flags & DUMP_LISTS_SIZE)
1507 fprintf (dump, "%d; ", sd_lists_size (insn, types));
1509 if (flags & DUMP_LISTS_DEPS)
1511 FOR_EACH_DEP (insn, types, sd_it, dep)
1513 dump_dep (dump, dep, dump_dep_flags | all);
1514 fprintf (dump, " ");
1519 /* Dump all information about deps_lists of INSN specified by TYPES
1520 to STDERR. */
1521 void
1522 sd_debug_lists (rtx insn, sd_list_types_def types)
1524 dump_lists (stderr, insn, types, 1);
1525 fprintf (stderr, "\n");
1528 /* A wrapper around add_dependence_1, to add a dependence of CON on
1529 PRO, with type DEP_TYPE. This function implements special handling
1530 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1531 the type to REG_DEP_ANTI if we can determine that predication is
1532 impossible; otherwise we add additional true dependencies on the
1533 INSN_COND_DEPS list of the jump (which PRO must be). */
1534 void
1535 add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1537 if (dep_type == REG_DEP_CONTROL
1538 && !(current_sched_info->flags & DO_PREDICATION))
1539 dep_type = REG_DEP_ANTI;
1541 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1542 so we must also make the insn dependent on the setter of the
1543 condition. */
1544 if (dep_type == REG_DEP_CONTROL)
1546 rtx_insn *real_pro = pro;
1547 rtx_insn *other = real_insn_for_shadow (real_pro);
1548 rtx cond;
1550 if (other != NULL_RTX)
1551 real_pro = other;
1552 cond = sched_get_reverse_condition_uncached (real_pro);
1553 /* Verify that the insn does not use a different value in
1554 the condition register than the one that was present at
1555 the jump. */
1556 if (cond == NULL_RTX)
1557 dep_type = REG_DEP_ANTI;
1558 else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1560 HARD_REG_SET uses;
1561 CLEAR_HARD_REG_SET (uses);
1562 note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1563 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1564 dep_type = REG_DEP_ANTI;
1566 if (dep_type == REG_DEP_CONTROL)
1568 if (sched_verbose >= 5)
1569 fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1570 INSN_UID (real_pro));
1571 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1572 REG_DEP_TRUE, false);
1576 add_dependence_1 (con, pro, dep_type);
1579 /* A convenience wrapper to operate on an entire list. HARD should be
1580 true if DEP_NONREG should be set on newly created dependencies. */
1582 static void
1583 add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1584 enum reg_note dep_type, bool hard)
1586 mark_as_hard = hard;
1587 for (; list; list = list->next ())
1589 if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1590 add_dependence (insn, list->insn (), dep_type);
1592 mark_as_hard = false;
1595 /* Similar, but free *LISTP at the same time, when the context
1596 is not readonly. HARD should be true if DEP_NONREG should be set on
1597 newly created dependencies. */
1599 static void
1600 add_dependence_list_and_free (struct deps_desc *deps, rtx_insn *insn,
1601 rtx_insn_list **listp,
1602 int uncond, enum reg_note dep_type, bool hard)
1604 add_dependence_list (insn, *listp, uncond, dep_type, hard);
1606 /* We don't want to short-circuit dependencies involving debug
1607 insns, because they may cause actual dependencies to be
1608 disregarded. */
1609 if (deps->readonly || DEBUG_INSN_P (insn))
1610 return;
1612 free_INSN_LIST_list (listp);
1615 /* Remove all occurrences of INSN from LIST. Return the number of
1616 occurrences removed. */
1618 static int
1619 remove_from_dependence_list (rtx insn, rtx_insn_list **listp)
1621 int removed = 0;
1623 while (*listp)
1625 if ((*listp)->insn () == insn)
1627 remove_free_INSN_LIST_node (listp);
1628 removed++;
1629 continue;
1632 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1635 return removed;
1638 /* Same as above, but process two lists at once. */
1639 static int
1640 remove_from_both_dependence_lists (rtx insn,
1641 rtx_insn_list **listp,
1642 rtx_expr_list **exprp)
1644 int removed = 0;
1646 while (*listp)
1648 if (XEXP (*listp, 0) == insn)
1650 remove_free_INSN_LIST_node (listp);
1651 remove_free_EXPR_LIST_node (exprp);
1652 removed++;
1653 continue;
1656 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1657 exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1660 return removed;
1663 /* Clear all dependencies for an insn. */
1664 static void
1665 delete_all_dependences (rtx insn)
1667 sd_iterator_def sd_it;
1668 dep_t dep;
1670 /* The below cycle can be optimized to clear the caches and back_deps
1671 in one call but that would provoke duplication of code from
1672 delete_dep (). */
1674 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1675 sd_iterator_cond (&sd_it, &dep);)
1676 sd_delete_dep (sd_it);
1679 /* All insns in a scheduling group except the first should only have
1680 dependencies on the previous insn in the group. So we find the
1681 first instruction in the scheduling group by walking the dependence
1682 chains backwards. Then we add the dependencies for the group to
1683 the previous nonnote insn. */
1685 static void
1686 chain_to_prev_insn (rtx_insn *insn)
1688 sd_iterator_def sd_it;
1689 dep_t dep;
1690 rtx_insn *prev_nonnote;
1692 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1694 rtx_insn *i = insn;
1695 rtx_insn *pro = DEP_PRO (dep);
1699 i = prev_nonnote_insn (i);
1701 if (pro == i)
1702 goto next_link;
1703 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1705 if (! sched_insns_conditions_mutex_p (i, pro))
1706 add_dependence (i, pro, DEP_TYPE (dep));
1707 next_link:;
1710 delete_all_dependences (insn);
1712 prev_nonnote = prev_nonnote_nondebug_insn (insn);
1713 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1714 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1715 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1718 /* Process an insn's memory dependencies. There are four kinds of
1719 dependencies:
1721 (0) read dependence: read follows read
1722 (1) true dependence: read follows write
1723 (2) output dependence: write follows write
1724 (3) anti dependence: write follows read
1726 We are careful to build only dependencies which actually exist, and
1727 use transitivity to avoid building too many links. */
1729 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1730 The MEM is a memory reference contained within INSN, which we are saving
1731 so that we can do memory aliasing on it. */
1733 static void
1734 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1735 rtx_insn *insn, rtx mem)
1737 rtx_insn_list **insn_list;
1738 rtx_insn_list *insn_node;
1739 rtx_expr_list **mem_list;
1740 rtx_expr_list *mem_node;
1742 gcc_assert (!deps->readonly);
1743 if (read_p)
1745 insn_list = &deps->pending_read_insns;
1746 mem_list = &deps->pending_read_mems;
1747 if (!DEBUG_INSN_P (insn))
1748 deps->pending_read_list_length++;
1750 else
1752 insn_list = &deps->pending_write_insns;
1753 mem_list = &deps->pending_write_mems;
1754 deps->pending_write_list_length++;
1757 insn_node = alloc_INSN_LIST (insn, *insn_list);
1758 *insn_list = insn_node;
1760 if (sched_deps_info->use_cselib)
1762 mem = shallow_copy_rtx (mem);
1763 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1764 GET_MODE (mem), insn);
1766 mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1767 *mem_list = mem_node;
1770 /* Make a dependency between every memory reference on the pending lists
1771 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1772 dependencies for a read operation, similarly with FOR_WRITE. */
1774 static void
1775 flush_pending_lists (struct deps_desc *deps, rtx_insn *insn, int for_read,
1776 int for_write)
1778 if (for_write)
1780 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1781 1, REG_DEP_ANTI, true);
1782 if (!deps->readonly)
1784 free_EXPR_LIST_list (&deps->pending_read_mems);
1785 deps->pending_read_list_length = 0;
1789 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1790 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1791 true);
1793 add_dependence_list_and_free (deps, insn,
1794 &deps->last_pending_memory_flush, 1,
1795 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1796 true);
1798 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1799 REG_DEP_ANTI, true);
1801 if (DEBUG_INSN_P (insn))
1803 if (for_write)
1804 free_INSN_LIST_list (&deps->pending_read_insns);
1805 free_INSN_LIST_list (&deps->pending_write_insns);
1806 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1807 free_INSN_LIST_list (&deps->pending_jump_insns);
1810 if (!deps->readonly)
1812 free_EXPR_LIST_list (&deps->pending_write_mems);
1813 deps->pending_write_list_length = 0;
1815 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1816 deps->pending_flush_length = 1;
1818 mark_as_hard = false;
1821 /* Instruction which dependencies we are analyzing. */
1822 static rtx_insn *cur_insn = NULL;
1824 /* Implement hooks for haifa scheduler. */
1826 static void
1827 haifa_start_insn (rtx_insn *insn)
1829 gcc_assert (insn && !cur_insn);
1831 cur_insn = insn;
1834 static void
1835 haifa_finish_insn (void)
1837 cur_insn = NULL;
1840 void
1841 haifa_note_reg_set (int regno)
1843 SET_REGNO_REG_SET (reg_pending_sets, regno);
1846 void
1847 haifa_note_reg_clobber (int regno)
1849 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1852 void
1853 haifa_note_reg_use (int regno)
1855 SET_REGNO_REG_SET (reg_pending_uses, regno);
1858 static void
1859 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1861 if (!(ds & SPECULATIVE))
1863 mem = NULL_RTX;
1864 pending_mem = NULL_RTX;
1866 else
1867 gcc_assert (ds & BEGIN_DATA);
1870 dep_def _dep, *dep = &_dep;
1872 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1873 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1874 DEP_NONREG (dep) = 1;
1875 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1880 static void
1881 haifa_note_dep (rtx_insn *elem, ds_t ds)
1883 dep_def _dep;
1884 dep_t dep = &_dep;
1886 init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1887 if (mark_as_hard)
1888 DEP_NONREG (dep) = 1;
1889 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1892 static void
1893 note_reg_use (int r)
1895 if (sched_deps_info->note_reg_use)
1896 sched_deps_info->note_reg_use (r);
1899 static void
1900 note_reg_set (int r)
1902 if (sched_deps_info->note_reg_set)
1903 sched_deps_info->note_reg_set (r);
1906 static void
1907 note_reg_clobber (int r)
1909 if (sched_deps_info->note_reg_clobber)
1910 sched_deps_info->note_reg_clobber (r);
1913 static void
1914 note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1916 if (sched_deps_info->note_mem_dep)
1917 sched_deps_info->note_mem_dep (m1, m2, e, ds);
1920 static void
1921 note_dep (rtx_insn *e, ds_t ds)
1923 if (sched_deps_info->note_dep)
1924 sched_deps_info->note_dep (e, ds);
1927 /* Return corresponding to DS reg_note. */
1928 enum reg_note
1929 ds_to_dt (ds_t ds)
1931 if (ds & DEP_TRUE)
1932 return REG_DEP_TRUE;
1933 else if (ds & DEP_OUTPUT)
1934 return REG_DEP_OUTPUT;
1935 else if (ds & DEP_ANTI)
1936 return REG_DEP_ANTI;
1937 else
1939 gcc_assert (ds & DEP_CONTROL);
1940 return REG_DEP_CONTROL;
1946 /* Functions for computation of info needed for register pressure
1947 sensitive insn scheduling. */
1950 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1951 static struct reg_use_data *
1952 create_insn_reg_use (int regno, rtx_insn *insn)
1954 struct reg_use_data *use;
1956 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1957 use->regno = regno;
1958 use->insn = insn;
1959 use->next_insn_use = INSN_REG_USE_LIST (insn);
1960 INSN_REG_USE_LIST (insn) = use;
1961 return use;
1964 /* Allocate reg_set_data structure for REGNO and INSN. */
1965 static void
1966 create_insn_reg_set (int regno, rtx insn)
1968 struct reg_set_data *set;
1970 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1971 set->regno = regno;
1972 set->insn = insn;
1973 set->next_insn_set = INSN_REG_SET_LIST (insn);
1974 INSN_REG_SET_LIST (insn) = set;
1977 /* Set up insn register uses for INSN and dependency context DEPS. */
1978 static void
1979 setup_insn_reg_uses (struct deps_desc *deps, rtx_insn *insn)
1981 unsigned i;
1982 reg_set_iterator rsi;
1983 struct reg_use_data *use, *use2, *next;
1984 struct deps_reg *reg_last;
1986 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1988 if (i < FIRST_PSEUDO_REGISTER
1989 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1990 continue;
1992 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1993 && ! REGNO_REG_SET_P (reg_pending_sets, i)
1994 && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1995 /* Ignore use which is not dying. */
1996 continue;
1998 use = create_insn_reg_use (i, insn);
1999 use->next_regno_use = use;
2000 reg_last = &deps->reg_last[i];
2002 /* Create the cycle list of uses. */
2003 for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
2005 use2 = create_insn_reg_use (i, list->insn ());
2006 next = use->next_regno_use;
2007 use->next_regno_use = use2;
2008 use2->next_regno_use = next;
2013 /* Register pressure info for the currently processed insn. */
2014 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
2016 /* Return TRUE if INSN has the use structure for REGNO. */
2017 static bool
2018 insn_use_p (rtx insn, int regno)
2020 struct reg_use_data *use;
2022 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2023 if (use->regno == regno)
2024 return true;
2025 return false;
2028 /* Update the register pressure info after birth of pseudo register REGNO
2029 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2030 the register is in clobber or unused after the insn. */
2031 static void
2032 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2034 int incr, new_incr;
2035 enum reg_class cl;
2037 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2038 cl = sched_regno_pressure_class[regno];
2039 if (cl != NO_REGS)
2041 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2042 if (clobber_p)
2044 new_incr = reg_pressure_info[cl].clobber_increase + incr;
2045 reg_pressure_info[cl].clobber_increase = new_incr;
2047 else if (unused_p)
2049 new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2050 reg_pressure_info[cl].unused_set_increase = new_incr;
2052 else
2054 new_incr = reg_pressure_info[cl].set_increase + incr;
2055 reg_pressure_info[cl].set_increase = new_incr;
2056 if (! insn_use_p (insn, regno))
2057 reg_pressure_info[cl].change += incr;
2058 create_insn_reg_set (regno, insn);
2060 gcc_assert (new_incr < (1 << INCREASE_BITS));
2064 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2065 hard registers involved in the birth. */
2066 static void
2067 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2068 bool clobber_p, bool unused_p)
2070 enum reg_class cl;
2071 int new_incr, last = regno + nregs;
2073 while (regno < last)
2075 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2076 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2078 cl = sched_regno_pressure_class[regno];
2079 if (cl != NO_REGS)
2081 if (clobber_p)
2083 new_incr = reg_pressure_info[cl].clobber_increase + 1;
2084 reg_pressure_info[cl].clobber_increase = new_incr;
2086 else if (unused_p)
2088 new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2089 reg_pressure_info[cl].unused_set_increase = new_incr;
2091 else
2093 new_incr = reg_pressure_info[cl].set_increase + 1;
2094 reg_pressure_info[cl].set_increase = new_incr;
2095 if (! insn_use_p (insn, regno))
2096 reg_pressure_info[cl].change += 1;
2097 create_insn_reg_set (regno, insn);
2099 gcc_assert (new_incr < (1 << INCREASE_BITS));
2102 regno++;
2106 /* Update the register pressure info after birth of pseudo or hard
2107 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2108 correspondingly that the register is in clobber or unused after the
2109 insn. */
2110 static void
2111 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2113 int regno;
2115 if (GET_CODE (reg) == SUBREG)
2116 reg = SUBREG_REG (reg);
2118 if (! REG_P (reg))
2119 return;
2121 regno = REGNO (reg);
2122 if (regno < FIRST_PSEUDO_REGISTER)
2123 mark_insn_hard_regno_birth (insn, regno,
2124 hard_regno_nregs[regno][GET_MODE (reg)],
2125 clobber_p, unused_p);
2126 else
2127 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2130 /* Update the register pressure info after death of pseudo register
2131 REGNO. */
2132 static void
2133 mark_pseudo_death (int regno)
2135 int incr;
2136 enum reg_class cl;
2138 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2139 cl = sched_regno_pressure_class[regno];
2140 if (cl != NO_REGS)
2142 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2143 reg_pressure_info[cl].change -= incr;
2147 /* Like mark_pseudo_death except that NREGS saying how many hard
2148 registers involved in the death. */
2149 static void
2150 mark_hard_regno_death (int regno, int nregs)
2152 enum reg_class cl;
2153 int last = regno + nregs;
2155 while (regno < last)
2157 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2158 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2160 cl = sched_regno_pressure_class[regno];
2161 if (cl != NO_REGS)
2162 reg_pressure_info[cl].change -= 1;
2164 regno++;
2168 /* Update the register pressure info after death of pseudo or hard
2169 register REG. */
2170 static void
2171 mark_reg_death (rtx reg)
2173 int regno;
2175 if (GET_CODE (reg) == SUBREG)
2176 reg = SUBREG_REG (reg);
2178 if (! REG_P (reg))
2179 return;
2181 regno = REGNO (reg);
2182 if (regno < FIRST_PSEUDO_REGISTER)
2183 mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
2184 else
2185 mark_pseudo_death (regno);
2188 /* Process SETTER of REG. DATA is an insn containing the setter. */
2189 static void
2190 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2192 if (setter != NULL_RTX && GET_CODE (setter) != SET)
2193 return;
2194 mark_insn_reg_birth
2195 ((rtx) data, reg, false,
2196 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2199 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2200 static void
2201 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2203 if (GET_CODE (setter) == CLOBBER)
2204 mark_insn_reg_birth ((rtx) data, reg, true, false);
2207 /* Set up reg pressure info related to INSN. */
2208 void
2209 init_insn_reg_pressure_info (rtx insn)
2211 int i, len;
2212 enum reg_class cl;
2213 static struct reg_pressure_data *pressure_info;
2214 rtx link;
2216 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2218 if (! INSN_P (insn))
2219 return;
2221 for (i = 0; i < ira_pressure_classes_num; i++)
2223 cl = ira_pressure_classes[i];
2224 reg_pressure_info[cl].clobber_increase = 0;
2225 reg_pressure_info[cl].set_increase = 0;
2226 reg_pressure_info[cl].unused_set_increase = 0;
2227 reg_pressure_info[cl].change = 0;
2230 note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2232 note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2234 #ifdef AUTO_INC_DEC
2235 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2236 if (REG_NOTE_KIND (link) == REG_INC)
2237 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2238 #endif
2240 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2241 if (REG_NOTE_KIND (link) == REG_DEAD)
2242 mark_reg_death (XEXP (link, 0));
2244 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2245 pressure_info
2246 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2247 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2248 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2249 * sizeof (int), 1);
2250 for (i = 0; i < ira_pressure_classes_num; i++)
2252 cl = ira_pressure_classes[i];
2253 pressure_info[i].clobber_increase
2254 = reg_pressure_info[cl].clobber_increase;
2255 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2256 pressure_info[i].unused_set_increase
2257 = reg_pressure_info[cl].unused_set_increase;
2258 pressure_info[i].change = reg_pressure_info[cl].change;
2265 /* Internal variable for sched_analyze_[12] () functions.
2266 If it is nonzero, this means that sched_analyze_[12] looks
2267 at the most toplevel SET. */
2268 static bool can_start_lhs_rhs_p;
2270 /* Extend reg info for the deps context DEPS given that
2271 we have just generated a register numbered REGNO. */
2272 static void
2273 extend_deps_reg_info (struct deps_desc *deps, int regno)
2275 int max_regno = regno + 1;
2277 gcc_assert (!reload_completed);
2279 /* In a readonly context, it would not hurt to extend info,
2280 but it should not be needed. */
2281 if (reload_completed && deps->readonly)
2283 deps->max_reg = max_regno;
2284 return;
2287 if (max_regno > deps->max_reg)
2289 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2290 max_regno);
2291 memset (&deps->reg_last[deps->max_reg],
2292 0, (max_regno - deps->max_reg)
2293 * sizeof (struct deps_reg));
2294 deps->max_reg = max_regno;
2298 /* Extends REG_INFO_P if needed. */
2299 void
2300 maybe_extend_reg_info_p (void)
2302 /* Extend REG_INFO_P, if needed. */
2303 if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2305 size_t new_reg_info_p_size = max_regno + 128;
2307 gcc_assert (!reload_completed && sel_sched_p ());
2309 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2310 new_reg_info_p_size,
2311 reg_info_p_size,
2312 sizeof (*reg_info_p));
2313 reg_info_p_size = new_reg_info_p_size;
2317 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2318 The type of the reference is specified by REF and can be SET,
2319 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2321 static void
2322 sched_analyze_reg (struct deps_desc *deps, int regno, machine_mode mode,
2323 enum rtx_code ref, rtx_insn *insn)
2325 /* We could emit new pseudos in renaming. Extend the reg structures. */
2326 if (!reload_completed && sel_sched_p ()
2327 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2328 extend_deps_reg_info (deps, regno);
2330 maybe_extend_reg_info_p ();
2332 /* A hard reg in a wide mode may really be multiple registers.
2333 If so, mark all of them just like the first. */
2334 if (regno < FIRST_PSEUDO_REGISTER)
2336 int i = hard_regno_nregs[regno][mode];
2337 if (ref == SET)
2339 while (--i >= 0)
2340 note_reg_set (regno + i);
2342 else if (ref == USE)
2344 while (--i >= 0)
2345 note_reg_use (regno + i);
2347 else
2349 while (--i >= 0)
2350 note_reg_clobber (regno + i);
2354 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2355 it does not reload. Ignore these as they have served their
2356 purpose already. */
2357 else if (regno >= deps->max_reg)
2359 enum rtx_code code = GET_CODE (PATTERN (insn));
2360 gcc_assert (code == USE || code == CLOBBER);
2363 else
2365 if (ref == SET)
2366 note_reg_set (regno);
2367 else if (ref == USE)
2368 note_reg_use (regno);
2369 else
2370 note_reg_clobber (regno);
2372 /* Pseudos that are REG_EQUIV to something may be replaced
2373 by that during reloading. We need only add dependencies for
2374 the address in the REG_EQUIV note. */
2375 if (!reload_completed && get_reg_known_equiv_p (regno))
2377 rtx t = get_reg_known_value (regno);
2378 if (MEM_P (t))
2379 sched_analyze_2 (deps, XEXP (t, 0), insn);
2382 /* Don't let it cross a call after scheduling if it doesn't
2383 already cross one. */
2384 if (REG_N_CALLS_CROSSED (regno) == 0)
2386 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2387 deps->sched_before_next_call
2388 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2389 else
2390 add_dependence_list (insn, deps->last_function_call, 1,
2391 REG_DEP_ANTI, false);
2396 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2397 rtx, X, creating all dependencies generated by the write to the
2398 destination of X, and reads of everything mentioned. */
2400 static void
2401 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2403 rtx dest = XEXP (x, 0);
2404 enum rtx_code code = GET_CODE (x);
2405 bool cslr_p = can_start_lhs_rhs_p;
2407 can_start_lhs_rhs_p = false;
2409 gcc_assert (dest);
2410 if (dest == 0)
2411 return;
2413 if (cslr_p && sched_deps_info->start_lhs)
2414 sched_deps_info->start_lhs (dest);
2416 if (GET_CODE (dest) == PARALLEL)
2418 int i;
2420 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2421 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2422 sched_analyze_1 (deps,
2423 gen_rtx_CLOBBER (VOIDmode,
2424 XEXP (XVECEXP (dest, 0, i), 0)),
2425 insn);
2427 if (cslr_p && sched_deps_info->finish_lhs)
2428 sched_deps_info->finish_lhs ();
2430 if (code == SET)
2432 can_start_lhs_rhs_p = cslr_p;
2434 sched_analyze_2 (deps, SET_SRC (x), insn);
2436 can_start_lhs_rhs_p = false;
2439 return;
2442 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2443 || GET_CODE (dest) == ZERO_EXTRACT)
2445 if (GET_CODE (dest) == STRICT_LOW_PART
2446 || GET_CODE (dest) == ZERO_EXTRACT
2447 || df_read_modify_subreg_p (dest))
2449 /* These both read and modify the result. We must handle
2450 them as writes to get proper dependencies for following
2451 instructions. We must handle them as reads to get proper
2452 dependencies from this to previous instructions.
2453 Thus we need to call sched_analyze_2. */
2455 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2457 if (GET_CODE (dest) == ZERO_EXTRACT)
2459 /* The second and third arguments are values read by this insn. */
2460 sched_analyze_2 (deps, XEXP (dest, 1), insn);
2461 sched_analyze_2 (deps, XEXP (dest, 2), insn);
2463 dest = XEXP (dest, 0);
2466 if (REG_P (dest))
2468 int regno = REGNO (dest);
2469 machine_mode mode = GET_MODE (dest);
2471 sched_analyze_reg (deps, regno, mode, code, insn);
2473 #ifdef STACK_REGS
2474 /* Treat all writes to a stack register as modifying the TOS. */
2475 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2477 /* Avoid analyzing the same register twice. */
2478 if (regno != FIRST_STACK_REG)
2479 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2481 add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2482 FIRST_STACK_REG);
2484 #endif
2486 else if (MEM_P (dest))
2488 /* Writing memory. */
2489 rtx t = dest;
2491 if (sched_deps_info->use_cselib)
2493 machine_mode address_mode = get_address_mode (dest);
2495 t = shallow_copy_rtx (dest);
2496 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2497 GET_MODE (t), insn);
2498 XEXP (t, 0)
2499 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2500 insn);
2502 t = canon_rtx (t);
2504 /* Pending lists can't get larger with a readonly context. */
2505 if (!deps->readonly
2506 && ((deps->pending_read_list_length + deps->pending_write_list_length)
2507 >= MAX_PENDING_LIST_LENGTH))
2509 /* Flush all pending reads and writes to prevent the pending lists
2510 from getting any larger. Insn scheduling runs too slowly when
2511 these lists get long. When compiling GCC with itself,
2512 this flush occurs 8 times for sparc, and 10 times for m88k using
2513 the default value of 32. */
2514 flush_pending_lists (deps, insn, false, true);
2516 else
2518 rtx_insn_list *pending;
2519 rtx_expr_list *pending_mem;
2521 pending = deps->pending_read_insns;
2522 pending_mem = deps->pending_read_mems;
2523 while (pending)
2525 if (anti_dependence (pending_mem->element (), t)
2526 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2527 note_mem_dep (t, pending_mem->element (), pending->insn (),
2528 DEP_ANTI);
2530 pending = pending->next ();
2531 pending_mem = pending_mem->next ();
2534 pending = deps->pending_write_insns;
2535 pending_mem = deps->pending_write_mems;
2536 while (pending)
2538 if (output_dependence (pending_mem->element (), t)
2539 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2540 note_mem_dep (t, pending_mem->element (),
2541 pending->insn (),
2542 DEP_OUTPUT);
2544 pending = pending->next ();
2545 pending_mem = pending_mem-> next ();
2548 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2549 REG_DEP_ANTI, true);
2550 add_dependence_list (insn, deps->pending_jump_insns, 1,
2551 REG_DEP_CONTROL, true);
2553 if (!deps->readonly)
2554 add_insn_mem_dependence (deps, false, insn, dest);
2556 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2559 if (cslr_p && sched_deps_info->finish_lhs)
2560 sched_deps_info->finish_lhs ();
2562 /* Analyze reads. */
2563 if (GET_CODE (x) == SET)
2565 can_start_lhs_rhs_p = cslr_p;
2567 sched_analyze_2 (deps, SET_SRC (x), insn);
2569 can_start_lhs_rhs_p = false;
2573 /* Analyze the uses of memory and registers in rtx X in INSN. */
2574 static void
2575 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2577 int i;
2578 int j;
2579 enum rtx_code code;
2580 const char *fmt;
2581 bool cslr_p = can_start_lhs_rhs_p;
2583 can_start_lhs_rhs_p = false;
2585 gcc_assert (x);
2586 if (x == 0)
2587 return;
2589 if (cslr_p && sched_deps_info->start_rhs)
2590 sched_deps_info->start_rhs (x);
2592 code = GET_CODE (x);
2594 switch (code)
2596 CASE_CONST_ANY:
2597 case SYMBOL_REF:
2598 case CONST:
2599 case LABEL_REF:
2600 /* Ignore constants. */
2601 if (cslr_p && sched_deps_info->finish_rhs)
2602 sched_deps_info->finish_rhs ();
2604 return;
2606 #ifdef HAVE_cc0
2607 case CC0:
2608 /* User of CC0 depends on immediately preceding insn. */
2609 SCHED_GROUP_P (insn) = 1;
2610 /* Don't move CC0 setter to another block (it can set up the
2611 same flag for previous CC0 users which is safe). */
2612 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2614 if (cslr_p && sched_deps_info->finish_rhs)
2615 sched_deps_info->finish_rhs ();
2617 return;
2618 #endif
2620 case REG:
2622 int regno = REGNO (x);
2623 machine_mode mode = GET_MODE (x);
2625 sched_analyze_reg (deps, regno, mode, USE, insn);
2627 #ifdef STACK_REGS
2628 /* Treat all reads of a stack register as modifying the TOS. */
2629 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2631 /* Avoid analyzing the same register twice. */
2632 if (regno != FIRST_STACK_REG)
2633 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2634 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2636 #endif
2638 if (cslr_p && sched_deps_info->finish_rhs)
2639 sched_deps_info->finish_rhs ();
2641 return;
2644 case MEM:
2646 /* Reading memory. */
2647 rtx u;
2648 rtx_insn_list *pending;
2649 rtx_expr_list *pending_mem;
2650 rtx t = x;
2652 if (sched_deps_info->use_cselib)
2654 machine_mode address_mode = get_address_mode (t);
2656 t = shallow_copy_rtx (t);
2657 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2658 GET_MODE (t), insn);
2659 XEXP (t, 0)
2660 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2661 insn);
2664 if (!DEBUG_INSN_P (insn))
2666 t = canon_rtx (t);
2667 pending = deps->pending_read_insns;
2668 pending_mem = deps->pending_read_mems;
2669 while (pending)
2671 if (read_dependence (pending_mem->element (), t)
2672 && ! sched_insns_conditions_mutex_p (insn,
2673 pending->insn ()))
2674 note_mem_dep (t, pending_mem->element (),
2675 pending->insn (),
2676 DEP_ANTI);
2678 pending = pending->next ();
2679 pending_mem = pending_mem->next ();
2682 pending = deps->pending_write_insns;
2683 pending_mem = deps->pending_write_mems;
2684 while (pending)
2686 if (true_dependence (pending_mem->element (), VOIDmode, t)
2687 && ! sched_insns_conditions_mutex_p (insn,
2688 pending->insn ()))
2689 note_mem_dep (t, pending_mem->element (),
2690 pending->insn (),
2691 sched_deps_info->generate_spec_deps
2692 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2694 pending = pending->next ();
2695 pending_mem = pending_mem->next ();
2698 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2699 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
2700 REG_DEP_ANTI);
2702 for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2703 if (deps_may_trap_p (x))
2705 if ((sched_deps_info->generate_spec_deps)
2706 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2708 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2709 MAX_DEP_WEAK);
2711 note_dep (as_a <rtx_insn *> (XEXP (u, 0)), ds);
2713 else
2714 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
2715 REG_DEP_CONTROL);
2719 /* Always add these dependencies to pending_reads, since
2720 this insn may be followed by a write. */
2721 if (!deps->readonly)
2723 if ((deps->pending_read_list_length
2724 + deps->pending_write_list_length)
2725 >= MAX_PENDING_LIST_LENGTH
2726 && !DEBUG_INSN_P (insn))
2727 flush_pending_lists (deps, insn, true, true);
2728 add_insn_mem_dependence (deps, true, insn, x);
2731 sched_analyze_2 (deps, XEXP (x, 0), insn);
2733 if (cslr_p && sched_deps_info->finish_rhs)
2734 sched_deps_info->finish_rhs ();
2736 return;
2739 /* Force pending stores to memory in case a trap handler needs them. */
2740 case TRAP_IF:
2741 flush_pending_lists (deps, insn, true, false);
2742 break;
2744 case PREFETCH:
2745 if (PREFETCH_SCHEDULE_BARRIER_P (x))
2746 reg_pending_barrier = TRUE_BARRIER;
2747 /* Prefetch insn contains addresses only. So if the prefetch
2748 address has no registers, there will be no dependencies on
2749 the prefetch insn. This is wrong with result code
2750 correctness point of view as such prefetch can be moved below
2751 a jump insn which usually generates MOVE_BARRIER preventing
2752 to move insns containing registers or memories through the
2753 barrier. It is also wrong with generated code performance
2754 point of view as prefetch withouth dependecies will have a
2755 tendency to be issued later instead of earlier. It is hard
2756 to generate accurate dependencies for prefetch insns as
2757 prefetch has only the start address but it is better to have
2758 something than nothing. */
2759 if (!deps->readonly)
2761 rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2762 if (sched_deps_info->use_cselib)
2763 cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2764 add_insn_mem_dependence (deps, true, insn, x);
2766 break;
2768 case UNSPEC_VOLATILE:
2769 flush_pending_lists (deps, insn, true, true);
2770 /* FALLTHRU */
2772 case ASM_OPERANDS:
2773 case ASM_INPUT:
2775 /* Traditional and volatile asm instructions must be considered to use
2776 and clobber all hard registers, all pseudo-registers and all of
2777 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2779 Consider for instance a volatile asm that changes the fpu rounding
2780 mode. An insn should not be moved across this even if it only uses
2781 pseudo-regs because it might give an incorrectly rounded result. */
2782 if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2783 && !DEBUG_INSN_P (insn))
2784 reg_pending_barrier = TRUE_BARRIER;
2786 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2787 We can not just fall through here since then we would be confused
2788 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2789 traditional asms unlike their normal usage. */
2791 if (code == ASM_OPERANDS)
2793 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2794 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2796 if (cslr_p && sched_deps_info->finish_rhs)
2797 sched_deps_info->finish_rhs ();
2799 return;
2801 break;
2804 case PRE_DEC:
2805 case POST_DEC:
2806 case PRE_INC:
2807 case POST_INC:
2808 /* These both read and modify the result. We must handle them as writes
2809 to get proper dependencies for following instructions. We must handle
2810 them as reads to get proper dependencies from this to previous
2811 instructions. Thus we need to pass them to both sched_analyze_1
2812 and sched_analyze_2. We must call sched_analyze_2 first in order
2813 to get the proper antecedent for the read. */
2814 sched_analyze_2 (deps, XEXP (x, 0), insn);
2815 sched_analyze_1 (deps, x, insn);
2817 if (cslr_p && sched_deps_info->finish_rhs)
2818 sched_deps_info->finish_rhs ();
2820 return;
2822 case POST_MODIFY:
2823 case PRE_MODIFY:
2824 /* op0 = op0 + op1 */
2825 sched_analyze_2 (deps, XEXP (x, 0), insn);
2826 sched_analyze_2 (deps, XEXP (x, 1), insn);
2827 sched_analyze_1 (deps, x, insn);
2829 if (cslr_p && sched_deps_info->finish_rhs)
2830 sched_deps_info->finish_rhs ();
2832 return;
2834 default:
2835 break;
2838 /* Other cases: walk the insn. */
2839 fmt = GET_RTX_FORMAT (code);
2840 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2842 if (fmt[i] == 'e')
2843 sched_analyze_2 (deps, XEXP (x, i), insn);
2844 else if (fmt[i] == 'E')
2845 for (j = 0; j < XVECLEN (x, i); j++)
2846 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2849 if (cslr_p && sched_deps_info->finish_rhs)
2850 sched_deps_info->finish_rhs ();
2853 /* Try to group two fuseable insns together to prevent scheduler
2854 from scheduling them apart. */
2856 static void
2857 sched_macro_fuse_insns (rtx_insn *insn)
2859 rtx_insn *prev;
2861 if (any_condjump_p (insn))
2863 unsigned int condreg1, condreg2;
2864 rtx cc_reg_1;
2865 targetm.fixed_condition_code_regs (&condreg1, &condreg2);
2866 cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2867 prev = prev_nonnote_nondebug_insn (insn);
2868 if (!reg_referenced_p (cc_reg_1, PATTERN (insn))
2869 || !prev
2870 || !modified_in_p (cc_reg_1, prev))
2871 return;
2873 else
2875 rtx insn_set = single_set (insn);
2877 prev = prev_nonnote_nondebug_insn (insn);
2878 if (!prev
2879 || !insn_set
2880 || !single_set (prev))
2881 return;
2885 if (targetm.sched.macro_fusion_pair_p (prev, insn))
2886 SCHED_GROUP_P (insn) = 1;
2890 /* Analyze an INSN with pattern X to find all dependencies. */
2891 static void
2892 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
2894 RTX_CODE code = GET_CODE (x);
2895 rtx link;
2896 unsigned i;
2897 reg_set_iterator rsi;
2899 if (! reload_completed)
2901 HARD_REG_SET temp;
2903 extract_insn (insn);
2904 preprocess_constraints (insn);
2905 ira_implicitly_set_insn_hard_regs (&temp);
2906 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2907 IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2910 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2911 && code == SET);
2913 /* Group compare and branch insns for macro-fusion. */
2914 if (targetm.sched.macro_fusion_p
2915 && targetm.sched.macro_fusion_p ())
2916 sched_macro_fuse_insns (insn);
2918 if (may_trap_p (x))
2919 /* Avoid moving trapping instructions across function calls that might
2920 not always return. */
2921 add_dependence_list (insn, deps->last_function_call_may_noreturn,
2922 1, REG_DEP_ANTI, true);
2924 /* We must avoid creating a situation in which two successors of the
2925 current block have different unwind info after scheduling. If at any
2926 point the two paths re-join this leads to incorrect unwind info. */
2927 /* ??? There are certain situations involving a forced frame pointer in
2928 which, with extra effort, we could fix up the unwind info at a later
2929 CFG join. However, it seems better to notice these cases earlier
2930 during prologue generation and avoid marking the frame pointer setup
2931 as frame-related at all. */
2932 if (RTX_FRAME_RELATED_P (insn))
2934 /* Make sure prologue insn is scheduled before next jump. */
2935 deps->sched_before_next_jump
2936 = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2938 /* Make sure epilogue insn is scheduled after preceding jumps. */
2939 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2940 true);
2943 if (code == COND_EXEC)
2945 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2947 /* ??? Should be recording conditions so we reduce the number of
2948 false dependencies. */
2949 x = COND_EXEC_CODE (x);
2950 code = GET_CODE (x);
2952 if (code == SET || code == CLOBBER)
2954 sched_analyze_1 (deps, x, insn);
2956 /* Bare clobber insns are used for letting life analysis, reg-stack
2957 and others know that a value is dead. Depend on the last call
2958 instruction so that reg-stack won't get confused. */
2959 if (code == CLOBBER)
2960 add_dependence_list (insn, deps->last_function_call, 1,
2961 REG_DEP_OUTPUT, true);
2963 else if (code == PARALLEL)
2965 for (i = XVECLEN (x, 0); i--;)
2967 rtx sub = XVECEXP (x, 0, i);
2968 code = GET_CODE (sub);
2970 if (code == COND_EXEC)
2972 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2973 sub = COND_EXEC_CODE (sub);
2974 code = GET_CODE (sub);
2976 if (code == SET || code == CLOBBER)
2977 sched_analyze_1 (deps, sub, insn);
2978 else
2979 sched_analyze_2 (deps, sub, insn);
2982 else
2983 sched_analyze_2 (deps, x, insn);
2985 /* Mark registers CLOBBERED or used by called function. */
2986 if (CALL_P (insn))
2988 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2990 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2991 sched_analyze_1 (deps, XEXP (link, 0), insn);
2992 else if (GET_CODE (XEXP (link, 0)) != SET)
2993 sched_analyze_2 (deps, XEXP (link, 0), insn);
2995 /* Don't schedule anything after a tail call, tail call needs
2996 to use at least all call-saved registers. */
2997 if (SIBLING_CALL_P (insn))
2998 reg_pending_barrier = TRUE_BARRIER;
2999 else if (find_reg_note (insn, REG_SETJMP, NULL))
3000 reg_pending_barrier = MOVE_BARRIER;
3003 if (JUMP_P (insn))
3005 rtx next;
3006 next = next_nonnote_nondebug_insn (insn);
3007 if (next && BARRIER_P (next))
3008 reg_pending_barrier = MOVE_BARRIER;
3009 else
3011 rtx_insn_list *pending;
3012 rtx_expr_list *pending_mem;
3014 if (sched_deps_info->compute_jump_reg_dependencies)
3016 (*sched_deps_info->compute_jump_reg_dependencies)
3017 (insn, reg_pending_control_uses);
3019 /* Make latency of jump equal to 0 by using anti-dependence. */
3020 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3022 struct deps_reg *reg_last = &deps->reg_last[i];
3023 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3024 false);
3025 add_dependence_list (insn, reg_last->implicit_sets,
3026 0, REG_DEP_ANTI, false);
3027 add_dependence_list (insn, reg_last->clobbers, 0,
3028 REG_DEP_ANTI, false);
3032 /* All memory writes and volatile reads must happen before the
3033 jump. Non-volatile reads must happen before the jump iff
3034 the result is needed by the above register used mask. */
3036 pending = deps->pending_write_insns;
3037 pending_mem = deps->pending_write_mems;
3038 while (pending)
3040 if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3041 add_dependence (insn, pending->insn (),
3042 REG_DEP_OUTPUT);
3043 pending = pending->next ();
3044 pending_mem = pending_mem->next ();
3047 pending = deps->pending_read_insns;
3048 pending_mem = deps->pending_read_mems;
3049 while (pending)
3051 if (MEM_VOLATILE_P (pending_mem->element ())
3052 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3053 add_dependence (insn, pending->insn (),
3054 REG_DEP_OUTPUT);
3055 pending = pending->next ();
3056 pending_mem = pending_mem->next ();
3059 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3060 REG_DEP_ANTI, true);
3061 add_dependence_list (insn, deps->pending_jump_insns, 1,
3062 REG_DEP_ANTI, true);
3066 /* If this instruction can throw an exception, then moving it changes
3067 where block boundaries fall. This is mighty confusing elsewhere.
3068 Therefore, prevent such an instruction from being moved. Same for
3069 non-jump instructions that define block boundaries.
3070 ??? Unclear whether this is still necessary in EBB mode. If not,
3071 add_branch_dependences should be adjusted for RGN mode instead. */
3072 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3073 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3074 reg_pending_barrier = MOVE_BARRIER;
3076 if (sched_pressure != SCHED_PRESSURE_NONE)
3078 setup_insn_reg_uses (deps, insn);
3079 init_insn_reg_pressure_info (insn);
3082 /* Add register dependencies for insn. */
3083 if (DEBUG_INSN_P (insn))
3085 rtx_insn *prev = deps->last_debug_insn;
3086 rtx u;
3088 if (!deps->readonly)
3089 deps->last_debug_insn = insn;
3091 if (prev)
3092 add_dependence (insn, prev, REG_DEP_ANTI);
3094 add_dependence_list (insn, deps->last_function_call, 1,
3095 REG_DEP_ANTI, false);
3097 if (!sel_sched_p ())
3098 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3099 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)), REG_DEP_ANTI);
3101 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3103 struct deps_reg *reg_last = &deps->reg_last[i];
3104 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3105 /* There's no point in making REG_DEP_CONTROL dependencies for
3106 debug insns. */
3107 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3108 false);
3110 if (!deps->readonly)
3111 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3113 CLEAR_REG_SET (reg_pending_uses);
3115 /* Quite often, a debug insn will refer to stuff in the
3116 previous instruction, but the reason we want this
3117 dependency here is to make sure the scheduler doesn't
3118 gratuitously move a debug insn ahead. This could dirty
3119 DF flags and cause additional analysis that wouldn't have
3120 occurred in compilation without debug insns, and such
3121 additional analysis can modify the generated code. */
3122 prev = PREV_INSN (insn);
3124 if (prev && NONDEBUG_INSN_P (prev))
3125 add_dependence (insn, prev, REG_DEP_ANTI);
3127 else
3129 regset_head set_or_clobbered;
3131 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3133 struct deps_reg *reg_last = &deps->reg_last[i];
3134 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3135 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3136 false);
3137 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3138 false);
3140 if (!deps->readonly)
3142 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3143 reg_last->uses_length++;
3147 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3148 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3150 struct deps_reg *reg_last = &deps->reg_last[i];
3151 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3152 add_dependence_list (insn, reg_last->implicit_sets, 0,
3153 REG_DEP_ANTI, false);
3154 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3155 false);
3157 if (!deps->readonly)
3159 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3160 reg_last->uses_length++;
3164 if (targetm.sched.exposed_pipeline)
3166 INIT_REG_SET (&set_or_clobbered);
3167 bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3168 reg_pending_sets);
3169 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3171 struct deps_reg *reg_last = &deps->reg_last[i];
3172 rtx list;
3173 for (list = reg_last->uses; list; list = XEXP (list, 1))
3175 rtx other = XEXP (list, 0);
3176 if (INSN_CACHED_COND (other) != const_true_rtx
3177 && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
3178 INSN_CACHED_COND (other) = const_true_rtx;
3183 /* If the current insn is conditional, we can't free any
3184 of the lists. */
3185 if (sched_has_condition_p (insn))
3187 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3189 struct deps_reg *reg_last = &deps->reg_last[i];
3190 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3191 false);
3192 add_dependence_list (insn, reg_last->implicit_sets, 0,
3193 REG_DEP_ANTI, false);
3194 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3195 false);
3196 add_dependence_list (insn, reg_last->control_uses, 0,
3197 REG_DEP_CONTROL, false);
3199 if (!deps->readonly)
3201 reg_last->clobbers
3202 = alloc_INSN_LIST (insn, reg_last->clobbers);
3203 reg_last->clobbers_length++;
3206 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3208 struct deps_reg *reg_last = &deps->reg_last[i];
3209 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3210 false);
3211 add_dependence_list (insn, reg_last->implicit_sets, 0,
3212 REG_DEP_ANTI, false);
3213 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3214 false);
3215 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3216 false);
3217 add_dependence_list (insn, reg_last->control_uses, 0,
3218 REG_DEP_CONTROL, false);
3220 if (!deps->readonly)
3221 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3224 else
3226 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3228 struct deps_reg *reg_last = &deps->reg_last[i];
3229 if (reg_last->uses_length >= MAX_PENDING_LIST_LENGTH
3230 || reg_last->clobbers_length >= MAX_PENDING_LIST_LENGTH)
3232 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3233 REG_DEP_OUTPUT, false);
3234 add_dependence_list_and_free (deps, insn,
3235 &reg_last->implicit_sets, 0,
3236 REG_DEP_ANTI, false);
3237 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3238 REG_DEP_ANTI, false);
3239 add_dependence_list_and_free (deps, insn,
3240 &reg_last->control_uses, 0,
3241 REG_DEP_ANTI, false);
3242 add_dependence_list_and_free (deps, insn,
3243 &reg_last->clobbers, 0,
3244 REG_DEP_OUTPUT, false);
3246 if (!deps->readonly)
3248 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3249 reg_last->clobbers_length = 0;
3250 reg_last->uses_length = 0;
3253 else
3255 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3256 false);
3257 add_dependence_list (insn, reg_last->implicit_sets, 0,
3258 REG_DEP_ANTI, false);
3259 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3260 false);
3261 add_dependence_list (insn, reg_last->control_uses, 0,
3262 REG_DEP_CONTROL, false);
3265 if (!deps->readonly)
3267 reg_last->clobbers_length++;
3268 reg_last->clobbers
3269 = alloc_INSN_LIST (insn, reg_last->clobbers);
3272 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3274 struct deps_reg *reg_last = &deps->reg_last[i];
3276 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3277 REG_DEP_OUTPUT, false);
3278 add_dependence_list_and_free (deps, insn,
3279 &reg_last->implicit_sets,
3280 0, REG_DEP_ANTI, false);
3281 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3282 REG_DEP_OUTPUT, false);
3283 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3284 REG_DEP_ANTI, false);
3285 add_dependence_list (insn, reg_last->control_uses, 0,
3286 REG_DEP_CONTROL, false);
3288 if (!deps->readonly)
3290 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3291 reg_last->uses_length = 0;
3292 reg_last->clobbers_length = 0;
3296 if (!deps->readonly)
3298 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3300 struct deps_reg *reg_last = &deps->reg_last[i];
3301 reg_last->control_uses
3302 = alloc_INSN_LIST (insn, reg_last->control_uses);
3307 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3308 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3310 struct deps_reg *reg_last = &deps->reg_last[i];
3311 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3312 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3313 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3314 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3315 false);
3317 if (!deps->readonly)
3318 reg_last->implicit_sets
3319 = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3322 if (!deps->readonly)
3324 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3325 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3326 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3327 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3328 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3329 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3330 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3332 /* Set up the pending barrier found. */
3333 deps->last_reg_pending_barrier = reg_pending_barrier;
3336 CLEAR_REG_SET (reg_pending_uses);
3337 CLEAR_REG_SET (reg_pending_clobbers);
3338 CLEAR_REG_SET (reg_pending_sets);
3339 CLEAR_REG_SET (reg_pending_control_uses);
3340 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3341 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3343 /* Add dependencies if a scheduling barrier was found. */
3344 if (reg_pending_barrier)
3346 /* In the case of barrier the most added dependencies are not
3347 real, so we use anti-dependence here. */
3348 if (sched_has_condition_p (insn))
3350 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3352 struct deps_reg *reg_last = &deps->reg_last[i];
3353 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3354 true);
3355 add_dependence_list (insn, reg_last->sets, 0,
3356 reg_pending_barrier == TRUE_BARRIER
3357 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3358 add_dependence_list (insn, reg_last->implicit_sets, 0,
3359 REG_DEP_ANTI, true);
3360 add_dependence_list (insn, reg_last->clobbers, 0,
3361 reg_pending_barrier == TRUE_BARRIER
3362 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3365 else
3367 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3369 struct deps_reg *reg_last = &deps->reg_last[i];
3370 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3371 REG_DEP_ANTI, true);
3372 add_dependence_list_and_free (deps, insn,
3373 &reg_last->control_uses, 0,
3374 REG_DEP_CONTROL, true);
3375 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3376 reg_pending_barrier == TRUE_BARRIER
3377 ? REG_DEP_TRUE : REG_DEP_ANTI,
3378 true);
3379 add_dependence_list_and_free (deps, insn,
3380 &reg_last->implicit_sets, 0,
3381 REG_DEP_ANTI, true);
3382 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3383 reg_pending_barrier == TRUE_BARRIER
3384 ? REG_DEP_TRUE : REG_DEP_ANTI,
3385 true);
3387 if (!deps->readonly)
3389 reg_last->uses_length = 0;
3390 reg_last->clobbers_length = 0;
3395 if (!deps->readonly)
3396 for (i = 0; i < (unsigned)deps->max_reg; i++)
3398 struct deps_reg *reg_last = &deps->reg_last[i];
3399 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3400 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3403 /* Don't flush pending lists on speculative checks for
3404 selective scheduling. */
3405 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3406 flush_pending_lists (deps, insn, true, true);
3408 reg_pending_barrier = NOT_A_BARRIER;
3411 /* If a post-call group is still open, see if it should remain so.
3412 This insn must be a simple move of a hard reg to a pseudo or
3413 vice-versa.
3415 We must avoid moving these insns for correctness on targets
3416 with small register classes, and for special registers like
3417 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3418 hard regs for all targets. */
3420 if (deps->in_post_call_group_p)
3422 rtx tmp, set = single_set (insn);
3423 int src_regno, dest_regno;
3425 if (set == NULL)
3427 if (DEBUG_INSN_P (insn))
3428 /* We don't want to mark debug insns as part of the same
3429 sched group. We know they really aren't, but if we use
3430 debug insns to tell that a call group is over, we'll
3431 get different code if debug insns are not there and
3432 instructions that follow seem like they should be part
3433 of the call group.
3435 Also, if we did, chain_to_prev_insn would move the
3436 deps of the debug insn to the call insn, modifying
3437 non-debug post-dependency counts of the debug insn
3438 dependencies and otherwise messing with the scheduling
3439 order.
3441 Instead, let such debug insns be scheduled freely, but
3442 keep the call group open in case there are insns that
3443 should be part of it afterwards. Since we grant debug
3444 insns higher priority than even sched group insns, it
3445 will all turn out all right. */
3446 goto debug_dont_end_call_group;
3447 else
3448 goto end_call_group;
3451 tmp = SET_DEST (set);
3452 if (GET_CODE (tmp) == SUBREG)
3453 tmp = SUBREG_REG (tmp);
3454 if (REG_P (tmp))
3455 dest_regno = REGNO (tmp);
3456 else
3457 goto end_call_group;
3459 tmp = SET_SRC (set);
3460 if (GET_CODE (tmp) == SUBREG)
3461 tmp = SUBREG_REG (tmp);
3462 if ((GET_CODE (tmp) == PLUS
3463 || GET_CODE (tmp) == MINUS)
3464 && REG_P (XEXP (tmp, 0))
3465 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3466 && dest_regno == STACK_POINTER_REGNUM)
3467 src_regno = STACK_POINTER_REGNUM;
3468 else if (REG_P (tmp))
3469 src_regno = REGNO (tmp);
3470 else
3471 goto end_call_group;
3473 if (src_regno < FIRST_PSEUDO_REGISTER
3474 || dest_regno < FIRST_PSEUDO_REGISTER)
3476 if (!deps->readonly
3477 && deps->in_post_call_group_p == post_call_initial)
3478 deps->in_post_call_group_p = post_call;
3480 if (!sel_sched_p () || sched_emulate_haifa_p)
3482 SCHED_GROUP_P (insn) = 1;
3483 CANT_MOVE (insn) = 1;
3486 else
3488 end_call_group:
3489 if (!deps->readonly)
3490 deps->in_post_call_group_p = not_post_call;
3494 debug_dont_end_call_group:
3495 if ((current_sched_info->flags & DO_SPECULATION)
3496 && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3497 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3498 be speculated. */
3500 if (sel_sched_p ())
3501 sel_mark_hard_insn (insn);
3502 else
3504 sd_iterator_def sd_it;
3505 dep_t dep;
3507 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3508 sd_iterator_cond (&sd_it, &dep);)
3509 change_spec_dep_to_hard (sd_it);
3513 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3514 honor their original ordering. */
3515 if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3517 if (deps->last_args_size)
3518 add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3519 deps->last_args_size = insn;
3523 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3524 longjmp, loop forever, ...). */
3525 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3526 test for ECF_NORETURN? */
3527 static bool
3528 call_may_noreturn_p (rtx insn)
3530 rtx call;
3532 /* const or pure calls that aren't looping will always return. */
3533 if (RTL_CONST_OR_PURE_CALL_P (insn)
3534 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3535 return false;
3537 call = get_call_rtx_from (insn);
3538 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3540 rtx symbol = XEXP (XEXP (call, 0), 0);
3541 if (SYMBOL_REF_DECL (symbol)
3542 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3544 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3545 == BUILT_IN_NORMAL)
3546 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3548 case BUILT_IN_BCMP:
3549 case BUILT_IN_BCOPY:
3550 case BUILT_IN_BZERO:
3551 case BUILT_IN_INDEX:
3552 case BUILT_IN_MEMCHR:
3553 case BUILT_IN_MEMCMP:
3554 case BUILT_IN_MEMCPY:
3555 case BUILT_IN_MEMMOVE:
3556 case BUILT_IN_MEMPCPY:
3557 case BUILT_IN_MEMSET:
3558 case BUILT_IN_RINDEX:
3559 case BUILT_IN_STPCPY:
3560 case BUILT_IN_STPNCPY:
3561 case BUILT_IN_STRCAT:
3562 case BUILT_IN_STRCHR:
3563 case BUILT_IN_STRCMP:
3564 case BUILT_IN_STRCPY:
3565 case BUILT_IN_STRCSPN:
3566 case BUILT_IN_STRLEN:
3567 case BUILT_IN_STRNCAT:
3568 case BUILT_IN_STRNCMP:
3569 case BUILT_IN_STRNCPY:
3570 case BUILT_IN_STRPBRK:
3571 case BUILT_IN_STRRCHR:
3572 case BUILT_IN_STRSPN:
3573 case BUILT_IN_STRSTR:
3574 /* Assume certain string/memory builtins always return. */
3575 return false;
3576 default:
3577 break;
3582 /* For all other calls assume that they might not always return. */
3583 return true;
3586 /* Return true if INSN should be made dependent on the previous instruction
3587 group, and if all INSN's dependencies should be moved to the first
3588 instruction of that group. */
3590 static bool
3591 chain_to_prev_insn_p (rtx insn)
3593 rtx prev, x;
3595 /* INSN forms a group with the previous instruction. */
3596 if (SCHED_GROUP_P (insn))
3597 return true;
3599 /* If the previous instruction clobbers a register R and this one sets
3600 part of R, the clobber was added specifically to help us track the
3601 liveness of R. There's no point scheduling the clobber and leaving
3602 INSN behind, especially if we move the clobber to another block. */
3603 prev = prev_nonnote_nondebug_insn (insn);
3604 if (prev
3605 && INSN_P (prev)
3606 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3607 && GET_CODE (PATTERN (prev)) == CLOBBER)
3609 x = XEXP (PATTERN (prev), 0);
3610 if (set_of (x, insn))
3611 return true;
3614 return false;
3617 /* Analyze INSN with DEPS as a context. */
3618 void
3619 deps_analyze_insn (struct deps_desc *deps, rtx_insn *insn)
3621 if (sched_deps_info->start_insn)
3622 sched_deps_info->start_insn (insn);
3624 /* Record the condition for this insn. */
3625 if (NONDEBUG_INSN_P (insn))
3627 rtx t;
3628 sched_get_condition_with_rev (insn, NULL);
3629 t = INSN_CACHED_COND (insn);
3630 INSN_COND_DEPS (insn) = NULL;
3631 if (reload_completed
3632 && (current_sched_info->flags & DO_PREDICATION)
3633 && COMPARISON_P (t)
3634 && REG_P (XEXP (t, 0))
3635 && CONSTANT_P (XEXP (t, 1)))
3637 unsigned int regno;
3638 int nregs;
3639 rtx_insn_list *cond_deps = NULL;
3640 t = XEXP (t, 0);
3641 regno = REGNO (t);
3642 nregs = hard_regno_nregs[regno][GET_MODE (t)];
3643 while (nregs-- > 0)
3645 struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3646 cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3647 cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3648 cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3650 INSN_COND_DEPS (insn) = cond_deps;
3654 if (JUMP_P (insn))
3656 /* Make each JUMP_INSN (but not a speculative check)
3657 a scheduling barrier for memory references. */
3658 if (!deps->readonly
3659 && !(sel_sched_p ()
3660 && sel_insn_is_speculation_check (insn)))
3662 /* Keep the list a reasonable size. */
3663 if (deps->pending_flush_length++ >= MAX_PENDING_LIST_LENGTH)
3664 flush_pending_lists (deps, insn, true, true);
3665 else
3666 deps->pending_jump_insns
3667 = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3670 /* For each insn which shouldn't cross a jump, add a dependence. */
3671 add_dependence_list_and_free (deps, insn,
3672 &deps->sched_before_next_jump, 1,
3673 REG_DEP_ANTI, true);
3675 sched_analyze_insn (deps, PATTERN (insn), insn);
3677 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3679 sched_analyze_insn (deps, PATTERN (insn), insn);
3681 else if (CALL_P (insn))
3683 int i;
3685 CANT_MOVE (insn) = 1;
3687 if (find_reg_note (insn, REG_SETJMP, NULL))
3689 /* This is setjmp. Assume that all registers, not just
3690 hard registers, may be clobbered by this call. */
3691 reg_pending_barrier = MOVE_BARRIER;
3693 else
3695 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3696 /* A call may read and modify global register variables. */
3697 if (global_regs[i])
3699 SET_REGNO_REG_SET (reg_pending_sets, i);
3700 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3702 /* Other call-clobbered hard regs may be clobbered.
3703 Since we only have a choice between 'might be clobbered'
3704 and 'definitely not clobbered', we must include all
3705 partly call-clobbered registers here. */
3706 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3707 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3708 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3709 /* We don't know what set of fixed registers might be used
3710 by the function, but it is certain that the stack pointer
3711 is among them, but be conservative. */
3712 else if (fixed_regs[i])
3713 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3714 /* The frame pointer is normally not used by the function
3715 itself, but by the debugger. */
3716 /* ??? MIPS o32 is an exception. It uses the frame pointer
3717 in the macro expansion of jal but does not represent this
3718 fact in the call_insn rtl. */
3719 else if (i == FRAME_POINTER_REGNUM
3720 || (i == HARD_FRAME_POINTER_REGNUM
3721 && (! reload_completed || frame_pointer_needed)))
3722 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3725 /* For each insn which shouldn't cross a call, add a dependence
3726 between that insn and this call insn. */
3727 add_dependence_list_and_free (deps, insn,
3728 &deps->sched_before_next_call, 1,
3729 REG_DEP_ANTI, true);
3731 sched_analyze_insn (deps, PATTERN (insn), insn);
3733 /* If CALL would be in a sched group, then this will violate
3734 convention that sched group insns have dependencies only on the
3735 previous instruction.
3737 Of course one can say: "Hey! What about head of the sched group?"
3738 And I will answer: "Basic principles (one dep per insn) are always
3739 the same." */
3740 gcc_assert (!SCHED_GROUP_P (insn));
3742 /* In the absence of interprocedural alias analysis, we must flush
3743 all pending reads and writes, and start new dependencies starting
3744 from here. But only flush writes for constant calls (which may
3745 be passed a pointer to something we haven't written yet). */
3746 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3748 if (!deps->readonly)
3750 /* Remember the last function call for limiting lifetimes. */
3751 free_INSN_LIST_list (&deps->last_function_call);
3752 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3754 if (call_may_noreturn_p (insn))
3756 /* Remember the last function call that might not always return
3757 normally for limiting moves of trapping insns. */
3758 free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3759 deps->last_function_call_may_noreturn
3760 = alloc_INSN_LIST (insn, NULL_RTX);
3763 /* Before reload, begin a post-call group, so as to keep the
3764 lifetimes of hard registers correct. */
3765 if (! reload_completed)
3766 deps->in_post_call_group_p = post_call;
3770 if (sched_deps_info->use_cselib)
3771 cselib_process_insn (insn);
3773 if (sched_deps_info->finish_insn)
3774 sched_deps_info->finish_insn ();
3776 /* Fixup the dependencies in the sched group. */
3777 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3778 && chain_to_prev_insn_p (insn)
3779 && !sel_sched_p ())
3780 chain_to_prev_insn (insn);
3783 /* Initialize DEPS for the new block beginning with HEAD. */
3784 void
3785 deps_start_bb (struct deps_desc *deps, rtx_insn *head)
3787 gcc_assert (!deps->readonly);
3789 /* Before reload, if the previous block ended in a call, show that
3790 we are inside a post-call group, so as to keep the lifetimes of
3791 hard registers correct. */
3792 if (! reload_completed && !LABEL_P (head))
3794 rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3796 if (insn && CALL_P (insn))
3797 deps->in_post_call_group_p = post_call_initial;
3801 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3802 dependencies for each insn. */
3803 void
3804 sched_analyze (struct deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3806 rtx_insn *insn;
3808 if (sched_deps_info->use_cselib)
3809 cselib_init (CSELIB_RECORD_MEMORY);
3811 deps_start_bb (deps, head);
3813 for (insn = head;; insn = NEXT_INSN (insn))
3816 if (INSN_P (insn))
3818 /* And initialize deps_lists. */
3819 sd_init_insn (insn);
3820 /* Clean up SCHED_GROUP_P which may be set by last
3821 scheduler pass. */
3822 if (SCHED_GROUP_P (insn))
3823 SCHED_GROUP_P (insn) = 0;
3826 deps_analyze_insn (deps, insn);
3828 if (insn == tail)
3830 if (sched_deps_info->use_cselib)
3831 cselib_finish ();
3832 return;
3835 gcc_unreachable ();
3838 /* Helper for sched_free_deps ().
3839 Delete INSN's (RESOLVED_P) backward dependencies. */
3840 static void
3841 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3843 sd_iterator_def sd_it;
3844 dep_t dep;
3845 sd_list_types_def types;
3847 if (resolved_p)
3848 types = SD_LIST_RES_BACK;
3849 else
3850 types = SD_LIST_BACK;
3852 for (sd_it = sd_iterator_start (insn, types);
3853 sd_iterator_cond (&sd_it, &dep);)
3855 dep_link_t link = *sd_it.linkp;
3856 dep_node_t node = DEP_LINK_NODE (link);
3857 deps_list_t back_list;
3858 deps_list_t forw_list;
3860 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3861 remove_from_deps_list (link, back_list);
3862 delete_dep_node (node);
3866 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3867 deps_lists. */
3868 void
3869 sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
3871 rtx_insn *insn;
3872 rtx_insn *next_tail = NEXT_INSN (tail);
3874 /* We make two passes since some insns may be scheduled before their
3875 dependencies are resolved. */
3876 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3877 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3879 /* Clear forward deps and leave the dep_nodes to the
3880 corresponding back_deps list. */
3881 if (resolved_p)
3882 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3883 else
3884 clear_deps_list (INSN_FORW_DEPS (insn));
3886 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3887 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3889 /* Clear resolved back deps together with its dep_nodes. */
3890 delete_dep_nodes_in_back_deps (insn, resolved_p);
3892 sd_finish_insn (insn);
3896 /* Initialize variables for region data dependence analysis.
3897 When LAZY_REG_LAST is true, do not allocate reg_last array
3898 of struct deps_desc immediately. */
3900 void
3901 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3903 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3905 deps->max_reg = max_reg;
3906 if (lazy_reg_last)
3907 deps->reg_last = NULL;
3908 else
3909 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3910 INIT_REG_SET (&deps->reg_last_in_use);
3912 deps->pending_read_insns = 0;
3913 deps->pending_read_mems = 0;
3914 deps->pending_write_insns = 0;
3915 deps->pending_write_mems = 0;
3916 deps->pending_jump_insns = 0;
3917 deps->pending_read_list_length = 0;
3918 deps->pending_write_list_length = 0;
3919 deps->pending_flush_length = 0;
3920 deps->last_pending_memory_flush = 0;
3921 deps->last_function_call = 0;
3922 deps->last_function_call_may_noreturn = 0;
3923 deps->sched_before_next_call = 0;
3924 deps->sched_before_next_jump = 0;
3925 deps->in_post_call_group_p = not_post_call;
3926 deps->last_debug_insn = 0;
3927 deps->last_args_size = 0;
3928 deps->last_reg_pending_barrier = NOT_A_BARRIER;
3929 deps->readonly = 0;
3932 /* Init only reg_last field of DEPS, which was not allocated before as
3933 we inited DEPS lazily. */
3934 void
3935 init_deps_reg_last (struct deps_desc *deps)
3937 gcc_assert (deps && deps->max_reg > 0);
3938 gcc_assert (deps->reg_last == NULL);
3940 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3944 /* Free insn lists found in DEPS. */
3946 void
3947 free_deps (struct deps_desc *deps)
3949 unsigned i;
3950 reg_set_iterator rsi;
3952 /* We set max_reg to 0 when this context was already freed. */
3953 if (deps->max_reg == 0)
3955 gcc_assert (deps->reg_last == NULL);
3956 return;
3958 deps->max_reg = 0;
3960 free_INSN_LIST_list (&deps->pending_read_insns);
3961 free_EXPR_LIST_list (&deps->pending_read_mems);
3962 free_INSN_LIST_list (&deps->pending_write_insns);
3963 free_EXPR_LIST_list (&deps->pending_write_mems);
3964 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3966 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3967 times. For a testcase with 42000 regs and 8000 small basic blocks,
3968 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3969 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3971 struct deps_reg *reg_last = &deps->reg_last[i];
3972 if (reg_last->uses)
3973 free_INSN_LIST_list (&reg_last->uses);
3974 if (reg_last->sets)
3975 free_INSN_LIST_list (&reg_last->sets);
3976 if (reg_last->implicit_sets)
3977 free_INSN_LIST_list (&reg_last->implicit_sets);
3978 if (reg_last->control_uses)
3979 free_INSN_LIST_list (&reg_last->control_uses);
3980 if (reg_last->clobbers)
3981 free_INSN_LIST_list (&reg_last->clobbers);
3983 CLEAR_REG_SET (&deps->reg_last_in_use);
3985 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3986 it at all. */
3987 free (deps->reg_last);
3988 deps->reg_last = NULL;
3990 deps = NULL;
3993 /* Remove INSN from dependence contexts DEPS. */
3994 void
3995 remove_from_deps (struct deps_desc *deps, rtx_insn *insn)
3997 int removed;
3998 unsigned i;
3999 reg_set_iterator rsi;
4001 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4002 &deps->pending_read_mems);
4003 if (!DEBUG_INSN_P (insn))
4004 deps->pending_read_list_length -= removed;
4005 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4006 &deps->pending_write_mems);
4007 deps->pending_write_list_length -= removed;
4009 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4010 deps->pending_flush_length -= removed;
4011 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4012 deps->pending_flush_length -= removed;
4014 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4016 struct deps_reg *reg_last = &deps->reg_last[i];
4017 if (reg_last->uses)
4018 remove_from_dependence_list (insn, &reg_last->uses);
4019 if (reg_last->sets)
4020 remove_from_dependence_list (insn, &reg_last->sets);
4021 if (reg_last->implicit_sets)
4022 remove_from_dependence_list (insn, &reg_last->implicit_sets);
4023 if (reg_last->clobbers)
4024 remove_from_dependence_list (insn, &reg_last->clobbers);
4025 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4026 && !reg_last->clobbers)
4027 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
4030 if (CALL_P (insn))
4032 remove_from_dependence_list (insn, &deps->last_function_call);
4033 remove_from_dependence_list (insn,
4034 &deps->last_function_call_may_noreturn);
4036 remove_from_dependence_list (insn, &deps->sched_before_next_call);
4039 /* Init deps data vector. */
4040 static void
4041 init_deps_data_vector (void)
4043 int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4044 if (reserve > 0 && ! h_d_i_d.space (reserve))
4045 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
4048 /* If it is profitable to use them, initialize or extend (depending on
4049 GLOBAL_P) dependency data. */
4050 void
4051 sched_deps_init (bool global_p)
4053 /* Average number of insns in the basic block.
4054 '+ 1' is used to make it nonzero. */
4055 int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4057 init_deps_data_vector ();
4059 /* We use another caching mechanism for selective scheduling, so
4060 we don't use this one. */
4061 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4063 /* ?!? We could save some memory by computing a per-region luid mapping
4064 which could reduce both the number of vectors in the cache and the
4065 size of each vector. Instead we just avoid the cache entirely unless
4066 the average number of instructions in a basic block is very high. See
4067 the comment before the declaration of true_dependency_cache for
4068 what we consider "very high". */
4069 cache_size = 0;
4070 extend_dependency_caches (sched_max_luid, true);
4073 if (global_p)
4075 dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
4076 /* Allocate lists for one block at a time. */
4077 insns_in_block);
4078 dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
4079 /* Allocate nodes for one block at a time.
4080 We assume that average insn has
4081 5 producers. */
4082 5 * insns_in_block);
4087 /* Create or extend (depending on CREATE_P) dependency caches to
4088 size N. */
4089 void
4090 extend_dependency_caches (int n, bool create_p)
4092 if (create_p || true_dependency_cache)
4094 int i, luid = cache_size + n;
4096 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4097 luid);
4098 output_dependency_cache = XRESIZEVEC (bitmap_head,
4099 output_dependency_cache, luid);
4100 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4101 luid);
4102 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4103 luid);
4105 if (current_sched_info->flags & DO_SPECULATION)
4106 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4107 luid);
4109 for (i = cache_size; i < luid; i++)
4111 bitmap_initialize (&true_dependency_cache[i], 0);
4112 bitmap_initialize (&output_dependency_cache[i], 0);
4113 bitmap_initialize (&anti_dependency_cache[i], 0);
4114 bitmap_initialize (&control_dependency_cache[i], 0);
4116 if (current_sched_info->flags & DO_SPECULATION)
4117 bitmap_initialize (&spec_dependency_cache[i], 0);
4119 cache_size = luid;
4123 /* Finalize dependency information for the whole function. */
4124 void
4125 sched_deps_finish (void)
4127 gcc_assert (deps_pools_are_empty_p ());
4128 free_alloc_pool_if_empty (&dn_pool);
4129 free_alloc_pool_if_empty (&dl_pool);
4130 gcc_assert (dn_pool == NULL && dl_pool == NULL);
4132 h_d_i_d.release ();
4133 cache_size = 0;
4135 if (true_dependency_cache)
4137 int i;
4139 for (i = 0; i < cache_size; i++)
4141 bitmap_clear (&true_dependency_cache[i]);
4142 bitmap_clear (&output_dependency_cache[i]);
4143 bitmap_clear (&anti_dependency_cache[i]);
4144 bitmap_clear (&control_dependency_cache[i]);
4146 if (sched_deps_info->generate_spec_deps)
4147 bitmap_clear (&spec_dependency_cache[i]);
4149 free (true_dependency_cache);
4150 true_dependency_cache = NULL;
4151 free (output_dependency_cache);
4152 output_dependency_cache = NULL;
4153 free (anti_dependency_cache);
4154 anti_dependency_cache = NULL;
4155 free (control_dependency_cache);
4156 control_dependency_cache = NULL;
4158 if (sched_deps_info->generate_spec_deps)
4160 free (spec_dependency_cache);
4161 spec_dependency_cache = NULL;
4167 /* Initialize some global variables needed by the dependency analysis
4168 code. */
4170 void
4171 init_deps_global (void)
4173 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4174 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4175 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4176 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4177 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4178 reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4179 reg_pending_barrier = NOT_A_BARRIER;
4181 if (!sel_sched_p () || sched_emulate_haifa_p)
4183 sched_deps_info->start_insn = haifa_start_insn;
4184 sched_deps_info->finish_insn = haifa_finish_insn;
4186 sched_deps_info->note_reg_set = haifa_note_reg_set;
4187 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4188 sched_deps_info->note_reg_use = haifa_note_reg_use;
4190 sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4191 sched_deps_info->note_dep = haifa_note_dep;
4195 /* Free everything used by the dependency analysis code. */
4197 void
4198 finish_deps_global (void)
4200 FREE_REG_SET (reg_pending_sets);
4201 FREE_REG_SET (reg_pending_clobbers);
4202 FREE_REG_SET (reg_pending_uses);
4203 FREE_REG_SET (reg_pending_control_uses);
4206 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4207 dw_t
4208 estimate_dep_weak (rtx mem1, rtx mem2)
4210 rtx r1, r2;
4212 if (mem1 == mem2)
4213 /* MEMs are the same - don't speculate. */
4214 return MIN_DEP_WEAK;
4216 r1 = XEXP (mem1, 0);
4217 r2 = XEXP (mem2, 0);
4219 if (r1 == r2
4220 || (REG_P (r1) && REG_P (r2)
4221 && REGNO (r1) == REGNO (r2)))
4222 /* Again, MEMs are the same. */
4223 return MIN_DEP_WEAK;
4224 else if ((REG_P (r1) && !REG_P (r2))
4225 || (!REG_P (r1) && REG_P (r2)))
4226 /* Different addressing modes - reason to be more speculative,
4227 than usual. */
4228 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4229 else
4230 /* We can't say anything about the dependence. */
4231 return UNCERTAIN_DEP_WEAK;
4234 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4235 This function can handle same INSN and ELEM (INSN == ELEM).
4236 It is a convenience wrapper. */
4237 static void
4238 add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4240 ds_t ds;
4241 bool internal;
4243 if (dep_type == REG_DEP_TRUE)
4244 ds = DEP_TRUE;
4245 else if (dep_type == REG_DEP_OUTPUT)
4246 ds = DEP_OUTPUT;
4247 else if (dep_type == REG_DEP_CONTROL)
4248 ds = DEP_CONTROL;
4249 else
4251 gcc_assert (dep_type == REG_DEP_ANTI);
4252 ds = DEP_ANTI;
4255 /* When add_dependence is called from inside sched-deps.c, we expect
4256 cur_insn to be non-null. */
4257 internal = cur_insn != NULL;
4258 if (internal)
4259 gcc_assert (insn == cur_insn);
4260 else
4261 cur_insn = insn;
4263 note_dep (elem, ds);
4264 if (!internal)
4265 cur_insn = NULL;
4268 /* Return weakness of speculative type TYPE in the dep_status DS,
4269 without checking to prevent ICEs on malformed input. */
4270 static dw_t
4271 get_dep_weak_1 (ds_t ds, ds_t type)
4273 ds = ds & type;
4275 switch (type)
4277 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4278 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4279 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4280 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4281 default: gcc_unreachable ();
4284 return (dw_t) ds;
4287 /* Return weakness of speculative type TYPE in the dep_status DS. */
4288 dw_t
4289 get_dep_weak (ds_t ds, ds_t type)
4291 dw_t dw = get_dep_weak_1 (ds, type);
4293 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4294 return dw;
4297 /* Return the dep_status, which has the same parameters as DS, except for
4298 speculative type TYPE, that will have weakness DW. */
4299 ds_t
4300 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4302 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4304 ds &= ~type;
4305 switch (type)
4307 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4308 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4309 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4310 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4311 default: gcc_unreachable ();
4313 return ds;
4316 /* Return the join of two dep_statuses DS1 and DS2.
4317 If MAX_P is true then choose the greater probability,
4318 otherwise multiply probabilities.
4319 This function assumes that both DS1 and DS2 contain speculative bits. */
4320 static ds_t
4321 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4323 ds_t ds, t;
4325 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4327 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4329 t = FIRST_SPEC_TYPE;
4332 if ((ds1 & t) && !(ds2 & t))
4333 ds |= ds1 & t;
4334 else if (!(ds1 & t) && (ds2 & t))
4335 ds |= ds2 & t;
4336 else if ((ds1 & t) && (ds2 & t))
4338 dw_t dw1 = get_dep_weak (ds1, t);
4339 dw_t dw2 = get_dep_weak (ds2, t);
4340 ds_t dw;
4342 if (!max_p)
4344 dw = ((ds_t) dw1) * ((ds_t) dw2);
4345 dw /= MAX_DEP_WEAK;
4346 if (dw < MIN_DEP_WEAK)
4347 dw = MIN_DEP_WEAK;
4349 else
4351 if (dw1 >= dw2)
4352 dw = dw1;
4353 else
4354 dw = dw2;
4357 ds = set_dep_weak (ds, t, (dw_t) dw);
4360 if (t == LAST_SPEC_TYPE)
4361 break;
4362 t <<= SPEC_TYPE_SHIFT;
4364 while (1);
4366 return ds;
4369 /* Return the join of two dep_statuses DS1 and DS2.
4370 This function assumes that both DS1 and DS2 contain speculative bits. */
4371 ds_t
4372 ds_merge (ds_t ds1, ds_t ds2)
4374 return ds_merge_1 (ds1, ds2, false);
4377 /* Return the join of two dep_statuses DS1 and DS2. */
4378 ds_t
4379 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4381 ds_t new_status = ds | ds2;
4383 if (new_status & SPECULATIVE)
4385 if ((ds && !(ds & SPECULATIVE))
4386 || (ds2 && !(ds2 & SPECULATIVE)))
4387 /* Then this dep can't be speculative. */
4388 new_status &= ~SPECULATIVE;
4389 else
4391 /* Both are speculative. Merging probabilities. */
4392 if (mem1)
4394 dw_t dw;
4396 dw = estimate_dep_weak (mem1, mem2);
4397 ds = set_dep_weak (ds, BEGIN_DATA, dw);
4400 if (!ds)
4401 new_status = ds2;
4402 else if (!ds2)
4403 new_status = ds;
4404 else
4405 new_status = ds_merge (ds2, ds);
4409 return new_status;
4412 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4413 probabilities. */
4414 ds_t
4415 ds_max_merge (ds_t ds1, ds_t ds2)
4417 if (ds1 == 0 && ds2 == 0)
4418 return 0;
4420 if (ds1 == 0 && ds2 != 0)
4421 return ds2;
4423 if (ds1 != 0 && ds2 == 0)
4424 return ds1;
4426 return ds_merge_1 (ds1, ds2, true);
4429 /* Return the probability of speculation success for the speculation
4430 status DS. */
4431 dw_t
4432 ds_weak (ds_t ds)
4434 ds_t res = 1, dt;
4435 int n = 0;
4437 dt = FIRST_SPEC_TYPE;
4440 if (ds & dt)
4442 res *= (ds_t) get_dep_weak (ds, dt);
4443 n++;
4446 if (dt == LAST_SPEC_TYPE)
4447 break;
4448 dt <<= SPEC_TYPE_SHIFT;
4450 while (1);
4452 gcc_assert (n);
4453 while (--n)
4454 res /= MAX_DEP_WEAK;
4456 if (res < MIN_DEP_WEAK)
4457 res = MIN_DEP_WEAK;
4459 gcc_assert (res <= MAX_DEP_WEAK);
4461 return (dw_t) res;
4464 /* Return a dep status that contains all speculation types of DS. */
4465 ds_t
4466 ds_get_speculation_types (ds_t ds)
4468 if (ds & BEGIN_DATA)
4469 ds |= BEGIN_DATA;
4470 if (ds & BE_IN_DATA)
4471 ds |= BE_IN_DATA;
4472 if (ds & BEGIN_CONTROL)
4473 ds |= BEGIN_CONTROL;
4474 if (ds & BE_IN_CONTROL)
4475 ds |= BE_IN_CONTROL;
4477 return ds & SPECULATIVE;
4480 /* Return a dep status that contains maximal weakness for each speculation
4481 type present in DS. */
4482 ds_t
4483 ds_get_max_dep_weak (ds_t ds)
4485 if (ds & BEGIN_DATA)
4486 ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4487 if (ds & BE_IN_DATA)
4488 ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4489 if (ds & BEGIN_CONTROL)
4490 ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4491 if (ds & BE_IN_CONTROL)
4492 ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4494 return ds;
4497 /* Dump information about the dependence status S. */
4498 static void
4499 dump_ds (FILE *f, ds_t s)
4501 fprintf (f, "{");
4503 if (s & BEGIN_DATA)
4504 fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4505 if (s & BE_IN_DATA)
4506 fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4507 if (s & BEGIN_CONTROL)
4508 fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4509 if (s & BE_IN_CONTROL)
4510 fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4512 if (s & HARD_DEP)
4513 fprintf (f, "HARD_DEP; ");
4515 if (s & DEP_TRUE)
4516 fprintf (f, "DEP_TRUE; ");
4517 if (s & DEP_OUTPUT)
4518 fprintf (f, "DEP_OUTPUT; ");
4519 if (s & DEP_ANTI)
4520 fprintf (f, "DEP_ANTI; ");
4521 if (s & DEP_CONTROL)
4522 fprintf (f, "DEP_CONTROL; ");
4524 fprintf (f, "}");
4527 DEBUG_FUNCTION void
4528 debug_ds (ds_t s)
4530 dump_ds (stderr, s);
4531 fprintf (stderr, "\n");
4534 #ifdef ENABLE_CHECKING
4535 /* Verify that dependence type and status are consistent.
4536 If RELAXED_P is true, then skip dep_weakness checks. */
4537 static void
4538 check_dep (dep_t dep, bool relaxed_p)
4540 enum reg_note dt = DEP_TYPE (dep);
4541 ds_t ds = DEP_STATUS (dep);
4543 gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4545 if (!(current_sched_info->flags & USE_DEPS_LIST))
4547 gcc_assert (ds == 0);
4548 return;
4551 /* Check that dependence type contains the same bits as the status. */
4552 if (dt == REG_DEP_TRUE)
4553 gcc_assert (ds & DEP_TRUE);
4554 else if (dt == REG_DEP_OUTPUT)
4555 gcc_assert ((ds & DEP_OUTPUT)
4556 && !(ds & DEP_TRUE));
4557 else if (dt == REG_DEP_ANTI)
4558 gcc_assert ((ds & DEP_ANTI)
4559 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4560 else
4561 gcc_assert (dt == REG_DEP_CONTROL
4562 && (ds & DEP_CONTROL)
4563 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4565 /* HARD_DEP can not appear in dep_status of a link. */
4566 gcc_assert (!(ds & HARD_DEP));
4568 /* Check that dependence status is set correctly when speculation is not
4569 supported. */
4570 if (!sched_deps_info->generate_spec_deps)
4571 gcc_assert (!(ds & SPECULATIVE));
4572 else if (ds & SPECULATIVE)
4574 if (!relaxed_p)
4576 ds_t type = FIRST_SPEC_TYPE;
4578 /* Check that dependence weakness is in proper range. */
4581 if (ds & type)
4582 get_dep_weak (ds, type);
4584 if (type == LAST_SPEC_TYPE)
4585 break;
4586 type <<= SPEC_TYPE_SHIFT;
4588 while (1);
4591 if (ds & BEGIN_SPEC)
4593 /* Only true dependence can be data speculative. */
4594 if (ds & BEGIN_DATA)
4595 gcc_assert (ds & DEP_TRUE);
4597 /* Control dependencies in the insn scheduler are represented by
4598 anti-dependencies, therefore only anti dependence can be
4599 control speculative. */
4600 if (ds & BEGIN_CONTROL)
4601 gcc_assert (ds & DEP_ANTI);
4603 else
4605 /* Subsequent speculations should resolve true dependencies. */
4606 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4609 /* Check that true and anti dependencies can't have other speculative
4610 statuses. */
4611 if (ds & DEP_TRUE)
4612 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4613 /* An output dependence can't be speculative at all. */
4614 gcc_assert (!(ds & DEP_OUTPUT));
4615 if (ds & DEP_ANTI)
4616 gcc_assert (ds & BEGIN_CONTROL);
4619 #endif /* ENABLE_CHECKING */
4621 /* The following code discovers opportunities to switch a memory reference
4622 and an increment by modifying the address. We ensure that this is done
4623 only for dependencies that are only used to show a single register
4624 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4625 instruction involved is subject to only one dep that can cause a pattern
4626 change.
4628 When we discover a suitable dependency, we fill in the dep_replacement
4629 structure to show how to modify the memory reference. */
4631 /* Holds information about a pair of memory reference and register increment
4632 insns which depend on each other, but could possibly be interchanged. */
4633 struct mem_inc_info
4635 rtx_insn *inc_insn;
4636 rtx_insn *mem_insn;
4638 rtx *mem_loc;
4639 /* A register occurring in the memory address for which we wish to break
4640 the dependence. This must be identical to the destination register of
4641 the increment. */
4642 rtx mem_reg0;
4643 /* Any kind of index that is added to that register. */
4644 rtx mem_index;
4645 /* The constant offset used in the memory address. */
4646 HOST_WIDE_INT mem_constant;
4647 /* The constant added in the increment insn. Negated if the increment is
4648 after the memory address. */
4649 HOST_WIDE_INT inc_constant;
4650 /* The source register used in the increment. May be different from mem_reg0
4651 if the increment occurs before the memory address. */
4652 rtx inc_input;
4655 /* Verify that the memory location described in MII can be replaced with
4656 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4657 insn remains unchanged by this function. */
4659 static rtx
4660 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4662 rtx mem = *mii->mem_loc;
4663 rtx new_mem;
4665 /* Jump through a lot of hoops to keep the attributes up to date. We
4666 do not want to call one of the change address variants that take
4667 an offset even though we know the offset in many cases. These
4668 assume you are changing where the address is pointing by the
4669 offset. */
4670 new_mem = replace_equiv_address_nv (mem, new_addr);
4671 if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4673 if (sched_verbose >= 5)
4674 fprintf (sched_dump, "validation failure\n");
4675 return NULL_RTX;
4678 /* Put back the old one. */
4679 validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4681 return new_mem;
4684 /* Return true if INSN is of a form "a = b op c" where a and b are
4685 regs. op is + if c is a reg and +|- if c is a const. Fill in
4686 informantion in MII about what is found.
4687 BEFORE_MEM indicates whether the increment is found before or after
4688 a corresponding memory reference. */
4690 static bool
4691 parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem)
4693 rtx pat = single_set (insn);
4694 rtx src, cst;
4695 bool regs_equal;
4697 if (RTX_FRAME_RELATED_P (insn) || !pat)
4698 return false;
4700 /* Result must be single reg. */
4701 if (!REG_P (SET_DEST (pat)))
4702 return false;
4704 if (GET_CODE (SET_SRC (pat)) != PLUS)
4705 return false;
4707 mii->inc_insn = insn;
4708 src = SET_SRC (pat);
4709 mii->inc_input = XEXP (src, 0);
4711 if (!REG_P (XEXP (src, 0)))
4712 return false;
4714 if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4715 return false;
4717 cst = XEXP (src, 1);
4718 if (!CONST_INT_P (cst))
4719 return false;
4720 mii->inc_constant = INTVAL (cst);
4722 regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4724 if (!before_mem)
4726 mii->inc_constant = -mii->inc_constant;
4727 if (!regs_equal)
4728 return false;
4731 if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4733 /* Note that the sign has already been reversed for !before_mem. */
4734 #ifdef STACK_GROWS_DOWNWARD
4735 return mii->inc_constant > 0;
4736 #else
4737 return mii->inc_constant < 0;
4738 #endif
4740 return true;
4743 /* Once a suitable mem reference has been found and the corresponding data
4744 in MII has been filled in, this function is called to find a suitable
4745 add or inc insn involving the register we found in the memory
4746 reference. */
4748 static bool
4749 find_inc (struct mem_inc_info *mii, bool backwards)
4751 sd_iterator_def sd_it;
4752 dep_t dep;
4754 sd_it = sd_iterator_start (mii->mem_insn,
4755 backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4756 while (sd_iterator_cond (&sd_it, &dep))
4758 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4759 rtx_insn *pro = DEP_PRO (dep);
4760 rtx_insn *con = DEP_CON (dep);
4761 rtx_insn *inc_cand = backwards ? pro : con;
4762 if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4763 goto next;
4764 if (parse_add_or_inc (mii, inc_cand, backwards))
4766 struct dep_replacement *desc;
4767 df_ref def;
4768 rtx newaddr, newmem;
4770 if (sched_verbose >= 5)
4771 fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4772 INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4774 /* Need to assure that none of the operands of the inc
4775 instruction are assigned to by the mem insn. */
4776 FOR_EACH_INSN_DEF (def, mii->mem_insn)
4777 if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4778 || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4780 if (sched_verbose >= 5)
4781 fprintf (sched_dump,
4782 "inc conflicts with store failure.\n");
4783 goto next;
4786 newaddr = mii->inc_input;
4787 if (mii->mem_index != NULL_RTX)
4788 newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4789 mii->mem_index);
4790 newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4791 mii->mem_constant + mii->inc_constant);
4792 newmem = attempt_change (mii, newaddr);
4793 if (newmem == NULL_RTX)
4794 goto next;
4795 if (sched_verbose >= 5)
4796 fprintf (sched_dump, "successful address replacement\n");
4797 desc = XCNEW (struct dep_replacement);
4798 DEP_REPLACE (dep) = desc;
4799 desc->loc = mii->mem_loc;
4800 desc->newval = newmem;
4801 desc->orig = *desc->loc;
4802 desc->insn = mii->mem_insn;
4803 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4804 INSN_SPEC_BACK_DEPS (con));
4805 if (backwards)
4807 FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4808 add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4809 REG_DEP_TRUE);
4811 else
4813 FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4814 add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4815 REG_DEP_ANTI);
4817 return true;
4819 next:
4820 sd_iterator_next (&sd_it);
4822 return false;
4825 /* A recursive function that walks ADDRESS_OF_X to find memory references
4826 which could be modified during scheduling. We call find_inc for each
4827 one we find that has a recognizable form. MII holds information about
4828 the pair of memory/increment instructions.
4829 We ensure that every instruction with a memory reference (which will be
4830 the location of the replacement) is assigned at most one breakable
4831 dependency. */
4833 static bool
4834 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4836 rtx x = *address_of_x;
4837 enum rtx_code code = GET_CODE (x);
4838 const char *const fmt = GET_RTX_FORMAT (code);
4839 int i;
4841 if (code == MEM)
4843 rtx reg0 = XEXP (x, 0);
4845 mii->mem_loc = address_of_x;
4846 mii->mem_index = NULL_RTX;
4847 mii->mem_constant = 0;
4848 if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4850 mii->mem_constant = INTVAL (XEXP (reg0, 1));
4851 reg0 = XEXP (reg0, 0);
4853 if (GET_CODE (reg0) == PLUS)
4855 mii->mem_index = XEXP (reg0, 1);
4856 reg0 = XEXP (reg0, 0);
4858 if (REG_P (reg0))
4860 df_ref use;
4861 int occurrences = 0;
4863 /* Make sure this reg appears only once in this insn. Can't use
4864 count_occurrences since that only works for pseudos. */
4865 FOR_EACH_INSN_USE (use, mii->mem_insn)
4866 if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use)))
4867 if (++occurrences > 1)
4869 if (sched_verbose >= 5)
4870 fprintf (sched_dump, "mem count failure\n");
4871 return false;
4874 mii->mem_reg0 = reg0;
4875 return find_inc (mii, true) || find_inc (mii, false);
4877 return false;
4880 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4882 /* If REG occurs inside a MEM used in a bit-field reference,
4883 that is unacceptable. */
4884 return false;
4887 /* Time for some deep diving. */
4888 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4890 if (fmt[i] == 'e')
4892 if (find_mem (mii, &XEXP (x, i)))
4893 return true;
4895 else if (fmt[i] == 'E')
4897 int j;
4898 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4899 if (find_mem (mii, &XVECEXP (x, i, j)))
4900 return true;
4903 return false;
4907 /* Examine the instructions between HEAD and TAIL and try to find
4908 dependencies that can be broken by modifying one of the patterns. */
4910 void
4911 find_modifiable_mems (rtx_insn *head, rtx_insn *tail)
4913 rtx_insn *insn, *next_tail = NEXT_INSN (tail);
4914 int success_in_block = 0;
4916 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4918 struct mem_inc_info mii;
4920 if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4921 continue;
4923 mii.mem_insn = insn;
4924 if (find_mem (&mii, &PATTERN (insn)))
4925 success_in_block++;
4927 if (success_in_block && sched_verbose >= 5)
4928 fprintf (sched_dump, "%d candidates for address modification found.\n",
4929 success_in_block);
4932 #endif /* INSN_SCHEDULING */