Daily bump.
[official-gcc.git] / gcc / sched-deps.c
blob5434831d3df2492496fdd69c3bf131140ada2e20
1 /* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992-2015 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
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 "hash-set.h"
30 #include "machmode.h"
31 #include "vec.h"
32 #include "double-int.h"
33 #include "input.h"
34 #include "alias.h"
35 #include "symtab.h"
36 #include "wide-int.h"
37 #include "inchash.h"
38 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
39 #include "tm_p.h"
40 #include "hard-reg-set.h"
41 #include "regs.h"
42 #include "input.h"
43 #include "function.h"
44 #include "flags.h"
45 #include "insn-config.h"
46 #include "insn-attr.h"
47 #include "except.h"
48 #include "recog.h"
49 #include "emit-rtl.h"
50 #include "dominance.h"
51 #include "cfg.h"
52 #include "cfgbuild.h"
53 #include "predict.h"
54 #include "basic-block.h"
55 #include "sched-int.h"
56 #include "params.h"
57 #include "cselib.h"
58 #include "ira.h"
59 #include "target.h"
61 #ifdef INSN_SCHEDULING
63 #ifdef ENABLE_CHECKING
64 #define CHECK (true)
65 #else
66 #define CHECK (false)
67 #endif
69 /* Holds current parameters for the dependency analyzer. */
70 struct sched_deps_info_def *sched_deps_info;
72 /* The data is specific to the Haifa scheduler. */
73 vec<haifa_deps_insn_data_def>
74 h_d_i_d = vNULL;
76 /* Return the major type present in the DS. */
77 enum reg_note
78 ds_to_dk (ds_t ds)
80 if (ds & DEP_TRUE)
81 return REG_DEP_TRUE;
83 if (ds & DEP_OUTPUT)
84 return REG_DEP_OUTPUT;
86 if (ds & DEP_CONTROL)
87 return REG_DEP_CONTROL;
89 gcc_assert (ds & DEP_ANTI);
91 return REG_DEP_ANTI;
94 /* Return equivalent dep_status. */
95 ds_t
96 dk_to_ds (enum reg_note dk)
98 switch (dk)
100 case REG_DEP_TRUE:
101 return DEP_TRUE;
103 case REG_DEP_OUTPUT:
104 return DEP_OUTPUT;
106 case REG_DEP_CONTROL:
107 return DEP_CONTROL;
109 default:
110 gcc_assert (dk == REG_DEP_ANTI);
111 return DEP_ANTI;
115 /* Functions to operate with dependence information container - dep_t. */
117 /* Init DEP with the arguments. */
118 void
119 init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
121 DEP_PRO (dep) = pro;
122 DEP_CON (dep) = con;
123 DEP_TYPE (dep) = type;
124 DEP_STATUS (dep) = ds;
125 DEP_COST (dep) = UNKNOWN_DEP_COST;
126 DEP_NONREG (dep) = 0;
127 DEP_MULTIPLE (dep) = 0;
128 DEP_REPLACE (dep) = NULL;
131 /* Init DEP with the arguments.
132 While most of the scheduler (including targets) only need the major type
133 of the dependency, it is convenient to hide full dep_status from them. */
134 void
135 init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
137 ds_t ds;
139 if ((current_sched_info->flags & USE_DEPS_LIST))
140 ds = dk_to_ds (kind);
141 else
142 ds = 0;
144 init_dep_1 (dep, pro, con, kind, ds);
147 /* Make a copy of FROM in TO. */
148 static void
149 copy_dep (dep_t to, dep_t from)
151 memcpy (to, from, sizeof (*to));
154 static void dump_ds (FILE *, ds_t);
156 /* Define flags for dump_dep (). */
158 /* Dump producer of the dependence. */
159 #define DUMP_DEP_PRO (2)
161 /* Dump consumer of the dependence. */
162 #define DUMP_DEP_CON (4)
164 /* Dump type of the dependence. */
165 #define DUMP_DEP_TYPE (8)
167 /* Dump status of the dependence. */
168 #define DUMP_DEP_STATUS (16)
170 /* Dump all information about the dependence. */
171 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
172 |DUMP_DEP_STATUS)
174 /* Dump DEP to DUMP.
175 FLAGS is a bit mask specifying what information about DEP needs
176 to be printed.
177 If FLAGS has the very first bit set, then dump all information about DEP
178 and propagate this bit into the callee dump functions. */
179 static void
180 dump_dep (FILE *dump, dep_t dep, int flags)
182 if (flags & 1)
183 flags |= DUMP_DEP_ALL;
185 fprintf (dump, "<");
187 if (flags & DUMP_DEP_PRO)
188 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
190 if (flags & DUMP_DEP_CON)
191 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
193 if (flags & DUMP_DEP_TYPE)
195 char t;
196 enum reg_note type = DEP_TYPE (dep);
198 switch (type)
200 case REG_DEP_TRUE:
201 t = 't';
202 break;
204 case REG_DEP_OUTPUT:
205 t = 'o';
206 break;
208 case REG_DEP_CONTROL:
209 t = 'c';
210 break;
212 case REG_DEP_ANTI:
213 t = 'a';
214 break;
216 default:
217 gcc_unreachable ();
218 break;
221 fprintf (dump, "%c; ", t);
224 if (flags & DUMP_DEP_STATUS)
226 if (current_sched_info->flags & USE_DEPS_LIST)
227 dump_ds (dump, DEP_STATUS (dep));
230 fprintf (dump, ">");
233 /* Default flags for dump_dep (). */
234 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
236 /* Dump all fields of DEP to STDERR. */
237 void
238 sd_debug_dep (dep_t dep)
240 dump_dep (stderr, dep, 1);
241 fprintf (stderr, "\n");
244 /* Determine whether DEP is a dependency link of a non-debug insn on a
245 debug insn. */
247 static inline bool
248 depl_on_debug_p (dep_link_t dep)
250 return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
251 && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
254 /* Functions to operate with a single link from the dependencies lists -
255 dep_link_t. */
257 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
258 PREV_NEXT_P. */
259 static void
260 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
262 dep_link_t next = *prev_nextp;
264 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
265 && DEP_LINK_NEXT (l) == NULL);
267 /* Init node being inserted. */
268 DEP_LINK_PREV_NEXTP (l) = prev_nextp;
269 DEP_LINK_NEXT (l) = next;
271 /* Fix next node. */
272 if (next != NULL)
274 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
276 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
279 /* Fix prev node. */
280 *prev_nextp = l;
283 /* Add dep_link LINK to deps_list L. */
284 static void
285 add_to_deps_list (dep_link_t link, deps_list_t l)
287 attach_dep_link (link, &DEPS_LIST_FIRST (l));
289 /* Don't count debug deps. */
290 if (!depl_on_debug_p (link))
291 ++DEPS_LIST_N_LINKS (l);
294 /* Detach dep_link L from the list. */
295 static void
296 detach_dep_link (dep_link_t l)
298 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
299 dep_link_t next = DEP_LINK_NEXT (l);
301 *prev_nextp = next;
303 if (next != NULL)
304 DEP_LINK_PREV_NEXTP (next) = prev_nextp;
306 DEP_LINK_PREV_NEXTP (l) = NULL;
307 DEP_LINK_NEXT (l) = NULL;
310 /* Remove link LINK from list LIST. */
311 static void
312 remove_from_deps_list (dep_link_t link, deps_list_t list)
314 detach_dep_link (link);
316 /* Don't count debug deps. */
317 if (!depl_on_debug_p (link))
318 --DEPS_LIST_N_LINKS (list);
321 /* Move link LINK from list FROM to list TO. */
322 static void
323 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
325 remove_from_deps_list (link, from);
326 add_to_deps_list (link, to);
329 /* Return true of LINK is not attached to any list. */
330 static bool
331 dep_link_is_detached_p (dep_link_t link)
333 return DEP_LINK_PREV_NEXTP (link) == NULL;
336 /* Pool to hold all dependency nodes (dep_node_t). */
337 static alloc_pool dn_pool;
339 /* Number of dep_nodes out there. */
340 static int dn_pool_diff = 0;
342 /* Create a dep_node. */
343 static dep_node_t
344 create_dep_node (void)
346 dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
347 dep_link_t back = DEP_NODE_BACK (n);
348 dep_link_t forw = DEP_NODE_FORW (n);
350 DEP_LINK_NODE (back) = n;
351 DEP_LINK_NEXT (back) = NULL;
352 DEP_LINK_PREV_NEXTP (back) = NULL;
354 DEP_LINK_NODE (forw) = n;
355 DEP_LINK_NEXT (forw) = NULL;
356 DEP_LINK_PREV_NEXTP (forw) = NULL;
358 ++dn_pool_diff;
360 return n;
363 /* Delete dep_node N. N must not be connected to any deps_list. */
364 static void
365 delete_dep_node (dep_node_t n)
367 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
368 && dep_link_is_detached_p (DEP_NODE_FORW (n)));
370 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
372 --dn_pool_diff;
374 pool_free (dn_pool, n);
377 /* Pool to hold dependencies lists (deps_list_t). */
378 static alloc_pool dl_pool;
380 /* Number of deps_lists out there. */
381 static int dl_pool_diff = 0;
383 /* Functions to operate with dependences lists - deps_list_t. */
385 /* Return true if list L is empty. */
386 static bool
387 deps_list_empty_p (deps_list_t l)
389 return DEPS_LIST_N_LINKS (l) == 0;
392 /* Create a new deps_list. */
393 static deps_list_t
394 create_deps_list (void)
396 deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
398 DEPS_LIST_FIRST (l) = NULL;
399 DEPS_LIST_N_LINKS (l) = 0;
401 ++dl_pool_diff;
402 return l;
405 /* Free deps_list L. */
406 static void
407 free_deps_list (deps_list_t l)
409 gcc_assert (deps_list_empty_p (l));
411 --dl_pool_diff;
413 pool_free (dl_pool, l);
416 /* Return true if there is no dep_nodes and deps_lists out there.
417 After the region is scheduled all the dependency nodes and lists
418 should [generally] be returned to pool. */
419 bool
420 deps_pools_are_empty_p (void)
422 return dn_pool_diff == 0 && dl_pool_diff == 0;
425 /* Remove all elements from L. */
426 static void
427 clear_deps_list (deps_list_t l)
431 dep_link_t link = DEPS_LIST_FIRST (l);
433 if (link == NULL)
434 break;
436 remove_from_deps_list (link, l);
438 while (1);
441 /* Decide whether a dependency should be treated as a hard or a speculative
442 dependency. */
443 static bool
444 dep_spec_p (dep_t dep)
446 if (current_sched_info->flags & DO_SPECULATION)
448 if (DEP_STATUS (dep) & SPECULATIVE)
449 return true;
451 if (current_sched_info->flags & DO_PREDICATION)
453 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
454 return true;
456 if (DEP_REPLACE (dep) != NULL)
457 return true;
458 return false;
461 static regset reg_pending_sets;
462 static regset reg_pending_clobbers;
463 static regset reg_pending_uses;
464 static regset reg_pending_control_uses;
465 static enum reg_pending_barrier_mode reg_pending_barrier;
467 /* Hard registers implicitly clobbered or used (or may be implicitly
468 clobbered or used) by the currently analyzed insn. For example,
469 insn in its constraint has one register class. Even if there is
470 currently no hard register in the insn, the particular hard
471 register will be in the insn after reload pass because the
472 constraint requires it. */
473 static HARD_REG_SET implicit_reg_pending_clobbers;
474 static HARD_REG_SET implicit_reg_pending_uses;
476 /* To speed up the test for duplicate dependency links we keep a
477 record of dependencies created by add_dependence when the average
478 number of instructions in a basic block is very large.
480 Studies have shown that there is typically around 5 instructions between
481 branches for typical C code. So we can make a guess that the average
482 basic block is approximately 5 instructions long; we will choose 100X
483 the average size as a very large basic block.
485 Each insn has associated bitmaps for its dependencies. Each bitmap
486 has enough entries to represent a dependency on any other insn in
487 the insn chain. All bitmap for true dependencies cache is
488 allocated then the rest two ones are also allocated. */
489 static bitmap_head *true_dependency_cache = NULL;
490 static bitmap_head *output_dependency_cache = NULL;
491 static bitmap_head *anti_dependency_cache = NULL;
492 static bitmap_head *control_dependency_cache = NULL;
493 static bitmap_head *spec_dependency_cache = NULL;
494 static int cache_size;
496 /* True if we should mark added dependencies as a non-register deps. */
497 static bool mark_as_hard;
499 static int deps_may_trap_p (const_rtx);
500 static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note);
501 static void add_dependence_list (rtx_insn *, rtx_insn_list *, int,
502 enum reg_note, bool);
503 static void add_dependence_list_and_free (struct deps_desc *, rtx_insn *,
504 rtx_insn_list **, int, enum reg_note,
505 bool);
506 static void delete_all_dependences (rtx);
507 static void chain_to_prev_insn (rtx_insn *);
509 static void flush_pending_lists (struct deps_desc *, rtx_insn *, int, int);
510 static void sched_analyze_1 (struct deps_desc *, rtx, rtx_insn *);
511 static void sched_analyze_2 (struct deps_desc *, rtx, rtx_insn *);
512 static void sched_analyze_insn (struct deps_desc *, rtx, rtx_insn *);
514 static bool sched_has_condition_p (const rtx_insn *);
515 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
517 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
518 rtx, rtx);
519 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
521 #ifdef ENABLE_CHECKING
522 static void check_dep (dep_t, bool);
523 #endif
525 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
527 static int
528 deps_may_trap_p (const_rtx mem)
530 const_rtx addr = XEXP (mem, 0);
532 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
534 const_rtx t = get_reg_known_value (REGNO (addr));
535 if (t)
536 addr = t;
538 return rtx_addr_can_trap_p (addr);
542 /* Find the condition under which INSN is executed. If REV is not NULL,
543 it is set to TRUE when the returned comparison should be reversed
544 to get the actual condition. */
545 static rtx
546 sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
548 rtx pat = PATTERN (insn);
549 rtx src;
551 if (rev)
552 *rev = false;
554 if (GET_CODE (pat) == COND_EXEC)
555 return COND_EXEC_TEST (pat);
557 if (!any_condjump_p (insn) || !onlyjump_p (insn))
558 return 0;
560 src = SET_SRC (pc_set (insn));
562 if (XEXP (src, 2) == pc_rtx)
563 return XEXP (src, 0);
564 else if (XEXP (src, 1) == pc_rtx)
566 rtx cond = XEXP (src, 0);
567 enum rtx_code revcode = reversed_comparison_code (cond, insn);
569 if (revcode == UNKNOWN)
570 return 0;
572 if (rev)
573 *rev = true;
574 return cond;
577 return 0;
580 /* Return the condition under which INSN does not execute (i.e. the
581 not-taken condition for a conditional branch), or NULL if we cannot
582 find such a condition. The caller should make a copy of the condition
583 before using it. */
585 sched_get_reverse_condition_uncached (const rtx_insn *insn)
587 bool rev;
588 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
589 if (cond == NULL_RTX)
590 return cond;
591 if (!rev)
593 enum rtx_code revcode = reversed_comparison_code (cond, insn);
594 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
595 XEXP (cond, 0),
596 XEXP (cond, 1));
598 return cond;
601 /* Caching variant of sched_get_condition_with_rev_uncached.
602 We only do actual work the first time we come here for an insn; the
603 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
604 static rtx
605 sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
607 bool tmp;
609 if (INSN_LUID (insn) == 0)
610 return sched_get_condition_with_rev_uncached (insn, rev);
612 if (INSN_CACHED_COND (insn) == const_true_rtx)
613 return NULL_RTX;
615 if (INSN_CACHED_COND (insn) != NULL_RTX)
617 if (rev)
618 *rev = INSN_REVERSE_COND (insn);
619 return INSN_CACHED_COND (insn);
622 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
623 INSN_REVERSE_COND (insn) = tmp;
625 if (INSN_CACHED_COND (insn) == NULL_RTX)
627 INSN_CACHED_COND (insn) = const_true_rtx;
628 return NULL_RTX;
631 if (rev)
632 *rev = INSN_REVERSE_COND (insn);
633 return INSN_CACHED_COND (insn);
636 /* True when we can find a condition under which INSN is executed. */
637 static bool
638 sched_has_condition_p (const rtx_insn *insn)
640 return !! sched_get_condition_with_rev (insn, NULL);
645 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
646 static int
647 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
649 if (COMPARISON_P (cond1)
650 && COMPARISON_P (cond2)
651 && GET_CODE (cond1) ==
652 (rev1==rev2
653 ? reversed_comparison_code (cond2, NULL)
654 : GET_CODE (cond2))
655 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
656 && XEXP (cond1, 1) == XEXP (cond2, 1))
657 return 1;
658 return 0;
661 /* Return true if insn1 and insn2 can never depend on one another because
662 the conditions under which they are executed are mutually exclusive. */
663 bool
664 sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
666 rtx cond1, cond2;
667 bool rev1 = false, rev2 = false;
669 /* df doesn't handle conditional lifetimes entirely correctly;
670 calls mess up the conditional lifetimes. */
671 if (!CALL_P (insn1) && !CALL_P (insn2))
673 cond1 = sched_get_condition_with_rev (insn1, &rev1);
674 cond2 = sched_get_condition_with_rev (insn2, &rev2);
675 if (cond1 && cond2
676 && conditions_mutex_p (cond1, cond2, rev1, rev2)
677 /* Make sure first instruction doesn't affect condition of second
678 instruction if switched. */
679 && !modified_in_p (cond1, insn2)
680 /* Make sure second instruction doesn't affect condition of first
681 instruction if switched. */
682 && !modified_in_p (cond2, insn1))
683 return true;
685 return false;
689 /* Return true if INSN can potentially be speculated with type DS. */
690 bool
691 sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
693 if (HAS_INTERNAL_DEP (insn))
694 return false;
696 if (!NONJUMP_INSN_P (insn))
697 return false;
699 if (SCHED_GROUP_P (insn))
700 return false;
702 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn)))
703 return false;
705 if (side_effects_p (PATTERN (insn)))
706 return false;
708 if (ds & BE_IN_SPEC)
709 /* The following instructions, which depend on a speculatively scheduled
710 instruction, cannot be speculatively scheduled along. */
712 if (may_trap_or_fault_p (PATTERN (insn)))
713 /* If instruction might fault, it cannot be speculatively scheduled.
714 For control speculation it's obvious why and for data speculation
715 it's because the insn might get wrong input if speculation
716 wasn't successful. */
717 return false;
719 if ((ds & BE_IN_DATA)
720 && sched_has_condition_p (insn))
721 /* If this is a predicated instruction, then it cannot be
722 speculatively scheduled. See PR35659. */
723 return false;
726 return true;
729 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
730 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
731 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
732 This function is used to switch sd_iterator to the next list.
733 !!! For internal use only. Might consider moving it to sched-int.h. */
734 void
735 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
736 deps_list_t *list_ptr, bool *resolved_p_ptr)
738 sd_list_types_def types = *types_ptr;
740 if (types & SD_LIST_HARD_BACK)
742 *list_ptr = INSN_HARD_BACK_DEPS (insn);
743 *resolved_p_ptr = false;
744 *types_ptr = types & ~SD_LIST_HARD_BACK;
746 else if (types & SD_LIST_SPEC_BACK)
748 *list_ptr = INSN_SPEC_BACK_DEPS (insn);
749 *resolved_p_ptr = false;
750 *types_ptr = types & ~SD_LIST_SPEC_BACK;
752 else if (types & SD_LIST_FORW)
754 *list_ptr = INSN_FORW_DEPS (insn);
755 *resolved_p_ptr = false;
756 *types_ptr = types & ~SD_LIST_FORW;
758 else if (types & SD_LIST_RES_BACK)
760 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
761 *resolved_p_ptr = true;
762 *types_ptr = types & ~SD_LIST_RES_BACK;
764 else if (types & SD_LIST_RES_FORW)
766 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
767 *resolved_p_ptr = true;
768 *types_ptr = types & ~SD_LIST_RES_FORW;
770 else
772 *list_ptr = NULL;
773 *resolved_p_ptr = false;
774 *types_ptr = SD_LIST_NONE;
778 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
780 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
782 int size = 0;
784 while (list_types != SD_LIST_NONE)
786 deps_list_t list;
787 bool resolved_p;
789 sd_next_list (insn, &list_types, &list, &resolved_p);
790 if (list)
791 size += DEPS_LIST_N_LINKS (list);
794 return size;
797 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
799 bool
800 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
802 while (list_types != SD_LIST_NONE)
804 deps_list_t list;
805 bool resolved_p;
807 sd_next_list (insn, &list_types, &list, &resolved_p);
808 if (!deps_list_empty_p (list))
809 return false;
812 return true;
815 /* Initialize data for INSN. */
816 void
817 sd_init_insn (rtx insn)
819 INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
820 INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
821 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
822 INSN_FORW_DEPS (insn) = create_deps_list ();
823 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
825 /* ??? It would be nice to allocate dependency caches here. */
828 /* Free data for INSN. */
829 void
830 sd_finish_insn (rtx insn)
832 /* ??? It would be nice to deallocate dependency caches here. */
834 free_deps_list (INSN_HARD_BACK_DEPS (insn));
835 INSN_HARD_BACK_DEPS (insn) = NULL;
837 free_deps_list (INSN_SPEC_BACK_DEPS (insn));
838 INSN_SPEC_BACK_DEPS (insn) = NULL;
840 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
841 INSN_RESOLVED_BACK_DEPS (insn) = NULL;
843 free_deps_list (INSN_FORW_DEPS (insn));
844 INSN_FORW_DEPS (insn) = NULL;
846 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
847 INSN_RESOLVED_FORW_DEPS (insn) = NULL;
850 /* Find a dependency between producer PRO and consumer CON.
851 Search through resolved dependency lists if RESOLVED_P is true.
852 If no such dependency is found return NULL,
853 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
854 with an iterator pointing to it. */
855 static dep_t
856 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
857 sd_iterator_def *sd_it_ptr)
859 sd_list_types_def pro_list_type;
860 sd_list_types_def con_list_type;
861 sd_iterator_def sd_it;
862 dep_t dep;
863 bool found_p = false;
865 if (resolved_p)
867 pro_list_type = SD_LIST_RES_FORW;
868 con_list_type = SD_LIST_RES_BACK;
870 else
872 pro_list_type = SD_LIST_FORW;
873 con_list_type = SD_LIST_BACK;
876 /* Walk through either back list of INSN or forw list of ELEM
877 depending on which one is shorter. */
878 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
880 /* Find the dep_link with producer PRO in consumer's back_deps. */
881 FOR_EACH_DEP (con, con_list_type, sd_it, dep)
882 if (DEP_PRO (dep) == pro)
884 found_p = true;
885 break;
888 else
890 /* Find the dep_link with consumer CON in producer's forw_deps. */
891 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
892 if (DEP_CON (dep) == con)
894 found_p = true;
895 break;
899 if (found_p)
901 if (sd_it_ptr != NULL)
902 *sd_it_ptr = sd_it;
904 return dep;
907 return NULL;
910 /* Find a dependency between producer PRO and consumer CON.
911 Use dependency [if available] to check if dependency is present at all.
912 Search through resolved dependency lists if RESOLVED_P is true.
913 If the dependency or NULL if none found. */
914 dep_t
915 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
917 if (true_dependency_cache != NULL)
918 /* Avoiding the list walk below can cut compile times dramatically
919 for some code. */
921 int elem_luid = INSN_LUID (pro);
922 int insn_luid = INSN_LUID (con);
924 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
925 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
926 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
927 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
928 return NULL;
931 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
934 /* Add or update a dependence described by DEP.
935 MEM1 and MEM2, if non-null, correspond to memory locations in case of
936 data speculation.
938 The function returns a value indicating if an old entry has been changed
939 or a new entry has been added to insn's backward deps.
941 This function merely checks if producer and consumer is the same insn
942 and doesn't create a dep in this case. Actual manipulation of
943 dependence data structures is performed in add_or_update_dep_1. */
944 static enum DEPS_ADJUST_RESULT
945 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
947 rtx_insn *elem = DEP_PRO (dep);
948 rtx_insn *insn = DEP_CON (dep);
950 gcc_assert (INSN_P (insn) && INSN_P (elem));
952 /* Don't depend an insn on itself. */
953 if (insn == elem)
955 if (sched_deps_info->generate_spec_deps)
956 /* INSN has an internal dependence, which we can't overcome. */
957 HAS_INTERNAL_DEP (insn) = 1;
959 return DEP_NODEP;
962 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
965 /* Ask dependency caches what needs to be done for dependence DEP.
966 Return DEP_CREATED if new dependence should be created and there is no
967 need to try to find one searching the dependencies lists.
968 Return DEP_PRESENT if there already is a dependence described by DEP and
969 hence nothing is to be done.
970 Return DEP_CHANGED if there already is a dependence, but it should be
971 updated to incorporate additional information from DEP. */
972 static enum DEPS_ADJUST_RESULT
973 ask_dependency_caches (dep_t dep)
975 int elem_luid = INSN_LUID (DEP_PRO (dep));
976 int insn_luid = INSN_LUID (DEP_CON (dep));
978 gcc_assert (true_dependency_cache != NULL
979 && output_dependency_cache != NULL
980 && anti_dependency_cache != NULL
981 && control_dependency_cache != NULL);
983 if (!(current_sched_info->flags & USE_DEPS_LIST))
985 enum reg_note present_dep_type;
987 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
988 present_dep_type = REG_DEP_TRUE;
989 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
990 present_dep_type = REG_DEP_OUTPUT;
991 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
992 present_dep_type = REG_DEP_ANTI;
993 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
994 present_dep_type = REG_DEP_CONTROL;
995 else
996 /* There is no existing dep so it should be created. */
997 return DEP_CREATED;
999 if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
1000 /* DEP does not add anything to the existing dependence. */
1001 return DEP_PRESENT;
1003 else
1005 ds_t present_dep_types = 0;
1007 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
1008 present_dep_types |= DEP_TRUE;
1009 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
1010 present_dep_types |= DEP_OUTPUT;
1011 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
1012 present_dep_types |= DEP_ANTI;
1013 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
1014 present_dep_types |= DEP_CONTROL;
1016 if (present_dep_types == 0)
1017 /* There is no existing dep so it should be created. */
1018 return DEP_CREATED;
1020 if (!(current_sched_info->flags & DO_SPECULATION)
1021 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
1023 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
1024 == present_dep_types)
1025 /* DEP does not add anything to the existing dependence. */
1026 return DEP_PRESENT;
1028 else
1030 /* Only true dependencies can be data speculative and
1031 only anti dependencies can be control speculative. */
1032 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1033 == present_dep_types);
1035 /* if (DEP is SPECULATIVE) then
1036 ..we should update DEP_STATUS
1037 else
1038 ..we should reset existing dep to non-speculative. */
1042 return DEP_CHANGED;
1045 /* Set dependency caches according to DEP. */
1046 static void
1047 set_dependency_caches (dep_t dep)
1049 int elem_luid = INSN_LUID (DEP_PRO (dep));
1050 int insn_luid = INSN_LUID (DEP_CON (dep));
1052 if (!(current_sched_info->flags & USE_DEPS_LIST))
1054 switch (DEP_TYPE (dep))
1056 case REG_DEP_TRUE:
1057 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1058 break;
1060 case REG_DEP_OUTPUT:
1061 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1062 break;
1064 case REG_DEP_ANTI:
1065 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1066 break;
1068 case REG_DEP_CONTROL:
1069 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1070 break;
1072 default:
1073 gcc_unreachable ();
1076 else
1078 ds_t ds = DEP_STATUS (dep);
1080 if (ds & DEP_TRUE)
1081 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1082 if (ds & DEP_OUTPUT)
1083 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1084 if (ds & DEP_ANTI)
1085 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1086 if (ds & DEP_CONTROL)
1087 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1089 if (ds & SPECULATIVE)
1091 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1092 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1097 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1098 caches accordingly. */
1099 static void
1100 update_dependency_caches (dep_t dep, enum reg_note old_type)
1102 int elem_luid = INSN_LUID (DEP_PRO (dep));
1103 int insn_luid = INSN_LUID (DEP_CON (dep));
1105 /* Clear corresponding cache entry because type of the link
1106 may have changed. Keep them if we use_deps_list. */
1107 if (!(current_sched_info->flags & USE_DEPS_LIST))
1109 switch (old_type)
1111 case REG_DEP_OUTPUT:
1112 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1113 break;
1115 case REG_DEP_ANTI:
1116 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1117 break;
1119 case REG_DEP_CONTROL:
1120 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1121 break;
1123 default:
1124 gcc_unreachable ();
1128 set_dependency_caches (dep);
1131 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1132 static void
1133 change_spec_dep_to_hard (sd_iterator_def sd_it)
1135 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1136 dep_link_t link = DEP_NODE_BACK (node);
1137 dep_t dep = DEP_NODE_DEP (node);
1138 rtx_insn *elem = DEP_PRO (dep);
1139 rtx_insn *insn = DEP_CON (dep);
1141 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1143 DEP_STATUS (dep) &= ~SPECULATIVE;
1145 if (true_dependency_cache != NULL)
1146 /* Clear the cache entry. */
1147 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1148 INSN_LUID (elem));
1151 /* Update DEP to incorporate information from NEW_DEP.
1152 SD_IT points to DEP in case it should be moved to another list.
1153 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1154 data-speculative dependence should be updated. */
1155 static enum DEPS_ADJUST_RESULT
1156 update_dep (dep_t dep, dep_t new_dep,
1157 sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1158 rtx mem1 ATTRIBUTE_UNUSED,
1159 rtx mem2 ATTRIBUTE_UNUSED)
1161 enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1162 enum reg_note old_type = DEP_TYPE (dep);
1163 bool was_spec = dep_spec_p (dep);
1165 DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1166 DEP_MULTIPLE (dep) = 1;
1168 /* If this is a more restrictive type of dependence than the
1169 existing one, then change the existing dependence to this
1170 type. */
1171 if ((int) DEP_TYPE (new_dep) < (int) old_type)
1173 DEP_TYPE (dep) = DEP_TYPE (new_dep);
1174 res = DEP_CHANGED;
1177 if (current_sched_info->flags & USE_DEPS_LIST)
1178 /* Update DEP_STATUS. */
1180 ds_t dep_status = DEP_STATUS (dep);
1181 ds_t ds = DEP_STATUS (new_dep);
1182 ds_t new_status = ds | dep_status;
1184 if (new_status & SPECULATIVE)
1186 /* Either existing dep or a dep we're adding or both are
1187 speculative. */
1188 if (!(ds & SPECULATIVE)
1189 || !(dep_status & SPECULATIVE))
1190 /* The new dep can't be speculative. */
1191 new_status &= ~SPECULATIVE;
1192 else
1194 /* Both are speculative. Merge probabilities. */
1195 if (mem1 != NULL)
1197 dw_t dw;
1199 dw = estimate_dep_weak (mem1, mem2);
1200 ds = set_dep_weak (ds, BEGIN_DATA, dw);
1203 new_status = ds_merge (dep_status, ds);
1207 ds = new_status;
1209 if (dep_status != ds)
1211 DEP_STATUS (dep) = ds;
1212 res = DEP_CHANGED;
1216 if (was_spec && !dep_spec_p (dep))
1217 /* The old dep was speculative, but now it isn't. */
1218 change_spec_dep_to_hard (sd_it);
1220 if (true_dependency_cache != NULL
1221 && res == DEP_CHANGED)
1222 update_dependency_caches (dep, old_type);
1224 return res;
1227 /* Add or update a dependence described by DEP.
1228 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1229 data speculation.
1231 The function returns a value indicating if an old entry has been changed
1232 or a new entry has been added to insn's backward deps or nothing has
1233 been updated at all. */
1234 static enum DEPS_ADJUST_RESULT
1235 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1236 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1238 bool maybe_present_p = true;
1239 bool present_p = false;
1241 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1242 && DEP_PRO (new_dep) != DEP_CON (new_dep));
1244 #ifdef ENABLE_CHECKING
1245 check_dep (new_dep, mem1 != NULL);
1246 #endif
1248 if (true_dependency_cache != NULL)
1250 switch (ask_dependency_caches (new_dep))
1252 case DEP_PRESENT:
1253 dep_t present_dep;
1254 sd_iterator_def sd_it;
1256 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1257 DEP_CON (new_dep),
1258 resolved_p, &sd_it);
1259 DEP_MULTIPLE (present_dep) = 1;
1260 return DEP_PRESENT;
1262 case DEP_CHANGED:
1263 maybe_present_p = true;
1264 present_p = true;
1265 break;
1267 case DEP_CREATED:
1268 maybe_present_p = false;
1269 present_p = false;
1270 break;
1272 default:
1273 gcc_unreachable ();
1274 break;
1278 /* Check that we don't already have this dependence. */
1279 if (maybe_present_p)
1281 dep_t present_dep;
1282 sd_iterator_def sd_it;
1284 gcc_assert (true_dependency_cache == NULL || present_p);
1286 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1287 DEP_CON (new_dep),
1288 resolved_p, &sd_it);
1290 if (present_dep != NULL)
1291 /* We found an existing dependency between ELEM and INSN. */
1292 return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1293 else
1294 /* We didn't find a dep, it shouldn't present in the cache. */
1295 gcc_assert (!present_p);
1298 /* Might want to check one level of transitivity to save conses.
1299 This check should be done in maybe_add_or_update_dep_1.
1300 Since we made it to add_or_update_dep_1, we must create
1301 (or update) a link. */
1303 if (mem1 != NULL_RTX)
1305 gcc_assert (sched_deps_info->generate_spec_deps);
1306 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1307 estimate_dep_weak (mem1, mem2));
1310 sd_add_dep (new_dep, resolved_p);
1312 return DEP_CREATED;
1315 /* Initialize BACK_LIST_PTR with consumer's backward list and
1316 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1317 initialize with lists that hold resolved deps. */
1318 static void
1319 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1320 deps_list_t *back_list_ptr,
1321 deps_list_t *forw_list_ptr)
1323 rtx_insn *con = DEP_CON (dep);
1325 if (!resolved_p)
1327 if (dep_spec_p (dep))
1328 *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1329 else
1330 *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1332 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1334 else
1336 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1337 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1341 /* Add dependence described by DEP.
1342 If RESOLVED_P is true treat the dependence as a resolved one. */
1343 void
1344 sd_add_dep (dep_t dep, bool resolved_p)
1346 dep_node_t n = create_dep_node ();
1347 deps_list_t con_back_deps;
1348 deps_list_t pro_forw_deps;
1349 rtx_insn *elem = DEP_PRO (dep);
1350 rtx_insn *insn = DEP_CON (dep);
1352 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1354 if ((current_sched_info->flags & DO_SPECULATION) == 0
1355 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1356 DEP_STATUS (dep) &= ~SPECULATIVE;
1358 copy_dep (DEP_NODE_DEP (n), dep);
1360 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1362 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1364 #ifdef ENABLE_CHECKING
1365 check_dep (dep, false);
1366 #endif
1368 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1370 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1371 in the bitmap caches of dependency information. */
1372 if (true_dependency_cache != NULL)
1373 set_dependency_caches (dep);
1376 /* Add or update backward dependence between INSN and ELEM
1377 with given type DEP_TYPE and dep_status DS.
1378 This function is a convenience wrapper. */
1379 enum DEPS_ADJUST_RESULT
1380 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1382 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1385 /* Resolved dependence pointed to by SD_IT.
1386 SD_IT will advance to the next element. */
1387 void
1388 sd_resolve_dep (sd_iterator_def sd_it)
1390 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1391 dep_t dep = DEP_NODE_DEP (node);
1392 rtx_insn *pro = DEP_PRO (dep);
1393 rtx_insn *con = DEP_CON (dep);
1395 if (dep_spec_p (dep))
1396 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1397 INSN_RESOLVED_BACK_DEPS (con));
1398 else
1399 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1400 INSN_RESOLVED_BACK_DEPS (con));
1402 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1403 INSN_RESOLVED_FORW_DEPS (pro));
1406 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1407 pointed to by SD_IT to unresolved state. */
1408 void
1409 sd_unresolve_dep (sd_iterator_def sd_it)
1411 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1412 dep_t dep = DEP_NODE_DEP (node);
1413 rtx_insn *pro = DEP_PRO (dep);
1414 rtx_insn *con = DEP_CON (dep);
1416 if (dep_spec_p (dep))
1417 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1418 INSN_SPEC_BACK_DEPS (con));
1419 else
1420 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1421 INSN_HARD_BACK_DEPS (con));
1423 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1424 INSN_FORW_DEPS (pro));
1427 /* Make TO depend on all the FROM's producers.
1428 If RESOLVED_P is true add dependencies to the resolved lists. */
1429 void
1430 sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p)
1432 sd_list_types_def list_type;
1433 sd_iterator_def sd_it;
1434 dep_t dep;
1436 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1438 FOR_EACH_DEP (from, list_type, sd_it, dep)
1440 dep_def _new_dep, *new_dep = &_new_dep;
1442 copy_dep (new_dep, dep);
1443 DEP_CON (new_dep) = to;
1444 sd_add_dep (new_dep, resolved_p);
1448 /* Remove a dependency referred to by SD_IT.
1449 SD_IT will point to the next dependence after removal. */
1450 void
1451 sd_delete_dep (sd_iterator_def sd_it)
1453 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1454 dep_t dep = DEP_NODE_DEP (n);
1455 rtx_insn *pro = DEP_PRO (dep);
1456 rtx_insn *con = DEP_CON (dep);
1457 deps_list_t con_back_deps;
1458 deps_list_t pro_forw_deps;
1460 if (true_dependency_cache != NULL)
1462 int elem_luid = INSN_LUID (pro);
1463 int insn_luid = INSN_LUID (con);
1465 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1466 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1467 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1468 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1470 if (current_sched_info->flags & DO_SPECULATION)
1471 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1474 get_back_and_forw_lists (dep, sd_it.resolved_p,
1475 &con_back_deps, &pro_forw_deps);
1477 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1478 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1480 delete_dep_node (n);
1483 /* Dump size of the lists. */
1484 #define DUMP_LISTS_SIZE (2)
1486 /* Dump dependencies of the lists. */
1487 #define DUMP_LISTS_DEPS (4)
1489 /* Dump all information about the lists. */
1490 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1492 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1493 FLAGS is a bit mask specifying what information about the lists needs
1494 to be printed.
1495 If FLAGS has the very first bit set, then dump all information about
1496 the lists and propagate this bit into the callee dump functions. */
1497 static void
1498 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1500 sd_iterator_def sd_it;
1501 dep_t dep;
1502 int all;
1504 all = (flags & 1);
1506 if (all)
1507 flags |= DUMP_LISTS_ALL;
1509 fprintf (dump, "[");
1511 if (flags & DUMP_LISTS_SIZE)
1512 fprintf (dump, "%d; ", sd_lists_size (insn, types));
1514 if (flags & DUMP_LISTS_DEPS)
1516 FOR_EACH_DEP (insn, types, sd_it, dep)
1518 dump_dep (dump, dep, dump_dep_flags | all);
1519 fprintf (dump, " ");
1524 /* Dump all information about deps_lists of INSN specified by TYPES
1525 to STDERR. */
1526 void
1527 sd_debug_lists (rtx insn, sd_list_types_def types)
1529 dump_lists (stderr, insn, types, 1);
1530 fprintf (stderr, "\n");
1533 /* A wrapper around add_dependence_1, to add a dependence of CON on
1534 PRO, with type DEP_TYPE. This function implements special handling
1535 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1536 the type to REG_DEP_ANTI if we can determine that predication is
1537 impossible; otherwise we add additional true dependencies on the
1538 INSN_COND_DEPS list of the jump (which PRO must be). */
1539 void
1540 add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1542 if (dep_type == REG_DEP_CONTROL
1543 && !(current_sched_info->flags & DO_PREDICATION))
1544 dep_type = REG_DEP_ANTI;
1546 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1547 so we must also make the insn dependent on the setter of the
1548 condition. */
1549 if (dep_type == REG_DEP_CONTROL)
1551 rtx_insn *real_pro = pro;
1552 rtx_insn *other = real_insn_for_shadow (real_pro);
1553 rtx cond;
1555 if (other != NULL_RTX)
1556 real_pro = other;
1557 cond = sched_get_reverse_condition_uncached (real_pro);
1558 /* Verify that the insn does not use a different value in
1559 the condition register than the one that was present at
1560 the jump. */
1561 if (cond == NULL_RTX)
1562 dep_type = REG_DEP_ANTI;
1563 else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1565 HARD_REG_SET uses;
1566 CLEAR_HARD_REG_SET (uses);
1567 note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1568 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1569 dep_type = REG_DEP_ANTI;
1571 if (dep_type == REG_DEP_CONTROL)
1573 if (sched_verbose >= 5)
1574 fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1575 INSN_UID (real_pro));
1576 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1577 REG_DEP_TRUE, false);
1581 add_dependence_1 (con, pro, dep_type);
1584 /* A convenience wrapper to operate on an entire list. HARD should be
1585 true if DEP_NONREG should be set on newly created dependencies. */
1587 static void
1588 add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1589 enum reg_note dep_type, bool hard)
1591 mark_as_hard = hard;
1592 for (; list; list = list->next ())
1594 if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1595 add_dependence (insn, list->insn (), dep_type);
1597 mark_as_hard = false;
1600 /* Similar, but free *LISTP at the same time, when the context
1601 is not readonly. HARD should be true if DEP_NONREG should be set on
1602 newly created dependencies. */
1604 static void
1605 add_dependence_list_and_free (struct deps_desc *deps, rtx_insn *insn,
1606 rtx_insn_list **listp,
1607 int uncond, enum reg_note dep_type, bool hard)
1609 add_dependence_list (insn, *listp, uncond, dep_type, hard);
1611 /* We don't want to short-circuit dependencies involving debug
1612 insns, because they may cause actual dependencies to be
1613 disregarded. */
1614 if (deps->readonly || DEBUG_INSN_P (insn))
1615 return;
1617 free_INSN_LIST_list (listp);
1620 /* Remove all occurrences of INSN from LIST. Return the number of
1621 occurrences removed. */
1623 static int
1624 remove_from_dependence_list (rtx insn, rtx_insn_list **listp)
1626 int removed = 0;
1628 while (*listp)
1630 if ((*listp)->insn () == insn)
1632 remove_free_INSN_LIST_node (listp);
1633 removed++;
1634 continue;
1637 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1640 return removed;
1643 /* Same as above, but process two lists at once. */
1644 static int
1645 remove_from_both_dependence_lists (rtx insn,
1646 rtx_insn_list **listp,
1647 rtx_expr_list **exprp)
1649 int removed = 0;
1651 while (*listp)
1653 if (XEXP (*listp, 0) == insn)
1655 remove_free_INSN_LIST_node (listp);
1656 remove_free_EXPR_LIST_node (exprp);
1657 removed++;
1658 continue;
1661 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1662 exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1665 return removed;
1668 /* Clear all dependencies for an insn. */
1669 static void
1670 delete_all_dependences (rtx insn)
1672 sd_iterator_def sd_it;
1673 dep_t dep;
1675 /* The below cycle can be optimized to clear the caches and back_deps
1676 in one call but that would provoke duplication of code from
1677 delete_dep (). */
1679 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1680 sd_iterator_cond (&sd_it, &dep);)
1681 sd_delete_dep (sd_it);
1684 /* All insns in a scheduling group except the first should only have
1685 dependencies on the previous insn in the group. So we find the
1686 first instruction in the scheduling group by walking the dependence
1687 chains backwards. Then we add the dependencies for the group to
1688 the previous nonnote insn. */
1690 static void
1691 chain_to_prev_insn (rtx_insn *insn)
1693 sd_iterator_def sd_it;
1694 dep_t dep;
1695 rtx_insn *prev_nonnote;
1697 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1699 rtx_insn *i = insn;
1700 rtx_insn *pro = DEP_PRO (dep);
1704 i = prev_nonnote_insn (i);
1706 if (pro == i)
1707 goto next_link;
1708 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1710 if (! sched_insns_conditions_mutex_p (i, pro))
1711 add_dependence (i, pro, DEP_TYPE (dep));
1712 next_link:;
1715 delete_all_dependences (insn);
1717 prev_nonnote = prev_nonnote_nondebug_insn (insn);
1718 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1719 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1720 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1723 /* Process an insn's memory dependencies. There are four kinds of
1724 dependencies:
1726 (0) read dependence: read follows read
1727 (1) true dependence: read follows write
1728 (2) output dependence: write follows write
1729 (3) anti dependence: write follows read
1731 We are careful to build only dependencies which actually exist, and
1732 use transitivity to avoid building too many links. */
1734 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1735 The MEM is a memory reference contained within INSN, which we are saving
1736 so that we can do memory aliasing on it. */
1738 static void
1739 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1740 rtx_insn *insn, rtx mem)
1742 rtx_insn_list **insn_list;
1743 rtx_insn_list *insn_node;
1744 rtx_expr_list **mem_list;
1745 rtx_expr_list *mem_node;
1747 gcc_assert (!deps->readonly);
1748 if (read_p)
1750 insn_list = &deps->pending_read_insns;
1751 mem_list = &deps->pending_read_mems;
1752 if (!DEBUG_INSN_P (insn))
1753 deps->pending_read_list_length++;
1755 else
1757 insn_list = &deps->pending_write_insns;
1758 mem_list = &deps->pending_write_mems;
1759 deps->pending_write_list_length++;
1762 insn_node = alloc_INSN_LIST (insn, *insn_list);
1763 *insn_list = insn_node;
1765 if (sched_deps_info->use_cselib)
1767 mem = shallow_copy_rtx (mem);
1768 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1769 GET_MODE (mem), insn);
1771 mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1772 *mem_list = mem_node;
1775 /* Make a dependency between every memory reference on the pending lists
1776 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1777 dependencies for a read operation, similarly with FOR_WRITE. */
1779 static void
1780 flush_pending_lists (struct deps_desc *deps, rtx_insn *insn, int for_read,
1781 int for_write)
1783 if (for_write)
1785 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1786 1, REG_DEP_ANTI, true);
1787 if (!deps->readonly)
1789 free_EXPR_LIST_list (&deps->pending_read_mems);
1790 deps->pending_read_list_length = 0;
1794 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1795 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1796 true);
1798 add_dependence_list_and_free (deps, insn,
1799 &deps->last_pending_memory_flush, 1,
1800 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1801 true);
1803 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1804 REG_DEP_ANTI, true);
1806 if (DEBUG_INSN_P (insn))
1808 if (for_write)
1809 free_INSN_LIST_list (&deps->pending_read_insns);
1810 free_INSN_LIST_list (&deps->pending_write_insns);
1811 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1812 free_INSN_LIST_list (&deps->pending_jump_insns);
1815 if (!deps->readonly)
1817 free_EXPR_LIST_list (&deps->pending_write_mems);
1818 deps->pending_write_list_length = 0;
1820 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1821 deps->pending_flush_length = 1;
1823 mark_as_hard = false;
1826 /* Instruction which dependencies we are analyzing. */
1827 static rtx_insn *cur_insn = NULL;
1829 /* Implement hooks for haifa scheduler. */
1831 static void
1832 haifa_start_insn (rtx_insn *insn)
1834 gcc_assert (insn && !cur_insn);
1836 cur_insn = insn;
1839 static void
1840 haifa_finish_insn (void)
1842 cur_insn = NULL;
1845 void
1846 haifa_note_reg_set (int regno)
1848 SET_REGNO_REG_SET (reg_pending_sets, regno);
1851 void
1852 haifa_note_reg_clobber (int regno)
1854 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1857 void
1858 haifa_note_reg_use (int regno)
1860 SET_REGNO_REG_SET (reg_pending_uses, regno);
1863 static void
1864 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1866 if (!(ds & SPECULATIVE))
1868 mem = NULL_RTX;
1869 pending_mem = NULL_RTX;
1871 else
1872 gcc_assert (ds & BEGIN_DATA);
1875 dep_def _dep, *dep = &_dep;
1877 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1878 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1879 DEP_NONREG (dep) = 1;
1880 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1885 static void
1886 haifa_note_dep (rtx_insn *elem, ds_t ds)
1888 dep_def _dep;
1889 dep_t dep = &_dep;
1891 init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1892 if (mark_as_hard)
1893 DEP_NONREG (dep) = 1;
1894 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1897 static void
1898 note_reg_use (int r)
1900 if (sched_deps_info->note_reg_use)
1901 sched_deps_info->note_reg_use (r);
1904 static void
1905 note_reg_set (int r)
1907 if (sched_deps_info->note_reg_set)
1908 sched_deps_info->note_reg_set (r);
1911 static void
1912 note_reg_clobber (int r)
1914 if (sched_deps_info->note_reg_clobber)
1915 sched_deps_info->note_reg_clobber (r);
1918 static void
1919 note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1921 if (sched_deps_info->note_mem_dep)
1922 sched_deps_info->note_mem_dep (m1, m2, e, ds);
1925 static void
1926 note_dep (rtx_insn *e, ds_t ds)
1928 if (sched_deps_info->note_dep)
1929 sched_deps_info->note_dep (e, ds);
1932 /* Return corresponding to DS reg_note. */
1933 enum reg_note
1934 ds_to_dt (ds_t ds)
1936 if (ds & DEP_TRUE)
1937 return REG_DEP_TRUE;
1938 else if (ds & DEP_OUTPUT)
1939 return REG_DEP_OUTPUT;
1940 else if (ds & DEP_ANTI)
1941 return REG_DEP_ANTI;
1942 else
1944 gcc_assert (ds & DEP_CONTROL);
1945 return REG_DEP_CONTROL;
1951 /* Functions for computation of info needed for register pressure
1952 sensitive insn scheduling. */
1955 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1956 static struct reg_use_data *
1957 create_insn_reg_use (int regno, rtx_insn *insn)
1959 struct reg_use_data *use;
1961 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1962 use->regno = regno;
1963 use->insn = insn;
1964 use->next_insn_use = INSN_REG_USE_LIST (insn);
1965 INSN_REG_USE_LIST (insn) = use;
1966 return use;
1969 /* Allocate reg_set_data structure for REGNO and INSN. */
1970 static void
1971 create_insn_reg_set (int regno, rtx insn)
1973 struct reg_set_data *set;
1975 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1976 set->regno = regno;
1977 set->insn = insn;
1978 set->next_insn_set = INSN_REG_SET_LIST (insn);
1979 INSN_REG_SET_LIST (insn) = set;
1982 /* Set up insn register uses for INSN and dependency context DEPS. */
1983 static void
1984 setup_insn_reg_uses (struct deps_desc *deps, rtx_insn *insn)
1986 unsigned i;
1987 reg_set_iterator rsi;
1988 struct reg_use_data *use, *use2, *next;
1989 struct deps_reg *reg_last;
1991 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1993 if (i < FIRST_PSEUDO_REGISTER
1994 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1995 continue;
1997 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1998 && ! REGNO_REG_SET_P (reg_pending_sets, i)
1999 && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
2000 /* Ignore use which is not dying. */
2001 continue;
2003 use = create_insn_reg_use (i, insn);
2004 use->next_regno_use = use;
2005 reg_last = &deps->reg_last[i];
2007 /* Create the cycle list of uses. */
2008 for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
2010 use2 = create_insn_reg_use (i, list->insn ());
2011 next = use->next_regno_use;
2012 use->next_regno_use = use2;
2013 use2->next_regno_use = next;
2018 /* Register pressure info for the currently processed insn. */
2019 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
2021 /* Return TRUE if INSN has the use structure for REGNO. */
2022 static bool
2023 insn_use_p (rtx insn, int regno)
2025 struct reg_use_data *use;
2027 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2028 if (use->regno == regno)
2029 return true;
2030 return false;
2033 /* Update the register pressure info after birth of pseudo register REGNO
2034 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2035 the register is in clobber or unused after the insn. */
2036 static void
2037 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2039 int incr, new_incr;
2040 enum reg_class cl;
2042 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2043 cl = sched_regno_pressure_class[regno];
2044 if (cl != NO_REGS)
2046 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2047 if (clobber_p)
2049 new_incr = reg_pressure_info[cl].clobber_increase + incr;
2050 reg_pressure_info[cl].clobber_increase = new_incr;
2052 else if (unused_p)
2054 new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2055 reg_pressure_info[cl].unused_set_increase = new_incr;
2057 else
2059 new_incr = reg_pressure_info[cl].set_increase + incr;
2060 reg_pressure_info[cl].set_increase = new_incr;
2061 if (! insn_use_p (insn, regno))
2062 reg_pressure_info[cl].change += incr;
2063 create_insn_reg_set (regno, insn);
2065 gcc_assert (new_incr < (1 << INCREASE_BITS));
2069 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2070 hard registers involved in the birth. */
2071 static void
2072 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2073 bool clobber_p, bool unused_p)
2075 enum reg_class cl;
2076 int new_incr, last = regno + nregs;
2078 while (regno < last)
2080 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2081 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2083 cl = sched_regno_pressure_class[regno];
2084 if (cl != NO_REGS)
2086 if (clobber_p)
2088 new_incr = reg_pressure_info[cl].clobber_increase + 1;
2089 reg_pressure_info[cl].clobber_increase = new_incr;
2091 else if (unused_p)
2093 new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2094 reg_pressure_info[cl].unused_set_increase = new_incr;
2096 else
2098 new_incr = reg_pressure_info[cl].set_increase + 1;
2099 reg_pressure_info[cl].set_increase = new_incr;
2100 if (! insn_use_p (insn, regno))
2101 reg_pressure_info[cl].change += 1;
2102 create_insn_reg_set (regno, insn);
2104 gcc_assert (new_incr < (1 << INCREASE_BITS));
2107 regno++;
2111 /* Update the register pressure info after birth of pseudo or hard
2112 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2113 correspondingly that the register is in clobber or unused after the
2114 insn. */
2115 static void
2116 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2118 int regno;
2120 if (GET_CODE (reg) == SUBREG)
2121 reg = SUBREG_REG (reg);
2123 if (! REG_P (reg))
2124 return;
2126 regno = REGNO (reg);
2127 if (regno < FIRST_PSEUDO_REGISTER)
2128 mark_insn_hard_regno_birth (insn, regno,
2129 hard_regno_nregs[regno][GET_MODE (reg)],
2130 clobber_p, unused_p);
2131 else
2132 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2135 /* Update the register pressure info after death of pseudo register
2136 REGNO. */
2137 static void
2138 mark_pseudo_death (int regno)
2140 int incr;
2141 enum reg_class cl;
2143 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2144 cl = sched_regno_pressure_class[regno];
2145 if (cl != NO_REGS)
2147 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2148 reg_pressure_info[cl].change -= incr;
2152 /* Like mark_pseudo_death except that NREGS saying how many hard
2153 registers involved in the death. */
2154 static void
2155 mark_hard_regno_death (int regno, int nregs)
2157 enum reg_class cl;
2158 int last = regno + nregs;
2160 while (regno < last)
2162 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2163 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2165 cl = sched_regno_pressure_class[regno];
2166 if (cl != NO_REGS)
2167 reg_pressure_info[cl].change -= 1;
2169 regno++;
2173 /* Update the register pressure info after death of pseudo or hard
2174 register REG. */
2175 static void
2176 mark_reg_death (rtx reg)
2178 int regno;
2180 if (GET_CODE (reg) == SUBREG)
2181 reg = SUBREG_REG (reg);
2183 if (! REG_P (reg))
2184 return;
2186 regno = REGNO (reg);
2187 if (regno < FIRST_PSEUDO_REGISTER)
2188 mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
2189 else
2190 mark_pseudo_death (regno);
2193 /* Process SETTER of REG. DATA is an insn containing the setter. */
2194 static void
2195 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2197 if (setter != NULL_RTX && GET_CODE (setter) != SET)
2198 return;
2199 mark_insn_reg_birth
2200 ((rtx) data, reg, false,
2201 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2204 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2205 static void
2206 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2208 if (GET_CODE (setter) == CLOBBER)
2209 mark_insn_reg_birth ((rtx) data, reg, true, false);
2212 /* Set up reg pressure info related to INSN. */
2213 void
2214 init_insn_reg_pressure_info (rtx insn)
2216 int i, len;
2217 enum reg_class cl;
2218 static struct reg_pressure_data *pressure_info;
2219 rtx link;
2221 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2223 if (! INSN_P (insn))
2224 return;
2226 for (i = 0; i < ira_pressure_classes_num; i++)
2228 cl = ira_pressure_classes[i];
2229 reg_pressure_info[cl].clobber_increase = 0;
2230 reg_pressure_info[cl].set_increase = 0;
2231 reg_pressure_info[cl].unused_set_increase = 0;
2232 reg_pressure_info[cl].change = 0;
2235 note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2237 note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2239 #ifdef AUTO_INC_DEC
2240 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2241 if (REG_NOTE_KIND (link) == REG_INC)
2242 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2243 #endif
2245 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2246 if (REG_NOTE_KIND (link) == REG_DEAD)
2247 mark_reg_death (XEXP (link, 0));
2249 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2250 pressure_info
2251 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2252 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2253 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2254 * sizeof (int), 1);
2255 for (i = 0; i < ira_pressure_classes_num; i++)
2257 cl = ira_pressure_classes[i];
2258 pressure_info[i].clobber_increase
2259 = reg_pressure_info[cl].clobber_increase;
2260 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2261 pressure_info[i].unused_set_increase
2262 = reg_pressure_info[cl].unused_set_increase;
2263 pressure_info[i].change = reg_pressure_info[cl].change;
2270 /* Internal variable for sched_analyze_[12] () functions.
2271 If it is nonzero, this means that sched_analyze_[12] looks
2272 at the most toplevel SET. */
2273 static bool can_start_lhs_rhs_p;
2275 /* Extend reg info for the deps context DEPS given that
2276 we have just generated a register numbered REGNO. */
2277 static void
2278 extend_deps_reg_info (struct deps_desc *deps, int regno)
2280 int max_regno = regno + 1;
2282 gcc_assert (!reload_completed);
2284 /* In a readonly context, it would not hurt to extend info,
2285 but it should not be needed. */
2286 if (reload_completed && deps->readonly)
2288 deps->max_reg = max_regno;
2289 return;
2292 if (max_regno > deps->max_reg)
2294 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2295 max_regno);
2296 memset (&deps->reg_last[deps->max_reg],
2297 0, (max_regno - deps->max_reg)
2298 * sizeof (struct deps_reg));
2299 deps->max_reg = max_regno;
2303 /* Extends REG_INFO_P if needed. */
2304 void
2305 maybe_extend_reg_info_p (void)
2307 /* Extend REG_INFO_P, if needed. */
2308 if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2310 size_t new_reg_info_p_size = max_regno + 128;
2312 gcc_assert (!reload_completed && sel_sched_p ());
2314 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2315 new_reg_info_p_size,
2316 reg_info_p_size,
2317 sizeof (*reg_info_p));
2318 reg_info_p_size = new_reg_info_p_size;
2322 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2323 The type of the reference is specified by REF and can be SET,
2324 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2326 static void
2327 sched_analyze_reg (struct deps_desc *deps, int regno, machine_mode mode,
2328 enum rtx_code ref, rtx_insn *insn)
2330 /* We could emit new pseudos in renaming. Extend the reg structures. */
2331 if (!reload_completed && sel_sched_p ()
2332 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2333 extend_deps_reg_info (deps, regno);
2335 maybe_extend_reg_info_p ();
2337 /* A hard reg in a wide mode may really be multiple registers.
2338 If so, mark all of them just like the first. */
2339 if (regno < FIRST_PSEUDO_REGISTER)
2341 int i = hard_regno_nregs[regno][mode];
2342 if (ref == SET)
2344 while (--i >= 0)
2345 note_reg_set (regno + i);
2347 else if (ref == USE)
2349 while (--i >= 0)
2350 note_reg_use (regno + i);
2352 else
2354 while (--i >= 0)
2355 note_reg_clobber (regno + i);
2359 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2360 it does not reload. Ignore these as they have served their
2361 purpose already. */
2362 else if (regno >= deps->max_reg)
2364 enum rtx_code code = GET_CODE (PATTERN (insn));
2365 gcc_assert (code == USE || code == CLOBBER);
2368 else
2370 if (ref == SET)
2371 note_reg_set (regno);
2372 else if (ref == USE)
2373 note_reg_use (regno);
2374 else
2375 note_reg_clobber (regno);
2377 /* Pseudos that are REG_EQUIV to something may be replaced
2378 by that during reloading. We need only add dependencies for
2379 the address in the REG_EQUIV note. */
2380 if (!reload_completed && get_reg_known_equiv_p (regno))
2382 rtx t = get_reg_known_value (regno);
2383 if (MEM_P (t))
2384 sched_analyze_2 (deps, XEXP (t, 0), insn);
2387 /* Don't let it cross a call after scheduling if it doesn't
2388 already cross one. */
2389 if (REG_N_CALLS_CROSSED (regno) == 0)
2391 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2392 deps->sched_before_next_call
2393 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2394 else
2395 add_dependence_list (insn, deps->last_function_call, 1,
2396 REG_DEP_ANTI, false);
2401 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2402 rtx, X, creating all dependencies generated by the write to the
2403 destination of X, and reads of everything mentioned. */
2405 static void
2406 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2408 rtx dest = XEXP (x, 0);
2409 enum rtx_code code = GET_CODE (x);
2410 bool cslr_p = can_start_lhs_rhs_p;
2412 can_start_lhs_rhs_p = false;
2414 gcc_assert (dest);
2415 if (dest == 0)
2416 return;
2418 if (cslr_p && sched_deps_info->start_lhs)
2419 sched_deps_info->start_lhs (dest);
2421 if (GET_CODE (dest) == PARALLEL)
2423 int i;
2425 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2426 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2427 sched_analyze_1 (deps,
2428 gen_rtx_CLOBBER (VOIDmode,
2429 XEXP (XVECEXP (dest, 0, i), 0)),
2430 insn);
2432 if (cslr_p && sched_deps_info->finish_lhs)
2433 sched_deps_info->finish_lhs ();
2435 if (code == SET)
2437 can_start_lhs_rhs_p = cslr_p;
2439 sched_analyze_2 (deps, SET_SRC (x), insn);
2441 can_start_lhs_rhs_p = false;
2444 return;
2447 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2448 || GET_CODE (dest) == ZERO_EXTRACT)
2450 if (GET_CODE (dest) == STRICT_LOW_PART
2451 || GET_CODE (dest) == ZERO_EXTRACT
2452 || df_read_modify_subreg_p (dest))
2454 /* These both read and modify the result. We must handle
2455 them as writes to get proper dependencies for following
2456 instructions. We must handle them as reads to get proper
2457 dependencies from this to previous instructions.
2458 Thus we need to call sched_analyze_2. */
2460 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2462 if (GET_CODE (dest) == ZERO_EXTRACT)
2464 /* The second and third arguments are values read by this insn. */
2465 sched_analyze_2 (deps, XEXP (dest, 1), insn);
2466 sched_analyze_2 (deps, XEXP (dest, 2), insn);
2468 dest = XEXP (dest, 0);
2471 if (REG_P (dest))
2473 int regno = REGNO (dest);
2474 machine_mode mode = GET_MODE (dest);
2476 sched_analyze_reg (deps, regno, mode, code, insn);
2478 #ifdef STACK_REGS
2479 /* Treat all writes to a stack register as modifying the TOS. */
2480 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2482 /* Avoid analyzing the same register twice. */
2483 if (regno != FIRST_STACK_REG)
2484 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2486 add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2487 FIRST_STACK_REG);
2489 #endif
2491 else if (MEM_P (dest))
2493 /* Writing memory. */
2494 rtx t = dest;
2496 if (sched_deps_info->use_cselib)
2498 machine_mode address_mode = get_address_mode (dest);
2500 t = shallow_copy_rtx (dest);
2501 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2502 GET_MODE (t), insn);
2503 XEXP (t, 0)
2504 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2505 insn);
2507 t = canon_rtx (t);
2509 /* Pending lists can't get larger with a readonly context. */
2510 if (!deps->readonly
2511 && ((deps->pending_read_list_length + deps->pending_write_list_length)
2512 >= MAX_PENDING_LIST_LENGTH))
2514 /* Flush all pending reads and writes to prevent the pending lists
2515 from getting any larger. Insn scheduling runs too slowly when
2516 these lists get long. When compiling GCC with itself,
2517 this flush occurs 8 times for sparc, and 10 times for m88k using
2518 the default value of 32. */
2519 flush_pending_lists (deps, insn, false, true);
2521 else
2523 rtx_insn_list *pending;
2524 rtx_expr_list *pending_mem;
2526 pending = deps->pending_read_insns;
2527 pending_mem = deps->pending_read_mems;
2528 while (pending)
2530 if (anti_dependence (pending_mem->element (), t)
2531 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2532 note_mem_dep (t, pending_mem->element (), pending->insn (),
2533 DEP_ANTI);
2535 pending = pending->next ();
2536 pending_mem = pending_mem->next ();
2539 pending = deps->pending_write_insns;
2540 pending_mem = deps->pending_write_mems;
2541 while (pending)
2543 if (output_dependence (pending_mem->element (), t)
2544 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2545 note_mem_dep (t, pending_mem->element (),
2546 pending->insn (),
2547 DEP_OUTPUT);
2549 pending = pending->next ();
2550 pending_mem = pending_mem-> next ();
2553 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2554 REG_DEP_ANTI, true);
2555 add_dependence_list (insn, deps->pending_jump_insns, 1,
2556 REG_DEP_CONTROL, true);
2558 if (!deps->readonly)
2559 add_insn_mem_dependence (deps, false, insn, dest);
2561 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2564 if (cslr_p && sched_deps_info->finish_lhs)
2565 sched_deps_info->finish_lhs ();
2567 /* Analyze reads. */
2568 if (GET_CODE (x) == SET)
2570 can_start_lhs_rhs_p = cslr_p;
2572 sched_analyze_2 (deps, SET_SRC (x), insn);
2574 can_start_lhs_rhs_p = false;
2578 /* Analyze the uses of memory and registers in rtx X in INSN. */
2579 static void
2580 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2582 int i;
2583 int j;
2584 enum rtx_code code;
2585 const char *fmt;
2586 bool cslr_p = can_start_lhs_rhs_p;
2588 can_start_lhs_rhs_p = false;
2590 gcc_assert (x);
2591 if (x == 0)
2592 return;
2594 if (cslr_p && sched_deps_info->start_rhs)
2595 sched_deps_info->start_rhs (x);
2597 code = GET_CODE (x);
2599 switch (code)
2601 CASE_CONST_ANY:
2602 case SYMBOL_REF:
2603 case CONST:
2604 case LABEL_REF:
2605 /* Ignore constants. */
2606 if (cslr_p && sched_deps_info->finish_rhs)
2607 sched_deps_info->finish_rhs ();
2609 return;
2611 #ifdef HAVE_cc0
2612 case CC0:
2613 /* User of CC0 depends on immediately preceding insn. */
2614 SCHED_GROUP_P (insn) = 1;
2615 /* Don't move CC0 setter to another block (it can set up the
2616 same flag for previous CC0 users which is safe). */
2617 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2619 if (cslr_p && sched_deps_info->finish_rhs)
2620 sched_deps_info->finish_rhs ();
2622 return;
2623 #endif
2625 case REG:
2627 int regno = REGNO (x);
2628 machine_mode mode = GET_MODE (x);
2630 sched_analyze_reg (deps, regno, mode, USE, insn);
2632 #ifdef STACK_REGS
2633 /* Treat all reads of a stack register as modifying the TOS. */
2634 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2636 /* Avoid analyzing the same register twice. */
2637 if (regno != FIRST_STACK_REG)
2638 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2639 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2641 #endif
2643 if (cslr_p && sched_deps_info->finish_rhs)
2644 sched_deps_info->finish_rhs ();
2646 return;
2649 case MEM:
2651 /* Reading memory. */
2652 rtx u;
2653 rtx_insn_list *pending;
2654 rtx_expr_list *pending_mem;
2655 rtx t = x;
2657 if (sched_deps_info->use_cselib)
2659 machine_mode address_mode = get_address_mode (t);
2661 t = shallow_copy_rtx (t);
2662 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2663 GET_MODE (t), insn);
2664 XEXP (t, 0)
2665 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2666 insn);
2669 if (!DEBUG_INSN_P (insn))
2671 t = canon_rtx (t);
2672 pending = deps->pending_read_insns;
2673 pending_mem = deps->pending_read_mems;
2674 while (pending)
2676 if (read_dependence (pending_mem->element (), t)
2677 && ! sched_insns_conditions_mutex_p (insn,
2678 pending->insn ()))
2679 note_mem_dep (t, pending_mem->element (),
2680 pending->insn (),
2681 DEP_ANTI);
2683 pending = pending->next ();
2684 pending_mem = pending_mem->next ();
2687 pending = deps->pending_write_insns;
2688 pending_mem = deps->pending_write_mems;
2689 while (pending)
2691 if (true_dependence (pending_mem->element (), VOIDmode, t)
2692 && ! sched_insns_conditions_mutex_p (insn,
2693 pending->insn ()))
2694 note_mem_dep (t, pending_mem->element (),
2695 pending->insn (),
2696 sched_deps_info->generate_spec_deps
2697 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2699 pending = pending->next ();
2700 pending_mem = pending_mem->next ();
2703 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2704 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
2705 REG_DEP_ANTI);
2707 for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2708 if (deps_may_trap_p (x))
2710 if ((sched_deps_info->generate_spec_deps)
2711 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2713 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2714 MAX_DEP_WEAK);
2716 note_dep (as_a <rtx_insn *> (XEXP (u, 0)), ds);
2718 else
2719 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
2720 REG_DEP_CONTROL);
2724 /* Always add these dependencies to pending_reads, since
2725 this insn may be followed by a write. */
2726 if (!deps->readonly)
2728 if ((deps->pending_read_list_length
2729 + deps->pending_write_list_length)
2730 >= MAX_PENDING_LIST_LENGTH
2731 && !DEBUG_INSN_P (insn))
2732 flush_pending_lists (deps, insn, true, true);
2733 add_insn_mem_dependence (deps, true, insn, x);
2736 sched_analyze_2 (deps, XEXP (x, 0), insn);
2738 if (cslr_p && sched_deps_info->finish_rhs)
2739 sched_deps_info->finish_rhs ();
2741 return;
2744 /* Force pending stores to memory in case a trap handler needs them. */
2745 case TRAP_IF:
2746 flush_pending_lists (deps, insn, true, false);
2747 break;
2749 case PREFETCH:
2750 if (PREFETCH_SCHEDULE_BARRIER_P (x))
2751 reg_pending_barrier = TRUE_BARRIER;
2752 /* Prefetch insn contains addresses only. So if the prefetch
2753 address has no registers, there will be no dependencies on
2754 the prefetch insn. This is wrong with result code
2755 correctness point of view as such prefetch can be moved below
2756 a jump insn which usually generates MOVE_BARRIER preventing
2757 to move insns containing registers or memories through the
2758 barrier. It is also wrong with generated code performance
2759 point of view as prefetch withouth dependecies will have a
2760 tendency to be issued later instead of earlier. It is hard
2761 to generate accurate dependencies for prefetch insns as
2762 prefetch has only the start address but it is better to have
2763 something than nothing. */
2764 if (!deps->readonly)
2766 rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2767 if (sched_deps_info->use_cselib)
2768 cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2769 add_insn_mem_dependence (deps, true, insn, x);
2771 break;
2773 case UNSPEC_VOLATILE:
2774 flush_pending_lists (deps, insn, true, true);
2775 /* FALLTHRU */
2777 case ASM_OPERANDS:
2778 case ASM_INPUT:
2780 /* Traditional and volatile asm instructions must be considered to use
2781 and clobber all hard registers, all pseudo-registers and all of
2782 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2784 Consider for instance a volatile asm that changes the fpu rounding
2785 mode. An insn should not be moved across this even if it only uses
2786 pseudo-regs because it might give an incorrectly rounded result. */
2787 if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2788 && !DEBUG_INSN_P (insn))
2789 reg_pending_barrier = TRUE_BARRIER;
2791 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2792 We can not just fall through here since then we would be confused
2793 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2794 traditional asms unlike their normal usage. */
2796 if (code == ASM_OPERANDS)
2798 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2799 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2801 if (cslr_p && sched_deps_info->finish_rhs)
2802 sched_deps_info->finish_rhs ();
2804 return;
2806 break;
2809 case PRE_DEC:
2810 case POST_DEC:
2811 case PRE_INC:
2812 case POST_INC:
2813 /* These both read and modify the result. We must handle them as writes
2814 to get proper dependencies for following instructions. We must handle
2815 them as reads to get proper dependencies from this to previous
2816 instructions. Thus we need to pass them to both sched_analyze_1
2817 and sched_analyze_2. We must call sched_analyze_2 first in order
2818 to get the proper antecedent for the read. */
2819 sched_analyze_2 (deps, XEXP (x, 0), insn);
2820 sched_analyze_1 (deps, x, insn);
2822 if (cslr_p && sched_deps_info->finish_rhs)
2823 sched_deps_info->finish_rhs ();
2825 return;
2827 case POST_MODIFY:
2828 case PRE_MODIFY:
2829 /* op0 = op0 + op1 */
2830 sched_analyze_2 (deps, XEXP (x, 0), insn);
2831 sched_analyze_2 (deps, XEXP (x, 1), insn);
2832 sched_analyze_1 (deps, x, insn);
2834 if (cslr_p && sched_deps_info->finish_rhs)
2835 sched_deps_info->finish_rhs ();
2837 return;
2839 default:
2840 break;
2843 /* Other cases: walk the insn. */
2844 fmt = GET_RTX_FORMAT (code);
2845 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2847 if (fmt[i] == 'e')
2848 sched_analyze_2 (deps, XEXP (x, i), insn);
2849 else if (fmt[i] == 'E')
2850 for (j = 0; j < XVECLEN (x, i); j++)
2851 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2854 if (cslr_p && sched_deps_info->finish_rhs)
2855 sched_deps_info->finish_rhs ();
2858 /* Try to group two fuseable insns together to prevent scheduler
2859 from scheduling them apart. */
2861 static void
2862 sched_macro_fuse_insns (rtx_insn *insn)
2864 rtx_insn *prev;
2866 if (any_condjump_p (insn))
2868 unsigned int condreg1, condreg2;
2869 rtx cc_reg_1;
2870 targetm.fixed_condition_code_regs (&condreg1, &condreg2);
2871 cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2872 prev = prev_nonnote_nondebug_insn (insn);
2873 if (!reg_referenced_p (cc_reg_1, PATTERN (insn))
2874 || !prev
2875 || !modified_in_p (cc_reg_1, prev))
2876 return;
2878 else
2880 rtx insn_set = single_set (insn);
2882 prev = prev_nonnote_nondebug_insn (insn);
2883 if (!prev
2884 || !insn_set
2885 || !single_set (prev))
2886 return;
2890 if (targetm.sched.macro_fusion_pair_p (prev, insn))
2891 SCHED_GROUP_P (insn) = 1;
2895 /* Analyze an INSN with pattern X to find all dependencies. */
2896 static void
2897 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
2899 RTX_CODE code = GET_CODE (x);
2900 rtx link;
2901 unsigned i;
2902 reg_set_iterator rsi;
2904 if (! reload_completed)
2906 HARD_REG_SET temp;
2908 extract_insn (insn);
2909 preprocess_constraints (insn);
2910 ira_implicitly_set_insn_hard_regs (&temp);
2911 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2912 IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2915 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2916 && code == SET);
2918 /* Group compare and branch insns for macro-fusion. */
2919 if (targetm.sched.macro_fusion_p
2920 && targetm.sched.macro_fusion_p ())
2921 sched_macro_fuse_insns (insn);
2923 if (may_trap_p (x))
2924 /* Avoid moving trapping instructions across function calls that might
2925 not always return. */
2926 add_dependence_list (insn, deps->last_function_call_may_noreturn,
2927 1, REG_DEP_ANTI, true);
2929 /* We must avoid creating a situation in which two successors of the
2930 current block have different unwind info after scheduling. If at any
2931 point the two paths re-join this leads to incorrect unwind info. */
2932 /* ??? There are certain situations involving a forced frame pointer in
2933 which, with extra effort, we could fix up the unwind info at a later
2934 CFG join. However, it seems better to notice these cases earlier
2935 during prologue generation and avoid marking the frame pointer setup
2936 as frame-related at all. */
2937 if (RTX_FRAME_RELATED_P (insn))
2939 /* Make sure prologue insn is scheduled before next jump. */
2940 deps->sched_before_next_jump
2941 = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2943 /* Make sure epilogue insn is scheduled after preceding jumps. */
2944 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2945 true);
2948 if (code == COND_EXEC)
2950 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2952 /* ??? Should be recording conditions so we reduce the number of
2953 false dependencies. */
2954 x = COND_EXEC_CODE (x);
2955 code = GET_CODE (x);
2957 if (code == SET || code == CLOBBER)
2959 sched_analyze_1 (deps, x, insn);
2961 /* Bare clobber insns are used for letting life analysis, reg-stack
2962 and others know that a value is dead. Depend on the last call
2963 instruction so that reg-stack won't get confused. */
2964 if (code == CLOBBER)
2965 add_dependence_list (insn, deps->last_function_call, 1,
2966 REG_DEP_OUTPUT, true);
2968 else if (code == PARALLEL)
2970 for (i = XVECLEN (x, 0); i--;)
2972 rtx sub = XVECEXP (x, 0, i);
2973 code = GET_CODE (sub);
2975 if (code == COND_EXEC)
2977 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2978 sub = COND_EXEC_CODE (sub);
2979 code = GET_CODE (sub);
2981 if (code == SET || code == CLOBBER)
2982 sched_analyze_1 (deps, sub, insn);
2983 else
2984 sched_analyze_2 (deps, sub, insn);
2987 else
2988 sched_analyze_2 (deps, x, insn);
2990 /* Mark registers CLOBBERED or used by called function. */
2991 if (CALL_P (insn))
2993 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2995 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2996 sched_analyze_1 (deps, XEXP (link, 0), insn);
2997 else if (GET_CODE (XEXP (link, 0)) != SET)
2998 sched_analyze_2 (deps, XEXP (link, 0), insn);
3000 /* Don't schedule anything after a tail call, tail call needs
3001 to use at least all call-saved registers. */
3002 if (SIBLING_CALL_P (insn))
3003 reg_pending_barrier = TRUE_BARRIER;
3004 else if (find_reg_note (insn, REG_SETJMP, NULL))
3005 reg_pending_barrier = MOVE_BARRIER;
3008 if (JUMP_P (insn))
3010 rtx next;
3011 next = next_nonnote_nondebug_insn (insn);
3012 if (next && BARRIER_P (next))
3013 reg_pending_barrier = MOVE_BARRIER;
3014 else
3016 rtx_insn_list *pending;
3017 rtx_expr_list *pending_mem;
3019 if (sched_deps_info->compute_jump_reg_dependencies)
3021 (*sched_deps_info->compute_jump_reg_dependencies)
3022 (insn, reg_pending_control_uses);
3024 /* Make latency of jump equal to 0 by using anti-dependence. */
3025 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3027 struct deps_reg *reg_last = &deps->reg_last[i];
3028 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3029 false);
3030 add_dependence_list (insn, reg_last->implicit_sets,
3031 0, REG_DEP_ANTI, false);
3032 add_dependence_list (insn, reg_last->clobbers, 0,
3033 REG_DEP_ANTI, false);
3037 /* All memory writes and volatile reads must happen before the
3038 jump. Non-volatile reads must happen before the jump iff
3039 the result is needed by the above register used mask. */
3041 pending = deps->pending_write_insns;
3042 pending_mem = deps->pending_write_mems;
3043 while (pending)
3045 if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3046 add_dependence (insn, pending->insn (),
3047 REG_DEP_OUTPUT);
3048 pending = pending->next ();
3049 pending_mem = pending_mem->next ();
3052 pending = deps->pending_read_insns;
3053 pending_mem = deps->pending_read_mems;
3054 while (pending)
3056 if (MEM_VOLATILE_P (pending_mem->element ())
3057 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3058 add_dependence (insn, pending->insn (),
3059 REG_DEP_OUTPUT);
3060 pending = pending->next ();
3061 pending_mem = pending_mem->next ();
3064 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3065 REG_DEP_ANTI, true);
3066 add_dependence_list (insn, deps->pending_jump_insns, 1,
3067 REG_DEP_ANTI, true);
3071 /* If this instruction can throw an exception, then moving it changes
3072 where block boundaries fall. This is mighty confusing elsewhere.
3073 Therefore, prevent such an instruction from being moved. Same for
3074 non-jump instructions that define block boundaries.
3075 ??? Unclear whether this is still necessary in EBB mode. If not,
3076 add_branch_dependences should be adjusted for RGN mode instead. */
3077 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3078 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3079 reg_pending_barrier = MOVE_BARRIER;
3081 if (sched_pressure != SCHED_PRESSURE_NONE)
3083 setup_insn_reg_uses (deps, insn);
3084 init_insn_reg_pressure_info (insn);
3087 /* Add register dependencies for insn. */
3088 if (DEBUG_INSN_P (insn))
3090 rtx_insn *prev = deps->last_debug_insn;
3091 rtx u;
3093 if (!deps->readonly)
3094 deps->last_debug_insn = insn;
3096 if (prev)
3097 add_dependence (insn, prev, REG_DEP_ANTI);
3099 add_dependence_list (insn, deps->last_function_call, 1,
3100 REG_DEP_ANTI, false);
3102 if (!sel_sched_p ())
3103 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3104 add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)), REG_DEP_ANTI);
3106 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3108 struct deps_reg *reg_last = &deps->reg_last[i];
3109 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3110 /* There's no point in making REG_DEP_CONTROL dependencies for
3111 debug insns. */
3112 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3113 false);
3115 if (!deps->readonly)
3116 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3118 CLEAR_REG_SET (reg_pending_uses);
3120 /* Quite often, a debug insn will refer to stuff in the
3121 previous instruction, but the reason we want this
3122 dependency here is to make sure the scheduler doesn't
3123 gratuitously move a debug insn ahead. This could dirty
3124 DF flags and cause additional analysis that wouldn't have
3125 occurred in compilation without debug insns, and such
3126 additional analysis can modify the generated code. */
3127 prev = PREV_INSN (insn);
3129 if (prev && NONDEBUG_INSN_P (prev))
3130 add_dependence (insn, prev, REG_DEP_ANTI);
3132 else
3134 regset_head set_or_clobbered;
3136 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3138 struct deps_reg *reg_last = &deps->reg_last[i];
3139 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3140 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3141 false);
3142 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3143 false);
3145 if (!deps->readonly)
3147 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3148 reg_last->uses_length++;
3152 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3153 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3155 struct deps_reg *reg_last = &deps->reg_last[i];
3156 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3157 add_dependence_list (insn, reg_last->implicit_sets, 0,
3158 REG_DEP_ANTI, false);
3159 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3160 false);
3162 if (!deps->readonly)
3164 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3165 reg_last->uses_length++;
3169 if (targetm.sched.exposed_pipeline)
3171 INIT_REG_SET (&set_or_clobbered);
3172 bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3173 reg_pending_sets);
3174 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3176 struct deps_reg *reg_last = &deps->reg_last[i];
3177 rtx list;
3178 for (list = reg_last->uses; list; list = XEXP (list, 1))
3180 rtx other = XEXP (list, 0);
3181 if (INSN_CACHED_COND (other) != const_true_rtx
3182 && refers_to_regno_p (i, INSN_CACHED_COND (other)))
3183 INSN_CACHED_COND (other) = const_true_rtx;
3188 /* If the current insn is conditional, we can't free any
3189 of the lists. */
3190 if (sched_has_condition_p (insn))
3192 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3194 struct deps_reg *reg_last = &deps->reg_last[i];
3195 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3196 false);
3197 add_dependence_list (insn, reg_last->implicit_sets, 0,
3198 REG_DEP_ANTI, false);
3199 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3200 false);
3201 add_dependence_list (insn, reg_last->control_uses, 0,
3202 REG_DEP_CONTROL, false);
3204 if (!deps->readonly)
3206 reg_last->clobbers
3207 = alloc_INSN_LIST (insn, reg_last->clobbers);
3208 reg_last->clobbers_length++;
3211 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3213 struct deps_reg *reg_last = &deps->reg_last[i];
3214 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3215 false);
3216 add_dependence_list (insn, reg_last->implicit_sets, 0,
3217 REG_DEP_ANTI, false);
3218 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3219 false);
3220 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3221 false);
3222 add_dependence_list (insn, reg_last->control_uses, 0,
3223 REG_DEP_CONTROL, false);
3225 if (!deps->readonly)
3226 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3229 else
3231 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3233 struct deps_reg *reg_last = &deps->reg_last[i];
3234 if (reg_last->uses_length >= MAX_PENDING_LIST_LENGTH
3235 || reg_last->clobbers_length >= MAX_PENDING_LIST_LENGTH)
3237 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3238 REG_DEP_OUTPUT, false);
3239 add_dependence_list_and_free (deps, insn,
3240 &reg_last->implicit_sets, 0,
3241 REG_DEP_ANTI, false);
3242 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3243 REG_DEP_ANTI, false);
3244 add_dependence_list_and_free (deps, insn,
3245 &reg_last->control_uses, 0,
3246 REG_DEP_ANTI, false);
3247 add_dependence_list_and_free (deps, insn,
3248 &reg_last->clobbers, 0,
3249 REG_DEP_OUTPUT, false);
3251 if (!deps->readonly)
3253 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3254 reg_last->clobbers_length = 0;
3255 reg_last->uses_length = 0;
3258 else
3260 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3261 false);
3262 add_dependence_list (insn, reg_last->implicit_sets, 0,
3263 REG_DEP_ANTI, false);
3264 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3265 false);
3266 add_dependence_list (insn, reg_last->control_uses, 0,
3267 REG_DEP_CONTROL, false);
3270 if (!deps->readonly)
3272 reg_last->clobbers_length++;
3273 reg_last->clobbers
3274 = alloc_INSN_LIST (insn, reg_last->clobbers);
3277 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3279 struct deps_reg *reg_last = &deps->reg_last[i];
3281 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3282 REG_DEP_OUTPUT, false);
3283 add_dependence_list_and_free (deps, insn,
3284 &reg_last->implicit_sets,
3285 0, REG_DEP_ANTI, false);
3286 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3287 REG_DEP_OUTPUT, false);
3288 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3289 REG_DEP_ANTI, false);
3290 add_dependence_list (insn, reg_last->control_uses, 0,
3291 REG_DEP_CONTROL, false);
3293 if (!deps->readonly)
3295 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3296 reg_last->uses_length = 0;
3297 reg_last->clobbers_length = 0;
3301 if (!deps->readonly)
3303 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3305 struct deps_reg *reg_last = &deps->reg_last[i];
3306 reg_last->control_uses
3307 = alloc_INSN_LIST (insn, reg_last->control_uses);
3312 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3313 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3315 struct deps_reg *reg_last = &deps->reg_last[i];
3316 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3317 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3318 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3319 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3320 false);
3322 if (!deps->readonly)
3323 reg_last->implicit_sets
3324 = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3327 if (!deps->readonly)
3329 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3330 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3331 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3332 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3333 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3334 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3335 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3337 /* Set up the pending barrier found. */
3338 deps->last_reg_pending_barrier = reg_pending_barrier;
3341 CLEAR_REG_SET (reg_pending_uses);
3342 CLEAR_REG_SET (reg_pending_clobbers);
3343 CLEAR_REG_SET (reg_pending_sets);
3344 CLEAR_REG_SET (reg_pending_control_uses);
3345 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3346 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3348 /* Add dependencies if a scheduling barrier was found. */
3349 if (reg_pending_barrier)
3351 /* In the case of barrier the most added dependencies are not
3352 real, so we use anti-dependence here. */
3353 if (sched_has_condition_p (insn))
3355 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3357 struct deps_reg *reg_last = &deps->reg_last[i];
3358 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3359 true);
3360 add_dependence_list (insn, reg_last->sets, 0,
3361 reg_pending_barrier == TRUE_BARRIER
3362 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3363 add_dependence_list (insn, reg_last->implicit_sets, 0,
3364 REG_DEP_ANTI, true);
3365 add_dependence_list (insn, reg_last->clobbers, 0,
3366 reg_pending_barrier == TRUE_BARRIER
3367 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3370 else
3372 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3374 struct deps_reg *reg_last = &deps->reg_last[i];
3375 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3376 REG_DEP_ANTI, true);
3377 add_dependence_list_and_free (deps, insn,
3378 &reg_last->control_uses, 0,
3379 REG_DEP_CONTROL, true);
3380 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3381 reg_pending_barrier == TRUE_BARRIER
3382 ? REG_DEP_TRUE : REG_DEP_ANTI,
3383 true);
3384 add_dependence_list_and_free (deps, insn,
3385 &reg_last->implicit_sets, 0,
3386 REG_DEP_ANTI, true);
3387 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3388 reg_pending_barrier == TRUE_BARRIER
3389 ? REG_DEP_TRUE : REG_DEP_ANTI,
3390 true);
3392 if (!deps->readonly)
3394 reg_last->uses_length = 0;
3395 reg_last->clobbers_length = 0;
3400 if (!deps->readonly)
3401 for (i = 0; i < (unsigned)deps->max_reg; i++)
3403 struct deps_reg *reg_last = &deps->reg_last[i];
3404 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3405 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3408 /* Don't flush pending lists on speculative checks for
3409 selective scheduling. */
3410 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3411 flush_pending_lists (deps, insn, true, true);
3413 reg_pending_barrier = NOT_A_BARRIER;
3416 /* If a post-call group is still open, see if it should remain so.
3417 This insn must be a simple move of a hard reg to a pseudo or
3418 vice-versa.
3420 We must avoid moving these insns for correctness on targets
3421 with small register classes, and for special registers like
3422 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3423 hard regs for all targets. */
3425 if (deps->in_post_call_group_p)
3427 rtx tmp, set = single_set (insn);
3428 int src_regno, dest_regno;
3430 if (set == NULL)
3432 if (DEBUG_INSN_P (insn))
3433 /* We don't want to mark debug insns as part of the same
3434 sched group. We know they really aren't, but if we use
3435 debug insns to tell that a call group is over, we'll
3436 get different code if debug insns are not there and
3437 instructions that follow seem like they should be part
3438 of the call group.
3440 Also, if we did, chain_to_prev_insn would move the
3441 deps of the debug insn to the call insn, modifying
3442 non-debug post-dependency counts of the debug insn
3443 dependencies and otherwise messing with the scheduling
3444 order.
3446 Instead, let such debug insns be scheduled freely, but
3447 keep the call group open in case there are insns that
3448 should be part of it afterwards. Since we grant debug
3449 insns higher priority than even sched group insns, it
3450 will all turn out all right. */
3451 goto debug_dont_end_call_group;
3452 else
3453 goto end_call_group;
3456 tmp = SET_DEST (set);
3457 if (GET_CODE (tmp) == SUBREG)
3458 tmp = SUBREG_REG (tmp);
3459 if (REG_P (tmp))
3460 dest_regno = REGNO (tmp);
3461 else
3462 goto end_call_group;
3464 tmp = SET_SRC (set);
3465 if (GET_CODE (tmp) == SUBREG)
3466 tmp = SUBREG_REG (tmp);
3467 if ((GET_CODE (tmp) == PLUS
3468 || GET_CODE (tmp) == MINUS)
3469 && REG_P (XEXP (tmp, 0))
3470 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3471 && dest_regno == STACK_POINTER_REGNUM)
3472 src_regno = STACK_POINTER_REGNUM;
3473 else if (REG_P (tmp))
3474 src_regno = REGNO (tmp);
3475 else
3476 goto end_call_group;
3478 if (src_regno < FIRST_PSEUDO_REGISTER
3479 || dest_regno < FIRST_PSEUDO_REGISTER)
3481 if (!deps->readonly
3482 && deps->in_post_call_group_p == post_call_initial)
3483 deps->in_post_call_group_p = post_call;
3485 if (!sel_sched_p () || sched_emulate_haifa_p)
3487 SCHED_GROUP_P (insn) = 1;
3488 CANT_MOVE (insn) = 1;
3491 else
3493 end_call_group:
3494 if (!deps->readonly)
3495 deps->in_post_call_group_p = not_post_call;
3499 debug_dont_end_call_group:
3500 if ((current_sched_info->flags & DO_SPECULATION)
3501 && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3502 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3503 be speculated. */
3505 if (sel_sched_p ())
3506 sel_mark_hard_insn (insn);
3507 else
3509 sd_iterator_def sd_it;
3510 dep_t dep;
3512 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3513 sd_iterator_cond (&sd_it, &dep);)
3514 change_spec_dep_to_hard (sd_it);
3518 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3519 honor their original ordering. */
3520 if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3522 if (deps->last_args_size)
3523 add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3524 deps->last_args_size = insn;
3528 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3529 longjmp, loop forever, ...). */
3530 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3531 test for ECF_NORETURN? */
3532 static bool
3533 call_may_noreturn_p (rtx insn)
3535 rtx call;
3537 /* const or pure calls that aren't looping will always return. */
3538 if (RTL_CONST_OR_PURE_CALL_P (insn)
3539 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3540 return false;
3542 call = get_call_rtx_from (insn);
3543 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3545 rtx symbol = XEXP (XEXP (call, 0), 0);
3546 if (SYMBOL_REF_DECL (symbol)
3547 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3549 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3550 == BUILT_IN_NORMAL)
3551 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3553 case BUILT_IN_BCMP:
3554 case BUILT_IN_BCOPY:
3555 case BUILT_IN_BZERO:
3556 case BUILT_IN_INDEX:
3557 case BUILT_IN_MEMCHR:
3558 case BUILT_IN_MEMCMP:
3559 case BUILT_IN_MEMCPY:
3560 case BUILT_IN_MEMMOVE:
3561 case BUILT_IN_MEMPCPY:
3562 case BUILT_IN_MEMSET:
3563 case BUILT_IN_RINDEX:
3564 case BUILT_IN_STPCPY:
3565 case BUILT_IN_STPNCPY:
3566 case BUILT_IN_STRCAT:
3567 case BUILT_IN_STRCHR:
3568 case BUILT_IN_STRCMP:
3569 case BUILT_IN_STRCPY:
3570 case BUILT_IN_STRCSPN:
3571 case BUILT_IN_STRLEN:
3572 case BUILT_IN_STRNCAT:
3573 case BUILT_IN_STRNCMP:
3574 case BUILT_IN_STRNCPY:
3575 case BUILT_IN_STRPBRK:
3576 case BUILT_IN_STRRCHR:
3577 case BUILT_IN_STRSPN:
3578 case BUILT_IN_STRSTR:
3579 /* Assume certain string/memory builtins always return. */
3580 return false;
3581 default:
3582 break;
3587 /* For all other calls assume that they might not always return. */
3588 return true;
3591 /* Return true if INSN should be made dependent on the previous instruction
3592 group, and if all INSN's dependencies should be moved to the first
3593 instruction of that group. */
3595 static bool
3596 chain_to_prev_insn_p (rtx insn)
3598 rtx prev, x;
3600 /* INSN forms a group with the previous instruction. */
3601 if (SCHED_GROUP_P (insn))
3602 return true;
3604 /* If the previous instruction clobbers a register R and this one sets
3605 part of R, the clobber was added specifically to help us track the
3606 liveness of R. There's no point scheduling the clobber and leaving
3607 INSN behind, especially if we move the clobber to another block. */
3608 prev = prev_nonnote_nondebug_insn (insn);
3609 if (prev
3610 && INSN_P (prev)
3611 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3612 && GET_CODE (PATTERN (prev)) == CLOBBER)
3614 x = XEXP (PATTERN (prev), 0);
3615 if (set_of (x, insn))
3616 return true;
3619 return false;
3622 /* Analyze INSN with DEPS as a context. */
3623 void
3624 deps_analyze_insn (struct deps_desc *deps, rtx_insn *insn)
3626 if (sched_deps_info->start_insn)
3627 sched_deps_info->start_insn (insn);
3629 /* Record the condition for this insn. */
3630 if (NONDEBUG_INSN_P (insn))
3632 rtx t;
3633 sched_get_condition_with_rev (insn, NULL);
3634 t = INSN_CACHED_COND (insn);
3635 INSN_COND_DEPS (insn) = NULL;
3636 if (reload_completed
3637 && (current_sched_info->flags & DO_PREDICATION)
3638 && COMPARISON_P (t)
3639 && REG_P (XEXP (t, 0))
3640 && CONSTANT_P (XEXP (t, 1)))
3642 unsigned int regno;
3643 int nregs;
3644 rtx_insn_list *cond_deps = NULL;
3645 t = XEXP (t, 0);
3646 regno = REGNO (t);
3647 nregs = hard_regno_nregs[regno][GET_MODE (t)];
3648 while (nregs-- > 0)
3650 struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3651 cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3652 cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3653 cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3655 INSN_COND_DEPS (insn) = cond_deps;
3659 if (JUMP_P (insn))
3661 /* Make each JUMP_INSN (but not a speculative check)
3662 a scheduling barrier for memory references. */
3663 if (!deps->readonly
3664 && !(sel_sched_p ()
3665 && sel_insn_is_speculation_check (insn)))
3667 /* Keep the list a reasonable size. */
3668 if (deps->pending_flush_length++ >= MAX_PENDING_LIST_LENGTH)
3669 flush_pending_lists (deps, insn, true, true);
3670 else
3671 deps->pending_jump_insns
3672 = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3675 /* For each insn which shouldn't cross a jump, add a dependence. */
3676 add_dependence_list_and_free (deps, insn,
3677 &deps->sched_before_next_jump, 1,
3678 REG_DEP_ANTI, true);
3680 sched_analyze_insn (deps, PATTERN (insn), insn);
3682 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3684 sched_analyze_insn (deps, PATTERN (insn), insn);
3686 else if (CALL_P (insn))
3688 int i;
3690 CANT_MOVE (insn) = 1;
3692 if (find_reg_note (insn, REG_SETJMP, NULL))
3694 /* This is setjmp. Assume that all registers, not just
3695 hard registers, may be clobbered by this call. */
3696 reg_pending_barrier = MOVE_BARRIER;
3698 else
3700 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3701 /* A call may read and modify global register variables. */
3702 if (global_regs[i])
3704 SET_REGNO_REG_SET (reg_pending_sets, i);
3705 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3707 /* Other call-clobbered hard regs may be clobbered.
3708 Since we only have a choice between 'might be clobbered'
3709 and 'definitely not clobbered', we must include all
3710 partly call-clobbered registers here. */
3711 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3712 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3713 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3714 /* We don't know what set of fixed registers might be used
3715 by the function, but it is certain that the stack pointer
3716 is among them, but be conservative. */
3717 else if (fixed_regs[i])
3718 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3719 /* The frame pointer is normally not used by the function
3720 itself, but by the debugger. */
3721 /* ??? MIPS o32 is an exception. It uses the frame pointer
3722 in the macro expansion of jal but does not represent this
3723 fact in the call_insn rtl. */
3724 else if (i == FRAME_POINTER_REGNUM
3725 || (i == HARD_FRAME_POINTER_REGNUM
3726 && (! reload_completed || frame_pointer_needed)))
3727 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3730 /* For each insn which shouldn't cross a call, add a dependence
3731 between that insn and this call insn. */
3732 add_dependence_list_and_free (deps, insn,
3733 &deps->sched_before_next_call, 1,
3734 REG_DEP_ANTI, true);
3736 sched_analyze_insn (deps, PATTERN (insn), insn);
3738 /* If CALL would be in a sched group, then this will violate
3739 convention that sched group insns have dependencies only on the
3740 previous instruction.
3742 Of course one can say: "Hey! What about head of the sched group?"
3743 And I will answer: "Basic principles (one dep per insn) are always
3744 the same." */
3745 gcc_assert (!SCHED_GROUP_P (insn));
3747 /* In the absence of interprocedural alias analysis, we must flush
3748 all pending reads and writes, and start new dependencies starting
3749 from here. But only flush writes for constant calls (which may
3750 be passed a pointer to something we haven't written yet). */
3751 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3753 if (!deps->readonly)
3755 /* Remember the last function call for limiting lifetimes. */
3756 free_INSN_LIST_list (&deps->last_function_call);
3757 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3759 if (call_may_noreturn_p (insn))
3761 /* Remember the last function call that might not always return
3762 normally for limiting moves of trapping insns. */
3763 free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3764 deps->last_function_call_may_noreturn
3765 = alloc_INSN_LIST (insn, NULL_RTX);
3768 /* Before reload, begin a post-call group, so as to keep the
3769 lifetimes of hard registers correct. */
3770 if (! reload_completed)
3771 deps->in_post_call_group_p = post_call;
3775 if (sched_deps_info->use_cselib)
3776 cselib_process_insn (insn);
3778 if (sched_deps_info->finish_insn)
3779 sched_deps_info->finish_insn ();
3781 /* Fixup the dependencies in the sched group. */
3782 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3783 && chain_to_prev_insn_p (insn)
3784 && !sel_sched_p ())
3785 chain_to_prev_insn (insn);
3788 /* Initialize DEPS for the new block beginning with HEAD. */
3789 void
3790 deps_start_bb (struct deps_desc *deps, rtx_insn *head)
3792 gcc_assert (!deps->readonly);
3794 /* Before reload, if the previous block ended in a call, show that
3795 we are inside a post-call group, so as to keep the lifetimes of
3796 hard registers correct. */
3797 if (! reload_completed && !LABEL_P (head))
3799 rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3801 if (insn && CALL_P (insn))
3802 deps->in_post_call_group_p = post_call_initial;
3806 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3807 dependencies for each insn. */
3808 void
3809 sched_analyze (struct deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3811 rtx_insn *insn;
3813 if (sched_deps_info->use_cselib)
3814 cselib_init (CSELIB_RECORD_MEMORY);
3816 deps_start_bb (deps, head);
3818 for (insn = head;; insn = NEXT_INSN (insn))
3821 if (INSN_P (insn))
3823 /* And initialize deps_lists. */
3824 sd_init_insn (insn);
3825 /* Clean up SCHED_GROUP_P which may be set by last
3826 scheduler pass. */
3827 if (SCHED_GROUP_P (insn))
3828 SCHED_GROUP_P (insn) = 0;
3831 deps_analyze_insn (deps, insn);
3833 if (insn == tail)
3835 if (sched_deps_info->use_cselib)
3836 cselib_finish ();
3837 return;
3840 gcc_unreachable ();
3843 /* Helper for sched_free_deps ().
3844 Delete INSN's (RESOLVED_P) backward dependencies. */
3845 static void
3846 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3848 sd_iterator_def sd_it;
3849 dep_t dep;
3850 sd_list_types_def types;
3852 if (resolved_p)
3853 types = SD_LIST_RES_BACK;
3854 else
3855 types = SD_LIST_BACK;
3857 for (sd_it = sd_iterator_start (insn, types);
3858 sd_iterator_cond (&sd_it, &dep);)
3860 dep_link_t link = *sd_it.linkp;
3861 dep_node_t node = DEP_LINK_NODE (link);
3862 deps_list_t back_list;
3863 deps_list_t forw_list;
3865 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3866 remove_from_deps_list (link, back_list);
3867 delete_dep_node (node);
3871 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3872 deps_lists. */
3873 void
3874 sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
3876 rtx_insn *insn;
3877 rtx_insn *next_tail = NEXT_INSN (tail);
3879 /* We make two passes since some insns may be scheduled before their
3880 dependencies are resolved. */
3881 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3882 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3884 /* Clear forward deps and leave the dep_nodes to the
3885 corresponding back_deps list. */
3886 if (resolved_p)
3887 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3888 else
3889 clear_deps_list (INSN_FORW_DEPS (insn));
3891 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3892 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3894 /* Clear resolved back deps together with its dep_nodes. */
3895 delete_dep_nodes_in_back_deps (insn, resolved_p);
3897 sd_finish_insn (insn);
3901 /* Initialize variables for region data dependence analysis.
3902 When LAZY_REG_LAST is true, do not allocate reg_last array
3903 of struct deps_desc immediately. */
3905 void
3906 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3908 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3910 deps->max_reg = max_reg;
3911 if (lazy_reg_last)
3912 deps->reg_last = NULL;
3913 else
3914 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3915 INIT_REG_SET (&deps->reg_last_in_use);
3917 deps->pending_read_insns = 0;
3918 deps->pending_read_mems = 0;
3919 deps->pending_write_insns = 0;
3920 deps->pending_write_mems = 0;
3921 deps->pending_jump_insns = 0;
3922 deps->pending_read_list_length = 0;
3923 deps->pending_write_list_length = 0;
3924 deps->pending_flush_length = 0;
3925 deps->last_pending_memory_flush = 0;
3926 deps->last_function_call = 0;
3927 deps->last_function_call_may_noreturn = 0;
3928 deps->sched_before_next_call = 0;
3929 deps->sched_before_next_jump = 0;
3930 deps->in_post_call_group_p = not_post_call;
3931 deps->last_debug_insn = 0;
3932 deps->last_args_size = 0;
3933 deps->last_reg_pending_barrier = NOT_A_BARRIER;
3934 deps->readonly = 0;
3937 /* Init only reg_last field of DEPS, which was not allocated before as
3938 we inited DEPS lazily. */
3939 void
3940 init_deps_reg_last (struct deps_desc *deps)
3942 gcc_assert (deps && deps->max_reg > 0);
3943 gcc_assert (deps->reg_last == NULL);
3945 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3949 /* Free insn lists found in DEPS. */
3951 void
3952 free_deps (struct deps_desc *deps)
3954 unsigned i;
3955 reg_set_iterator rsi;
3957 /* We set max_reg to 0 when this context was already freed. */
3958 if (deps->max_reg == 0)
3960 gcc_assert (deps->reg_last == NULL);
3961 return;
3963 deps->max_reg = 0;
3965 free_INSN_LIST_list (&deps->pending_read_insns);
3966 free_EXPR_LIST_list (&deps->pending_read_mems);
3967 free_INSN_LIST_list (&deps->pending_write_insns);
3968 free_EXPR_LIST_list (&deps->pending_write_mems);
3969 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3971 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3972 times. For a testcase with 42000 regs and 8000 small basic blocks,
3973 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3974 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3976 struct deps_reg *reg_last = &deps->reg_last[i];
3977 if (reg_last->uses)
3978 free_INSN_LIST_list (&reg_last->uses);
3979 if (reg_last->sets)
3980 free_INSN_LIST_list (&reg_last->sets);
3981 if (reg_last->implicit_sets)
3982 free_INSN_LIST_list (&reg_last->implicit_sets);
3983 if (reg_last->control_uses)
3984 free_INSN_LIST_list (&reg_last->control_uses);
3985 if (reg_last->clobbers)
3986 free_INSN_LIST_list (&reg_last->clobbers);
3988 CLEAR_REG_SET (&deps->reg_last_in_use);
3990 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3991 it at all. */
3992 free (deps->reg_last);
3993 deps->reg_last = NULL;
3995 deps = NULL;
3998 /* Remove INSN from dependence contexts DEPS. */
3999 void
4000 remove_from_deps (struct deps_desc *deps, rtx_insn *insn)
4002 int removed;
4003 unsigned i;
4004 reg_set_iterator rsi;
4006 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4007 &deps->pending_read_mems);
4008 if (!DEBUG_INSN_P (insn))
4009 deps->pending_read_list_length -= removed;
4010 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4011 &deps->pending_write_mems);
4012 deps->pending_write_list_length -= removed;
4014 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4015 deps->pending_flush_length -= removed;
4016 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4017 deps->pending_flush_length -= removed;
4019 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4021 struct deps_reg *reg_last = &deps->reg_last[i];
4022 if (reg_last->uses)
4023 remove_from_dependence_list (insn, &reg_last->uses);
4024 if (reg_last->sets)
4025 remove_from_dependence_list (insn, &reg_last->sets);
4026 if (reg_last->implicit_sets)
4027 remove_from_dependence_list (insn, &reg_last->implicit_sets);
4028 if (reg_last->clobbers)
4029 remove_from_dependence_list (insn, &reg_last->clobbers);
4030 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4031 && !reg_last->clobbers)
4032 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
4035 if (CALL_P (insn))
4037 remove_from_dependence_list (insn, &deps->last_function_call);
4038 remove_from_dependence_list (insn,
4039 &deps->last_function_call_may_noreturn);
4041 remove_from_dependence_list (insn, &deps->sched_before_next_call);
4044 /* Init deps data vector. */
4045 static void
4046 init_deps_data_vector (void)
4048 int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4049 if (reserve > 0 && ! h_d_i_d.space (reserve))
4050 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
4053 /* If it is profitable to use them, initialize or extend (depending on
4054 GLOBAL_P) dependency data. */
4055 void
4056 sched_deps_init (bool global_p)
4058 /* Average number of insns in the basic block.
4059 '+ 1' is used to make it nonzero. */
4060 int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4062 init_deps_data_vector ();
4064 /* We use another caching mechanism for selective scheduling, so
4065 we don't use this one. */
4066 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4068 /* ?!? We could save some memory by computing a per-region luid mapping
4069 which could reduce both the number of vectors in the cache and the
4070 size of each vector. Instead we just avoid the cache entirely unless
4071 the average number of instructions in a basic block is very high. See
4072 the comment before the declaration of true_dependency_cache for
4073 what we consider "very high". */
4074 cache_size = 0;
4075 extend_dependency_caches (sched_max_luid, true);
4078 if (global_p)
4080 dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
4081 /* Allocate lists for one block at a time. */
4082 insns_in_block);
4083 dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
4084 /* Allocate nodes for one block at a time.
4085 We assume that average insn has
4086 5 producers. */
4087 5 * insns_in_block);
4092 /* Create or extend (depending on CREATE_P) dependency caches to
4093 size N. */
4094 void
4095 extend_dependency_caches (int n, bool create_p)
4097 if (create_p || true_dependency_cache)
4099 int i, luid = cache_size + n;
4101 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4102 luid);
4103 output_dependency_cache = XRESIZEVEC (bitmap_head,
4104 output_dependency_cache, luid);
4105 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4106 luid);
4107 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4108 luid);
4110 if (current_sched_info->flags & DO_SPECULATION)
4111 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4112 luid);
4114 for (i = cache_size; i < luid; i++)
4116 bitmap_initialize (&true_dependency_cache[i], 0);
4117 bitmap_initialize (&output_dependency_cache[i], 0);
4118 bitmap_initialize (&anti_dependency_cache[i], 0);
4119 bitmap_initialize (&control_dependency_cache[i], 0);
4121 if (current_sched_info->flags & DO_SPECULATION)
4122 bitmap_initialize (&spec_dependency_cache[i], 0);
4124 cache_size = luid;
4128 /* Finalize dependency information for the whole function. */
4129 void
4130 sched_deps_finish (void)
4132 gcc_assert (deps_pools_are_empty_p ());
4133 free_alloc_pool_if_empty (&dn_pool);
4134 free_alloc_pool_if_empty (&dl_pool);
4135 gcc_assert (dn_pool == NULL && dl_pool == NULL);
4137 h_d_i_d.release ();
4138 cache_size = 0;
4140 if (true_dependency_cache)
4142 int i;
4144 for (i = 0; i < cache_size; i++)
4146 bitmap_clear (&true_dependency_cache[i]);
4147 bitmap_clear (&output_dependency_cache[i]);
4148 bitmap_clear (&anti_dependency_cache[i]);
4149 bitmap_clear (&control_dependency_cache[i]);
4151 if (sched_deps_info->generate_spec_deps)
4152 bitmap_clear (&spec_dependency_cache[i]);
4154 free (true_dependency_cache);
4155 true_dependency_cache = NULL;
4156 free (output_dependency_cache);
4157 output_dependency_cache = NULL;
4158 free (anti_dependency_cache);
4159 anti_dependency_cache = NULL;
4160 free (control_dependency_cache);
4161 control_dependency_cache = NULL;
4163 if (sched_deps_info->generate_spec_deps)
4165 free (spec_dependency_cache);
4166 spec_dependency_cache = NULL;
4172 /* Initialize some global variables needed by the dependency analysis
4173 code. */
4175 void
4176 init_deps_global (void)
4178 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4179 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4180 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4181 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4182 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4183 reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4184 reg_pending_barrier = NOT_A_BARRIER;
4186 if (!sel_sched_p () || sched_emulate_haifa_p)
4188 sched_deps_info->start_insn = haifa_start_insn;
4189 sched_deps_info->finish_insn = haifa_finish_insn;
4191 sched_deps_info->note_reg_set = haifa_note_reg_set;
4192 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4193 sched_deps_info->note_reg_use = haifa_note_reg_use;
4195 sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4196 sched_deps_info->note_dep = haifa_note_dep;
4200 /* Free everything used by the dependency analysis code. */
4202 void
4203 finish_deps_global (void)
4205 FREE_REG_SET (reg_pending_sets);
4206 FREE_REG_SET (reg_pending_clobbers);
4207 FREE_REG_SET (reg_pending_uses);
4208 FREE_REG_SET (reg_pending_control_uses);
4211 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4212 dw_t
4213 estimate_dep_weak (rtx mem1, rtx mem2)
4215 rtx r1, r2;
4217 if (mem1 == mem2)
4218 /* MEMs are the same - don't speculate. */
4219 return MIN_DEP_WEAK;
4221 r1 = XEXP (mem1, 0);
4222 r2 = XEXP (mem2, 0);
4224 if (r1 == r2
4225 || (REG_P (r1) && REG_P (r2)
4226 && REGNO (r1) == REGNO (r2)))
4227 /* Again, MEMs are the same. */
4228 return MIN_DEP_WEAK;
4229 else if ((REG_P (r1) && !REG_P (r2))
4230 || (!REG_P (r1) && REG_P (r2)))
4231 /* Different addressing modes - reason to be more speculative,
4232 than usual. */
4233 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4234 else
4235 /* We can't say anything about the dependence. */
4236 return UNCERTAIN_DEP_WEAK;
4239 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4240 This function can handle same INSN and ELEM (INSN == ELEM).
4241 It is a convenience wrapper. */
4242 static void
4243 add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4245 ds_t ds;
4246 bool internal;
4248 if (dep_type == REG_DEP_TRUE)
4249 ds = DEP_TRUE;
4250 else if (dep_type == REG_DEP_OUTPUT)
4251 ds = DEP_OUTPUT;
4252 else if (dep_type == REG_DEP_CONTROL)
4253 ds = DEP_CONTROL;
4254 else
4256 gcc_assert (dep_type == REG_DEP_ANTI);
4257 ds = DEP_ANTI;
4260 /* When add_dependence is called from inside sched-deps.c, we expect
4261 cur_insn to be non-null. */
4262 internal = cur_insn != NULL;
4263 if (internal)
4264 gcc_assert (insn == cur_insn);
4265 else
4266 cur_insn = insn;
4268 note_dep (elem, ds);
4269 if (!internal)
4270 cur_insn = NULL;
4273 /* Return weakness of speculative type TYPE in the dep_status DS,
4274 without checking to prevent ICEs on malformed input. */
4275 static dw_t
4276 get_dep_weak_1 (ds_t ds, ds_t type)
4278 ds = ds & type;
4280 switch (type)
4282 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4283 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4284 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4285 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4286 default: gcc_unreachable ();
4289 return (dw_t) ds;
4292 /* Return weakness of speculative type TYPE in the dep_status DS. */
4293 dw_t
4294 get_dep_weak (ds_t ds, ds_t type)
4296 dw_t dw = get_dep_weak_1 (ds, type);
4298 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4299 return dw;
4302 /* Return the dep_status, which has the same parameters as DS, except for
4303 speculative type TYPE, that will have weakness DW. */
4304 ds_t
4305 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4307 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4309 ds &= ~type;
4310 switch (type)
4312 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4313 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4314 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4315 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4316 default: gcc_unreachable ();
4318 return ds;
4321 /* Return the join of two dep_statuses DS1 and DS2.
4322 If MAX_P is true then choose the greater probability,
4323 otherwise multiply probabilities.
4324 This function assumes that both DS1 and DS2 contain speculative bits. */
4325 static ds_t
4326 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4328 ds_t ds, t;
4330 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4332 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4334 t = FIRST_SPEC_TYPE;
4337 if ((ds1 & t) && !(ds2 & t))
4338 ds |= ds1 & t;
4339 else if (!(ds1 & t) && (ds2 & t))
4340 ds |= ds2 & t;
4341 else if ((ds1 & t) && (ds2 & t))
4343 dw_t dw1 = get_dep_weak (ds1, t);
4344 dw_t dw2 = get_dep_weak (ds2, t);
4345 ds_t dw;
4347 if (!max_p)
4349 dw = ((ds_t) dw1) * ((ds_t) dw2);
4350 dw /= MAX_DEP_WEAK;
4351 if (dw < MIN_DEP_WEAK)
4352 dw = MIN_DEP_WEAK;
4354 else
4356 if (dw1 >= dw2)
4357 dw = dw1;
4358 else
4359 dw = dw2;
4362 ds = set_dep_weak (ds, t, (dw_t) dw);
4365 if (t == LAST_SPEC_TYPE)
4366 break;
4367 t <<= SPEC_TYPE_SHIFT;
4369 while (1);
4371 return ds;
4374 /* Return the join of two dep_statuses DS1 and DS2.
4375 This function assumes that both DS1 and DS2 contain speculative bits. */
4376 ds_t
4377 ds_merge (ds_t ds1, ds_t ds2)
4379 return ds_merge_1 (ds1, ds2, false);
4382 /* Return the join of two dep_statuses DS1 and DS2. */
4383 ds_t
4384 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4386 ds_t new_status = ds | ds2;
4388 if (new_status & SPECULATIVE)
4390 if ((ds && !(ds & SPECULATIVE))
4391 || (ds2 && !(ds2 & SPECULATIVE)))
4392 /* Then this dep can't be speculative. */
4393 new_status &= ~SPECULATIVE;
4394 else
4396 /* Both are speculative. Merging probabilities. */
4397 if (mem1)
4399 dw_t dw;
4401 dw = estimate_dep_weak (mem1, mem2);
4402 ds = set_dep_weak (ds, BEGIN_DATA, dw);
4405 if (!ds)
4406 new_status = ds2;
4407 else if (!ds2)
4408 new_status = ds;
4409 else
4410 new_status = ds_merge (ds2, ds);
4414 return new_status;
4417 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4418 probabilities. */
4419 ds_t
4420 ds_max_merge (ds_t ds1, ds_t ds2)
4422 if (ds1 == 0 && ds2 == 0)
4423 return 0;
4425 if (ds1 == 0 && ds2 != 0)
4426 return ds2;
4428 if (ds1 != 0 && ds2 == 0)
4429 return ds1;
4431 return ds_merge_1 (ds1, ds2, true);
4434 /* Return the probability of speculation success for the speculation
4435 status DS. */
4436 dw_t
4437 ds_weak (ds_t ds)
4439 ds_t res = 1, dt;
4440 int n = 0;
4442 dt = FIRST_SPEC_TYPE;
4445 if (ds & dt)
4447 res *= (ds_t) get_dep_weak (ds, dt);
4448 n++;
4451 if (dt == LAST_SPEC_TYPE)
4452 break;
4453 dt <<= SPEC_TYPE_SHIFT;
4455 while (1);
4457 gcc_assert (n);
4458 while (--n)
4459 res /= MAX_DEP_WEAK;
4461 if (res < MIN_DEP_WEAK)
4462 res = MIN_DEP_WEAK;
4464 gcc_assert (res <= MAX_DEP_WEAK);
4466 return (dw_t) res;
4469 /* Return a dep status that contains all speculation types of DS. */
4470 ds_t
4471 ds_get_speculation_types (ds_t ds)
4473 if (ds & BEGIN_DATA)
4474 ds |= BEGIN_DATA;
4475 if (ds & BE_IN_DATA)
4476 ds |= BE_IN_DATA;
4477 if (ds & BEGIN_CONTROL)
4478 ds |= BEGIN_CONTROL;
4479 if (ds & BE_IN_CONTROL)
4480 ds |= BE_IN_CONTROL;
4482 return ds & SPECULATIVE;
4485 /* Return a dep status that contains maximal weakness for each speculation
4486 type present in DS. */
4487 ds_t
4488 ds_get_max_dep_weak (ds_t ds)
4490 if (ds & BEGIN_DATA)
4491 ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4492 if (ds & BE_IN_DATA)
4493 ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4494 if (ds & BEGIN_CONTROL)
4495 ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4496 if (ds & BE_IN_CONTROL)
4497 ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4499 return ds;
4502 /* Dump information about the dependence status S. */
4503 static void
4504 dump_ds (FILE *f, ds_t s)
4506 fprintf (f, "{");
4508 if (s & BEGIN_DATA)
4509 fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4510 if (s & BE_IN_DATA)
4511 fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4512 if (s & BEGIN_CONTROL)
4513 fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4514 if (s & BE_IN_CONTROL)
4515 fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4517 if (s & HARD_DEP)
4518 fprintf (f, "HARD_DEP; ");
4520 if (s & DEP_TRUE)
4521 fprintf (f, "DEP_TRUE; ");
4522 if (s & DEP_OUTPUT)
4523 fprintf (f, "DEP_OUTPUT; ");
4524 if (s & DEP_ANTI)
4525 fprintf (f, "DEP_ANTI; ");
4526 if (s & DEP_CONTROL)
4527 fprintf (f, "DEP_CONTROL; ");
4529 fprintf (f, "}");
4532 DEBUG_FUNCTION void
4533 debug_ds (ds_t s)
4535 dump_ds (stderr, s);
4536 fprintf (stderr, "\n");
4539 #ifdef ENABLE_CHECKING
4540 /* Verify that dependence type and status are consistent.
4541 If RELAXED_P is true, then skip dep_weakness checks. */
4542 static void
4543 check_dep (dep_t dep, bool relaxed_p)
4545 enum reg_note dt = DEP_TYPE (dep);
4546 ds_t ds = DEP_STATUS (dep);
4548 gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4550 if (!(current_sched_info->flags & USE_DEPS_LIST))
4552 gcc_assert (ds == 0);
4553 return;
4556 /* Check that dependence type contains the same bits as the status. */
4557 if (dt == REG_DEP_TRUE)
4558 gcc_assert (ds & DEP_TRUE);
4559 else if (dt == REG_DEP_OUTPUT)
4560 gcc_assert ((ds & DEP_OUTPUT)
4561 && !(ds & DEP_TRUE));
4562 else if (dt == REG_DEP_ANTI)
4563 gcc_assert ((ds & DEP_ANTI)
4564 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4565 else
4566 gcc_assert (dt == REG_DEP_CONTROL
4567 && (ds & DEP_CONTROL)
4568 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4570 /* HARD_DEP can not appear in dep_status of a link. */
4571 gcc_assert (!(ds & HARD_DEP));
4573 /* Check that dependence status is set correctly when speculation is not
4574 supported. */
4575 if (!sched_deps_info->generate_spec_deps)
4576 gcc_assert (!(ds & SPECULATIVE));
4577 else if (ds & SPECULATIVE)
4579 if (!relaxed_p)
4581 ds_t type = FIRST_SPEC_TYPE;
4583 /* Check that dependence weakness is in proper range. */
4586 if (ds & type)
4587 get_dep_weak (ds, type);
4589 if (type == LAST_SPEC_TYPE)
4590 break;
4591 type <<= SPEC_TYPE_SHIFT;
4593 while (1);
4596 if (ds & BEGIN_SPEC)
4598 /* Only true dependence can be data speculative. */
4599 if (ds & BEGIN_DATA)
4600 gcc_assert (ds & DEP_TRUE);
4602 /* Control dependencies in the insn scheduler are represented by
4603 anti-dependencies, therefore only anti dependence can be
4604 control speculative. */
4605 if (ds & BEGIN_CONTROL)
4606 gcc_assert (ds & DEP_ANTI);
4608 else
4610 /* Subsequent speculations should resolve true dependencies. */
4611 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4614 /* Check that true and anti dependencies can't have other speculative
4615 statuses. */
4616 if (ds & DEP_TRUE)
4617 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4618 /* An output dependence can't be speculative at all. */
4619 gcc_assert (!(ds & DEP_OUTPUT));
4620 if (ds & DEP_ANTI)
4621 gcc_assert (ds & BEGIN_CONTROL);
4624 #endif /* ENABLE_CHECKING */
4626 /* The following code discovers opportunities to switch a memory reference
4627 and an increment by modifying the address. We ensure that this is done
4628 only for dependencies that are only used to show a single register
4629 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4630 instruction involved is subject to only one dep that can cause a pattern
4631 change.
4633 When we discover a suitable dependency, we fill in the dep_replacement
4634 structure to show how to modify the memory reference. */
4636 /* Holds information about a pair of memory reference and register increment
4637 insns which depend on each other, but could possibly be interchanged. */
4638 struct mem_inc_info
4640 rtx_insn *inc_insn;
4641 rtx_insn *mem_insn;
4643 rtx *mem_loc;
4644 /* A register occurring in the memory address for which we wish to break
4645 the dependence. This must be identical to the destination register of
4646 the increment. */
4647 rtx mem_reg0;
4648 /* Any kind of index that is added to that register. */
4649 rtx mem_index;
4650 /* The constant offset used in the memory address. */
4651 HOST_WIDE_INT mem_constant;
4652 /* The constant added in the increment insn. Negated if the increment is
4653 after the memory address. */
4654 HOST_WIDE_INT inc_constant;
4655 /* The source register used in the increment. May be different from mem_reg0
4656 if the increment occurs before the memory address. */
4657 rtx inc_input;
4660 /* Verify that the memory location described in MII can be replaced with
4661 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4662 insn remains unchanged by this function. */
4664 static rtx
4665 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4667 rtx mem = *mii->mem_loc;
4668 rtx new_mem;
4670 /* Jump through a lot of hoops to keep the attributes up to date. We
4671 do not want to call one of the change address variants that take
4672 an offset even though we know the offset in many cases. These
4673 assume you are changing where the address is pointing by the
4674 offset. */
4675 new_mem = replace_equiv_address_nv (mem, new_addr);
4676 if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4678 if (sched_verbose >= 5)
4679 fprintf (sched_dump, "validation failure\n");
4680 return NULL_RTX;
4683 /* Put back the old one. */
4684 validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4686 return new_mem;
4689 /* Return true if INSN is of a form "a = b op c" where a and b are
4690 regs. op is + if c is a reg and +|- if c is a const. Fill in
4691 informantion in MII about what is found.
4692 BEFORE_MEM indicates whether the increment is found before or after
4693 a corresponding memory reference. */
4695 static bool
4696 parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem)
4698 rtx pat = single_set (insn);
4699 rtx src, cst;
4700 bool regs_equal;
4702 if (RTX_FRAME_RELATED_P (insn) || !pat)
4703 return false;
4705 /* Result must be single reg. */
4706 if (!REG_P (SET_DEST (pat)))
4707 return false;
4709 if (GET_CODE (SET_SRC (pat)) != PLUS)
4710 return false;
4712 mii->inc_insn = insn;
4713 src = SET_SRC (pat);
4714 mii->inc_input = XEXP (src, 0);
4716 if (!REG_P (XEXP (src, 0)))
4717 return false;
4719 if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4720 return false;
4722 cst = XEXP (src, 1);
4723 if (!CONST_INT_P (cst))
4724 return false;
4725 mii->inc_constant = INTVAL (cst);
4727 regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4729 if (!before_mem)
4731 mii->inc_constant = -mii->inc_constant;
4732 if (!regs_equal)
4733 return false;
4736 if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4738 /* Note that the sign has already been reversed for !before_mem. */
4739 #ifdef STACK_GROWS_DOWNWARD
4740 return mii->inc_constant > 0;
4741 #else
4742 return mii->inc_constant < 0;
4743 #endif
4745 return true;
4748 /* Once a suitable mem reference has been found and the corresponding data
4749 in MII has been filled in, this function is called to find a suitable
4750 add or inc insn involving the register we found in the memory
4751 reference. */
4753 static bool
4754 find_inc (struct mem_inc_info *mii, bool backwards)
4756 sd_iterator_def sd_it;
4757 dep_t dep;
4759 sd_it = sd_iterator_start (mii->mem_insn,
4760 backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4761 while (sd_iterator_cond (&sd_it, &dep))
4763 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4764 rtx_insn *pro = DEP_PRO (dep);
4765 rtx_insn *con = DEP_CON (dep);
4766 rtx_insn *inc_cand = backwards ? pro : con;
4767 if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4768 goto next;
4769 if (parse_add_or_inc (mii, inc_cand, backwards))
4771 struct dep_replacement *desc;
4772 df_ref def;
4773 rtx newaddr, newmem;
4775 if (sched_verbose >= 5)
4776 fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4777 INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4779 /* Need to assure that none of the operands of the inc
4780 instruction are assigned to by the mem insn. */
4781 FOR_EACH_INSN_DEF (def, mii->mem_insn)
4782 if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4783 || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4785 if (sched_verbose >= 5)
4786 fprintf (sched_dump,
4787 "inc conflicts with store failure.\n");
4788 goto next;
4791 newaddr = mii->inc_input;
4792 if (mii->mem_index != NULL_RTX)
4793 newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4794 mii->mem_index);
4795 newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4796 mii->mem_constant + mii->inc_constant);
4797 newmem = attempt_change (mii, newaddr);
4798 if (newmem == NULL_RTX)
4799 goto next;
4800 if (sched_verbose >= 5)
4801 fprintf (sched_dump, "successful address replacement\n");
4802 desc = XCNEW (struct dep_replacement);
4803 DEP_REPLACE (dep) = desc;
4804 desc->loc = mii->mem_loc;
4805 desc->newval = newmem;
4806 desc->orig = *desc->loc;
4807 desc->insn = mii->mem_insn;
4808 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4809 INSN_SPEC_BACK_DEPS (con));
4810 if (backwards)
4812 FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4813 add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4814 REG_DEP_TRUE);
4816 else
4818 FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4819 add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4820 REG_DEP_ANTI);
4822 return true;
4824 next:
4825 sd_iterator_next (&sd_it);
4827 return false;
4830 /* A recursive function that walks ADDRESS_OF_X to find memory references
4831 which could be modified during scheduling. We call find_inc for each
4832 one we find that has a recognizable form. MII holds information about
4833 the pair of memory/increment instructions.
4834 We ensure that every instruction with a memory reference (which will be
4835 the location of the replacement) is assigned at most one breakable
4836 dependency. */
4838 static bool
4839 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4841 rtx x = *address_of_x;
4842 enum rtx_code code = GET_CODE (x);
4843 const char *const fmt = GET_RTX_FORMAT (code);
4844 int i;
4846 if (code == MEM)
4848 rtx reg0 = XEXP (x, 0);
4850 mii->mem_loc = address_of_x;
4851 mii->mem_index = NULL_RTX;
4852 mii->mem_constant = 0;
4853 if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4855 mii->mem_constant = INTVAL (XEXP (reg0, 1));
4856 reg0 = XEXP (reg0, 0);
4858 if (GET_CODE (reg0) == PLUS)
4860 mii->mem_index = XEXP (reg0, 1);
4861 reg0 = XEXP (reg0, 0);
4863 if (REG_P (reg0))
4865 df_ref use;
4866 int occurrences = 0;
4868 /* Make sure this reg appears only once in this insn. Can't use
4869 count_occurrences since that only works for pseudos. */
4870 FOR_EACH_INSN_USE (use, mii->mem_insn)
4871 if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use)))
4872 if (++occurrences > 1)
4874 if (sched_verbose >= 5)
4875 fprintf (sched_dump, "mem count failure\n");
4876 return false;
4879 mii->mem_reg0 = reg0;
4880 return find_inc (mii, true) || find_inc (mii, false);
4882 return false;
4885 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4887 /* If REG occurs inside a MEM used in a bit-field reference,
4888 that is unacceptable. */
4889 return false;
4892 /* Time for some deep diving. */
4893 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4895 if (fmt[i] == 'e')
4897 if (find_mem (mii, &XEXP (x, i)))
4898 return true;
4900 else if (fmt[i] == 'E')
4902 int j;
4903 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4904 if (find_mem (mii, &XVECEXP (x, i, j)))
4905 return true;
4908 return false;
4912 /* Examine the instructions between HEAD and TAIL and try to find
4913 dependencies that can be broken by modifying one of the patterns. */
4915 void
4916 find_modifiable_mems (rtx_insn *head, rtx_insn *tail)
4918 rtx_insn *insn, *next_tail = NEXT_INSN (tail);
4919 int success_in_block = 0;
4921 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4923 struct mem_inc_info mii;
4925 if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4926 continue;
4928 mii.mem_insn = insn;
4929 if (find_mem (&mii, &PATTERN (insn)))
4930 success_in_block++;
4932 if (success_in_block && sched_verbose >= 5)
4933 fprintf (sched_dump, "%d candidates for address modification found.\n",
4934 success_in_block);
4937 #endif /* INSN_SCHEDULING */