2012-11-28 Oleg Raikhman <oleg@adapteva.com>
[official-gcc.git] / gcc / sched-deps.c
blobf8b124d46f146980a8b727b09b7e5bff0b2b2458
1 /* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
5 2011, 2012
6 Free Software Foundation, Inc.
7 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
8 and currently maintained by, Jim Wilson (wilson@cygnus.com)
10 This file is part of GCC.
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 3, or (at your option) any later
15 version.
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 for more details.
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING3. If not see
24 <http://www.gnu.org/licenses/>. */
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "diagnostic-core.h"
31 #include "rtl.h"
32 #include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
33 #include "tm_p.h"
34 #include "hard-reg-set.h"
35 #include "regs.h"
36 #include "function.h"
37 #include "flags.h"
38 #include "insn-config.h"
39 #include "insn-attr.h"
40 #include "except.h"
41 #include "recog.h"
42 #include "emit-rtl.h"
43 #include "sched-int.h"
44 #include "params.h"
45 #include "cselib.h"
46 #include "ira.h"
47 #include "target.h"
49 #ifdef INSN_SCHEDULING
51 #ifdef ENABLE_CHECKING
52 #define CHECK (true)
53 #else
54 #define CHECK (false)
55 #endif
57 /* Holds current parameters for the dependency analyzer. */
58 struct sched_deps_info_def *sched_deps_info;
60 /* The data is specific to the Haifa scheduler. */
61 vec<haifa_deps_insn_data_def>
62 h_d_i_d = vNULL;
64 /* Return the major type present in the DS. */
65 enum reg_note
66 ds_to_dk (ds_t ds)
68 if (ds & DEP_TRUE)
69 return REG_DEP_TRUE;
71 if (ds & DEP_OUTPUT)
72 return REG_DEP_OUTPUT;
74 if (ds & DEP_CONTROL)
75 return REG_DEP_CONTROL;
77 gcc_assert (ds & DEP_ANTI);
79 return REG_DEP_ANTI;
82 /* Return equivalent dep_status. */
83 ds_t
84 dk_to_ds (enum reg_note dk)
86 switch (dk)
88 case REG_DEP_TRUE:
89 return DEP_TRUE;
91 case REG_DEP_OUTPUT:
92 return DEP_OUTPUT;
94 case REG_DEP_CONTROL:
95 return DEP_CONTROL;
97 default:
98 gcc_assert (dk == REG_DEP_ANTI);
99 return DEP_ANTI;
103 /* Functions to operate with dependence information container - dep_t. */
105 /* Init DEP with the arguments. */
106 void
107 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
109 DEP_PRO (dep) = pro;
110 DEP_CON (dep) = con;
111 DEP_TYPE (dep) = type;
112 DEP_STATUS (dep) = ds;
113 DEP_COST (dep) = UNKNOWN_DEP_COST;
114 DEP_NONREG (dep) = 0;
115 DEP_MULTIPLE (dep) = 0;
116 DEP_REPLACE (dep) = NULL;
119 /* Init DEP with the arguments.
120 While most of the scheduler (including targets) only need the major type
121 of the dependency, it is convenient to hide full dep_status from them. */
122 void
123 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
125 ds_t ds;
127 if ((current_sched_info->flags & USE_DEPS_LIST))
128 ds = dk_to_ds (kind);
129 else
130 ds = 0;
132 init_dep_1 (dep, pro, con, kind, ds);
135 /* Make a copy of FROM in TO. */
136 static void
137 copy_dep (dep_t to, dep_t from)
139 memcpy (to, from, sizeof (*to));
142 static void dump_ds (FILE *, ds_t);
144 /* Define flags for dump_dep (). */
146 /* Dump producer of the dependence. */
147 #define DUMP_DEP_PRO (2)
149 /* Dump consumer of the dependence. */
150 #define DUMP_DEP_CON (4)
152 /* Dump type of the dependence. */
153 #define DUMP_DEP_TYPE (8)
155 /* Dump status of the dependence. */
156 #define DUMP_DEP_STATUS (16)
158 /* Dump all information about the dependence. */
159 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
160 |DUMP_DEP_STATUS)
162 /* Dump DEP to DUMP.
163 FLAGS is a bit mask specifying what information about DEP needs
164 to be printed.
165 If FLAGS has the very first bit set, then dump all information about DEP
166 and propagate this bit into the callee dump functions. */
167 static void
168 dump_dep (FILE *dump, dep_t dep, int flags)
170 if (flags & 1)
171 flags |= DUMP_DEP_ALL;
173 fprintf (dump, "<");
175 if (flags & DUMP_DEP_PRO)
176 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
178 if (flags & DUMP_DEP_CON)
179 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
181 if (flags & DUMP_DEP_TYPE)
183 char t;
184 enum reg_note type = DEP_TYPE (dep);
186 switch (type)
188 case REG_DEP_TRUE:
189 t = 't';
190 break;
192 case REG_DEP_OUTPUT:
193 t = 'o';
194 break;
196 case REG_DEP_CONTROL:
197 t = 'c';
198 break;
200 case REG_DEP_ANTI:
201 t = 'a';
202 break;
204 default:
205 gcc_unreachable ();
206 break;
209 fprintf (dump, "%c; ", t);
212 if (flags & DUMP_DEP_STATUS)
214 if (current_sched_info->flags & USE_DEPS_LIST)
215 dump_ds (dump, DEP_STATUS (dep));
218 fprintf (dump, ">");
221 /* Default flags for dump_dep (). */
222 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
224 /* Dump all fields of DEP to STDERR. */
225 void
226 sd_debug_dep (dep_t dep)
228 dump_dep (stderr, dep, 1);
229 fprintf (stderr, "\n");
232 /* Determine whether DEP is a dependency link of a non-debug insn on a
233 debug insn. */
235 static inline bool
236 depl_on_debug_p (dep_link_t dep)
238 return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
239 && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
242 /* Functions to operate with a single link from the dependencies lists -
243 dep_link_t. */
245 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
246 PREV_NEXT_P. */
247 static void
248 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
250 dep_link_t next = *prev_nextp;
252 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
253 && DEP_LINK_NEXT (l) == NULL);
255 /* Init node being inserted. */
256 DEP_LINK_PREV_NEXTP (l) = prev_nextp;
257 DEP_LINK_NEXT (l) = next;
259 /* Fix next node. */
260 if (next != NULL)
262 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
264 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
267 /* Fix prev node. */
268 *prev_nextp = l;
271 /* Add dep_link LINK to deps_list L. */
272 static void
273 add_to_deps_list (dep_link_t link, deps_list_t l)
275 attach_dep_link (link, &DEPS_LIST_FIRST (l));
277 /* Don't count debug deps. */
278 if (!depl_on_debug_p (link))
279 ++DEPS_LIST_N_LINKS (l);
282 /* Detach dep_link L from the list. */
283 static void
284 detach_dep_link (dep_link_t l)
286 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
287 dep_link_t next = DEP_LINK_NEXT (l);
289 *prev_nextp = next;
291 if (next != NULL)
292 DEP_LINK_PREV_NEXTP (next) = prev_nextp;
294 DEP_LINK_PREV_NEXTP (l) = NULL;
295 DEP_LINK_NEXT (l) = NULL;
298 /* Remove link LINK from list LIST. */
299 static void
300 remove_from_deps_list (dep_link_t link, deps_list_t list)
302 detach_dep_link (link);
304 /* Don't count debug deps. */
305 if (!depl_on_debug_p (link))
306 --DEPS_LIST_N_LINKS (list);
309 /* Move link LINK from list FROM to list TO. */
310 static void
311 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
313 remove_from_deps_list (link, from);
314 add_to_deps_list (link, to);
317 /* Return true of LINK is not attached to any list. */
318 static bool
319 dep_link_is_detached_p (dep_link_t link)
321 return DEP_LINK_PREV_NEXTP (link) == NULL;
324 /* Pool to hold all dependency nodes (dep_node_t). */
325 static alloc_pool dn_pool;
327 /* Number of dep_nodes out there. */
328 static int dn_pool_diff = 0;
330 /* Create a dep_node. */
331 static dep_node_t
332 create_dep_node (void)
334 dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
335 dep_link_t back = DEP_NODE_BACK (n);
336 dep_link_t forw = DEP_NODE_FORW (n);
338 DEP_LINK_NODE (back) = n;
339 DEP_LINK_NEXT (back) = NULL;
340 DEP_LINK_PREV_NEXTP (back) = NULL;
342 DEP_LINK_NODE (forw) = n;
343 DEP_LINK_NEXT (forw) = NULL;
344 DEP_LINK_PREV_NEXTP (forw) = NULL;
346 ++dn_pool_diff;
348 return n;
351 /* Delete dep_node N. N must not be connected to any deps_list. */
352 static void
353 delete_dep_node (dep_node_t n)
355 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
356 && dep_link_is_detached_p (DEP_NODE_FORW (n)));
358 --dn_pool_diff;
360 pool_free (dn_pool, n);
363 /* Pool to hold dependencies lists (deps_list_t). */
364 static alloc_pool dl_pool;
366 /* Number of deps_lists out there. */
367 static int dl_pool_diff = 0;
369 /* Functions to operate with dependences lists - deps_list_t. */
371 /* Return true if list L is empty. */
372 static bool
373 deps_list_empty_p (deps_list_t l)
375 return DEPS_LIST_N_LINKS (l) == 0;
378 /* Create a new deps_list. */
379 static deps_list_t
380 create_deps_list (void)
382 deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
384 DEPS_LIST_FIRST (l) = NULL;
385 DEPS_LIST_N_LINKS (l) = 0;
387 ++dl_pool_diff;
388 return l;
391 /* Free deps_list L. */
392 static void
393 free_deps_list (deps_list_t l)
395 gcc_assert (deps_list_empty_p (l));
397 --dl_pool_diff;
399 pool_free (dl_pool, l);
402 /* Return true if there is no dep_nodes and deps_lists out there.
403 After the region is scheduled all the dependency nodes and lists
404 should [generally] be returned to pool. */
405 bool
406 deps_pools_are_empty_p (void)
408 return dn_pool_diff == 0 && dl_pool_diff == 0;
411 /* Remove all elements from L. */
412 static void
413 clear_deps_list (deps_list_t l)
417 dep_link_t link = DEPS_LIST_FIRST (l);
419 if (link == NULL)
420 break;
422 remove_from_deps_list (link, l);
424 while (1);
427 /* Decide whether a dependency should be treated as a hard or a speculative
428 dependency. */
429 static bool
430 dep_spec_p (dep_t dep)
432 if (current_sched_info->flags & DO_SPECULATION)
434 if (DEP_STATUS (dep) & SPECULATIVE)
435 return true;
437 if (current_sched_info->flags & DO_PREDICATION)
439 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
440 return true;
442 if (DEP_REPLACE (dep) != NULL)
443 return true;
444 return false;
447 static regset reg_pending_sets;
448 static regset reg_pending_clobbers;
449 static regset reg_pending_uses;
450 static regset reg_pending_control_uses;
451 static enum reg_pending_barrier_mode reg_pending_barrier;
453 /* Hard registers implicitly clobbered or used (or may be implicitly
454 clobbered or used) by the currently analyzed insn. For example,
455 insn in its constraint has one register class. Even if there is
456 currently no hard register in the insn, the particular hard
457 register will be in the insn after reload pass because the
458 constraint requires it. */
459 static HARD_REG_SET implicit_reg_pending_clobbers;
460 static HARD_REG_SET implicit_reg_pending_uses;
462 /* To speed up the test for duplicate dependency links we keep a
463 record of dependencies created by add_dependence when the average
464 number of instructions in a basic block is very large.
466 Studies have shown that there is typically around 5 instructions between
467 branches for typical C code. So we can make a guess that the average
468 basic block is approximately 5 instructions long; we will choose 100X
469 the average size as a very large basic block.
471 Each insn has associated bitmaps for its dependencies. Each bitmap
472 has enough entries to represent a dependency on any other insn in
473 the insn chain. All bitmap for true dependencies cache is
474 allocated then the rest two ones are also allocated. */
475 static bitmap_head *true_dependency_cache = NULL;
476 static bitmap_head *output_dependency_cache = NULL;
477 static bitmap_head *anti_dependency_cache = NULL;
478 static bitmap_head *control_dependency_cache = NULL;
479 static bitmap_head *spec_dependency_cache = NULL;
480 static int cache_size;
482 /* True if we should mark added dependencies as a non-register deps. */
483 static bool mark_as_hard;
485 static int deps_may_trap_p (const_rtx);
486 static void add_dependence_1 (rtx, rtx, enum reg_note);
487 static void add_dependence_list (rtx, rtx, int, enum reg_note, bool);
488 static void add_dependence_list_and_free (struct deps_desc *, rtx,
489 rtx *, int, enum reg_note, bool);
490 static void delete_all_dependences (rtx);
491 static void chain_to_prev_insn (rtx);
493 static void flush_pending_lists (struct deps_desc *, rtx, int, int);
494 static void sched_analyze_1 (struct deps_desc *, rtx, rtx);
495 static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
496 static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
498 static bool sched_has_condition_p (const_rtx);
499 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
501 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
502 rtx, rtx);
503 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
505 #ifdef ENABLE_CHECKING
506 static void check_dep (dep_t, bool);
507 #endif
509 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
511 static int
512 deps_may_trap_p (const_rtx mem)
514 const_rtx addr = XEXP (mem, 0);
516 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
518 const_rtx t = get_reg_known_value (REGNO (addr));
519 if (t)
520 addr = t;
522 return rtx_addr_can_trap_p (addr);
526 /* Find the condition under which INSN is executed. If REV is not NULL,
527 it is set to TRUE when the returned comparison should be reversed
528 to get the actual condition. */
529 static rtx
530 sched_get_condition_with_rev_uncached (const_rtx insn, bool *rev)
532 rtx pat = PATTERN (insn);
533 rtx src;
535 if (rev)
536 *rev = false;
538 if (GET_CODE (pat) == COND_EXEC)
539 return COND_EXEC_TEST (pat);
541 if (!any_condjump_p (insn) || !onlyjump_p (insn))
542 return 0;
544 src = SET_SRC (pc_set (insn));
546 if (XEXP (src, 2) == pc_rtx)
547 return XEXP (src, 0);
548 else if (XEXP (src, 1) == pc_rtx)
550 rtx cond = XEXP (src, 0);
551 enum rtx_code revcode = reversed_comparison_code (cond, insn);
553 if (revcode == UNKNOWN)
554 return 0;
556 if (rev)
557 *rev = true;
558 return cond;
561 return 0;
564 /* Return the condition under which INSN does not execute (i.e. the
565 not-taken condition for a conditional branch), or NULL if we cannot
566 find such a condition. The caller should make a copy of the condition
567 before using it. */
569 sched_get_reverse_condition_uncached (const_rtx insn)
571 bool rev;
572 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
573 if (cond == NULL_RTX)
574 return cond;
575 if (!rev)
577 enum rtx_code revcode = reversed_comparison_code (cond, insn);
578 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
579 XEXP (cond, 0),
580 XEXP (cond, 1));
582 return cond;
585 /* Caching variant of sched_get_condition_with_rev_uncached.
586 We only do actual work the first time we come here for an insn; the
587 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
588 static rtx
589 sched_get_condition_with_rev (const_rtx insn, bool *rev)
591 bool tmp;
593 if (INSN_LUID (insn) == 0)
594 return sched_get_condition_with_rev_uncached (insn, rev);
596 if (INSN_CACHED_COND (insn) == const_true_rtx)
597 return NULL_RTX;
599 if (INSN_CACHED_COND (insn) != NULL_RTX)
601 if (rev)
602 *rev = INSN_REVERSE_COND (insn);
603 return INSN_CACHED_COND (insn);
606 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
607 INSN_REVERSE_COND (insn) = tmp;
609 if (INSN_CACHED_COND (insn) == NULL_RTX)
611 INSN_CACHED_COND (insn) = const_true_rtx;
612 return NULL_RTX;
615 if (rev)
616 *rev = INSN_REVERSE_COND (insn);
617 return INSN_CACHED_COND (insn);
620 /* True when we can find a condition under which INSN is executed. */
621 static bool
622 sched_has_condition_p (const_rtx insn)
624 return !! sched_get_condition_with_rev (insn, NULL);
629 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
630 static int
631 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
633 if (COMPARISON_P (cond1)
634 && COMPARISON_P (cond2)
635 && GET_CODE (cond1) ==
636 (rev1==rev2
637 ? reversed_comparison_code (cond2, NULL)
638 : GET_CODE (cond2))
639 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
640 && XEXP (cond1, 1) == XEXP (cond2, 1))
641 return 1;
642 return 0;
645 /* Return true if insn1 and insn2 can never depend on one another because
646 the conditions under which they are executed are mutually exclusive. */
647 bool
648 sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
650 rtx cond1, cond2;
651 bool rev1 = false, rev2 = false;
653 /* df doesn't handle conditional lifetimes entirely correctly;
654 calls mess up the conditional lifetimes. */
655 if (!CALL_P (insn1) && !CALL_P (insn2))
657 cond1 = sched_get_condition_with_rev (insn1, &rev1);
658 cond2 = sched_get_condition_with_rev (insn2, &rev2);
659 if (cond1 && cond2
660 && conditions_mutex_p (cond1, cond2, rev1, rev2)
661 /* Make sure first instruction doesn't affect condition of second
662 instruction if switched. */
663 && !modified_in_p (cond1, insn2)
664 /* Make sure second instruction doesn't affect condition of first
665 instruction if switched. */
666 && !modified_in_p (cond2, insn1))
667 return true;
669 return false;
673 /* Return true if INSN can potentially be speculated with type DS. */
674 bool
675 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
677 if (HAS_INTERNAL_DEP (insn))
678 return false;
680 if (!NONJUMP_INSN_P (insn))
681 return false;
683 if (SCHED_GROUP_P (insn))
684 return false;
686 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
687 return false;
689 if (side_effects_p (PATTERN (insn)))
690 return false;
692 if (ds & BE_IN_SPEC)
693 /* The following instructions, which depend on a speculatively scheduled
694 instruction, cannot be speculatively scheduled along. */
696 if (may_trap_or_fault_p (PATTERN (insn)))
697 /* If instruction might fault, it cannot be speculatively scheduled.
698 For control speculation it's obvious why and for data speculation
699 it's because the insn might get wrong input if speculation
700 wasn't successful. */
701 return false;
703 if ((ds & BE_IN_DATA)
704 && sched_has_condition_p (insn))
705 /* If this is a predicated instruction, then it cannot be
706 speculatively scheduled. See PR35659. */
707 return false;
710 return true;
713 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
714 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
715 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
716 This function is used to switch sd_iterator to the next list.
717 !!! For internal use only. Might consider moving it to sched-int.h. */
718 void
719 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
720 deps_list_t *list_ptr, bool *resolved_p_ptr)
722 sd_list_types_def types = *types_ptr;
724 if (types & SD_LIST_HARD_BACK)
726 *list_ptr = INSN_HARD_BACK_DEPS (insn);
727 *resolved_p_ptr = false;
728 *types_ptr = types & ~SD_LIST_HARD_BACK;
730 else if (types & SD_LIST_SPEC_BACK)
732 *list_ptr = INSN_SPEC_BACK_DEPS (insn);
733 *resolved_p_ptr = false;
734 *types_ptr = types & ~SD_LIST_SPEC_BACK;
736 else if (types & SD_LIST_FORW)
738 *list_ptr = INSN_FORW_DEPS (insn);
739 *resolved_p_ptr = false;
740 *types_ptr = types & ~SD_LIST_FORW;
742 else if (types & SD_LIST_RES_BACK)
744 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
745 *resolved_p_ptr = true;
746 *types_ptr = types & ~SD_LIST_RES_BACK;
748 else if (types & SD_LIST_RES_FORW)
750 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
751 *resolved_p_ptr = true;
752 *types_ptr = types & ~SD_LIST_RES_FORW;
754 else
756 *list_ptr = NULL;
757 *resolved_p_ptr = false;
758 *types_ptr = SD_LIST_NONE;
762 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
764 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
766 int size = 0;
768 while (list_types != SD_LIST_NONE)
770 deps_list_t list;
771 bool resolved_p;
773 sd_next_list (insn, &list_types, &list, &resolved_p);
774 if (list)
775 size += DEPS_LIST_N_LINKS (list);
778 return size;
781 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
783 bool
784 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
786 while (list_types != SD_LIST_NONE)
788 deps_list_t list;
789 bool resolved_p;
791 sd_next_list (insn, &list_types, &list, &resolved_p);
792 if (!deps_list_empty_p (list))
793 return false;
796 return true;
799 /* Initialize data for INSN. */
800 void
801 sd_init_insn (rtx insn)
803 INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
804 INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
805 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
806 INSN_FORW_DEPS (insn) = create_deps_list ();
807 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
809 /* ??? It would be nice to allocate dependency caches here. */
812 /* Free data for INSN. */
813 void
814 sd_finish_insn (rtx insn)
816 /* ??? It would be nice to deallocate dependency caches here. */
818 free_deps_list (INSN_HARD_BACK_DEPS (insn));
819 INSN_HARD_BACK_DEPS (insn) = NULL;
821 free_deps_list (INSN_SPEC_BACK_DEPS (insn));
822 INSN_SPEC_BACK_DEPS (insn) = NULL;
824 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
825 INSN_RESOLVED_BACK_DEPS (insn) = NULL;
827 free_deps_list (INSN_FORW_DEPS (insn));
828 INSN_FORW_DEPS (insn) = NULL;
830 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
831 INSN_RESOLVED_FORW_DEPS (insn) = NULL;
834 /* Find a dependency between producer PRO and consumer CON.
835 Search through resolved dependency lists if RESOLVED_P is true.
836 If no such dependency is found return NULL,
837 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
838 with an iterator pointing to it. */
839 static dep_t
840 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
841 sd_iterator_def *sd_it_ptr)
843 sd_list_types_def pro_list_type;
844 sd_list_types_def con_list_type;
845 sd_iterator_def sd_it;
846 dep_t dep;
847 bool found_p = false;
849 if (resolved_p)
851 pro_list_type = SD_LIST_RES_FORW;
852 con_list_type = SD_LIST_RES_BACK;
854 else
856 pro_list_type = SD_LIST_FORW;
857 con_list_type = SD_LIST_BACK;
860 /* Walk through either back list of INSN or forw list of ELEM
861 depending on which one is shorter. */
862 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
864 /* Find the dep_link with producer PRO in consumer's back_deps. */
865 FOR_EACH_DEP (con, con_list_type, sd_it, dep)
866 if (DEP_PRO (dep) == pro)
868 found_p = true;
869 break;
872 else
874 /* Find the dep_link with consumer CON in producer's forw_deps. */
875 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
876 if (DEP_CON (dep) == con)
878 found_p = true;
879 break;
883 if (found_p)
885 if (sd_it_ptr != NULL)
886 *sd_it_ptr = sd_it;
888 return dep;
891 return NULL;
894 /* Find a dependency between producer PRO and consumer CON.
895 Use dependency [if available] to check if dependency is present at all.
896 Search through resolved dependency lists if RESOLVED_P is true.
897 If the dependency or NULL if none found. */
898 dep_t
899 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
901 if (true_dependency_cache != NULL)
902 /* Avoiding the list walk below can cut compile times dramatically
903 for some code. */
905 int elem_luid = INSN_LUID (pro);
906 int insn_luid = INSN_LUID (con);
908 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
909 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
910 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
911 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
912 return NULL;
915 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
918 /* Add or update a dependence described by DEP.
919 MEM1 and MEM2, if non-null, correspond to memory locations in case of
920 data speculation.
922 The function returns a value indicating if an old entry has been changed
923 or a new entry has been added to insn's backward deps.
925 This function merely checks if producer and consumer is the same insn
926 and doesn't create a dep in this case. Actual manipulation of
927 dependence data structures is performed in add_or_update_dep_1. */
928 static enum DEPS_ADJUST_RESULT
929 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
931 rtx elem = DEP_PRO (dep);
932 rtx insn = DEP_CON (dep);
934 gcc_assert (INSN_P (insn) && INSN_P (elem));
936 /* Don't depend an insn on itself. */
937 if (insn == elem)
939 if (sched_deps_info->generate_spec_deps)
940 /* INSN has an internal dependence, which we can't overcome. */
941 HAS_INTERNAL_DEP (insn) = 1;
943 return DEP_NODEP;
946 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
949 /* Ask dependency caches what needs to be done for dependence DEP.
950 Return DEP_CREATED if new dependence should be created and there is no
951 need to try to find one searching the dependencies lists.
952 Return DEP_PRESENT if there already is a dependence described by DEP and
953 hence nothing is to be done.
954 Return DEP_CHANGED if there already is a dependence, but it should be
955 updated to incorporate additional information from DEP. */
956 static enum DEPS_ADJUST_RESULT
957 ask_dependency_caches (dep_t dep)
959 int elem_luid = INSN_LUID (DEP_PRO (dep));
960 int insn_luid = INSN_LUID (DEP_CON (dep));
962 gcc_assert (true_dependency_cache != NULL
963 && output_dependency_cache != NULL
964 && anti_dependency_cache != NULL
965 && control_dependency_cache != NULL);
967 if (!(current_sched_info->flags & USE_DEPS_LIST))
969 enum reg_note present_dep_type;
971 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
972 present_dep_type = REG_DEP_TRUE;
973 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
974 present_dep_type = REG_DEP_OUTPUT;
975 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
976 present_dep_type = REG_DEP_ANTI;
977 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
978 present_dep_type = REG_DEP_CONTROL;
979 else
980 /* There is no existing dep so it should be created. */
981 return DEP_CREATED;
983 if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
984 /* DEP does not add anything to the existing dependence. */
985 return DEP_PRESENT;
987 else
989 ds_t present_dep_types = 0;
991 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
992 present_dep_types |= DEP_TRUE;
993 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
994 present_dep_types |= DEP_OUTPUT;
995 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
996 present_dep_types |= DEP_ANTI;
997 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
998 present_dep_types |= DEP_CONTROL;
1000 if (present_dep_types == 0)
1001 /* There is no existing dep so it should be created. */
1002 return DEP_CREATED;
1004 if (!(current_sched_info->flags & DO_SPECULATION)
1005 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
1007 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
1008 == present_dep_types)
1009 /* DEP does not add anything to the existing dependence. */
1010 return DEP_PRESENT;
1012 else
1014 /* Only true dependencies can be data speculative and
1015 only anti dependencies can be control speculative. */
1016 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1017 == present_dep_types);
1019 /* if (DEP is SPECULATIVE) then
1020 ..we should update DEP_STATUS
1021 else
1022 ..we should reset existing dep to non-speculative. */
1026 return DEP_CHANGED;
1029 /* Set dependency caches according to DEP. */
1030 static void
1031 set_dependency_caches (dep_t dep)
1033 int elem_luid = INSN_LUID (DEP_PRO (dep));
1034 int insn_luid = INSN_LUID (DEP_CON (dep));
1036 if (!(current_sched_info->flags & USE_DEPS_LIST))
1038 switch (DEP_TYPE (dep))
1040 case REG_DEP_TRUE:
1041 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1042 break;
1044 case REG_DEP_OUTPUT:
1045 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1046 break;
1048 case REG_DEP_ANTI:
1049 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1050 break;
1052 case REG_DEP_CONTROL:
1053 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1054 break;
1056 default:
1057 gcc_unreachable ();
1060 else
1062 ds_t ds = DEP_STATUS (dep);
1064 if (ds & DEP_TRUE)
1065 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1066 if (ds & DEP_OUTPUT)
1067 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1068 if (ds & DEP_ANTI)
1069 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1070 if (ds & DEP_CONTROL)
1071 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1073 if (ds & SPECULATIVE)
1075 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1076 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1081 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1082 caches accordingly. */
1083 static void
1084 update_dependency_caches (dep_t dep, enum reg_note old_type)
1086 int elem_luid = INSN_LUID (DEP_PRO (dep));
1087 int insn_luid = INSN_LUID (DEP_CON (dep));
1089 /* Clear corresponding cache entry because type of the link
1090 may have changed. Keep them if we use_deps_list. */
1091 if (!(current_sched_info->flags & USE_DEPS_LIST))
1093 switch (old_type)
1095 case REG_DEP_OUTPUT:
1096 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1097 break;
1099 case REG_DEP_ANTI:
1100 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1101 break;
1103 case REG_DEP_CONTROL:
1104 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1105 break;
1107 default:
1108 gcc_unreachable ();
1112 set_dependency_caches (dep);
1115 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1116 static void
1117 change_spec_dep_to_hard (sd_iterator_def sd_it)
1119 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1120 dep_link_t link = DEP_NODE_BACK (node);
1121 dep_t dep = DEP_NODE_DEP (node);
1122 rtx elem = DEP_PRO (dep);
1123 rtx insn = DEP_CON (dep);
1125 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1127 DEP_STATUS (dep) &= ~SPECULATIVE;
1129 if (true_dependency_cache != NULL)
1130 /* Clear the cache entry. */
1131 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1132 INSN_LUID (elem));
1135 /* Update DEP to incorporate information from NEW_DEP.
1136 SD_IT points to DEP in case it should be moved to another list.
1137 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1138 data-speculative dependence should be updated. */
1139 static enum DEPS_ADJUST_RESULT
1140 update_dep (dep_t dep, dep_t new_dep,
1141 sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1142 rtx mem1 ATTRIBUTE_UNUSED,
1143 rtx mem2 ATTRIBUTE_UNUSED)
1145 enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1146 enum reg_note old_type = DEP_TYPE (dep);
1147 bool was_spec = dep_spec_p (dep);
1149 DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1150 DEP_MULTIPLE (dep) = 1;
1152 /* If this is a more restrictive type of dependence than the
1153 existing one, then change the existing dependence to this
1154 type. */
1155 if ((int) DEP_TYPE (new_dep) < (int) old_type)
1157 DEP_TYPE (dep) = DEP_TYPE (new_dep);
1158 res = DEP_CHANGED;
1161 if (current_sched_info->flags & USE_DEPS_LIST)
1162 /* Update DEP_STATUS. */
1164 ds_t dep_status = DEP_STATUS (dep);
1165 ds_t ds = DEP_STATUS (new_dep);
1166 ds_t new_status = ds | dep_status;
1168 if (new_status & SPECULATIVE)
1170 /* Either existing dep or a dep we're adding or both are
1171 speculative. */
1172 if (!(ds & SPECULATIVE)
1173 || !(dep_status & SPECULATIVE))
1174 /* The new dep can't be speculative. */
1175 new_status &= ~SPECULATIVE;
1176 else
1178 /* Both are speculative. Merge probabilities. */
1179 if (mem1 != NULL)
1181 dw_t dw;
1183 dw = estimate_dep_weak (mem1, mem2);
1184 ds = set_dep_weak (ds, BEGIN_DATA, dw);
1187 new_status = ds_merge (dep_status, ds);
1191 ds = new_status;
1193 if (dep_status != ds)
1195 DEP_STATUS (dep) = ds;
1196 res = DEP_CHANGED;
1200 if (was_spec && !dep_spec_p (dep))
1201 /* The old dep was speculative, but now it isn't. */
1202 change_spec_dep_to_hard (sd_it);
1204 if (true_dependency_cache != NULL
1205 && res == DEP_CHANGED)
1206 update_dependency_caches (dep, old_type);
1208 return res;
1211 /* Add or update a dependence described by DEP.
1212 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1213 data speculation.
1215 The function returns a value indicating if an old entry has been changed
1216 or a new entry has been added to insn's backward deps or nothing has
1217 been updated at all. */
1218 static enum DEPS_ADJUST_RESULT
1219 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1220 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1222 bool maybe_present_p = true;
1223 bool present_p = false;
1225 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1226 && DEP_PRO (new_dep) != DEP_CON (new_dep));
1228 #ifdef ENABLE_CHECKING
1229 check_dep (new_dep, mem1 != NULL);
1230 #endif
1232 if (true_dependency_cache != NULL)
1234 switch (ask_dependency_caches (new_dep))
1236 case DEP_PRESENT:
1237 return DEP_PRESENT;
1239 case DEP_CHANGED:
1240 maybe_present_p = true;
1241 present_p = true;
1242 break;
1244 case DEP_CREATED:
1245 maybe_present_p = false;
1246 present_p = false;
1247 break;
1249 default:
1250 gcc_unreachable ();
1251 break;
1255 /* Check that we don't already have this dependence. */
1256 if (maybe_present_p)
1258 dep_t present_dep;
1259 sd_iterator_def sd_it;
1261 gcc_assert (true_dependency_cache == NULL || present_p);
1263 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1264 DEP_CON (new_dep),
1265 resolved_p, &sd_it);
1267 if (present_dep != NULL)
1268 /* We found an existing dependency between ELEM and INSN. */
1269 return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1270 else
1271 /* We didn't find a dep, it shouldn't present in the cache. */
1272 gcc_assert (!present_p);
1275 /* Might want to check one level of transitivity to save conses.
1276 This check should be done in maybe_add_or_update_dep_1.
1277 Since we made it to add_or_update_dep_1, we must create
1278 (or update) a link. */
1280 if (mem1 != NULL_RTX)
1282 gcc_assert (sched_deps_info->generate_spec_deps);
1283 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1284 estimate_dep_weak (mem1, mem2));
1287 sd_add_dep (new_dep, resolved_p);
1289 return DEP_CREATED;
1292 /* Initialize BACK_LIST_PTR with consumer's backward list and
1293 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1294 initialize with lists that hold resolved deps. */
1295 static void
1296 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1297 deps_list_t *back_list_ptr,
1298 deps_list_t *forw_list_ptr)
1300 rtx con = DEP_CON (dep);
1302 if (!resolved_p)
1304 if (dep_spec_p (dep))
1305 *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1306 else
1307 *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1309 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1311 else
1313 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1314 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1318 /* Add dependence described by DEP.
1319 If RESOLVED_P is true treat the dependence as a resolved one. */
1320 void
1321 sd_add_dep (dep_t dep, bool resolved_p)
1323 dep_node_t n = create_dep_node ();
1324 deps_list_t con_back_deps;
1325 deps_list_t pro_forw_deps;
1326 rtx elem = DEP_PRO (dep);
1327 rtx insn = DEP_CON (dep);
1329 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1331 if ((current_sched_info->flags & DO_SPECULATION) == 0
1332 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1333 DEP_STATUS (dep) &= ~SPECULATIVE;
1335 copy_dep (DEP_NODE_DEP (n), dep);
1337 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1339 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1341 #ifdef ENABLE_CHECKING
1342 check_dep (dep, false);
1343 #endif
1345 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1347 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1348 in the bitmap caches of dependency information. */
1349 if (true_dependency_cache != NULL)
1350 set_dependency_caches (dep);
1353 /* Add or update backward dependence between INSN and ELEM
1354 with given type DEP_TYPE and dep_status DS.
1355 This function is a convenience wrapper. */
1356 enum DEPS_ADJUST_RESULT
1357 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1359 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1362 /* Resolved dependence pointed to by SD_IT.
1363 SD_IT will advance to the next element. */
1364 void
1365 sd_resolve_dep (sd_iterator_def sd_it)
1367 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1368 dep_t dep = DEP_NODE_DEP (node);
1369 rtx pro = DEP_PRO (dep);
1370 rtx con = DEP_CON (dep);
1372 if (dep_spec_p (dep))
1373 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1374 INSN_RESOLVED_BACK_DEPS (con));
1375 else
1376 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1377 INSN_RESOLVED_BACK_DEPS (con));
1379 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1380 INSN_RESOLVED_FORW_DEPS (pro));
1383 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1384 pointed to by SD_IT to unresolved state. */
1385 void
1386 sd_unresolve_dep (sd_iterator_def sd_it)
1388 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1389 dep_t dep = DEP_NODE_DEP (node);
1390 rtx pro = DEP_PRO (dep);
1391 rtx con = DEP_CON (dep);
1393 if (dep_spec_p (dep))
1394 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1395 INSN_SPEC_BACK_DEPS (con));
1396 else
1397 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1398 INSN_HARD_BACK_DEPS (con));
1400 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1401 INSN_FORW_DEPS (pro));
1404 /* Make TO depend on all the FROM's producers.
1405 If RESOLVED_P is true add dependencies to the resolved lists. */
1406 void
1407 sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
1409 sd_list_types_def list_type;
1410 sd_iterator_def sd_it;
1411 dep_t dep;
1413 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1415 FOR_EACH_DEP (from, list_type, sd_it, dep)
1417 dep_def _new_dep, *new_dep = &_new_dep;
1419 copy_dep (new_dep, dep);
1420 DEP_CON (new_dep) = to;
1421 sd_add_dep (new_dep, resolved_p);
1425 /* Remove a dependency referred to by SD_IT.
1426 SD_IT will point to the next dependence after removal. */
1427 void
1428 sd_delete_dep (sd_iterator_def sd_it)
1430 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1431 dep_t dep = DEP_NODE_DEP (n);
1432 rtx pro = DEP_PRO (dep);
1433 rtx con = DEP_CON (dep);
1434 deps_list_t con_back_deps;
1435 deps_list_t pro_forw_deps;
1437 if (true_dependency_cache != NULL)
1439 int elem_luid = INSN_LUID (pro);
1440 int insn_luid = INSN_LUID (con);
1442 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1443 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1444 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1445 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1447 if (current_sched_info->flags & DO_SPECULATION)
1448 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1451 get_back_and_forw_lists (dep, sd_it.resolved_p,
1452 &con_back_deps, &pro_forw_deps);
1454 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1455 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1457 delete_dep_node (n);
1460 /* Dump size of the lists. */
1461 #define DUMP_LISTS_SIZE (2)
1463 /* Dump dependencies of the lists. */
1464 #define DUMP_LISTS_DEPS (4)
1466 /* Dump all information about the lists. */
1467 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1469 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1470 FLAGS is a bit mask specifying what information about the lists needs
1471 to be printed.
1472 If FLAGS has the very first bit set, then dump all information about
1473 the lists and propagate this bit into the callee dump functions. */
1474 static void
1475 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1477 sd_iterator_def sd_it;
1478 dep_t dep;
1479 int all;
1481 all = (flags & 1);
1483 if (all)
1484 flags |= DUMP_LISTS_ALL;
1486 fprintf (dump, "[");
1488 if (flags & DUMP_LISTS_SIZE)
1489 fprintf (dump, "%d; ", sd_lists_size (insn, types));
1491 if (flags & DUMP_LISTS_DEPS)
1493 FOR_EACH_DEP (insn, types, sd_it, dep)
1495 dump_dep (dump, dep, dump_dep_flags | all);
1496 fprintf (dump, " ");
1501 /* Dump all information about deps_lists of INSN specified by TYPES
1502 to STDERR. */
1503 void
1504 sd_debug_lists (rtx insn, sd_list_types_def types)
1506 dump_lists (stderr, insn, types, 1);
1507 fprintf (stderr, "\n");
1510 /* A wrapper around add_dependence_1, to add a dependence of CON on
1511 PRO, with type DEP_TYPE. This function implements special handling
1512 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1513 the type to REG_DEP_ANTI if we can determine that predication is
1514 impossible; otherwise we add additional true dependencies on the
1515 INSN_COND_DEPS list of the jump (which PRO must be). */
1516 void
1517 add_dependence (rtx con, rtx pro, enum reg_note dep_type)
1519 if (dep_type == REG_DEP_CONTROL
1520 && !(current_sched_info->flags & DO_PREDICATION))
1521 dep_type = REG_DEP_ANTI;
1523 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1524 so we must also make the insn dependent on the setter of the
1525 condition. */
1526 if (dep_type == REG_DEP_CONTROL)
1528 rtx real_pro = pro;
1529 rtx other = real_insn_for_shadow (real_pro);
1530 rtx cond;
1532 if (other != NULL_RTX)
1533 real_pro = other;
1534 cond = sched_get_reverse_condition_uncached (real_pro);
1535 /* Verify that the insn does not use a different value in
1536 the condition register than the one that was present at
1537 the jump. */
1538 if (cond == NULL_RTX)
1539 dep_type = REG_DEP_ANTI;
1540 else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1542 HARD_REG_SET uses;
1543 CLEAR_HARD_REG_SET (uses);
1544 note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1545 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1546 dep_type = REG_DEP_ANTI;
1548 if (dep_type == REG_DEP_CONTROL)
1550 if (sched_verbose >= 5)
1551 fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1552 INSN_UID (real_pro));
1553 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1554 REG_DEP_TRUE, false);
1558 add_dependence_1 (con, pro, dep_type);
1561 /* A convenience wrapper to operate on an entire list. HARD should be
1562 true if DEP_NONREG should be set on newly created dependencies. */
1564 static void
1565 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type,
1566 bool hard)
1568 mark_as_hard = hard;
1569 for (; list; list = XEXP (list, 1))
1571 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1572 add_dependence (insn, XEXP (list, 0), dep_type);
1574 mark_as_hard = false;
1577 /* Similar, but free *LISTP at the same time, when the context
1578 is not readonly. HARD should be true if DEP_NONREG should be set on
1579 newly created dependencies. */
1581 static void
1582 add_dependence_list_and_free (struct deps_desc *deps, rtx insn, rtx *listp,
1583 int uncond, enum reg_note dep_type, bool hard)
1585 add_dependence_list (insn, *listp, uncond, dep_type, hard);
1587 /* We don't want to short-circuit dependencies involving debug
1588 insns, because they may cause actual dependencies to be
1589 disregarded. */
1590 if (deps->readonly || DEBUG_INSN_P (insn))
1591 return;
1593 free_INSN_LIST_list (listp);
1596 /* Remove all occurrences of INSN from LIST. Return the number of
1597 occurrences removed. */
1599 static int
1600 remove_from_dependence_list (rtx insn, rtx* listp)
1602 int removed = 0;
1604 while (*listp)
1606 if (XEXP (*listp, 0) == insn)
1608 remove_free_INSN_LIST_node (listp);
1609 removed++;
1610 continue;
1613 listp = &XEXP (*listp, 1);
1616 return removed;
1619 /* Same as above, but process two lists at once. */
1620 static int
1621 remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
1623 int removed = 0;
1625 while (*listp)
1627 if (XEXP (*listp, 0) == insn)
1629 remove_free_INSN_LIST_node (listp);
1630 remove_free_EXPR_LIST_node (exprp);
1631 removed++;
1632 continue;
1635 listp = &XEXP (*listp, 1);
1636 exprp = &XEXP (*exprp, 1);
1639 return removed;
1642 /* Clear all dependencies for an insn. */
1643 static void
1644 delete_all_dependences (rtx insn)
1646 sd_iterator_def sd_it;
1647 dep_t dep;
1649 /* The below cycle can be optimized to clear the caches and back_deps
1650 in one call but that would provoke duplication of code from
1651 delete_dep (). */
1653 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1654 sd_iterator_cond (&sd_it, &dep);)
1655 sd_delete_dep (sd_it);
1658 /* All insns in a scheduling group except the first should only have
1659 dependencies on the previous insn in the group. So we find the
1660 first instruction in the scheduling group by walking the dependence
1661 chains backwards. Then we add the dependencies for the group to
1662 the previous nonnote insn. */
1664 static void
1665 chain_to_prev_insn (rtx insn)
1667 sd_iterator_def sd_it;
1668 dep_t dep;
1669 rtx prev_nonnote;
1671 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1673 rtx i = insn;
1674 rtx pro = DEP_PRO (dep);
1678 i = prev_nonnote_insn (i);
1680 if (pro == i)
1681 goto next_link;
1682 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1684 if (! sched_insns_conditions_mutex_p (i, pro))
1685 add_dependence (i, pro, DEP_TYPE (dep));
1686 next_link:;
1689 delete_all_dependences (insn);
1691 prev_nonnote = prev_nonnote_nondebug_insn (insn);
1692 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1693 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1694 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1697 /* Process an insn's memory dependencies. There are four kinds of
1698 dependencies:
1700 (0) read dependence: read follows read
1701 (1) true dependence: read follows write
1702 (2) output dependence: write follows write
1703 (3) anti dependence: write follows read
1705 We are careful to build only dependencies which actually exist, and
1706 use transitivity to avoid building too many links. */
1708 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1709 The MEM is a memory reference contained within INSN, which we are saving
1710 so that we can do memory aliasing on it. */
1712 static void
1713 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1714 rtx insn, rtx mem)
1716 rtx *insn_list;
1717 rtx *mem_list;
1718 rtx link;
1720 gcc_assert (!deps->readonly);
1721 if (read_p)
1723 insn_list = &deps->pending_read_insns;
1724 mem_list = &deps->pending_read_mems;
1725 if (!DEBUG_INSN_P (insn))
1726 deps->pending_read_list_length++;
1728 else
1730 insn_list = &deps->pending_write_insns;
1731 mem_list = &deps->pending_write_mems;
1732 deps->pending_write_list_length++;
1735 link = alloc_INSN_LIST (insn, *insn_list);
1736 *insn_list = link;
1738 if (sched_deps_info->use_cselib)
1740 mem = shallow_copy_rtx (mem);
1741 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1742 GET_MODE (mem), insn);
1744 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1745 *mem_list = link;
1748 /* Make a dependency between every memory reference on the pending lists
1749 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1750 dependencies for a read operation, similarly with FOR_WRITE. */
1752 static void
1753 flush_pending_lists (struct deps_desc *deps, rtx insn, int for_read,
1754 int for_write)
1756 if (for_write)
1758 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1759 1, REG_DEP_ANTI, true);
1760 if (!deps->readonly)
1762 free_EXPR_LIST_list (&deps->pending_read_mems);
1763 deps->pending_read_list_length = 0;
1767 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1768 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1769 true);
1771 add_dependence_list_and_free (deps, insn,
1772 &deps->last_pending_memory_flush, 1,
1773 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1774 true);
1776 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1777 REG_DEP_ANTI, true);
1779 if (DEBUG_INSN_P (insn))
1781 if (for_write)
1782 free_INSN_LIST_list (&deps->pending_read_insns);
1783 free_INSN_LIST_list (&deps->pending_write_insns);
1784 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1785 free_INSN_LIST_list (&deps->pending_jump_insns);
1788 if (!deps->readonly)
1790 free_EXPR_LIST_list (&deps->pending_write_mems);
1791 deps->pending_write_list_length = 0;
1793 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1794 deps->pending_flush_length = 1;
1796 mark_as_hard = false;
1799 /* Instruction which dependencies we are analyzing. */
1800 static rtx cur_insn = NULL_RTX;
1802 /* Implement hooks for haifa scheduler. */
1804 static void
1805 haifa_start_insn (rtx insn)
1807 gcc_assert (insn && !cur_insn);
1809 cur_insn = insn;
1812 static void
1813 haifa_finish_insn (void)
1815 cur_insn = NULL;
1818 void
1819 haifa_note_reg_set (int regno)
1821 SET_REGNO_REG_SET (reg_pending_sets, regno);
1824 void
1825 haifa_note_reg_clobber (int regno)
1827 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1830 void
1831 haifa_note_reg_use (int regno)
1833 SET_REGNO_REG_SET (reg_pending_uses, regno);
1836 static void
1837 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx pending_insn, ds_t ds)
1839 if (!(ds & SPECULATIVE))
1841 mem = NULL_RTX;
1842 pending_mem = NULL_RTX;
1844 else
1845 gcc_assert (ds & BEGIN_DATA);
1848 dep_def _dep, *dep = &_dep;
1850 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1851 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1852 DEP_NONREG (dep) = 1;
1853 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1858 static void
1859 haifa_note_dep (rtx elem, ds_t ds)
1861 dep_def _dep;
1862 dep_t dep = &_dep;
1864 init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1865 if (mark_as_hard)
1866 DEP_NONREG (dep) = 1;
1867 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1870 static void
1871 note_reg_use (int r)
1873 if (sched_deps_info->note_reg_use)
1874 sched_deps_info->note_reg_use (r);
1877 static void
1878 note_reg_set (int r)
1880 if (sched_deps_info->note_reg_set)
1881 sched_deps_info->note_reg_set (r);
1884 static void
1885 note_reg_clobber (int r)
1887 if (sched_deps_info->note_reg_clobber)
1888 sched_deps_info->note_reg_clobber (r);
1891 static void
1892 note_mem_dep (rtx m1, rtx m2, rtx e, ds_t ds)
1894 if (sched_deps_info->note_mem_dep)
1895 sched_deps_info->note_mem_dep (m1, m2, e, ds);
1898 static void
1899 note_dep (rtx e, ds_t ds)
1901 if (sched_deps_info->note_dep)
1902 sched_deps_info->note_dep (e, ds);
1905 /* Return corresponding to DS reg_note. */
1906 enum reg_note
1907 ds_to_dt (ds_t ds)
1909 if (ds & DEP_TRUE)
1910 return REG_DEP_TRUE;
1911 else if (ds & DEP_OUTPUT)
1912 return REG_DEP_OUTPUT;
1913 else if (ds & DEP_ANTI)
1914 return REG_DEP_ANTI;
1915 else
1917 gcc_assert (ds & DEP_CONTROL);
1918 return REG_DEP_CONTROL;
1924 /* Functions for computation of info needed for register pressure
1925 sensitive insn scheduling. */
1928 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1929 static struct reg_use_data *
1930 create_insn_reg_use (int regno, rtx insn)
1932 struct reg_use_data *use;
1934 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1935 use->regno = regno;
1936 use->insn = insn;
1937 use->next_insn_use = INSN_REG_USE_LIST (insn);
1938 INSN_REG_USE_LIST (insn) = use;
1939 return use;
1942 /* Allocate and return reg_set_data structure for REGNO and INSN. */
1943 static struct reg_set_data *
1944 create_insn_reg_set (int regno, rtx insn)
1946 struct reg_set_data *set;
1948 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1949 set->regno = regno;
1950 set->insn = insn;
1951 set->next_insn_set = INSN_REG_SET_LIST (insn);
1952 INSN_REG_SET_LIST (insn) = set;
1953 return set;
1956 /* Set up insn register uses for INSN and dependency context DEPS. */
1957 static void
1958 setup_insn_reg_uses (struct deps_desc *deps, rtx insn)
1960 unsigned i;
1961 reg_set_iterator rsi;
1962 rtx list;
1963 struct reg_use_data *use, *use2, *next;
1964 struct deps_reg *reg_last;
1966 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1968 if (i < FIRST_PSEUDO_REGISTER
1969 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1970 continue;
1972 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1973 && ! REGNO_REG_SET_P (reg_pending_sets, i)
1974 && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1975 /* Ignore use which is not dying. */
1976 continue;
1978 use = create_insn_reg_use (i, insn);
1979 use->next_regno_use = use;
1980 reg_last = &deps->reg_last[i];
1982 /* Create the cycle list of uses. */
1983 for (list = reg_last->uses; list; list = XEXP (list, 1))
1985 use2 = create_insn_reg_use (i, XEXP (list, 0));
1986 next = use->next_regno_use;
1987 use->next_regno_use = use2;
1988 use2->next_regno_use = next;
1993 /* Register pressure info for the currently processed insn. */
1994 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1996 /* Return TRUE if INSN has the use structure for REGNO. */
1997 static bool
1998 insn_use_p (rtx insn, int regno)
2000 struct reg_use_data *use;
2002 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2003 if (use->regno == regno)
2004 return true;
2005 return false;
2008 /* Update the register pressure info after birth of pseudo register REGNO
2009 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2010 the register is in clobber or unused after the insn. */
2011 static void
2012 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2014 int incr, new_incr;
2015 enum reg_class cl;
2017 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2018 cl = sched_regno_pressure_class[regno];
2019 if (cl != NO_REGS)
2021 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2022 if (clobber_p)
2024 new_incr = reg_pressure_info[cl].clobber_increase + incr;
2025 reg_pressure_info[cl].clobber_increase = new_incr;
2027 else if (unused_p)
2029 new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2030 reg_pressure_info[cl].unused_set_increase = new_incr;
2032 else
2034 new_incr = reg_pressure_info[cl].set_increase + incr;
2035 reg_pressure_info[cl].set_increase = new_incr;
2036 if (! insn_use_p (insn, regno))
2037 reg_pressure_info[cl].change += incr;
2038 create_insn_reg_set (regno, insn);
2040 gcc_assert (new_incr < (1 << INCREASE_BITS));
2044 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2045 hard registers involved in the birth. */
2046 static void
2047 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2048 bool clobber_p, bool unused_p)
2050 enum reg_class cl;
2051 int new_incr, last = regno + nregs;
2053 while (regno < last)
2055 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2056 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2058 cl = sched_regno_pressure_class[regno];
2059 if (cl != NO_REGS)
2061 if (clobber_p)
2063 new_incr = reg_pressure_info[cl].clobber_increase + 1;
2064 reg_pressure_info[cl].clobber_increase = new_incr;
2066 else if (unused_p)
2068 new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2069 reg_pressure_info[cl].unused_set_increase = new_incr;
2071 else
2073 new_incr = reg_pressure_info[cl].set_increase + 1;
2074 reg_pressure_info[cl].set_increase = new_incr;
2075 if (! insn_use_p (insn, regno))
2076 reg_pressure_info[cl].change += 1;
2077 create_insn_reg_set (regno, insn);
2079 gcc_assert (new_incr < (1 << INCREASE_BITS));
2082 regno++;
2086 /* Update the register pressure info after birth of pseudo or hard
2087 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2088 correspondingly that the register is in clobber or unused after the
2089 insn. */
2090 static void
2091 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2093 int regno;
2095 if (GET_CODE (reg) == SUBREG)
2096 reg = SUBREG_REG (reg);
2098 if (! REG_P (reg))
2099 return;
2101 regno = REGNO (reg);
2102 if (regno < FIRST_PSEUDO_REGISTER)
2103 mark_insn_hard_regno_birth (insn, regno,
2104 hard_regno_nregs[regno][GET_MODE (reg)],
2105 clobber_p, unused_p);
2106 else
2107 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2110 /* Update the register pressure info after death of pseudo register
2111 REGNO. */
2112 static void
2113 mark_pseudo_death (int regno)
2115 int incr;
2116 enum reg_class cl;
2118 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2119 cl = sched_regno_pressure_class[regno];
2120 if (cl != NO_REGS)
2122 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2123 reg_pressure_info[cl].change -= incr;
2127 /* Like mark_pseudo_death except that NREGS saying how many hard
2128 registers involved in the death. */
2129 static void
2130 mark_hard_regno_death (int regno, int nregs)
2132 enum reg_class cl;
2133 int last = regno + nregs;
2135 while (regno < last)
2137 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2138 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2140 cl = sched_regno_pressure_class[regno];
2141 if (cl != NO_REGS)
2142 reg_pressure_info[cl].change -= 1;
2144 regno++;
2148 /* Update the register pressure info after death of pseudo or hard
2149 register REG. */
2150 static void
2151 mark_reg_death (rtx reg)
2153 int regno;
2155 if (GET_CODE (reg) == SUBREG)
2156 reg = SUBREG_REG (reg);
2158 if (! REG_P (reg))
2159 return;
2161 regno = REGNO (reg);
2162 if (regno < FIRST_PSEUDO_REGISTER)
2163 mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
2164 else
2165 mark_pseudo_death (regno);
2168 /* Process SETTER of REG. DATA is an insn containing the setter. */
2169 static void
2170 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2172 if (setter != NULL_RTX && GET_CODE (setter) != SET)
2173 return;
2174 mark_insn_reg_birth
2175 ((rtx) data, reg, false,
2176 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2179 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2180 static void
2181 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2183 if (GET_CODE (setter) == CLOBBER)
2184 mark_insn_reg_birth ((rtx) data, reg, true, false);
2187 /* Set up reg pressure info related to INSN. */
2188 void
2189 init_insn_reg_pressure_info (rtx insn)
2191 int i, len;
2192 enum reg_class cl;
2193 static struct reg_pressure_data *pressure_info;
2194 rtx link;
2196 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2198 if (! INSN_P (insn))
2199 return;
2201 for (i = 0; i < ira_pressure_classes_num; i++)
2203 cl = ira_pressure_classes[i];
2204 reg_pressure_info[cl].clobber_increase = 0;
2205 reg_pressure_info[cl].set_increase = 0;
2206 reg_pressure_info[cl].unused_set_increase = 0;
2207 reg_pressure_info[cl].change = 0;
2210 note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2212 note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2214 #ifdef AUTO_INC_DEC
2215 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2216 if (REG_NOTE_KIND (link) == REG_INC)
2217 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2218 #endif
2220 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2221 if (REG_NOTE_KIND (link) == REG_DEAD)
2222 mark_reg_death (XEXP (link, 0));
2224 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2225 pressure_info
2226 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2227 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2228 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2229 * sizeof (int), 1);
2230 for (i = 0; i < ira_pressure_classes_num; i++)
2232 cl = ira_pressure_classes[i];
2233 pressure_info[i].clobber_increase
2234 = reg_pressure_info[cl].clobber_increase;
2235 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2236 pressure_info[i].unused_set_increase
2237 = reg_pressure_info[cl].unused_set_increase;
2238 pressure_info[i].change = reg_pressure_info[cl].change;
2245 /* Internal variable for sched_analyze_[12] () functions.
2246 If it is nonzero, this means that sched_analyze_[12] looks
2247 at the most toplevel SET. */
2248 static bool can_start_lhs_rhs_p;
2250 /* Extend reg info for the deps context DEPS given that
2251 we have just generated a register numbered REGNO. */
2252 static void
2253 extend_deps_reg_info (struct deps_desc *deps, int regno)
2255 int max_regno = regno + 1;
2257 gcc_assert (!reload_completed);
2259 /* In a readonly context, it would not hurt to extend info,
2260 but it should not be needed. */
2261 if (reload_completed && deps->readonly)
2263 deps->max_reg = max_regno;
2264 return;
2267 if (max_regno > deps->max_reg)
2269 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2270 max_regno);
2271 memset (&deps->reg_last[deps->max_reg],
2272 0, (max_regno - deps->max_reg)
2273 * sizeof (struct deps_reg));
2274 deps->max_reg = max_regno;
2278 /* Extends REG_INFO_P if needed. */
2279 void
2280 maybe_extend_reg_info_p (void)
2282 /* Extend REG_INFO_P, if needed. */
2283 if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2285 size_t new_reg_info_p_size = max_regno + 128;
2287 gcc_assert (!reload_completed && sel_sched_p ());
2289 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2290 new_reg_info_p_size,
2291 reg_info_p_size,
2292 sizeof (*reg_info_p));
2293 reg_info_p_size = new_reg_info_p_size;
2297 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2298 The type of the reference is specified by REF and can be SET,
2299 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2301 static void
2302 sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
2303 enum rtx_code ref, rtx insn)
2305 /* We could emit new pseudos in renaming. Extend the reg structures. */
2306 if (!reload_completed && sel_sched_p ()
2307 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2308 extend_deps_reg_info (deps, regno);
2310 maybe_extend_reg_info_p ();
2312 /* A hard reg in a wide mode may really be multiple registers.
2313 If so, mark all of them just like the first. */
2314 if (regno < FIRST_PSEUDO_REGISTER)
2316 int i = hard_regno_nregs[regno][mode];
2317 if (ref == SET)
2319 while (--i >= 0)
2320 note_reg_set (regno + i);
2322 else if (ref == USE)
2324 while (--i >= 0)
2325 note_reg_use (regno + i);
2327 else
2329 while (--i >= 0)
2330 note_reg_clobber (regno + i);
2334 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2335 it does not reload. Ignore these as they have served their
2336 purpose already. */
2337 else if (regno >= deps->max_reg)
2339 enum rtx_code code = GET_CODE (PATTERN (insn));
2340 gcc_assert (code == USE || code == CLOBBER);
2343 else
2345 if (ref == SET)
2346 note_reg_set (regno);
2347 else if (ref == USE)
2348 note_reg_use (regno);
2349 else
2350 note_reg_clobber (regno);
2352 /* Pseudos that are REG_EQUIV to something may be replaced
2353 by that during reloading. We need only add dependencies for
2354 the address in the REG_EQUIV note. */
2355 if (!reload_completed && get_reg_known_equiv_p (regno))
2357 rtx t = get_reg_known_value (regno);
2358 if (MEM_P (t))
2359 sched_analyze_2 (deps, XEXP (t, 0), insn);
2362 /* Don't let it cross a call after scheduling if it doesn't
2363 already cross one. */
2364 if (REG_N_CALLS_CROSSED (regno) == 0)
2366 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2367 deps->sched_before_next_call
2368 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2369 else
2370 add_dependence_list (insn, deps->last_function_call, 1,
2371 REG_DEP_ANTI, false);
2376 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2377 rtx, X, creating all dependencies generated by the write to the
2378 destination of X, and reads of everything mentioned. */
2380 static void
2381 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx insn)
2383 rtx dest = XEXP (x, 0);
2384 enum rtx_code code = GET_CODE (x);
2385 bool cslr_p = can_start_lhs_rhs_p;
2387 can_start_lhs_rhs_p = false;
2389 gcc_assert (dest);
2390 if (dest == 0)
2391 return;
2393 if (cslr_p && sched_deps_info->start_lhs)
2394 sched_deps_info->start_lhs (dest);
2396 if (GET_CODE (dest) == PARALLEL)
2398 int i;
2400 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2401 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2402 sched_analyze_1 (deps,
2403 gen_rtx_CLOBBER (VOIDmode,
2404 XEXP (XVECEXP (dest, 0, i), 0)),
2405 insn);
2407 if (cslr_p && sched_deps_info->finish_lhs)
2408 sched_deps_info->finish_lhs ();
2410 if (code == SET)
2412 can_start_lhs_rhs_p = cslr_p;
2414 sched_analyze_2 (deps, SET_SRC (x), insn);
2416 can_start_lhs_rhs_p = false;
2419 return;
2422 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2423 || GET_CODE (dest) == ZERO_EXTRACT)
2425 if (GET_CODE (dest) == STRICT_LOW_PART
2426 || GET_CODE (dest) == ZERO_EXTRACT
2427 || df_read_modify_subreg_p (dest))
2429 /* These both read and modify the result. We must handle
2430 them as writes to get proper dependencies for following
2431 instructions. We must handle them as reads to get proper
2432 dependencies from this to previous instructions.
2433 Thus we need to call sched_analyze_2. */
2435 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2437 if (GET_CODE (dest) == ZERO_EXTRACT)
2439 /* The second and third arguments are values read by this insn. */
2440 sched_analyze_2 (deps, XEXP (dest, 1), insn);
2441 sched_analyze_2 (deps, XEXP (dest, 2), insn);
2443 dest = XEXP (dest, 0);
2446 if (REG_P (dest))
2448 int regno = REGNO (dest);
2449 enum machine_mode mode = GET_MODE (dest);
2451 sched_analyze_reg (deps, regno, mode, code, insn);
2453 #ifdef STACK_REGS
2454 /* Treat all writes to a stack register as modifying the TOS. */
2455 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2457 /* Avoid analyzing the same register twice. */
2458 if (regno != FIRST_STACK_REG)
2459 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2461 add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2462 FIRST_STACK_REG);
2464 #endif
2466 else if (MEM_P (dest))
2468 /* Writing memory. */
2469 rtx t = dest;
2471 if (sched_deps_info->use_cselib)
2473 enum machine_mode address_mode = get_address_mode (dest);
2475 t = shallow_copy_rtx (dest);
2476 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2477 GET_MODE (t), insn);
2478 XEXP (t, 0)
2479 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2480 insn);
2482 t = canon_rtx (t);
2484 /* Pending lists can't get larger with a readonly context. */
2485 if (!deps->readonly
2486 && ((deps->pending_read_list_length + deps->pending_write_list_length)
2487 > MAX_PENDING_LIST_LENGTH))
2489 /* Flush all pending reads and writes to prevent the pending lists
2490 from getting any larger. Insn scheduling runs too slowly when
2491 these lists get long. When compiling GCC with itself,
2492 this flush occurs 8 times for sparc, and 10 times for m88k using
2493 the default value of 32. */
2494 flush_pending_lists (deps, insn, false, true);
2496 else
2498 rtx pending, pending_mem;
2500 pending = deps->pending_read_insns;
2501 pending_mem = deps->pending_read_mems;
2502 while (pending)
2504 if (anti_dependence (XEXP (pending_mem, 0), t)
2505 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2506 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2507 DEP_ANTI);
2509 pending = XEXP (pending, 1);
2510 pending_mem = XEXP (pending_mem, 1);
2513 pending = deps->pending_write_insns;
2514 pending_mem = deps->pending_write_mems;
2515 while (pending)
2517 if (output_dependence (XEXP (pending_mem, 0), t)
2518 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2519 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2520 DEP_OUTPUT);
2522 pending = XEXP (pending, 1);
2523 pending_mem = XEXP (pending_mem, 1);
2526 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2527 REG_DEP_ANTI, true);
2528 add_dependence_list (insn, deps->pending_jump_insns, 1,
2529 REG_DEP_CONTROL, true);
2531 if (!deps->readonly)
2532 add_insn_mem_dependence (deps, false, insn, dest);
2534 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2537 if (cslr_p && sched_deps_info->finish_lhs)
2538 sched_deps_info->finish_lhs ();
2540 /* Analyze reads. */
2541 if (GET_CODE (x) == SET)
2543 can_start_lhs_rhs_p = cslr_p;
2545 sched_analyze_2 (deps, SET_SRC (x), insn);
2547 can_start_lhs_rhs_p = false;
2551 /* Analyze the uses of memory and registers in rtx X in INSN. */
2552 static void
2553 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx insn)
2555 int i;
2556 int j;
2557 enum rtx_code code;
2558 const char *fmt;
2559 bool cslr_p = can_start_lhs_rhs_p;
2561 can_start_lhs_rhs_p = false;
2563 gcc_assert (x);
2564 if (x == 0)
2565 return;
2567 if (cslr_p && sched_deps_info->start_rhs)
2568 sched_deps_info->start_rhs (x);
2570 code = GET_CODE (x);
2572 switch (code)
2574 CASE_CONST_ANY:
2575 case SYMBOL_REF:
2576 case CONST:
2577 case LABEL_REF:
2578 /* Ignore constants. */
2579 if (cslr_p && sched_deps_info->finish_rhs)
2580 sched_deps_info->finish_rhs ();
2582 return;
2584 #ifdef HAVE_cc0
2585 case CC0:
2586 /* User of CC0 depends on immediately preceding insn. */
2587 SCHED_GROUP_P (insn) = 1;
2588 /* Don't move CC0 setter to another block (it can set up the
2589 same flag for previous CC0 users which is safe). */
2590 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2592 if (cslr_p && sched_deps_info->finish_rhs)
2593 sched_deps_info->finish_rhs ();
2595 return;
2596 #endif
2598 case REG:
2600 int regno = REGNO (x);
2601 enum machine_mode mode = GET_MODE (x);
2603 sched_analyze_reg (deps, regno, mode, USE, insn);
2605 #ifdef STACK_REGS
2606 /* Treat all reads of a stack register as modifying the TOS. */
2607 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2609 /* Avoid analyzing the same register twice. */
2610 if (regno != FIRST_STACK_REG)
2611 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2612 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2614 #endif
2616 if (cslr_p && sched_deps_info->finish_rhs)
2617 sched_deps_info->finish_rhs ();
2619 return;
2622 case MEM:
2624 /* Reading memory. */
2625 rtx u;
2626 rtx pending, pending_mem;
2627 rtx t = x;
2629 if (sched_deps_info->use_cselib)
2631 enum machine_mode address_mode = get_address_mode (t);
2633 t = shallow_copy_rtx (t);
2634 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2635 GET_MODE (t), insn);
2636 XEXP (t, 0)
2637 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2638 insn);
2641 if (!DEBUG_INSN_P (insn))
2643 t = canon_rtx (t);
2644 pending = deps->pending_read_insns;
2645 pending_mem = deps->pending_read_mems;
2646 while (pending)
2648 if (read_dependence (XEXP (pending_mem, 0), t)
2649 && ! sched_insns_conditions_mutex_p (insn,
2650 XEXP (pending, 0)))
2651 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2652 DEP_ANTI);
2654 pending = XEXP (pending, 1);
2655 pending_mem = XEXP (pending_mem, 1);
2658 pending = deps->pending_write_insns;
2659 pending_mem = deps->pending_write_mems;
2660 while (pending)
2662 if (true_dependence (XEXP (pending_mem, 0), VOIDmode, t)
2663 && ! sched_insns_conditions_mutex_p (insn,
2664 XEXP (pending, 0)))
2665 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2666 sched_deps_info->generate_spec_deps
2667 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2669 pending = XEXP (pending, 1);
2670 pending_mem = XEXP (pending_mem, 1);
2673 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2674 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2676 for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
2677 if (deps_may_trap_p (x))
2679 if ((sched_deps_info->generate_spec_deps)
2680 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2682 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2683 MAX_DEP_WEAK);
2685 note_dep (XEXP (u, 0), ds);
2687 else
2688 add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
2692 /* Always add these dependencies to pending_reads, since
2693 this insn may be followed by a write. */
2694 if (!deps->readonly)
2695 add_insn_mem_dependence (deps, true, insn, x);
2697 sched_analyze_2 (deps, XEXP (x, 0), insn);
2699 if (cslr_p && sched_deps_info->finish_rhs)
2700 sched_deps_info->finish_rhs ();
2702 return;
2705 /* Force pending stores to memory in case a trap handler needs them. */
2706 case TRAP_IF:
2707 flush_pending_lists (deps, insn, true, false);
2708 break;
2710 case PREFETCH:
2711 if (PREFETCH_SCHEDULE_BARRIER_P (x))
2712 reg_pending_barrier = TRUE_BARRIER;
2713 break;
2715 case UNSPEC_VOLATILE:
2716 flush_pending_lists (deps, insn, true, true);
2717 /* FALLTHRU */
2719 case ASM_OPERANDS:
2720 case ASM_INPUT:
2722 /* Traditional and volatile asm instructions must be considered to use
2723 and clobber all hard registers, all pseudo-registers and all of
2724 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2726 Consider for instance a volatile asm that changes the fpu rounding
2727 mode. An insn should not be moved across this even if it only uses
2728 pseudo-regs because it might give an incorrectly rounded result. */
2729 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2730 reg_pending_barrier = TRUE_BARRIER;
2732 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2733 We can not just fall through here since then we would be confused
2734 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2735 traditional asms unlike their normal usage. */
2737 if (code == ASM_OPERANDS)
2739 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2740 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2742 if (cslr_p && sched_deps_info->finish_rhs)
2743 sched_deps_info->finish_rhs ();
2745 return;
2747 break;
2750 case PRE_DEC:
2751 case POST_DEC:
2752 case PRE_INC:
2753 case POST_INC:
2754 /* These both read and modify the result. We must handle them as writes
2755 to get proper dependencies for following instructions. We must handle
2756 them as reads to get proper dependencies from this to previous
2757 instructions. Thus we need to pass them to both sched_analyze_1
2758 and sched_analyze_2. We must call sched_analyze_2 first in order
2759 to get the proper antecedent for the read. */
2760 sched_analyze_2 (deps, XEXP (x, 0), insn);
2761 sched_analyze_1 (deps, x, insn);
2763 if (cslr_p && sched_deps_info->finish_rhs)
2764 sched_deps_info->finish_rhs ();
2766 return;
2768 case POST_MODIFY:
2769 case PRE_MODIFY:
2770 /* op0 = op0 + op1 */
2771 sched_analyze_2 (deps, XEXP (x, 0), insn);
2772 sched_analyze_2 (deps, XEXP (x, 1), insn);
2773 sched_analyze_1 (deps, x, insn);
2775 if (cslr_p && sched_deps_info->finish_rhs)
2776 sched_deps_info->finish_rhs ();
2778 return;
2780 default:
2781 break;
2784 /* Other cases: walk the insn. */
2785 fmt = GET_RTX_FORMAT (code);
2786 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2788 if (fmt[i] == 'e')
2789 sched_analyze_2 (deps, XEXP (x, i), insn);
2790 else if (fmt[i] == 'E')
2791 for (j = 0; j < XVECLEN (x, i); j++)
2792 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2795 if (cslr_p && sched_deps_info->finish_rhs)
2796 sched_deps_info->finish_rhs ();
2799 /* Analyze an INSN with pattern X to find all dependencies. */
2800 static void
2801 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
2803 RTX_CODE code = GET_CODE (x);
2804 rtx link;
2805 unsigned i;
2806 reg_set_iterator rsi;
2808 if (! reload_completed)
2810 HARD_REG_SET temp;
2812 extract_insn (insn);
2813 preprocess_constraints ();
2814 ira_implicitly_set_insn_hard_regs (&temp);
2815 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2816 IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2819 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2820 && code == SET);
2822 if (may_trap_p (x))
2823 /* Avoid moving trapping instructions across function calls that might
2824 not always return. */
2825 add_dependence_list (insn, deps->last_function_call_may_noreturn,
2826 1, REG_DEP_ANTI, true);
2828 /* We must avoid creating a situation in which two successors of the
2829 current block have different unwind info after scheduling. If at any
2830 point the two paths re-join this leads to incorrect unwind info. */
2831 /* ??? There are certain situations involving a forced frame pointer in
2832 which, with extra effort, we could fix up the unwind info at a later
2833 CFG join. However, it seems better to notice these cases earlier
2834 during prologue generation and avoid marking the frame pointer setup
2835 as frame-related at all. */
2836 if (RTX_FRAME_RELATED_P (insn))
2838 /* Make sure prologue insn is scheduled before next jump. */
2839 deps->sched_before_next_jump
2840 = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2842 /* Make sure epilogue insn is scheduled after preceding jumps. */
2843 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2844 true);
2847 if (code == COND_EXEC)
2849 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2851 /* ??? Should be recording conditions so we reduce the number of
2852 false dependencies. */
2853 x = COND_EXEC_CODE (x);
2854 code = GET_CODE (x);
2856 if (code == SET || code == CLOBBER)
2858 sched_analyze_1 (deps, x, insn);
2860 /* Bare clobber insns are used for letting life analysis, reg-stack
2861 and others know that a value is dead. Depend on the last call
2862 instruction so that reg-stack won't get confused. */
2863 if (code == CLOBBER)
2864 add_dependence_list (insn, deps->last_function_call, 1,
2865 REG_DEP_OUTPUT, true);
2867 else if (code == PARALLEL)
2869 for (i = XVECLEN (x, 0); i--;)
2871 rtx sub = XVECEXP (x, 0, i);
2872 code = GET_CODE (sub);
2874 if (code == COND_EXEC)
2876 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2877 sub = COND_EXEC_CODE (sub);
2878 code = GET_CODE (sub);
2880 if (code == SET || code == CLOBBER)
2881 sched_analyze_1 (deps, sub, insn);
2882 else
2883 sched_analyze_2 (deps, sub, insn);
2886 else
2887 sched_analyze_2 (deps, x, insn);
2889 /* Mark registers CLOBBERED or used by called function. */
2890 if (CALL_P (insn))
2892 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2894 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2895 sched_analyze_1 (deps, XEXP (link, 0), insn);
2896 else if (GET_CODE (XEXP (link, 0)) != SET)
2897 sched_analyze_2 (deps, XEXP (link, 0), insn);
2899 /* Don't schedule anything after a tail call, tail call needs
2900 to use at least all call-saved registers. */
2901 if (SIBLING_CALL_P (insn))
2902 reg_pending_barrier = TRUE_BARRIER;
2903 else if (find_reg_note (insn, REG_SETJMP, NULL))
2904 reg_pending_barrier = MOVE_BARRIER;
2907 if (JUMP_P (insn))
2909 rtx next;
2910 next = next_nonnote_nondebug_insn (insn);
2911 if (next && BARRIER_P (next))
2912 reg_pending_barrier = MOVE_BARRIER;
2913 else
2915 rtx pending, pending_mem;
2917 if (sched_deps_info->compute_jump_reg_dependencies)
2919 (*sched_deps_info->compute_jump_reg_dependencies)
2920 (insn, reg_pending_control_uses);
2922 /* Make latency of jump equal to 0 by using anti-dependence. */
2923 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
2925 struct deps_reg *reg_last = &deps->reg_last[i];
2926 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
2927 false);
2928 add_dependence_list (insn, reg_last->implicit_sets,
2929 0, REG_DEP_ANTI, false);
2930 add_dependence_list (insn, reg_last->clobbers, 0,
2931 REG_DEP_ANTI, false);
2935 /* All memory writes and volatile reads must happen before the
2936 jump. Non-volatile reads must happen before the jump iff
2937 the result is needed by the above register used mask. */
2939 pending = deps->pending_write_insns;
2940 pending_mem = deps->pending_write_mems;
2941 while (pending)
2943 if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2944 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2945 pending = XEXP (pending, 1);
2946 pending_mem = XEXP (pending_mem, 1);
2949 pending = deps->pending_read_insns;
2950 pending_mem = deps->pending_read_mems;
2951 while (pending)
2953 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2954 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2955 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2956 pending = XEXP (pending, 1);
2957 pending_mem = XEXP (pending_mem, 1);
2960 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2961 REG_DEP_ANTI, true);
2962 add_dependence_list (insn, deps->pending_jump_insns, 1,
2963 REG_DEP_ANTI, true);
2967 /* If this instruction can throw an exception, then moving it changes
2968 where block boundaries fall. This is mighty confusing elsewhere.
2969 Therefore, prevent such an instruction from being moved. Same for
2970 non-jump instructions that define block boundaries.
2971 ??? Unclear whether this is still necessary in EBB mode. If not,
2972 add_branch_dependences should be adjusted for RGN mode instead. */
2973 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2974 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2975 reg_pending_barrier = MOVE_BARRIER;
2977 if (sched_pressure != SCHED_PRESSURE_NONE)
2979 setup_insn_reg_uses (deps, insn);
2980 init_insn_reg_pressure_info (insn);
2983 /* Add register dependencies for insn. */
2984 if (DEBUG_INSN_P (insn))
2986 rtx prev = deps->last_debug_insn;
2987 rtx u;
2989 if (!deps->readonly)
2990 deps->last_debug_insn = insn;
2992 if (prev)
2993 add_dependence (insn, prev, REG_DEP_ANTI);
2995 add_dependence_list (insn, deps->last_function_call, 1,
2996 REG_DEP_ANTI, false);
2998 if (!sel_sched_p ())
2999 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
3000 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3002 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3004 struct deps_reg *reg_last = &deps->reg_last[i];
3005 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3006 /* There's no point in making REG_DEP_CONTROL dependencies for
3007 debug insns. */
3008 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3009 false);
3011 if (!deps->readonly)
3012 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3014 CLEAR_REG_SET (reg_pending_uses);
3016 /* Quite often, a debug insn will refer to stuff in the
3017 previous instruction, but the reason we want this
3018 dependency here is to make sure the scheduler doesn't
3019 gratuitously move a debug insn ahead. This could dirty
3020 DF flags and cause additional analysis that wouldn't have
3021 occurred in compilation without debug insns, and such
3022 additional analysis can modify the generated code. */
3023 prev = PREV_INSN (insn);
3025 if (prev && NONDEBUG_INSN_P (prev))
3026 add_dependence (insn, prev, REG_DEP_ANTI);
3028 else
3030 regset_head set_or_clobbered;
3032 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3034 struct deps_reg *reg_last = &deps->reg_last[i];
3035 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3036 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3037 false);
3038 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3039 false);
3041 if (!deps->readonly)
3043 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3044 reg_last->uses_length++;
3048 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3049 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3051 struct deps_reg *reg_last = &deps->reg_last[i];
3052 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3053 add_dependence_list (insn, reg_last->implicit_sets, 0,
3054 REG_DEP_ANTI, false);
3055 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3056 false);
3058 if (!deps->readonly)
3060 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3061 reg_last->uses_length++;
3065 if (targetm.sched.exposed_pipeline)
3067 INIT_REG_SET (&set_or_clobbered);
3068 bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3069 reg_pending_sets);
3070 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3072 struct deps_reg *reg_last = &deps->reg_last[i];
3073 rtx list;
3074 for (list = reg_last->uses; list; list = XEXP (list, 1))
3076 rtx other = XEXP (list, 0);
3077 if (INSN_CACHED_COND (other) != const_true_rtx
3078 && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
3079 INSN_CACHED_COND (other) = const_true_rtx;
3084 /* If the current insn is conditional, we can't free any
3085 of the lists. */
3086 if (sched_has_condition_p (insn))
3088 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3090 struct deps_reg *reg_last = &deps->reg_last[i];
3091 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3092 false);
3093 add_dependence_list (insn, reg_last->implicit_sets, 0,
3094 REG_DEP_ANTI, false);
3095 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3096 false);
3097 add_dependence_list (insn, reg_last->control_uses, 0,
3098 REG_DEP_CONTROL, false);
3100 if (!deps->readonly)
3102 reg_last->clobbers
3103 = alloc_INSN_LIST (insn, reg_last->clobbers);
3104 reg_last->clobbers_length++;
3107 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3109 struct deps_reg *reg_last = &deps->reg_last[i];
3110 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3111 false);
3112 add_dependence_list (insn, reg_last->implicit_sets, 0,
3113 REG_DEP_ANTI, false);
3114 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3115 false);
3116 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3117 false);
3118 add_dependence_list (insn, reg_last->control_uses, 0,
3119 REG_DEP_CONTROL, false);
3121 if (!deps->readonly)
3122 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3125 else
3127 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3129 struct deps_reg *reg_last = &deps->reg_last[i];
3130 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
3131 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
3133 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3134 REG_DEP_OUTPUT, false);
3135 add_dependence_list_and_free (deps, insn,
3136 &reg_last->implicit_sets, 0,
3137 REG_DEP_ANTI, false);
3138 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3139 REG_DEP_ANTI, false);
3140 add_dependence_list_and_free (deps, insn,
3141 &reg_last->control_uses, 0,
3142 REG_DEP_ANTI, false);
3143 add_dependence_list_and_free (deps, insn,
3144 &reg_last->clobbers, 0,
3145 REG_DEP_OUTPUT, false);
3147 if (!deps->readonly)
3149 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3150 reg_last->clobbers_length = 0;
3151 reg_last->uses_length = 0;
3154 else
3156 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3157 false);
3158 add_dependence_list (insn, reg_last->implicit_sets, 0,
3159 REG_DEP_ANTI, false);
3160 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3161 false);
3162 add_dependence_list (insn, reg_last->control_uses, 0,
3163 REG_DEP_CONTROL, false);
3166 if (!deps->readonly)
3168 reg_last->clobbers_length++;
3169 reg_last->clobbers
3170 = alloc_INSN_LIST (insn, reg_last->clobbers);
3173 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3175 struct deps_reg *reg_last = &deps->reg_last[i];
3177 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3178 REG_DEP_OUTPUT, false);
3179 add_dependence_list_and_free (deps, insn,
3180 &reg_last->implicit_sets,
3181 0, REG_DEP_ANTI, false);
3182 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3183 REG_DEP_OUTPUT, false);
3184 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3185 REG_DEP_ANTI, false);
3186 add_dependence_list (insn, reg_last->control_uses, 0,
3187 REG_DEP_CONTROL, false);
3189 if (!deps->readonly)
3191 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3192 reg_last->uses_length = 0;
3193 reg_last->clobbers_length = 0;
3197 if (!deps->readonly)
3199 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3201 struct deps_reg *reg_last = &deps->reg_last[i];
3202 reg_last->control_uses
3203 = alloc_INSN_LIST (insn, reg_last->control_uses);
3208 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3209 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3211 struct deps_reg *reg_last = &deps->reg_last[i];
3212 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3213 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3214 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3215 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3216 false);
3218 if (!deps->readonly)
3219 reg_last->implicit_sets
3220 = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3223 if (!deps->readonly)
3225 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3226 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3227 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3228 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3229 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3230 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3231 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3233 /* Set up the pending barrier found. */
3234 deps->last_reg_pending_barrier = reg_pending_barrier;
3237 CLEAR_REG_SET (reg_pending_uses);
3238 CLEAR_REG_SET (reg_pending_clobbers);
3239 CLEAR_REG_SET (reg_pending_sets);
3240 CLEAR_REG_SET (reg_pending_control_uses);
3241 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3242 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3244 /* Add dependencies if a scheduling barrier was found. */
3245 if (reg_pending_barrier)
3247 /* In the case of barrier the most added dependencies are not
3248 real, so we use anti-dependence here. */
3249 if (sched_has_condition_p (insn))
3251 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3253 struct deps_reg *reg_last = &deps->reg_last[i];
3254 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3255 true);
3256 add_dependence_list (insn, reg_last->sets, 0,
3257 reg_pending_barrier == TRUE_BARRIER
3258 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3259 add_dependence_list (insn, reg_last->implicit_sets, 0,
3260 REG_DEP_ANTI, true);
3261 add_dependence_list (insn, reg_last->clobbers, 0,
3262 reg_pending_barrier == TRUE_BARRIER
3263 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3266 else
3268 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3270 struct deps_reg *reg_last = &deps->reg_last[i];
3271 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3272 REG_DEP_ANTI, true);
3273 add_dependence_list_and_free (deps, insn,
3274 &reg_last->control_uses, 0,
3275 REG_DEP_CONTROL, true);
3276 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3277 reg_pending_barrier == TRUE_BARRIER
3278 ? REG_DEP_TRUE : REG_DEP_ANTI,
3279 true);
3280 add_dependence_list_and_free (deps, insn,
3281 &reg_last->implicit_sets, 0,
3282 REG_DEP_ANTI, true);
3283 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3284 reg_pending_barrier == TRUE_BARRIER
3285 ? REG_DEP_TRUE : REG_DEP_ANTI,
3286 true);
3288 if (!deps->readonly)
3290 reg_last->uses_length = 0;
3291 reg_last->clobbers_length = 0;
3296 if (!deps->readonly)
3297 for (i = 0; i < (unsigned)deps->max_reg; i++)
3299 struct deps_reg *reg_last = &deps->reg_last[i];
3300 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3301 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3304 /* Flush pending lists on jumps, but not on speculative checks. */
3305 if (JUMP_P (insn) && !(sel_sched_p ()
3306 && sel_insn_is_speculation_check (insn)))
3307 flush_pending_lists (deps, insn, true, true);
3309 reg_pending_barrier = NOT_A_BARRIER;
3312 /* If a post-call group is still open, see if it should remain so.
3313 This insn must be a simple move of a hard reg to a pseudo or
3314 vice-versa.
3316 We must avoid moving these insns for correctness on targets
3317 with small register classes, and for special registers like
3318 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3319 hard regs for all targets. */
3321 if (deps->in_post_call_group_p)
3323 rtx tmp, set = single_set (insn);
3324 int src_regno, dest_regno;
3326 if (set == NULL)
3328 if (DEBUG_INSN_P (insn))
3329 /* We don't want to mark debug insns as part of the same
3330 sched group. We know they really aren't, but if we use
3331 debug insns to tell that a call group is over, we'll
3332 get different code if debug insns are not there and
3333 instructions that follow seem like they should be part
3334 of the call group.
3336 Also, if we did, chain_to_prev_insn would move the
3337 deps of the debug insn to the call insn, modifying
3338 non-debug post-dependency counts of the debug insn
3339 dependencies and otherwise messing with the scheduling
3340 order.
3342 Instead, let such debug insns be scheduled freely, but
3343 keep the call group open in case there are insns that
3344 should be part of it afterwards. Since we grant debug
3345 insns higher priority than even sched group insns, it
3346 will all turn out all right. */
3347 goto debug_dont_end_call_group;
3348 else
3349 goto end_call_group;
3352 tmp = SET_DEST (set);
3353 if (GET_CODE (tmp) == SUBREG)
3354 tmp = SUBREG_REG (tmp);
3355 if (REG_P (tmp))
3356 dest_regno = REGNO (tmp);
3357 else
3358 goto end_call_group;
3360 tmp = SET_SRC (set);
3361 if (GET_CODE (tmp) == SUBREG)
3362 tmp = SUBREG_REG (tmp);
3363 if ((GET_CODE (tmp) == PLUS
3364 || GET_CODE (tmp) == MINUS)
3365 && REG_P (XEXP (tmp, 0))
3366 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3367 && dest_regno == STACK_POINTER_REGNUM)
3368 src_regno = STACK_POINTER_REGNUM;
3369 else if (REG_P (tmp))
3370 src_regno = REGNO (tmp);
3371 else
3372 goto end_call_group;
3374 if (src_regno < FIRST_PSEUDO_REGISTER
3375 || dest_regno < FIRST_PSEUDO_REGISTER)
3377 if (!deps->readonly
3378 && deps->in_post_call_group_p == post_call_initial)
3379 deps->in_post_call_group_p = post_call;
3381 if (!sel_sched_p () || sched_emulate_haifa_p)
3383 SCHED_GROUP_P (insn) = 1;
3384 CANT_MOVE (insn) = 1;
3387 else
3389 end_call_group:
3390 if (!deps->readonly)
3391 deps->in_post_call_group_p = not_post_call;
3395 debug_dont_end_call_group:
3396 if ((current_sched_info->flags & DO_SPECULATION)
3397 && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3398 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3399 be speculated. */
3401 if (sel_sched_p ())
3402 sel_mark_hard_insn (insn);
3403 else
3405 sd_iterator_def sd_it;
3406 dep_t dep;
3408 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3409 sd_iterator_cond (&sd_it, &dep);)
3410 change_spec_dep_to_hard (sd_it);
3415 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3416 longjmp, loop forever, ...). */
3417 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3418 test for ECF_NORETURN? */
3419 static bool
3420 call_may_noreturn_p (rtx insn)
3422 rtx call;
3424 /* const or pure calls that aren't looping will always return. */
3425 if (RTL_CONST_OR_PURE_CALL_P (insn)
3426 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3427 return false;
3429 call = get_call_rtx_from (insn);
3430 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3432 rtx symbol = XEXP (XEXP (call, 0), 0);
3433 if (SYMBOL_REF_DECL (symbol)
3434 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3436 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3437 == BUILT_IN_NORMAL)
3438 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3440 case BUILT_IN_BCMP:
3441 case BUILT_IN_BCOPY:
3442 case BUILT_IN_BZERO:
3443 case BUILT_IN_INDEX:
3444 case BUILT_IN_MEMCHR:
3445 case BUILT_IN_MEMCMP:
3446 case BUILT_IN_MEMCPY:
3447 case BUILT_IN_MEMMOVE:
3448 case BUILT_IN_MEMPCPY:
3449 case BUILT_IN_MEMSET:
3450 case BUILT_IN_RINDEX:
3451 case BUILT_IN_STPCPY:
3452 case BUILT_IN_STPNCPY:
3453 case BUILT_IN_STRCAT:
3454 case BUILT_IN_STRCHR:
3455 case BUILT_IN_STRCMP:
3456 case BUILT_IN_STRCPY:
3457 case BUILT_IN_STRCSPN:
3458 case BUILT_IN_STRLEN:
3459 case BUILT_IN_STRNCAT:
3460 case BUILT_IN_STRNCMP:
3461 case BUILT_IN_STRNCPY:
3462 case BUILT_IN_STRPBRK:
3463 case BUILT_IN_STRRCHR:
3464 case BUILT_IN_STRSPN:
3465 case BUILT_IN_STRSTR:
3466 /* Assume certain string/memory builtins always return. */
3467 return false;
3468 default:
3469 break;
3474 /* For all other calls assume that they might not always return. */
3475 return true;
3478 /* Return true if INSN should be made dependent on the previous instruction
3479 group, and if all INSN's dependencies should be moved to the first
3480 instruction of that group. */
3482 static bool
3483 chain_to_prev_insn_p (rtx insn)
3485 rtx prev, x;
3487 /* INSN forms a group with the previous instruction. */
3488 if (SCHED_GROUP_P (insn))
3489 return true;
3491 /* If the previous instruction clobbers a register R and this one sets
3492 part of R, the clobber was added specifically to help us track the
3493 liveness of R. There's no point scheduling the clobber and leaving
3494 INSN behind, especially if we move the clobber to another block. */
3495 prev = prev_nonnote_nondebug_insn (insn);
3496 if (prev
3497 && INSN_P (prev)
3498 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3499 && GET_CODE (PATTERN (prev)) == CLOBBER)
3501 x = XEXP (PATTERN (prev), 0);
3502 if (set_of (x, insn))
3503 return true;
3506 return false;
3509 /* Analyze INSN with DEPS as a context. */
3510 void
3511 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3513 if (sched_deps_info->start_insn)
3514 sched_deps_info->start_insn (insn);
3516 /* Record the condition for this insn. */
3517 if (NONDEBUG_INSN_P (insn))
3519 rtx t;
3520 sched_get_condition_with_rev (insn, NULL);
3521 t = INSN_CACHED_COND (insn);
3522 INSN_COND_DEPS (insn) = NULL_RTX;
3523 if (reload_completed
3524 && (current_sched_info->flags & DO_PREDICATION)
3525 && COMPARISON_P (t)
3526 && REG_P (XEXP (t, 0))
3527 && CONSTANT_P (XEXP (t, 1)))
3529 unsigned int regno;
3530 int nregs;
3531 t = XEXP (t, 0);
3532 regno = REGNO (t);
3533 nregs = hard_regno_nregs[regno][GET_MODE (t)];
3534 t = NULL_RTX;
3535 while (nregs-- > 0)
3537 struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3538 t = concat_INSN_LIST (reg_last->sets, t);
3539 t = concat_INSN_LIST (reg_last->clobbers, t);
3540 t = concat_INSN_LIST (reg_last->implicit_sets, t);
3542 INSN_COND_DEPS (insn) = t;
3546 if (JUMP_P (insn))
3548 /* Make each JUMP_INSN (but not a speculative check)
3549 a scheduling barrier for memory references. */
3550 if (!deps->readonly
3551 && !(sel_sched_p ()
3552 && sel_insn_is_speculation_check (insn)))
3554 /* Keep the list a reasonable size. */
3555 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3556 flush_pending_lists (deps, insn, true, true);
3557 else
3558 deps->pending_jump_insns
3559 = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3562 /* For each insn which shouldn't cross a jump, add a dependence. */
3563 add_dependence_list_and_free (deps, insn,
3564 &deps->sched_before_next_jump, 1,
3565 REG_DEP_ANTI, true);
3567 sched_analyze_insn (deps, PATTERN (insn), insn);
3569 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3571 sched_analyze_insn (deps, PATTERN (insn), insn);
3573 else if (CALL_P (insn))
3575 int i;
3577 CANT_MOVE (insn) = 1;
3579 if (find_reg_note (insn, REG_SETJMP, NULL))
3581 /* This is setjmp. Assume that all registers, not just
3582 hard registers, may be clobbered by this call. */
3583 reg_pending_barrier = MOVE_BARRIER;
3585 else
3587 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3588 /* A call may read and modify global register variables. */
3589 if (global_regs[i])
3591 SET_REGNO_REG_SET (reg_pending_sets, i);
3592 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3594 /* Other call-clobbered hard regs may be clobbered.
3595 Since we only have a choice between 'might be clobbered'
3596 and 'definitely not clobbered', we must include all
3597 partly call-clobbered registers here. */
3598 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3599 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3600 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3601 /* We don't know what set of fixed registers might be used
3602 by the function, but it is certain that the stack pointer
3603 is among them, but be conservative. */
3604 else if (fixed_regs[i])
3605 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3606 /* The frame pointer is normally not used by the function
3607 itself, but by the debugger. */
3608 /* ??? MIPS o32 is an exception. It uses the frame pointer
3609 in the macro expansion of jal but does not represent this
3610 fact in the call_insn rtl. */
3611 else if (i == FRAME_POINTER_REGNUM
3612 || (i == HARD_FRAME_POINTER_REGNUM
3613 && (! reload_completed || frame_pointer_needed)))
3614 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3617 /* For each insn which shouldn't cross a call, add a dependence
3618 between that insn and this call insn. */
3619 add_dependence_list_and_free (deps, insn,
3620 &deps->sched_before_next_call, 1,
3621 REG_DEP_ANTI, true);
3623 sched_analyze_insn (deps, PATTERN (insn), insn);
3625 /* If CALL would be in a sched group, then this will violate
3626 convention that sched group insns have dependencies only on the
3627 previous instruction.
3629 Of course one can say: "Hey! What about head of the sched group?"
3630 And I will answer: "Basic principles (one dep per insn) are always
3631 the same." */
3632 gcc_assert (!SCHED_GROUP_P (insn));
3634 /* In the absence of interprocedural alias analysis, we must flush
3635 all pending reads and writes, and start new dependencies starting
3636 from here. But only flush writes for constant calls (which may
3637 be passed a pointer to something we haven't written yet). */
3638 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3640 if (!deps->readonly)
3642 /* Remember the last function call for limiting lifetimes. */
3643 free_INSN_LIST_list (&deps->last_function_call);
3644 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3646 if (call_may_noreturn_p (insn))
3648 /* Remember the last function call that might not always return
3649 normally for limiting moves of trapping insns. */
3650 free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3651 deps->last_function_call_may_noreturn
3652 = alloc_INSN_LIST (insn, NULL_RTX);
3655 /* Before reload, begin a post-call group, so as to keep the
3656 lifetimes of hard registers correct. */
3657 if (! reload_completed)
3658 deps->in_post_call_group_p = post_call;
3662 if (sched_deps_info->use_cselib)
3663 cselib_process_insn (insn);
3665 /* EH_REGION insn notes can not appear until well after we complete
3666 scheduling. */
3667 if (NOTE_P (insn))
3668 gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3669 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3671 if (sched_deps_info->finish_insn)
3672 sched_deps_info->finish_insn ();
3674 /* Fixup the dependencies in the sched group. */
3675 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3676 && chain_to_prev_insn_p (insn)
3677 && !sel_sched_p ())
3678 chain_to_prev_insn (insn);
3681 /* Initialize DEPS for the new block beginning with HEAD. */
3682 void
3683 deps_start_bb (struct deps_desc *deps, rtx head)
3685 gcc_assert (!deps->readonly);
3687 /* Before reload, if the previous block ended in a call, show that
3688 we are inside a post-call group, so as to keep the lifetimes of
3689 hard registers correct. */
3690 if (! reload_completed && !LABEL_P (head))
3692 rtx insn = prev_nonnote_nondebug_insn (head);
3694 if (insn && CALL_P (insn))
3695 deps->in_post_call_group_p = post_call_initial;
3699 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3700 dependencies for each insn. */
3701 void
3702 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3704 rtx insn;
3706 if (sched_deps_info->use_cselib)
3707 cselib_init (CSELIB_RECORD_MEMORY);
3709 deps_start_bb (deps, head);
3711 for (insn = head;; insn = NEXT_INSN (insn))
3714 if (INSN_P (insn))
3716 /* And initialize deps_lists. */
3717 sd_init_insn (insn);
3720 deps_analyze_insn (deps, insn);
3722 if (insn == tail)
3724 if (sched_deps_info->use_cselib)
3725 cselib_finish ();
3726 return;
3729 gcc_unreachable ();
3732 /* Helper for sched_free_deps ().
3733 Delete INSN's (RESOLVED_P) backward dependencies. */
3734 static void
3735 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3737 sd_iterator_def sd_it;
3738 dep_t dep;
3739 sd_list_types_def types;
3741 if (resolved_p)
3742 types = SD_LIST_RES_BACK;
3743 else
3744 types = SD_LIST_BACK;
3746 for (sd_it = sd_iterator_start (insn, types);
3747 sd_iterator_cond (&sd_it, &dep);)
3749 dep_link_t link = *sd_it.linkp;
3750 dep_node_t node = DEP_LINK_NODE (link);
3751 deps_list_t back_list;
3752 deps_list_t forw_list;
3754 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3755 remove_from_deps_list (link, back_list);
3756 delete_dep_node (node);
3760 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3761 deps_lists. */
3762 void
3763 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3765 rtx insn;
3766 rtx next_tail = NEXT_INSN (tail);
3768 /* We make two passes since some insns may be scheduled before their
3769 dependencies are resolved. */
3770 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3771 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3773 /* Clear forward deps and leave the dep_nodes to the
3774 corresponding back_deps list. */
3775 if (resolved_p)
3776 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3777 else
3778 clear_deps_list (INSN_FORW_DEPS (insn));
3780 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3781 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3783 /* Clear resolved back deps together with its dep_nodes. */
3784 delete_dep_nodes_in_back_deps (insn, resolved_p);
3786 sd_finish_insn (insn);
3790 /* Initialize variables for region data dependence analysis.
3791 When LAZY_REG_LAST is true, do not allocate reg_last array
3792 of struct deps_desc immediately. */
3794 void
3795 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3797 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3799 deps->max_reg = max_reg;
3800 if (lazy_reg_last)
3801 deps->reg_last = NULL;
3802 else
3803 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3804 INIT_REG_SET (&deps->reg_last_in_use);
3806 deps->pending_read_insns = 0;
3807 deps->pending_read_mems = 0;
3808 deps->pending_write_insns = 0;
3809 deps->pending_write_mems = 0;
3810 deps->pending_jump_insns = 0;
3811 deps->pending_read_list_length = 0;
3812 deps->pending_write_list_length = 0;
3813 deps->pending_flush_length = 0;
3814 deps->last_pending_memory_flush = 0;
3815 deps->last_function_call = 0;
3816 deps->last_function_call_may_noreturn = 0;
3817 deps->sched_before_next_call = 0;
3818 deps->sched_before_next_jump = 0;
3819 deps->in_post_call_group_p = not_post_call;
3820 deps->last_debug_insn = 0;
3821 deps->last_reg_pending_barrier = NOT_A_BARRIER;
3822 deps->readonly = 0;
3825 /* Init only reg_last field of DEPS, which was not allocated before as
3826 we inited DEPS lazily. */
3827 void
3828 init_deps_reg_last (struct deps_desc *deps)
3830 gcc_assert (deps && deps->max_reg > 0);
3831 gcc_assert (deps->reg_last == NULL);
3833 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3837 /* Free insn lists found in DEPS. */
3839 void
3840 free_deps (struct deps_desc *deps)
3842 unsigned i;
3843 reg_set_iterator rsi;
3845 /* We set max_reg to 0 when this context was already freed. */
3846 if (deps->max_reg == 0)
3848 gcc_assert (deps->reg_last == NULL);
3849 return;
3851 deps->max_reg = 0;
3853 free_INSN_LIST_list (&deps->pending_read_insns);
3854 free_EXPR_LIST_list (&deps->pending_read_mems);
3855 free_INSN_LIST_list (&deps->pending_write_insns);
3856 free_EXPR_LIST_list (&deps->pending_write_mems);
3857 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3859 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3860 times. For a testcase with 42000 regs and 8000 small basic blocks,
3861 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3862 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3864 struct deps_reg *reg_last = &deps->reg_last[i];
3865 if (reg_last->uses)
3866 free_INSN_LIST_list (&reg_last->uses);
3867 if (reg_last->sets)
3868 free_INSN_LIST_list (&reg_last->sets);
3869 if (reg_last->implicit_sets)
3870 free_INSN_LIST_list (&reg_last->implicit_sets);
3871 if (reg_last->control_uses)
3872 free_INSN_LIST_list (&reg_last->control_uses);
3873 if (reg_last->clobbers)
3874 free_INSN_LIST_list (&reg_last->clobbers);
3876 CLEAR_REG_SET (&deps->reg_last_in_use);
3878 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3879 it at all. */
3880 free (deps->reg_last);
3881 deps->reg_last = NULL;
3883 deps = NULL;
3886 /* Remove INSN from dependence contexts DEPS. */
3887 void
3888 remove_from_deps (struct deps_desc *deps, rtx insn)
3890 int removed;
3891 unsigned i;
3892 reg_set_iterator rsi;
3894 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3895 &deps->pending_read_mems);
3896 if (!DEBUG_INSN_P (insn))
3897 deps->pending_read_list_length -= removed;
3898 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3899 &deps->pending_write_mems);
3900 deps->pending_write_list_length -= removed;
3902 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
3903 deps->pending_flush_length -= removed;
3904 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3905 deps->pending_flush_length -= removed;
3907 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3909 struct deps_reg *reg_last = &deps->reg_last[i];
3910 if (reg_last->uses)
3911 remove_from_dependence_list (insn, &reg_last->uses);
3912 if (reg_last->sets)
3913 remove_from_dependence_list (insn, &reg_last->sets);
3914 if (reg_last->implicit_sets)
3915 remove_from_dependence_list (insn, &reg_last->implicit_sets);
3916 if (reg_last->clobbers)
3917 remove_from_dependence_list (insn, &reg_last->clobbers);
3918 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3919 && !reg_last->clobbers)
3920 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3923 if (CALL_P (insn))
3925 remove_from_dependence_list (insn, &deps->last_function_call);
3926 remove_from_dependence_list (insn,
3927 &deps->last_function_call_may_noreturn);
3929 remove_from_dependence_list (insn, &deps->sched_before_next_call);
3932 /* Init deps data vector. */
3933 static void
3934 init_deps_data_vector (void)
3936 int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
3937 if (reserve > 0 && ! h_d_i_d.space (reserve))
3938 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
3941 /* If it is profitable to use them, initialize or extend (depending on
3942 GLOBAL_P) dependency data. */
3943 void
3944 sched_deps_init (bool global_p)
3946 /* Average number of insns in the basic block.
3947 '+ 1' is used to make it nonzero. */
3948 int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3950 init_deps_data_vector ();
3952 /* We use another caching mechanism for selective scheduling, so
3953 we don't use this one. */
3954 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3956 /* ?!? We could save some memory by computing a per-region luid mapping
3957 which could reduce both the number of vectors in the cache and the
3958 size of each vector. Instead we just avoid the cache entirely unless
3959 the average number of instructions in a basic block is very high. See
3960 the comment before the declaration of true_dependency_cache for
3961 what we consider "very high". */
3962 cache_size = 0;
3963 extend_dependency_caches (sched_max_luid, true);
3966 if (global_p)
3968 dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3969 /* Allocate lists for one block at a time. */
3970 insns_in_block);
3971 dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3972 /* Allocate nodes for one block at a time.
3973 We assume that average insn has
3974 5 producers. */
3975 5 * insns_in_block);
3980 /* Create or extend (depending on CREATE_P) dependency caches to
3981 size N. */
3982 void
3983 extend_dependency_caches (int n, bool create_p)
3985 if (create_p || true_dependency_cache)
3987 int i, luid = cache_size + n;
3989 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3990 luid);
3991 output_dependency_cache = XRESIZEVEC (bitmap_head,
3992 output_dependency_cache, luid);
3993 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
3994 luid);
3995 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
3996 luid);
3998 if (current_sched_info->flags & DO_SPECULATION)
3999 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4000 luid);
4002 for (i = cache_size; i < luid; i++)
4004 bitmap_initialize (&true_dependency_cache[i], 0);
4005 bitmap_initialize (&output_dependency_cache[i], 0);
4006 bitmap_initialize (&anti_dependency_cache[i], 0);
4007 bitmap_initialize (&control_dependency_cache[i], 0);
4009 if (current_sched_info->flags & DO_SPECULATION)
4010 bitmap_initialize (&spec_dependency_cache[i], 0);
4012 cache_size = luid;
4016 /* Finalize dependency information for the whole function. */
4017 void
4018 sched_deps_finish (void)
4020 gcc_assert (deps_pools_are_empty_p ());
4021 free_alloc_pool_if_empty (&dn_pool);
4022 free_alloc_pool_if_empty (&dl_pool);
4023 gcc_assert (dn_pool == NULL && dl_pool == NULL);
4025 h_d_i_d.release ();
4026 cache_size = 0;
4028 if (true_dependency_cache)
4030 int i;
4032 for (i = 0; i < cache_size; i++)
4034 bitmap_clear (&true_dependency_cache[i]);
4035 bitmap_clear (&output_dependency_cache[i]);
4036 bitmap_clear (&anti_dependency_cache[i]);
4037 bitmap_clear (&control_dependency_cache[i]);
4039 if (sched_deps_info->generate_spec_deps)
4040 bitmap_clear (&spec_dependency_cache[i]);
4042 free (true_dependency_cache);
4043 true_dependency_cache = NULL;
4044 free (output_dependency_cache);
4045 output_dependency_cache = NULL;
4046 free (anti_dependency_cache);
4047 anti_dependency_cache = NULL;
4048 free (control_dependency_cache);
4049 control_dependency_cache = NULL;
4051 if (sched_deps_info->generate_spec_deps)
4053 free (spec_dependency_cache);
4054 spec_dependency_cache = NULL;
4060 /* Initialize some global variables needed by the dependency analysis
4061 code. */
4063 void
4064 init_deps_global (void)
4066 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4067 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4068 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4069 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4070 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4071 reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4072 reg_pending_barrier = NOT_A_BARRIER;
4074 if (!sel_sched_p () || sched_emulate_haifa_p)
4076 sched_deps_info->start_insn = haifa_start_insn;
4077 sched_deps_info->finish_insn = haifa_finish_insn;
4079 sched_deps_info->note_reg_set = haifa_note_reg_set;
4080 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4081 sched_deps_info->note_reg_use = haifa_note_reg_use;
4083 sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4084 sched_deps_info->note_dep = haifa_note_dep;
4088 /* Free everything used by the dependency analysis code. */
4090 void
4091 finish_deps_global (void)
4093 FREE_REG_SET (reg_pending_sets);
4094 FREE_REG_SET (reg_pending_clobbers);
4095 FREE_REG_SET (reg_pending_uses);
4096 FREE_REG_SET (reg_pending_control_uses);
4099 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4100 dw_t
4101 estimate_dep_weak (rtx mem1, rtx mem2)
4103 rtx r1, r2;
4105 if (mem1 == mem2)
4106 /* MEMs are the same - don't speculate. */
4107 return MIN_DEP_WEAK;
4109 r1 = XEXP (mem1, 0);
4110 r2 = XEXP (mem2, 0);
4112 if (r1 == r2
4113 || (REG_P (r1) && REG_P (r2)
4114 && REGNO (r1) == REGNO (r2)))
4115 /* Again, MEMs are the same. */
4116 return MIN_DEP_WEAK;
4117 else if ((REG_P (r1) && !REG_P (r2))
4118 || (!REG_P (r1) && REG_P (r2)))
4119 /* Different addressing modes - reason to be more speculative,
4120 than usual. */
4121 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4122 else
4123 /* We can't say anything about the dependence. */
4124 return UNCERTAIN_DEP_WEAK;
4127 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4128 This function can handle same INSN and ELEM (INSN == ELEM).
4129 It is a convenience wrapper. */
4130 static void
4131 add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
4133 ds_t ds;
4134 bool internal;
4136 if (dep_type == REG_DEP_TRUE)
4137 ds = DEP_TRUE;
4138 else if (dep_type == REG_DEP_OUTPUT)
4139 ds = DEP_OUTPUT;
4140 else if (dep_type == REG_DEP_CONTROL)
4141 ds = DEP_CONTROL;
4142 else
4144 gcc_assert (dep_type == REG_DEP_ANTI);
4145 ds = DEP_ANTI;
4148 /* When add_dependence is called from inside sched-deps.c, we expect
4149 cur_insn to be non-null. */
4150 internal = cur_insn != NULL;
4151 if (internal)
4152 gcc_assert (insn == cur_insn);
4153 else
4154 cur_insn = insn;
4156 note_dep (elem, ds);
4157 if (!internal)
4158 cur_insn = NULL;
4161 /* Return weakness of speculative type TYPE in the dep_status DS. */
4162 dw_t
4163 get_dep_weak_1 (ds_t ds, ds_t type)
4165 ds = ds & type;
4167 switch (type)
4169 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4170 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4171 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4172 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4173 default: gcc_unreachable ();
4176 return (dw_t) ds;
4179 dw_t
4180 get_dep_weak (ds_t ds, ds_t type)
4182 dw_t dw = get_dep_weak_1 (ds, type);
4184 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4185 return dw;
4188 /* Return the dep_status, which has the same parameters as DS, except for
4189 speculative type TYPE, that will have weakness DW. */
4190 ds_t
4191 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4193 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4195 ds &= ~type;
4196 switch (type)
4198 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4199 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4200 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4201 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4202 default: gcc_unreachable ();
4204 return ds;
4207 /* Return the join of two dep_statuses DS1 and DS2.
4208 If MAX_P is true then choose the greater probability,
4209 otherwise multiply probabilities.
4210 This function assumes that both DS1 and DS2 contain speculative bits. */
4211 static ds_t
4212 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4214 ds_t ds, t;
4216 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4218 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4220 t = FIRST_SPEC_TYPE;
4223 if ((ds1 & t) && !(ds2 & t))
4224 ds |= ds1 & t;
4225 else if (!(ds1 & t) && (ds2 & t))
4226 ds |= ds2 & t;
4227 else if ((ds1 & t) && (ds2 & t))
4229 dw_t dw1 = get_dep_weak (ds1, t);
4230 dw_t dw2 = get_dep_weak (ds2, t);
4231 ds_t dw;
4233 if (!max_p)
4235 dw = ((ds_t) dw1) * ((ds_t) dw2);
4236 dw /= MAX_DEP_WEAK;
4237 if (dw < MIN_DEP_WEAK)
4238 dw = MIN_DEP_WEAK;
4240 else
4242 if (dw1 >= dw2)
4243 dw = dw1;
4244 else
4245 dw = dw2;
4248 ds = set_dep_weak (ds, t, (dw_t) dw);
4251 if (t == LAST_SPEC_TYPE)
4252 break;
4253 t <<= SPEC_TYPE_SHIFT;
4255 while (1);
4257 return ds;
4260 /* Return the join of two dep_statuses DS1 and DS2.
4261 This function assumes that both DS1 and DS2 contain speculative bits. */
4262 ds_t
4263 ds_merge (ds_t ds1, ds_t ds2)
4265 return ds_merge_1 (ds1, ds2, false);
4268 /* Return the join of two dep_statuses DS1 and DS2. */
4269 ds_t
4270 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4272 ds_t new_status = ds | ds2;
4274 if (new_status & SPECULATIVE)
4276 if ((ds && !(ds & SPECULATIVE))
4277 || (ds2 && !(ds2 & SPECULATIVE)))
4278 /* Then this dep can't be speculative. */
4279 new_status &= ~SPECULATIVE;
4280 else
4282 /* Both are speculative. Merging probabilities. */
4283 if (mem1)
4285 dw_t dw;
4287 dw = estimate_dep_weak (mem1, mem2);
4288 ds = set_dep_weak (ds, BEGIN_DATA, dw);
4291 if (!ds)
4292 new_status = ds2;
4293 else if (!ds2)
4294 new_status = ds;
4295 else
4296 new_status = ds_merge (ds2, ds);
4300 return new_status;
4303 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4304 probabilities. */
4305 ds_t
4306 ds_max_merge (ds_t ds1, ds_t ds2)
4308 if (ds1 == 0 && ds2 == 0)
4309 return 0;
4311 if (ds1 == 0 && ds2 != 0)
4312 return ds2;
4314 if (ds1 != 0 && ds2 == 0)
4315 return ds1;
4317 return ds_merge_1 (ds1, ds2, true);
4320 /* Return the probability of speculation success for the speculation
4321 status DS. */
4322 dw_t
4323 ds_weak (ds_t ds)
4325 ds_t res = 1, dt;
4326 int n = 0;
4328 dt = FIRST_SPEC_TYPE;
4331 if (ds & dt)
4333 res *= (ds_t) get_dep_weak (ds, dt);
4334 n++;
4337 if (dt == LAST_SPEC_TYPE)
4338 break;
4339 dt <<= SPEC_TYPE_SHIFT;
4341 while (1);
4343 gcc_assert (n);
4344 while (--n)
4345 res /= MAX_DEP_WEAK;
4347 if (res < MIN_DEP_WEAK)
4348 res = MIN_DEP_WEAK;
4350 gcc_assert (res <= MAX_DEP_WEAK);
4352 return (dw_t) res;
4355 /* Return a dep status that contains all speculation types of DS. */
4356 ds_t
4357 ds_get_speculation_types (ds_t ds)
4359 if (ds & BEGIN_DATA)
4360 ds |= BEGIN_DATA;
4361 if (ds & BE_IN_DATA)
4362 ds |= BE_IN_DATA;
4363 if (ds & BEGIN_CONTROL)
4364 ds |= BEGIN_CONTROL;
4365 if (ds & BE_IN_CONTROL)
4366 ds |= BE_IN_CONTROL;
4368 return ds & SPECULATIVE;
4371 /* Return a dep status that contains maximal weakness for each speculation
4372 type present in DS. */
4373 ds_t
4374 ds_get_max_dep_weak (ds_t ds)
4376 if (ds & BEGIN_DATA)
4377 ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4378 if (ds & BE_IN_DATA)
4379 ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4380 if (ds & BEGIN_CONTROL)
4381 ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4382 if (ds & BE_IN_CONTROL)
4383 ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4385 return ds;
4388 /* Dump information about the dependence status S. */
4389 static void
4390 dump_ds (FILE *f, ds_t s)
4392 fprintf (f, "{");
4394 if (s & BEGIN_DATA)
4395 fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4396 if (s & BE_IN_DATA)
4397 fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4398 if (s & BEGIN_CONTROL)
4399 fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4400 if (s & BE_IN_CONTROL)
4401 fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4403 if (s & HARD_DEP)
4404 fprintf (f, "HARD_DEP; ");
4406 if (s & DEP_TRUE)
4407 fprintf (f, "DEP_TRUE; ");
4408 if (s & DEP_OUTPUT)
4409 fprintf (f, "DEP_OUTPUT; ");
4410 if (s & DEP_ANTI)
4411 fprintf (f, "DEP_ANTI; ");
4412 if (s & DEP_CONTROL)
4413 fprintf (f, "DEP_CONTROL; ");
4415 fprintf (f, "}");
4418 DEBUG_FUNCTION void
4419 debug_ds (ds_t s)
4421 dump_ds (stderr, s);
4422 fprintf (stderr, "\n");
4425 #ifdef ENABLE_CHECKING
4426 /* Verify that dependence type and status are consistent.
4427 If RELAXED_P is true, then skip dep_weakness checks. */
4428 static void
4429 check_dep (dep_t dep, bool relaxed_p)
4431 enum reg_note dt = DEP_TYPE (dep);
4432 ds_t ds = DEP_STATUS (dep);
4434 gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4436 if (!(current_sched_info->flags & USE_DEPS_LIST))
4438 gcc_assert (ds == 0);
4439 return;
4442 /* Check that dependence type contains the same bits as the status. */
4443 if (dt == REG_DEP_TRUE)
4444 gcc_assert (ds & DEP_TRUE);
4445 else if (dt == REG_DEP_OUTPUT)
4446 gcc_assert ((ds & DEP_OUTPUT)
4447 && !(ds & DEP_TRUE));
4448 else if (dt == REG_DEP_ANTI)
4449 gcc_assert ((ds & DEP_ANTI)
4450 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4451 else
4452 gcc_assert (dt == REG_DEP_CONTROL
4453 && (ds & DEP_CONTROL)
4454 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4456 /* HARD_DEP can not appear in dep_status of a link. */
4457 gcc_assert (!(ds & HARD_DEP));
4459 /* Check that dependence status is set correctly when speculation is not
4460 supported. */
4461 if (!sched_deps_info->generate_spec_deps)
4462 gcc_assert (!(ds & SPECULATIVE));
4463 else if (ds & SPECULATIVE)
4465 if (!relaxed_p)
4467 ds_t type = FIRST_SPEC_TYPE;
4469 /* Check that dependence weakness is in proper range. */
4472 if (ds & type)
4473 get_dep_weak (ds, type);
4475 if (type == LAST_SPEC_TYPE)
4476 break;
4477 type <<= SPEC_TYPE_SHIFT;
4479 while (1);
4482 if (ds & BEGIN_SPEC)
4484 /* Only true dependence can be data speculative. */
4485 if (ds & BEGIN_DATA)
4486 gcc_assert (ds & DEP_TRUE);
4488 /* Control dependencies in the insn scheduler are represented by
4489 anti-dependencies, therefore only anti dependence can be
4490 control speculative. */
4491 if (ds & BEGIN_CONTROL)
4492 gcc_assert (ds & DEP_ANTI);
4494 else
4496 /* Subsequent speculations should resolve true dependencies. */
4497 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4500 /* Check that true and anti dependencies can't have other speculative
4501 statuses. */
4502 if (ds & DEP_TRUE)
4503 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4504 /* An output dependence can't be speculative at all. */
4505 gcc_assert (!(ds & DEP_OUTPUT));
4506 if (ds & DEP_ANTI)
4507 gcc_assert (ds & BEGIN_CONTROL);
4510 #endif /* ENABLE_CHECKING */
4512 /* The following code discovers opportunities to switch a memory reference
4513 and an increment by modifying the address. We ensure that this is done
4514 only for dependencies that are only used to show a single register
4515 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4516 instruction involved is subject to only one dep that can cause a pattern
4517 change.
4519 When we discover a suitable dependency, we fill in the dep_replacement
4520 structure to show how to modify the memory reference. */
4522 /* Holds information about a pair of memory reference and register increment
4523 insns which depend on each other, but could possibly be interchanged. */
4524 struct mem_inc_info
4526 rtx inc_insn;
4527 rtx mem_insn;
4529 rtx *mem_loc;
4530 /* A register occurring in the memory address for which we wish to break
4531 the dependence. This must be identical to the destination register of
4532 the increment. */
4533 rtx mem_reg0;
4534 /* Any kind of index that is added to that register. */
4535 rtx mem_index;
4536 /* The constant offset used in the memory address. */
4537 HOST_WIDE_INT mem_constant;
4538 /* The constant added in the increment insn. Negated if the increment is
4539 after the memory address. */
4540 HOST_WIDE_INT inc_constant;
4541 /* The source register used in the increment. May be different from mem_reg0
4542 if the increment occurs before the memory address. */
4543 rtx inc_input;
4546 /* Verify that the memory location described in MII can be replaced with
4547 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4548 insn remains unchanged by this function. */
4550 static rtx
4551 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4553 rtx mem = *mii->mem_loc;
4554 rtx new_mem;
4556 /* Jump thru a lot of hoops to keep the attributes up to date. We
4557 do not want to call one of the change address variants that take
4558 an offset even though we know the offset in many cases. These
4559 assume you are changing where the address is pointing by the
4560 offset. */
4561 new_mem = replace_equiv_address_nv (mem, new_addr);
4562 if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4564 if (sched_verbose >= 5)
4565 fprintf (sched_dump, "validation failure\n");
4566 return NULL_RTX;
4569 /* Put back the old one. */
4570 validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4572 return new_mem;
4575 /* Return true if INSN is of a form "a = b op c" where a and b are
4576 regs. op is + if c is a reg and +|- if c is a const. Fill in
4577 informantion in MII about what is found.
4578 BEFORE_MEM indicates whether the increment is found before or after
4579 a corresponding memory reference. */
4581 static bool
4582 parse_add_or_inc (struct mem_inc_info *mii, rtx insn, bool before_mem)
4584 rtx pat = single_set (insn);
4585 rtx src, cst;
4586 bool regs_equal;
4588 if (RTX_FRAME_RELATED_P (insn) || !pat)
4589 return false;
4591 /* Result must be single reg. */
4592 if (!REG_P (SET_DEST (pat)))
4593 return false;
4595 if (GET_CODE (SET_SRC (pat)) != PLUS)
4596 return false;
4598 mii->inc_insn = insn;
4599 src = SET_SRC (pat);
4600 mii->inc_input = XEXP (src, 0);
4602 if (!REG_P (XEXP (src, 0)))
4603 return false;
4605 if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4606 return false;
4608 cst = XEXP (src, 1);
4609 if (!CONST_INT_P (cst))
4610 return false;
4611 mii->inc_constant = INTVAL (cst);
4613 regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4615 if (!before_mem)
4617 mii->inc_constant = -mii->inc_constant;
4618 if (!regs_equal)
4619 return false;
4622 if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4624 /* Note that the sign has already been reversed for !before_mem. */
4625 #ifdef STACK_GROWS_DOWNWARD
4626 return mii->inc_constant > 0;
4627 #else
4628 return mii->inc_constant < 0;
4629 #endif
4631 return true;
4634 /* Once a suitable mem reference has been found and the corresponding data
4635 in MII has been filled in, this function is called to find a suitable
4636 add or inc insn involving the register we found in the memory
4637 reference. */
4639 static bool
4640 find_inc (struct mem_inc_info *mii, bool backwards)
4642 sd_iterator_def sd_it;
4643 dep_t dep;
4645 sd_it = sd_iterator_start (mii->mem_insn,
4646 backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4647 while (sd_iterator_cond (&sd_it, &dep))
4649 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4650 rtx pro = DEP_PRO (dep);
4651 rtx con = DEP_CON (dep);
4652 rtx inc_cand = backwards ? pro : con;
4653 if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4654 goto next;
4655 if (parse_add_or_inc (mii, inc_cand, backwards))
4657 struct dep_replacement *desc;
4658 df_ref *def_rec;
4659 rtx newaddr, newmem;
4661 if (sched_verbose >= 5)
4662 fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4663 INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4665 /* Need to assure that none of the operands of the inc
4666 instruction are assigned to by the mem insn. */
4667 for (def_rec = DF_INSN_DEFS (mii->mem_insn); *def_rec; def_rec++)
4669 df_ref def = *def_rec;
4670 if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4671 || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4673 if (sched_verbose >= 5)
4674 fprintf (sched_dump,
4675 "inc conflicts with store failure.\n");
4676 goto next;
4679 newaddr = mii->inc_input;
4680 if (mii->mem_index != NULL_RTX)
4681 newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4682 mii->mem_index);
4683 newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4684 mii->mem_constant + mii->inc_constant);
4685 newmem = attempt_change (mii, newaddr);
4686 if (newmem == NULL_RTX)
4687 goto next;
4688 if (sched_verbose >= 5)
4689 fprintf (sched_dump, "successful address replacement\n");
4690 desc = XCNEW (struct dep_replacement);
4691 DEP_REPLACE (dep) = desc;
4692 desc->loc = mii->mem_loc;
4693 desc->newval = newmem;
4694 desc->orig = *desc->loc;
4695 desc->insn = mii->mem_insn;
4696 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4697 INSN_SPEC_BACK_DEPS (con));
4698 if (backwards)
4700 FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4701 add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4702 REG_DEP_TRUE);
4704 else
4706 FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4707 add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4708 REG_DEP_ANTI);
4710 return true;
4712 next:
4713 sd_iterator_next (&sd_it);
4715 return false;
4718 /* A recursive function that walks ADDRESS_OF_X to find memory references
4719 which could be modified during scheduling. We call find_inc for each
4720 one we find that has a recognizable form. MII holds information about
4721 the pair of memory/increment instructions.
4722 We ensure that every instruction with a memory reference (which will be
4723 the location of the replacement) is assigned at most one breakable
4724 dependency. */
4726 static bool
4727 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4729 rtx x = *address_of_x;
4730 enum rtx_code code = GET_CODE (x);
4731 const char *const fmt = GET_RTX_FORMAT (code);
4732 int i;
4734 if (code == MEM)
4736 rtx reg0 = XEXP (x, 0);
4738 mii->mem_loc = address_of_x;
4739 mii->mem_index = NULL_RTX;
4740 mii->mem_constant = 0;
4741 if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4743 mii->mem_constant = INTVAL (XEXP (reg0, 1));
4744 reg0 = XEXP (reg0, 0);
4746 if (GET_CODE (reg0) == PLUS)
4748 mii->mem_index = XEXP (reg0, 1);
4749 reg0 = XEXP (reg0, 0);
4751 if (REG_P (reg0))
4753 df_ref *def_rec;
4754 int occurrences = 0;
4756 /* Make sure this reg appears only once in this insn. Can't use
4757 count_occurrences since that only works for pseudos. */
4758 for (def_rec = DF_INSN_USES (mii->mem_insn); *def_rec; def_rec++)
4760 df_ref def = *def_rec;
4761 if (reg_overlap_mentioned_p (reg0, DF_REF_REG (def)))
4762 if (++occurrences > 1)
4764 if (sched_verbose >= 5)
4765 fprintf (sched_dump, "mem count failure\n");
4766 return false;
4770 mii->mem_reg0 = reg0;
4771 return find_inc (mii, true) || find_inc (mii, false);
4773 return false;
4776 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4778 /* If REG occurs inside a MEM used in a bit-field reference,
4779 that is unacceptable. */
4780 return false;
4783 /* Time for some deep diving. */
4784 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4786 if (fmt[i] == 'e')
4788 if (find_mem (mii, &XEXP (x, i)))
4789 return true;
4791 else if (fmt[i] == 'E')
4793 int j;
4794 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4795 if (find_mem (mii, &XVECEXP (x, i, j)))
4796 return true;
4799 return false;
4803 /* Examine the instructions between HEAD and TAIL and try to find
4804 dependencies that can be broken by modifying one of the patterns. */
4806 void
4807 find_modifiable_mems (rtx head, rtx tail)
4809 rtx insn, next_tail = NEXT_INSN (tail);
4810 int success_in_block = 0;
4812 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4814 struct mem_inc_info mii;
4816 if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4817 continue;
4819 mii.mem_insn = insn;
4820 if (find_mem (&mii, &PATTERN (insn)))
4821 success_in_block++;
4823 if (success_in_block && sched_verbose >= 5)
4824 fprintf (sched_dump, "%d candidates for address modification found.\n",
4825 success_in_block);
4828 #endif /* INSN_SCHEDULING */