Daily bump.
[official-gcc.git] / gcc / sched-deps.c
blobb2393bf28fb5ff9d0a006bd18127262d13f17a16
1 /* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992-2017 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "backend.h"
27 #include "target.h"
28 #include "rtl.h"
29 #include "tree.h"
30 #include "df.h"
31 #include "insn-config.h"
32 #include "regs.h"
33 #include "memmodel.h"
34 #include "ira.h"
35 #include "ira-int.h"
36 #include "insn-attr.h"
37 #include "cfgbuild.h"
38 #include "sched-int.h"
39 #include "params.h"
40 #include "cselib.h"
42 #ifdef INSN_SCHEDULING
44 /* Holds current parameters for the dependency analyzer. */
45 struct sched_deps_info_def *sched_deps_info;
47 /* The data is specific to the Haifa scheduler. */
48 vec<haifa_deps_insn_data_def>
49 h_d_i_d = vNULL;
51 /* Return the major type present in the DS. */
52 enum reg_note
53 ds_to_dk (ds_t ds)
55 if (ds & DEP_TRUE)
56 return REG_DEP_TRUE;
58 if (ds & DEP_OUTPUT)
59 return REG_DEP_OUTPUT;
61 if (ds & DEP_CONTROL)
62 return REG_DEP_CONTROL;
64 gcc_assert (ds & DEP_ANTI);
66 return REG_DEP_ANTI;
69 /* Return equivalent dep_status. */
70 ds_t
71 dk_to_ds (enum reg_note dk)
73 switch (dk)
75 case REG_DEP_TRUE:
76 return DEP_TRUE;
78 case REG_DEP_OUTPUT:
79 return DEP_OUTPUT;
81 case REG_DEP_CONTROL:
82 return DEP_CONTROL;
84 default:
85 gcc_assert (dk == REG_DEP_ANTI);
86 return DEP_ANTI;
90 /* Functions to operate with dependence information container - dep_t. */
92 /* Init DEP with the arguments. */
93 void
94 init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
96 DEP_PRO (dep) = pro;
97 DEP_CON (dep) = con;
98 DEP_TYPE (dep) = type;
99 DEP_STATUS (dep) = ds;
100 DEP_COST (dep) = UNKNOWN_DEP_COST;
101 DEP_NONREG (dep) = 0;
102 DEP_MULTIPLE (dep) = 0;
103 DEP_REPLACE (dep) = NULL;
106 /* Init DEP with the arguments.
107 While most of the scheduler (including targets) only need the major type
108 of the dependency, it is convenient to hide full dep_status from them. */
109 void
110 init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
112 ds_t ds;
114 if ((current_sched_info->flags & USE_DEPS_LIST))
115 ds = dk_to_ds (kind);
116 else
117 ds = 0;
119 init_dep_1 (dep, pro, con, kind, ds);
122 /* Make a copy of FROM in TO. */
123 static void
124 copy_dep (dep_t to, dep_t from)
126 memcpy (to, from, sizeof (*to));
129 static void dump_ds (FILE *, ds_t);
131 /* Define flags for dump_dep (). */
133 /* Dump producer of the dependence. */
134 #define DUMP_DEP_PRO (2)
136 /* Dump consumer of the dependence. */
137 #define DUMP_DEP_CON (4)
139 /* Dump type of the dependence. */
140 #define DUMP_DEP_TYPE (8)
142 /* Dump status of the dependence. */
143 #define DUMP_DEP_STATUS (16)
145 /* Dump all information about the dependence. */
146 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
147 |DUMP_DEP_STATUS)
149 /* Dump DEP to DUMP.
150 FLAGS is a bit mask specifying what information about DEP needs
151 to be printed.
152 If FLAGS has the very first bit set, then dump all information about DEP
153 and propagate this bit into the callee dump functions. */
154 static void
155 dump_dep (FILE *dump, dep_t dep, int flags)
157 if (flags & 1)
158 flags |= DUMP_DEP_ALL;
160 fprintf (dump, "<");
162 if (flags & DUMP_DEP_PRO)
163 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
165 if (flags & DUMP_DEP_CON)
166 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
168 if (flags & DUMP_DEP_TYPE)
170 char t;
171 enum reg_note type = DEP_TYPE (dep);
173 switch (type)
175 case REG_DEP_TRUE:
176 t = 't';
177 break;
179 case REG_DEP_OUTPUT:
180 t = 'o';
181 break;
183 case REG_DEP_CONTROL:
184 t = 'c';
185 break;
187 case REG_DEP_ANTI:
188 t = 'a';
189 break;
191 default:
192 gcc_unreachable ();
193 break;
196 fprintf (dump, "%c; ", t);
199 if (flags & DUMP_DEP_STATUS)
201 if (current_sched_info->flags & USE_DEPS_LIST)
202 dump_ds (dump, DEP_STATUS (dep));
205 fprintf (dump, ">");
208 /* Default flags for dump_dep (). */
209 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
211 /* Dump all fields of DEP to STDERR. */
212 void
213 sd_debug_dep (dep_t dep)
215 dump_dep (stderr, dep, 1);
216 fprintf (stderr, "\n");
219 /* Determine whether DEP is a dependency link of a non-debug insn on a
220 debug insn. */
222 static inline bool
223 depl_on_debug_p (dep_link_t dep)
225 return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
226 && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
229 /* Functions to operate with a single link from the dependencies lists -
230 dep_link_t. */
232 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
233 PREV_NEXT_P. */
234 static void
235 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
237 dep_link_t next = *prev_nextp;
239 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
240 && DEP_LINK_NEXT (l) == NULL);
242 /* Init node being inserted. */
243 DEP_LINK_PREV_NEXTP (l) = prev_nextp;
244 DEP_LINK_NEXT (l) = next;
246 /* Fix next node. */
247 if (next != NULL)
249 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
251 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
254 /* Fix prev node. */
255 *prev_nextp = l;
258 /* Add dep_link LINK to deps_list L. */
259 static void
260 add_to_deps_list (dep_link_t link, deps_list_t l)
262 attach_dep_link (link, &DEPS_LIST_FIRST (l));
264 /* Don't count debug deps. */
265 if (!depl_on_debug_p (link))
266 ++DEPS_LIST_N_LINKS (l);
269 /* Detach dep_link L from the list. */
270 static void
271 detach_dep_link (dep_link_t l)
273 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
274 dep_link_t next = DEP_LINK_NEXT (l);
276 *prev_nextp = next;
278 if (next != NULL)
279 DEP_LINK_PREV_NEXTP (next) = prev_nextp;
281 DEP_LINK_PREV_NEXTP (l) = NULL;
282 DEP_LINK_NEXT (l) = NULL;
285 /* Remove link LINK from list LIST. */
286 static void
287 remove_from_deps_list (dep_link_t link, deps_list_t list)
289 detach_dep_link (link);
291 /* Don't count debug deps. */
292 if (!depl_on_debug_p (link))
293 --DEPS_LIST_N_LINKS (list);
296 /* Move link LINK from list FROM to list TO. */
297 static void
298 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
300 remove_from_deps_list (link, from);
301 add_to_deps_list (link, to);
304 /* Return true of LINK is not attached to any list. */
305 static bool
306 dep_link_is_detached_p (dep_link_t link)
308 return DEP_LINK_PREV_NEXTP (link) == NULL;
311 /* Pool to hold all dependency nodes (dep_node_t). */
312 static object_allocator<_dep_node> *dn_pool;
314 /* Number of dep_nodes out there. */
315 static int dn_pool_diff = 0;
317 /* Create a dep_node. */
318 static dep_node_t
319 create_dep_node (void)
321 dep_node_t n = dn_pool->allocate ();
322 dep_link_t back = DEP_NODE_BACK (n);
323 dep_link_t forw = DEP_NODE_FORW (n);
325 DEP_LINK_NODE (back) = n;
326 DEP_LINK_NEXT (back) = NULL;
327 DEP_LINK_PREV_NEXTP (back) = NULL;
329 DEP_LINK_NODE (forw) = n;
330 DEP_LINK_NEXT (forw) = NULL;
331 DEP_LINK_PREV_NEXTP (forw) = NULL;
333 ++dn_pool_diff;
335 return n;
338 /* Delete dep_node N. N must not be connected to any deps_list. */
339 static void
340 delete_dep_node (dep_node_t n)
342 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
343 && dep_link_is_detached_p (DEP_NODE_FORW (n)));
345 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
347 --dn_pool_diff;
349 dn_pool->remove (n);
352 /* Pool to hold dependencies lists (deps_list_t). */
353 static object_allocator<_deps_list> *dl_pool;
355 /* Number of deps_lists out there. */
356 static int dl_pool_diff = 0;
358 /* Functions to operate with dependences lists - deps_list_t. */
360 /* Return true if list L is empty. */
361 static bool
362 deps_list_empty_p (deps_list_t l)
364 return DEPS_LIST_N_LINKS (l) == 0;
367 /* Create a new deps_list. */
368 static deps_list_t
369 create_deps_list (void)
371 deps_list_t l = dl_pool->allocate ();
373 DEPS_LIST_FIRST (l) = NULL;
374 DEPS_LIST_N_LINKS (l) = 0;
376 ++dl_pool_diff;
377 return l;
380 /* Free deps_list L. */
381 static void
382 free_deps_list (deps_list_t l)
384 gcc_assert (deps_list_empty_p (l));
386 --dl_pool_diff;
388 dl_pool->remove (l);
391 /* Return true if there is no dep_nodes and deps_lists out there.
392 After the region is scheduled all the dependency nodes and lists
393 should [generally] be returned to pool. */
394 bool
395 deps_pools_are_empty_p (void)
397 return dn_pool_diff == 0 && dl_pool_diff == 0;
400 /* Remove all elements from L. */
401 static void
402 clear_deps_list (deps_list_t l)
406 dep_link_t link = DEPS_LIST_FIRST (l);
408 if (link == NULL)
409 break;
411 remove_from_deps_list (link, l);
413 while (1);
416 /* Decide whether a dependency should be treated as a hard or a speculative
417 dependency. */
418 static bool
419 dep_spec_p (dep_t dep)
421 if (current_sched_info->flags & DO_SPECULATION)
423 if (DEP_STATUS (dep) & SPECULATIVE)
424 return true;
426 if (current_sched_info->flags & DO_PREDICATION)
428 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
429 return true;
431 if (DEP_REPLACE (dep) != NULL)
432 return true;
433 return false;
436 static regset reg_pending_sets;
437 static regset reg_pending_clobbers;
438 static regset reg_pending_uses;
439 static regset reg_pending_control_uses;
440 static enum reg_pending_barrier_mode reg_pending_barrier;
442 /* Hard registers implicitly clobbered or used (or may be implicitly
443 clobbered or used) by the currently analyzed insn. For example,
444 insn in its constraint has one register class. Even if there is
445 currently no hard register in the insn, the particular hard
446 register will be in the insn after reload pass because the
447 constraint requires it. */
448 static HARD_REG_SET implicit_reg_pending_clobbers;
449 static HARD_REG_SET implicit_reg_pending_uses;
451 /* To speed up the test for duplicate dependency links we keep a
452 record of dependencies created by add_dependence when the average
453 number of instructions in a basic block is very large.
455 Studies have shown that there is typically around 5 instructions between
456 branches for typical C code. So we can make a guess that the average
457 basic block is approximately 5 instructions long; we will choose 100X
458 the average size as a very large basic block.
460 Each insn has associated bitmaps for its dependencies. Each bitmap
461 has enough entries to represent a dependency on any other insn in
462 the insn chain. All bitmap for true dependencies cache is
463 allocated then the rest two ones are also allocated. */
464 static bitmap_head *true_dependency_cache = NULL;
465 static bitmap_head *output_dependency_cache = NULL;
466 static bitmap_head *anti_dependency_cache = NULL;
467 static bitmap_head *control_dependency_cache = NULL;
468 static bitmap_head *spec_dependency_cache = NULL;
469 static int cache_size;
471 /* True if we should mark added dependencies as a non-register deps. */
472 static bool mark_as_hard;
474 static int deps_may_trap_p (const_rtx);
475 static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note);
476 static void add_dependence_list (rtx_insn *, rtx_insn_list *, int,
477 enum reg_note, bool);
478 static void add_dependence_list_and_free (struct deps_desc *, rtx_insn *,
479 rtx_insn_list **, int, enum reg_note,
480 bool);
481 static void delete_all_dependences (rtx_insn *);
482 static void chain_to_prev_insn (rtx_insn *);
484 static void flush_pending_lists (struct deps_desc *, rtx_insn *, int, int);
485 static void sched_analyze_1 (struct deps_desc *, rtx, rtx_insn *);
486 static void sched_analyze_2 (struct deps_desc *, rtx, rtx_insn *);
487 static void sched_analyze_insn (struct deps_desc *, rtx, rtx_insn *);
489 static bool sched_has_condition_p (const rtx_insn *);
490 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
492 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
493 rtx, rtx);
494 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
496 static void check_dep (dep_t, bool);
499 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
501 static int
502 deps_may_trap_p (const_rtx mem)
504 const_rtx addr = XEXP (mem, 0);
506 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
508 const_rtx t = get_reg_known_value (REGNO (addr));
509 if (t)
510 addr = t;
512 return rtx_addr_can_trap_p (addr);
516 /* Find the condition under which INSN is executed. If REV is not NULL,
517 it is set to TRUE when the returned comparison should be reversed
518 to get the actual condition. */
519 static rtx
520 sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
522 rtx pat = PATTERN (insn);
523 rtx src;
525 if (rev)
526 *rev = false;
528 if (GET_CODE (pat) == COND_EXEC)
529 return COND_EXEC_TEST (pat);
531 if (!any_condjump_p (insn) || !onlyjump_p (insn))
532 return 0;
534 src = SET_SRC (pc_set (insn));
536 if (XEXP (src, 2) == pc_rtx)
537 return XEXP (src, 0);
538 else if (XEXP (src, 1) == pc_rtx)
540 rtx cond = XEXP (src, 0);
541 enum rtx_code revcode = reversed_comparison_code (cond, insn);
543 if (revcode == UNKNOWN)
544 return 0;
546 if (rev)
547 *rev = true;
548 return cond;
551 return 0;
554 /* Return the condition under which INSN does not execute (i.e. the
555 not-taken condition for a conditional branch), or NULL if we cannot
556 find such a condition. The caller should make a copy of the condition
557 before using it. */
559 sched_get_reverse_condition_uncached (const rtx_insn *insn)
561 bool rev;
562 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
563 if (cond == NULL_RTX)
564 return cond;
565 if (!rev)
567 enum rtx_code revcode = reversed_comparison_code (cond, insn);
568 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
569 XEXP (cond, 0),
570 XEXP (cond, 1));
572 return cond;
575 /* Caching variant of sched_get_condition_with_rev_uncached.
576 We only do actual work the first time we come here for an insn; the
577 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
578 static rtx
579 sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
581 bool tmp;
583 if (INSN_LUID (insn) == 0)
584 return sched_get_condition_with_rev_uncached (insn, rev);
586 if (INSN_CACHED_COND (insn) == const_true_rtx)
587 return NULL_RTX;
589 if (INSN_CACHED_COND (insn) != NULL_RTX)
591 if (rev)
592 *rev = INSN_REVERSE_COND (insn);
593 return INSN_CACHED_COND (insn);
596 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
597 INSN_REVERSE_COND (insn) = tmp;
599 if (INSN_CACHED_COND (insn) == NULL_RTX)
601 INSN_CACHED_COND (insn) = const_true_rtx;
602 return NULL_RTX;
605 if (rev)
606 *rev = INSN_REVERSE_COND (insn);
607 return INSN_CACHED_COND (insn);
610 /* True when we can find a condition under which INSN is executed. */
611 static bool
612 sched_has_condition_p (const rtx_insn *insn)
614 return !! sched_get_condition_with_rev (insn, NULL);
619 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
620 static int
621 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
623 if (COMPARISON_P (cond1)
624 && COMPARISON_P (cond2)
625 && GET_CODE (cond1) ==
626 (rev1==rev2
627 ? reversed_comparison_code (cond2, NULL)
628 : GET_CODE (cond2))
629 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
630 && XEXP (cond1, 1) == XEXP (cond2, 1))
631 return 1;
632 return 0;
635 /* Return true if insn1 and insn2 can never depend on one another because
636 the conditions under which they are executed are mutually exclusive. */
637 bool
638 sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
640 rtx cond1, cond2;
641 bool rev1 = false, rev2 = false;
643 /* df doesn't handle conditional lifetimes entirely correctly;
644 calls mess up the conditional lifetimes. */
645 if (!CALL_P (insn1) && !CALL_P (insn2))
647 cond1 = sched_get_condition_with_rev (insn1, &rev1);
648 cond2 = sched_get_condition_with_rev (insn2, &rev2);
649 if (cond1 && cond2
650 && conditions_mutex_p (cond1, cond2, rev1, rev2)
651 /* Make sure first instruction doesn't affect condition of second
652 instruction if switched. */
653 && !modified_in_p (cond1, insn2)
654 /* Make sure second instruction doesn't affect condition of first
655 instruction if switched. */
656 && !modified_in_p (cond2, insn1))
657 return true;
659 return false;
663 /* Return true if INSN can potentially be speculated with type DS. */
664 bool
665 sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
667 if (HAS_INTERNAL_DEP (insn))
668 return false;
670 if (!NONJUMP_INSN_P (insn))
671 return false;
673 if (SCHED_GROUP_P (insn))
674 return false;
676 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn)))
677 return false;
679 if (side_effects_p (PATTERN (insn)))
680 return false;
682 if (ds & BE_IN_SPEC)
683 /* The following instructions, which depend on a speculatively scheduled
684 instruction, cannot be speculatively scheduled along. */
686 if (may_trap_or_fault_p (PATTERN (insn)))
687 /* If instruction might fault, it cannot be speculatively scheduled.
688 For control speculation it's obvious why and for data speculation
689 it's because the insn might get wrong input if speculation
690 wasn't successful. */
691 return false;
693 if ((ds & BE_IN_DATA)
694 && sched_has_condition_p (insn))
695 /* If this is a predicated instruction, then it cannot be
696 speculatively scheduled. See PR35659. */
697 return false;
700 return true;
703 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
704 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
705 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
706 This function is used to switch sd_iterator to the next list.
707 !!! For internal use only. Might consider moving it to sched-int.h. */
708 void
709 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
710 deps_list_t *list_ptr, bool *resolved_p_ptr)
712 sd_list_types_def types = *types_ptr;
714 if (types & SD_LIST_HARD_BACK)
716 *list_ptr = INSN_HARD_BACK_DEPS (insn);
717 *resolved_p_ptr = false;
718 *types_ptr = types & ~SD_LIST_HARD_BACK;
720 else if (types & SD_LIST_SPEC_BACK)
722 *list_ptr = INSN_SPEC_BACK_DEPS (insn);
723 *resolved_p_ptr = false;
724 *types_ptr = types & ~SD_LIST_SPEC_BACK;
726 else if (types & SD_LIST_FORW)
728 *list_ptr = INSN_FORW_DEPS (insn);
729 *resolved_p_ptr = false;
730 *types_ptr = types & ~SD_LIST_FORW;
732 else if (types & SD_LIST_RES_BACK)
734 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
735 *resolved_p_ptr = true;
736 *types_ptr = types & ~SD_LIST_RES_BACK;
738 else if (types & SD_LIST_RES_FORW)
740 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
741 *resolved_p_ptr = true;
742 *types_ptr = types & ~SD_LIST_RES_FORW;
744 else
746 *list_ptr = NULL;
747 *resolved_p_ptr = false;
748 *types_ptr = SD_LIST_NONE;
752 /* Return the summary size of INSN's lists defined by LIST_TYPES. */
754 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
756 int size = 0;
758 while (list_types != SD_LIST_NONE)
760 deps_list_t list;
761 bool resolved_p;
763 sd_next_list (insn, &list_types, &list, &resolved_p);
764 if (list)
765 size += DEPS_LIST_N_LINKS (list);
768 return size;
771 /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
773 bool
774 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
776 while (list_types != SD_LIST_NONE)
778 deps_list_t list;
779 bool resolved_p;
781 sd_next_list (insn, &list_types, &list, &resolved_p);
782 if (!deps_list_empty_p (list))
783 return false;
786 return true;
789 /* Initialize data for INSN. */
790 void
791 sd_init_insn (rtx_insn *insn)
793 INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
794 INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
795 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
796 INSN_FORW_DEPS (insn) = create_deps_list ();
797 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
799 /* ??? It would be nice to allocate dependency caches here. */
802 /* Free data for INSN. */
803 void
804 sd_finish_insn (rtx_insn *insn)
806 /* ??? It would be nice to deallocate dependency caches here. */
808 free_deps_list (INSN_HARD_BACK_DEPS (insn));
809 INSN_HARD_BACK_DEPS (insn) = NULL;
811 free_deps_list (INSN_SPEC_BACK_DEPS (insn));
812 INSN_SPEC_BACK_DEPS (insn) = NULL;
814 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
815 INSN_RESOLVED_BACK_DEPS (insn) = NULL;
817 free_deps_list (INSN_FORW_DEPS (insn));
818 INSN_FORW_DEPS (insn) = NULL;
820 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
821 INSN_RESOLVED_FORW_DEPS (insn) = NULL;
824 /* Find a dependency between producer PRO and consumer CON.
825 Search through resolved dependency lists if RESOLVED_P is true.
826 If no such dependency is found return NULL,
827 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
828 with an iterator pointing to it. */
829 static dep_t
830 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
831 sd_iterator_def *sd_it_ptr)
833 sd_list_types_def pro_list_type;
834 sd_list_types_def con_list_type;
835 sd_iterator_def sd_it;
836 dep_t dep;
837 bool found_p = false;
839 if (resolved_p)
841 pro_list_type = SD_LIST_RES_FORW;
842 con_list_type = SD_LIST_RES_BACK;
844 else
846 pro_list_type = SD_LIST_FORW;
847 con_list_type = SD_LIST_BACK;
850 /* Walk through either back list of INSN or forw list of ELEM
851 depending on which one is shorter. */
852 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
854 /* Find the dep_link with producer PRO in consumer's back_deps. */
855 FOR_EACH_DEP (con, con_list_type, sd_it, dep)
856 if (DEP_PRO (dep) == pro)
858 found_p = true;
859 break;
862 else
864 /* Find the dep_link with consumer CON in producer's forw_deps. */
865 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
866 if (DEP_CON (dep) == con)
868 found_p = true;
869 break;
873 if (found_p)
875 if (sd_it_ptr != NULL)
876 *sd_it_ptr = sd_it;
878 return dep;
881 return NULL;
884 /* Find a dependency between producer PRO and consumer CON.
885 Use dependency [if available] to check if dependency is present at all.
886 Search through resolved dependency lists if RESOLVED_P is true.
887 If the dependency or NULL if none found. */
888 dep_t
889 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
891 if (true_dependency_cache != NULL)
892 /* Avoiding the list walk below can cut compile times dramatically
893 for some code. */
895 int elem_luid = INSN_LUID (pro);
896 int insn_luid = INSN_LUID (con);
898 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
899 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
900 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
901 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
902 return NULL;
905 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
908 /* Add or update a dependence described by DEP.
909 MEM1 and MEM2, if non-null, correspond to memory locations in case of
910 data speculation.
912 The function returns a value indicating if an old entry has been changed
913 or a new entry has been added to insn's backward deps.
915 This function merely checks if producer and consumer is the same insn
916 and doesn't create a dep in this case. Actual manipulation of
917 dependence data structures is performed in add_or_update_dep_1. */
918 static enum DEPS_ADJUST_RESULT
919 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
921 rtx_insn *elem = DEP_PRO (dep);
922 rtx_insn *insn = DEP_CON (dep);
924 gcc_assert (INSN_P (insn) && INSN_P (elem));
926 /* Don't depend an insn on itself. */
927 if (insn == elem)
929 if (sched_deps_info->generate_spec_deps)
930 /* INSN has an internal dependence, which we can't overcome. */
931 HAS_INTERNAL_DEP (insn) = 1;
933 return DEP_NODEP;
936 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
939 /* Ask dependency caches what needs to be done for dependence DEP.
940 Return DEP_CREATED if new dependence should be created and there is no
941 need to try to find one searching the dependencies lists.
942 Return DEP_PRESENT if there already is a dependence described by DEP and
943 hence nothing is to be done.
944 Return DEP_CHANGED if there already is a dependence, but it should be
945 updated to incorporate additional information from DEP. */
946 static enum DEPS_ADJUST_RESULT
947 ask_dependency_caches (dep_t dep)
949 int elem_luid = INSN_LUID (DEP_PRO (dep));
950 int insn_luid = INSN_LUID (DEP_CON (dep));
952 gcc_assert (true_dependency_cache != NULL
953 && output_dependency_cache != NULL
954 && anti_dependency_cache != NULL
955 && control_dependency_cache != NULL);
957 if (!(current_sched_info->flags & USE_DEPS_LIST))
959 enum reg_note present_dep_type;
961 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
962 present_dep_type = REG_DEP_TRUE;
963 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
964 present_dep_type = REG_DEP_OUTPUT;
965 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
966 present_dep_type = REG_DEP_ANTI;
967 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
968 present_dep_type = REG_DEP_CONTROL;
969 else
970 /* There is no existing dep so it should be created. */
971 return DEP_CREATED;
973 if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
974 /* DEP does not add anything to the existing dependence. */
975 return DEP_PRESENT;
977 else
979 ds_t present_dep_types = 0;
981 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
982 present_dep_types |= DEP_TRUE;
983 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
984 present_dep_types |= DEP_OUTPUT;
985 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
986 present_dep_types |= DEP_ANTI;
987 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
988 present_dep_types |= DEP_CONTROL;
990 if (present_dep_types == 0)
991 /* There is no existing dep so it should be created. */
992 return DEP_CREATED;
994 if (!(current_sched_info->flags & DO_SPECULATION)
995 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
997 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
998 == present_dep_types)
999 /* DEP does not add anything to the existing dependence. */
1000 return DEP_PRESENT;
1002 else
1004 /* Only true dependencies can be data speculative and
1005 only anti dependencies can be control speculative. */
1006 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1007 == present_dep_types);
1009 /* if (DEP is SPECULATIVE) then
1010 ..we should update DEP_STATUS
1011 else
1012 ..we should reset existing dep to non-speculative. */
1016 return DEP_CHANGED;
1019 /* Set dependency caches according to DEP. */
1020 static void
1021 set_dependency_caches (dep_t dep)
1023 int elem_luid = INSN_LUID (DEP_PRO (dep));
1024 int insn_luid = INSN_LUID (DEP_CON (dep));
1026 if (!(current_sched_info->flags & USE_DEPS_LIST))
1028 switch (DEP_TYPE (dep))
1030 case REG_DEP_TRUE:
1031 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1032 break;
1034 case REG_DEP_OUTPUT:
1035 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1036 break;
1038 case REG_DEP_ANTI:
1039 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1040 break;
1042 case REG_DEP_CONTROL:
1043 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1044 break;
1046 default:
1047 gcc_unreachable ();
1050 else
1052 ds_t ds = DEP_STATUS (dep);
1054 if (ds & DEP_TRUE)
1055 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1056 if (ds & DEP_OUTPUT)
1057 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1058 if (ds & DEP_ANTI)
1059 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1060 if (ds & DEP_CONTROL)
1061 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1063 if (ds & SPECULATIVE)
1065 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1066 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1071 /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1072 caches accordingly. */
1073 static void
1074 update_dependency_caches (dep_t dep, enum reg_note old_type)
1076 int elem_luid = INSN_LUID (DEP_PRO (dep));
1077 int insn_luid = INSN_LUID (DEP_CON (dep));
1079 /* Clear corresponding cache entry because type of the link
1080 may have changed. Keep them if we use_deps_list. */
1081 if (!(current_sched_info->flags & USE_DEPS_LIST))
1083 switch (old_type)
1085 case REG_DEP_OUTPUT:
1086 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1087 break;
1089 case REG_DEP_ANTI:
1090 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1091 break;
1093 case REG_DEP_CONTROL:
1094 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1095 break;
1097 default:
1098 gcc_unreachable ();
1102 set_dependency_caches (dep);
1105 /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1106 static void
1107 change_spec_dep_to_hard (sd_iterator_def sd_it)
1109 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1110 dep_link_t link = DEP_NODE_BACK (node);
1111 dep_t dep = DEP_NODE_DEP (node);
1112 rtx_insn *elem = DEP_PRO (dep);
1113 rtx_insn *insn = DEP_CON (dep);
1115 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1117 DEP_STATUS (dep) &= ~SPECULATIVE;
1119 if (true_dependency_cache != NULL)
1120 /* Clear the cache entry. */
1121 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1122 INSN_LUID (elem));
1125 /* Update DEP to incorporate information from NEW_DEP.
1126 SD_IT points to DEP in case it should be moved to another list.
1127 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1128 data-speculative dependence should be updated. */
1129 static enum DEPS_ADJUST_RESULT
1130 update_dep (dep_t dep, dep_t new_dep,
1131 sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1132 rtx mem1 ATTRIBUTE_UNUSED,
1133 rtx mem2 ATTRIBUTE_UNUSED)
1135 enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1136 enum reg_note old_type = DEP_TYPE (dep);
1137 bool was_spec = dep_spec_p (dep);
1139 DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1140 DEP_MULTIPLE (dep) = 1;
1142 /* If this is a more restrictive type of dependence than the
1143 existing one, then change the existing dependence to this
1144 type. */
1145 if ((int) DEP_TYPE (new_dep) < (int) old_type)
1147 DEP_TYPE (dep) = DEP_TYPE (new_dep);
1148 res = DEP_CHANGED;
1151 if (current_sched_info->flags & USE_DEPS_LIST)
1152 /* Update DEP_STATUS. */
1154 ds_t dep_status = DEP_STATUS (dep);
1155 ds_t ds = DEP_STATUS (new_dep);
1156 ds_t new_status = ds | dep_status;
1158 if (new_status & SPECULATIVE)
1160 /* Either existing dep or a dep we're adding or both are
1161 speculative. */
1162 if (!(ds & SPECULATIVE)
1163 || !(dep_status & SPECULATIVE))
1164 /* The new dep can't be speculative. */
1165 new_status &= ~SPECULATIVE;
1166 else
1168 /* Both are speculative. Merge probabilities. */
1169 if (mem1 != NULL)
1171 dw_t dw;
1173 dw = estimate_dep_weak (mem1, mem2);
1174 ds = set_dep_weak (ds, BEGIN_DATA, dw);
1177 new_status = ds_merge (dep_status, ds);
1181 ds = new_status;
1183 if (dep_status != ds)
1185 DEP_STATUS (dep) = ds;
1186 res = DEP_CHANGED;
1190 if (was_spec && !dep_spec_p (dep))
1191 /* The old dep was speculative, but now it isn't. */
1192 change_spec_dep_to_hard (sd_it);
1194 if (true_dependency_cache != NULL
1195 && res == DEP_CHANGED)
1196 update_dependency_caches (dep, old_type);
1198 return res;
1201 /* Add or update a dependence described by DEP.
1202 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1203 data speculation.
1205 The function returns a value indicating if an old entry has been changed
1206 or a new entry has been added to insn's backward deps or nothing has
1207 been updated at all. */
1208 static enum DEPS_ADJUST_RESULT
1209 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1210 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1212 bool maybe_present_p = true;
1213 bool present_p = false;
1215 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1216 && DEP_PRO (new_dep) != DEP_CON (new_dep));
1218 if (flag_checking)
1219 check_dep (new_dep, mem1 != NULL);
1221 if (true_dependency_cache != NULL)
1223 switch (ask_dependency_caches (new_dep))
1225 case DEP_PRESENT:
1226 dep_t present_dep;
1227 sd_iterator_def sd_it;
1229 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1230 DEP_CON (new_dep),
1231 resolved_p, &sd_it);
1232 DEP_MULTIPLE (present_dep) = 1;
1233 return DEP_PRESENT;
1235 case DEP_CHANGED:
1236 maybe_present_p = true;
1237 present_p = true;
1238 break;
1240 case DEP_CREATED:
1241 maybe_present_p = false;
1242 present_p = false;
1243 break;
1245 default:
1246 gcc_unreachable ();
1247 break;
1251 /* Check that we don't already have this dependence. */
1252 if (maybe_present_p)
1254 dep_t present_dep;
1255 sd_iterator_def sd_it;
1257 gcc_assert (true_dependency_cache == NULL || present_p);
1259 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1260 DEP_CON (new_dep),
1261 resolved_p, &sd_it);
1263 if (present_dep != NULL)
1264 /* We found an existing dependency between ELEM and INSN. */
1265 return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1266 else
1267 /* We didn't find a dep, it shouldn't present in the cache. */
1268 gcc_assert (!present_p);
1271 /* Might want to check one level of transitivity to save conses.
1272 This check should be done in maybe_add_or_update_dep_1.
1273 Since we made it to add_or_update_dep_1, we must create
1274 (or update) a link. */
1276 if (mem1 != NULL_RTX)
1278 gcc_assert (sched_deps_info->generate_spec_deps);
1279 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1280 estimate_dep_weak (mem1, mem2));
1283 sd_add_dep (new_dep, resolved_p);
1285 return DEP_CREATED;
1288 /* Initialize BACK_LIST_PTR with consumer's backward list and
1289 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1290 initialize with lists that hold resolved deps. */
1291 static void
1292 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1293 deps_list_t *back_list_ptr,
1294 deps_list_t *forw_list_ptr)
1296 rtx_insn *con = DEP_CON (dep);
1298 if (!resolved_p)
1300 if (dep_spec_p (dep))
1301 *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1302 else
1303 *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1305 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1307 else
1309 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1310 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1314 /* Add dependence described by DEP.
1315 If RESOLVED_P is true treat the dependence as a resolved one. */
1316 void
1317 sd_add_dep (dep_t dep, bool resolved_p)
1319 dep_node_t n = create_dep_node ();
1320 deps_list_t con_back_deps;
1321 deps_list_t pro_forw_deps;
1322 rtx_insn *elem = DEP_PRO (dep);
1323 rtx_insn *insn = DEP_CON (dep);
1325 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1327 if ((current_sched_info->flags & DO_SPECULATION) == 0
1328 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1329 DEP_STATUS (dep) &= ~SPECULATIVE;
1331 copy_dep (DEP_NODE_DEP (n), dep);
1333 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1335 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1337 if (flag_checking)
1338 check_dep (dep, false);
1340 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1342 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1343 in the bitmap caches of dependency information. */
1344 if (true_dependency_cache != NULL)
1345 set_dependency_caches (dep);
1348 /* Add or update backward dependence between INSN and ELEM
1349 with given type DEP_TYPE and dep_status DS.
1350 This function is a convenience wrapper. */
1351 enum DEPS_ADJUST_RESULT
1352 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1354 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1357 /* Resolved dependence pointed to by SD_IT.
1358 SD_IT will advance to the next element. */
1359 void
1360 sd_resolve_dep (sd_iterator_def sd_it)
1362 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1363 dep_t dep = DEP_NODE_DEP (node);
1364 rtx_insn *pro = DEP_PRO (dep);
1365 rtx_insn *con = DEP_CON (dep);
1367 if (dep_spec_p (dep))
1368 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1369 INSN_RESOLVED_BACK_DEPS (con));
1370 else
1371 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1372 INSN_RESOLVED_BACK_DEPS (con));
1374 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1375 INSN_RESOLVED_FORW_DEPS (pro));
1378 /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1379 pointed to by SD_IT to unresolved state. */
1380 void
1381 sd_unresolve_dep (sd_iterator_def sd_it)
1383 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1384 dep_t dep = DEP_NODE_DEP (node);
1385 rtx_insn *pro = DEP_PRO (dep);
1386 rtx_insn *con = DEP_CON (dep);
1388 if (dep_spec_p (dep))
1389 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1390 INSN_SPEC_BACK_DEPS (con));
1391 else
1392 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1393 INSN_HARD_BACK_DEPS (con));
1395 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1396 INSN_FORW_DEPS (pro));
1399 /* Make TO depend on all the FROM's producers.
1400 If RESOLVED_P is true add dependencies to the resolved lists. */
1401 void
1402 sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p)
1404 sd_list_types_def list_type;
1405 sd_iterator_def sd_it;
1406 dep_t dep;
1408 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1410 FOR_EACH_DEP (from, list_type, sd_it, dep)
1412 dep_def _new_dep, *new_dep = &_new_dep;
1414 copy_dep (new_dep, dep);
1415 DEP_CON (new_dep) = to;
1416 sd_add_dep (new_dep, resolved_p);
1420 /* Remove a dependency referred to by SD_IT.
1421 SD_IT will point to the next dependence after removal. */
1422 void
1423 sd_delete_dep (sd_iterator_def sd_it)
1425 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1426 dep_t dep = DEP_NODE_DEP (n);
1427 rtx_insn *pro = DEP_PRO (dep);
1428 rtx_insn *con = DEP_CON (dep);
1429 deps_list_t con_back_deps;
1430 deps_list_t pro_forw_deps;
1432 if (true_dependency_cache != NULL)
1434 int elem_luid = INSN_LUID (pro);
1435 int insn_luid = INSN_LUID (con);
1437 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1438 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1439 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1440 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1442 if (current_sched_info->flags & DO_SPECULATION)
1443 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1446 get_back_and_forw_lists (dep, sd_it.resolved_p,
1447 &con_back_deps, &pro_forw_deps);
1449 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1450 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1452 delete_dep_node (n);
1455 /* Dump size of the lists. */
1456 #define DUMP_LISTS_SIZE (2)
1458 /* Dump dependencies of the lists. */
1459 #define DUMP_LISTS_DEPS (4)
1461 /* Dump all information about the lists. */
1462 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1464 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1465 FLAGS is a bit mask specifying what information about the lists needs
1466 to be printed.
1467 If FLAGS has the very first bit set, then dump all information about
1468 the lists and propagate this bit into the callee dump functions. */
1469 static void
1470 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1472 sd_iterator_def sd_it;
1473 dep_t dep;
1474 int all;
1476 all = (flags & 1);
1478 if (all)
1479 flags |= DUMP_LISTS_ALL;
1481 fprintf (dump, "[");
1483 if (flags & DUMP_LISTS_SIZE)
1484 fprintf (dump, "%d; ", sd_lists_size (insn, types));
1486 if (flags & DUMP_LISTS_DEPS)
1488 FOR_EACH_DEP (insn, types, sd_it, dep)
1490 dump_dep (dump, dep, dump_dep_flags | all);
1491 fprintf (dump, " ");
1496 /* Dump all information about deps_lists of INSN specified by TYPES
1497 to STDERR. */
1498 void
1499 sd_debug_lists (rtx insn, sd_list_types_def types)
1501 dump_lists (stderr, insn, types, 1);
1502 fprintf (stderr, "\n");
1505 /* A wrapper around add_dependence_1, to add a dependence of CON on
1506 PRO, with type DEP_TYPE. This function implements special handling
1507 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1508 the type to REG_DEP_ANTI if we can determine that predication is
1509 impossible; otherwise we add additional true dependencies on the
1510 INSN_COND_DEPS list of the jump (which PRO must be). */
1511 void
1512 add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1514 if (dep_type == REG_DEP_CONTROL
1515 && !(current_sched_info->flags & DO_PREDICATION))
1516 dep_type = REG_DEP_ANTI;
1518 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1519 so we must also make the insn dependent on the setter of the
1520 condition. */
1521 if (dep_type == REG_DEP_CONTROL)
1523 rtx_insn *real_pro = pro;
1524 rtx_insn *other = real_insn_for_shadow (real_pro);
1525 rtx cond;
1527 if (other != NULL_RTX)
1528 real_pro = other;
1529 cond = sched_get_reverse_condition_uncached (real_pro);
1530 /* Verify that the insn does not use a different value in
1531 the condition register than the one that was present at
1532 the jump. */
1533 if (cond == NULL_RTX)
1534 dep_type = REG_DEP_ANTI;
1535 else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1537 HARD_REG_SET uses;
1538 CLEAR_HARD_REG_SET (uses);
1539 note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1540 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1541 dep_type = REG_DEP_ANTI;
1543 if (dep_type == REG_DEP_CONTROL)
1545 if (sched_verbose >= 5)
1546 fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1547 INSN_UID (real_pro));
1548 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1549 REG_DEP_TRUE, false);
1553 add_dependence_1 (con, pro, dep_type);
1556 /* A convenience wrapper to operate on an entire list. HARD should be
1557 true if DEP_NONREG should be set on newly created dependencies. */
1559 static void
1560 add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1561 enum reg_note dep_type, bool hard)
1563 mark_as_hard = hard;
1564 for (; list; list = list->next ())
1566 if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1567 add_dependence (insn, list->insn (), dep_type);
1569 mark_as_hard = false;
1572 /* Similar, but free *LISTP at the same time, when the context
1573 is not readonly. HARD should be true if DEP_NONREG should be set on
1574 newly created dependencies. */
1576 static void
1577 add_dependence_list_and_free (struct deps_desc *deps, rtx_insn *insn,
1578 rtx_insn_list **listp,
1579 int uncond, enum reg_note dep_type, bool hard)
1581 add_dependence_list (insn, *listp, uncond, dep_type, hard);
1583 /* We don't want to short-circuit dependencies involving debug
1584 insns, because they may cause actual dependencies to be
1585 disregarded. */
1586 if (deps->readonly || DEBUG_INSN_P (insn))
1587 return;
1589 free_INSN_LIST_list (listp);
1592 /* Remove all occurrences of INSN from LIST. Return the number of
1593 occurrences removed. */
1595 static int
1596 remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp)
1598 int removed = 0;
1600 while (*listp)
1602 if ((*listp)->insn () == insn)
1604 remove_free_INSN_LIST_node (listp);
1605 removed++;
1606 continue;
1609 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1612 return removed;
1615 /* Same as above, but process two lists at once. */
1616 static int
1617 remove_from_both_dependence_lists (rtx_insn *insn,
1618 rtx_insn_list **listp,
1619 rtx_expr_list **exprp)
1621 int removed = 0;
1623 while (*listp)
1625 if (XEXP (*listp, 0) == insn)
1627 remove_free_INSN_LIST_node (listp);
1628 remove_free_EXPR_LIST_node (exprp);
1629 removed++;
1630 continue;
1633 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1634 exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1637 return removed;
1640 /* Clear all dependencies for an insn. */
1641 static void
1642 delete_all_dependences (rtx_insn *insn)
1644 sd_iterator_def sd_it;
1645 dep_t dep;
1647 /* The below cycle can be optimized to clear the caches and back_deps
1648 in one call but that would provoke duplication of code from
1649 delete_dep (). */
1651 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1652 sd_iterator_cond (&sd_it, &dep);)
1653 sd_delete_dep (sd_it);
1656 /* All insns in a scheduling group except the first should only have
1657 dependencies on the previous insn in the group. So we find the
1658 first instruction in the scheduling group by walking the dependence
1659 chains backwards. Then we add the dependencies for the group to
1660 the previous nonnote insn. */
1662 static void
1663 chain_to_prev_insn (rtx_insn *insn)
1665 sd_iterator_def sd_it;
1666 dep_t dep;
1667 rtx_insn *prev_nonnote;
1669 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1671 rtx_insn *i = insn;
1672 rtx_insn *pro = DEP_PRO (dep);
1676 i = prev_nonnote_insn (i);
1678 if (pro == i)
1679 goto next_link;
1680 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1682 if (! sched_insns_conditions_mutex_p (i, pro))
1683 add_dependence (i, pro, DEP_TYPE (dep));
1684 next_link:;
1687 delete_all_dependences (insn);
1689 prev_nonnote = prev_nonnote_nondebug_insn (insn);
1690 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1691 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1692 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1695 /* Process an insn's memory dependencies. There are four kinds of
1696 dependencies:
1698 (0) read dependence: read follows read
1699 (1) true dependence: read follows write
1700 (2) output dependence: write follows write
1701 (3) anti dependence: write follows read
1703 We are careful to build only dependencies which actually exist, and
1704 use transitivity to avoid building too many links. */
1706 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1707 The MEM is a memory reference contained within INSN, which we are saving
1708 so that we can do memory aliasing on it. */
1710 static void
1711 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1712 rtx_insn *insn, rtx mem)
1714 rtx_insn_list **insn_list;
1715 rtx_insn_list *insn_node;
1716 rtx_expr_list **mem_list;
1717 rtx_expr_list *mem_node;
1719 gcc_assert (!deps->readonly);
1720 if (read_p)
1722 insn_list = &deps->pending_read_insns;
1723 mem_list = &deps->pending_read_mems;
1724 if (!DEBUG_INSN_P (insn))
1725 deps->pending_read_list_length++;
1727 else
1729 insn_list = &deps->pending_write_insns;
1730 mem_list = &deps->pending_write_mems;
1731 deps->pending_write_list_length++;
1734 insn_node = alloc_INSN_LIST (insn, *insn_list);
1735 *insn_list = insn_node;
1737 if (sched_deps_info->use_cselib)
1739 mem = shallow_copy_rtx (mem);
1740 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1741 GET_MODE (mem), insn);
1743 mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1744 *mem_list = mem_node;
1747 /* Make a dependency between every memory reference on the pending lists
1748 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1749 dependencies for a read operation, similarly with FOR_WRITE. */
1751 static void
1752 flush_pending_lists (struct deps_desc *deps, rtx_insn *insn, int for_read,
1753 int for_write)
1755 if (for_write)
1757 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1758 1, REG_DEP_ANTI, true);
1759 if (!deps->readonly)
1761 free_EXPR_LIST_list (&deps->pending_read_mems);
1762 deps->pending_read_list_length = 0;
1766 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1767 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1768 true);
1770 add_dependence_list_and_free (deps, insn,
1771 &deps->last_pending_memory_flush, 1,
1772 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1773 true);
1775 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1776 REG_DEP_ANTI, true);
1778 if (DEBUG_INSN_P (insn))
1780 if (for_write)
1781 free_INSN_LIST_list (&deps->pending_read_insns);
1782 free_INSN_LIST_list (&deps->pending_write_insns);
1783 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1784 free_INSN_LIST_list (&deps->pending_jump_insns);
1787 if (!deps->readonly)
1789 free_EXPR_LIST_list (&deps->pending_write_mems);
1790 deps->pending_write_list_length = 0;
1792 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1793 deps->pending_flush_length = 1;
1795 mark_as_hard = false;
1798 /* Instruction which dependencies we are analyzing. */
1799 static rtx_insn *cur_insn = NULL;
1801 /* Implement hooks for haifa scheduler. */
1803 static void
1804 haifa_start_insn (rtx_insn *insn)
1806 gcc_assert (insn && !cur_insn);
1808 cur_insn = insn;
1811 static void
1812 haifa_finish_insn (void)
1814 cur_insn = NULL;
1817 void
1818 haifa_note_reg_set (int regno)
1820 SET_REGNO_REG_SET (reg_pending_sets, regno);
1823 void
1824 haifa_note_reg_clobber (int regno)
1826 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1829 void
1830 haifa_note_reg_use (int regno)
1832 SET_REGNO_REG_SET (reg_pending_uses, regno);
1835 static void
1836 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1838 if (!(ds & SPECULATIVE))
1840 mem = NULL_RTX;
1841 pending_mem = NULL_RTX;
1843 else
1844 gcc_assert (ds & BEGIN_DATA);
1847 dep_def _dep, *dep = &_dep;
1849 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1850 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1851 DEP_NONREG (dep) = 1;
1852 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1857 static void
1858 haifa_note_dep (rtx_insn *elem, ds_t ds)
1860 dep_def _dep;
1861 dep_t dep = &_dep;
1863 init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1864 if (mark_as_hard)
1865 DEP_NONREG (dep) = 1;
1866 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1869 static void
1870 note_reg_use (int r)
1872 if (sched_deps_info->note_reg_use)
1873 sched_deps_info->note_reg_use (r);
1876 static void
1877 note_reg_set (int r)
1879 if (sched_deps_info->note_reg_set)
1880 sched_deps_info->note_reg_set (r);
1883 static void
1884 note_reg_clobber (int r)
1886 if (sched_deps_info->note_reg_clobber)
1887 sched_deps_info->note_reg_clobber (r);
1890 static void
1891 note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1893 if (sched_deps_info->note_mem_dep)
1894 sched_deps_info->note_mem_dep (m1, m2, e, ds);
1897 static void
1898 note_dep (rtx_insn *e, ds_t ds)
1900 if (sched_deps_info->note_dep)
1901 sched_deps_info->note_dep (e, ds);
1904 /* Return corresponding to DS reg_note. */
1905 enum reg_note
1906 ds_to_dt (ds_t ds)
1908 if (ds & DEP_TRUE)
1909 return REG_DEP_TRUE;
1910 else if (ds & DEP_OUTPUT)
1911 return REG_DEP_OUTPUT;
1912 else if (ds & DEP_ANTI)
1913 return REG_DEP_ANTI;
1914 else
1916 gcc_assert (ds & DEP_CONTROL);
1917 return REG_DEP_CONTROL;
1923 /* Functions for computation of info needed for register pressure
1924 sensitive insn scheduling. */
1927 /* Allocate and return reg_use_data structure for REGNO and INSN. */
1928 static struct reg_use_data *
1929 create_insn_reg_use (int regno, rtx_insn *insn)
1931 struct reg_use_data *use;
1933 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1934 use->regno = regno;
1935 use->insn = insn;
1936 use->next_insn_use = INSN_REG_USE_LIST (insn);
1937 INSN_REG_USE_LIST (insn) = use;
1938 return use;
1941 /* Allocate reg_set_data structure for REGNO and INSN. */
1942 static void
1943 create_insn_reg_set (int regno, rtx insn)
1945 struct reg_set_data *set;
1947 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1948 set->regno = regno;
1949 set->insn = insn;
1950 set->next_insn_set = INSN_REG_SET_LIST (insn);
1951 INSN_REG_SET_LIST (insn) = set;
1954 /* Set up insn register uses for INSN and dependency context DEPS. */
1955 static void
1956 setup_insn_reg_uses (struct deps_desc *deps, rtx_insn *insn)
1958 unsigned i;
1959 reg_set_iterator rsi;
1960 struct reg_use_data *use, *use2, *next;
1961 struct deps_reg *reg_last;
1963 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1965 if (i < FIRST_PSEUDO_REGISTER
1966 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1967 continue;
1969 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1970 && ! REGNO_REG_SET_P (reg_pending_sets, i)
1971 && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1972 /* Ignore use which is not dying. */
1973 continue;
1975 use = create_insn_reg_use (i, insn);
1976 use->next_regno_use = use;
1977 reg_last = &deps->reg_last[i];
1979 /* Create the cycle list of uses. */
1980 for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
1982 use2 = create_insn_reg_use (i, list->insn ());
1983 next = use->next_regno_use;
1984 use->next_regno_use = use2;
1985 use2->next_regno_use = next;
1990 /* Register pressure info for the currently processed insn. */
1991 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1993 /* Return TRUE if INSN has the use structure for REGNO. */
1994 static bool
1995 insn_use_p (rtx insn, int regno)
1997 struct reg_use_data *use;
1999 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2000 if (use->regno == regno)
2001 return true;
2002 return false;
2005 /* Update the register pressure info after birth of pseudo register REGNO
2006 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2007 the register is in clobber or unused after the insn. */
2008 static void
2009 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2011 int incr, new_incr;
2012 enum reg_class cl;
2014 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2015 cl = sched_regno_pressure_class[regno];
2016 if (cl != NO_REGS)
2018 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2019 if (clobber_p)
2021 new_incr = reg_pressure_info[cl].clobber_increase + incr;
2022 reg_pressure_info[cl].clobber_increase = new_incr;
2024 else if (unused_p)
2026 new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2027 reg_pressure_info[cl].unused_set_increase = new_incr;
2029 else
2031 new_incr = reg_pressure_info[cl].set_increase + incr;
2032 reg_pressure_info[cl].set_increase = new_incr;
2033 if (! insn_use_p (insn, regno))
2034 reg_pressure_info[cl].change += incr;
2035 create_insn_reg_set (regno, insn);
2037 gcc_assert (new_incr < (1 << INCREASE_BITS));
2041 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2042 hard registers involved in the birth. */
2043 static void
2044 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2045 bool clobber_p, bool unused_p)
2047 enum reg_class cl;
2048 int new_incr, last = regno + nregs;
2050 while (regno < last)
2052 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2053 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2055 cl = sched_regno_pressure_class[regno];
2056 if (cl != NO_REGS)
2058 if (clobber_p)
2060 new_incr = reg_pressure_info[cl].clobber_increase + 1;
2061 reg_pressure_info[cl].clobber_increase = new_incr;
2063 else if (unused_p)
2065 new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2066 reg_pressure_info[cl].unused_set_increase = new_incr;
2068 else
2070 new_incr = reg_pressure_info[cl].set_increase + 1;
2071 reg_pressure_info[cl].set_increase = new_incr;
2072 if (! insn_use_p (insn, regno))
2073 reg_pressure_info[cl].change += 1;
2074 create_insn_reg_set (regno, insn);
2076 gcc_assert (new_incr < (1 << INCREASE_BITS));
2079 regno++;
2083 /* Update the register pressure info after birth of pseudo or hard
2084 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2085 correspondingly that the register is in clobber or unused after the
2086 insn. */
2087 static void
2088 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2090 int regno;
2092 if (GET_CODE (reg) == SUBREG)
2093 reg = SUBREG_REG (reg);
2095 if (! REG_P (reg))
2096 return;
2098 regno = REGNO (reg);
2099 if (regno < FIRST_PSEUDO_REGISTER)
2100 mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg),
2101 clobber_p, unused_p);
2102 else
2103 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2106 /* Update the register pressure info after death of pseudo register
2107 REGNO. */
2108 static void
2109 mark_pseudo_death (int regno)
2111 int incr;
2112 enum reg_class cl;
2114 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2115 cl = sched_regno_pressure_class[regno];
2116 if (cl != NO_REGS)
2118 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2119 reg_pressure_info[cl].change -= incr;
2123 /* Like mark_pseudo_death except that NREGS saying how many hard
2124 registers involved in the death. */
2125 static void
2126 mark_hard_regno_death (int regno, int nregs)
2128 enum reg_class cl;
2129 int last = regno + nregs;
2131 while (regno < last)
2133 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2134 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2136 cl = sched_regno_pressure_class[regno];
2137 if (cl != NO_REGS)
2138 reg_pressure_info[cl].change -= 1;
2140 regno++;
2144 /* Update the register pressure info after death of pseudo or hard
2145 register REG. */
2146 static void
2147 mark_reg_death (rtx reg)
2149 int regno;
2151 if (GET_CODE (reg) == SUBREG)
2152 reg = SUBREG_REG (reg);
2154 if (! REG_P (reg))
2155 return;
2157 regno = REGNO (reg);
2158 if (regno < FIRST_PSEUDO_REGISTER)
2159 mark_hard_regno_death (regno, REG_NREGS (reg));
2160 else
2161 mark_pseudo_death (regno);
2164 /* Process SETTER of REG. DATA is an insn containing the setter. */
2165 static void
2166 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2168 if (setter != NULL_RTX && GET_CODE (setter) != SET)
2169 return;
2170 mark_insn_reg_birth
2171 ((rtx) data, reg, false,
2172 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2175 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2176 static void
2177 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2179 if (GET_CODE (setter) == CLOBBER)
2180 mark_insn_reg_birth ((rtx) data, reg, true, false);
2183 /* Set up reg pressure info related to INSN. */
2184 void
2185 init_insn_reg_pressure_info (rtx_insn *insn)
2187 int i, len;
2188 enum reg_class cl;
2189 static struct reg_pressure_data *pressure_info;
2190 rtx link;
2192 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2194 if (! INSN_P (insn))
2195 return;
2197 for (i = 0; i < ira_pressure_classes_num; i++)
2199 cl = ira_pressure_classes[i];
2200 reg_pressure_info[cl].clobber_increase = 0;
2201 reg_pressure_info[cl].set_increase = 0;
2202 reg_pressure_info[cl].unused_set_increase = 0;
2203 reg_pressure_info[cl].change = 0;
2206 note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2208 note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2210 if (AUTO_INC_DEC)
2211 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2212 if (REG_NOTE_KIND (link) == REG_INC)
2213 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2215 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2216 if (REG_NOTE_KIND (link) == REG_DEAD)
2217 mark_reg_death (XEXP (link, 0));
2219 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2220 pressure_info
2221 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2222 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2223 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2224 * sizeof (int), 1);
2225 for (i = 0; i < ira_pressure_classes_num; i++)
2227 cl = ira_pressure_classes[i];
2228 pressure_info[i].clobber_increase
2229 = reg_pressure_info[cl].clobber_increase;
2230 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2231 pressure_info[i].unused_set_increase
2232 = reg_pressure_info[cl].unused_set_increase;
2233 pressure_info[i].change = reg_pressure_info[cl].change;
2240 /* Internal variable for sched_analyze_[12] () functions.
2241 If it is nonzero, this means that sched_analyze_[12] looks
2242 at the most toplevel SET. */
2243 static bool can_start_lhs_rhs_p;
2245 /* Extend reg info for the deps context DEPS given that
2246 we have just generated a register numbered REGNO. */
2247 static void
2248 extend_deps_reg_info (struct deps_desc *deps, int regno)
2250 int max_regno = regno + 1;
2252 gcc_assert (!reload_completed);
2254 /* In a readonly context, it would not hurt to extend info,
2255 but it should not be needed. */
2256 if (reload_completed && deps->readonly)
2258 deps->max_reg = max_regno;
2259 return;
2262 if (max_regno > deps->max_reg)
2264 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2265 max_regno);
2266 memset (&deps->reg_last[deps->max_reg],
2267 0, (max_regno - deps->max_reg)
2268 * sizeof (struct deps_reg));
2269 deps->max_reg = max_regno;
2273 /* Extends REG_INFO_P if needed. */
2274 void
2275 maybe_extend_reg_info_p (void)
2277 /* Extend REG_INFO_P, if needed. */
2278 if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2280 size_t new_reg_info_p_size = max_regno + 128;
2282 gcc_assert (!reload_completed && sel_sched_p ());
2284 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2285 new_reg_info_p_size,
2286 reg_info_p_size,
2287 sizeof (*reg_info_p));
2288 reg_info_p_size = new_reg_info_p_size;
2292 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2293 The type of the reference is specified by REF and can be SET,
2294 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2296 static void
2297 sched_analyze_reg (struct deps_desc *deps, int regno, machine_mode mode,
2298 enum rtx_code ref, rtx_insn *insn)
2300 /* We could emit new pseudos in renaming. Extend the reg structures. */
2301 if (!reload_completed && sel_sched_p ()
2302 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2303 extend_deps_reg_info (deps, regno);
2305 maybe_extend_reg_info_p ();
2307 /* A hard reg in a wide mode may really be multiple registers.
2308 If so, mark all of them just like the first. */
2309 if (regno < FIRST_PSEUDO_REGISTER)
2311 int i = hard_regno_nregs[regno][mode];
2312 if (ref == SET)
2314 while (--i >= 0)
2315 note_reg_set (regno + i);
2317 else if (ref == USE)
2319 while (--i >= 0)
2320 note_reg_use (regno + i);
2322 else
2324 while (--i >= 0)
2325 note_reg_clobber (regno + i);
2329 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2330 it does not reload. Ignore these as they have served their
2331 purpose already. */
2332 else if (regno >= deps->max_reg)
2334 enum rtx_code code = GET_CODE (PATTERN (insn));
2335 gcc_assert (code == USE || code == CLOBBER);
2338 else
2340 if (ref == SET)
2341 note_reg_set (regno);
2342 else if (ref == USE)
2343 note_reg_use (regno);
2344 else
2345 note_reg_clobber (regno);
2347 /* Pseudos that are REG_EQUIV to something may be replaced
2348 by that during reloading. We need only add dependencies for
2349 the address in the REG_EQUIV note. */
2350 if (!reload_completed && get_reg_known_equiv_p (regno))
2352 rtx t = get_reg_known_value (regno);
2353 if (MEM_P (t))
2354 sched_analyze_2 (deps, XEXP (t, 0), insn);
2357 /* Don't let it cross a call after scheduling if it doesn't
2358 already cross one. */
2359 if (REG_N_CALLS_CROSSED (regno) == 0)
2361 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2362 deps->sched_before_next_call
2363 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2364 else
2365 add_dependence_list (insn, deps->last_function_call, 1,
2366 REG_DEP_ANTI, false);
2371 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2372 rtx, X, creating all dependencies generated by the write to the
2373 destination of X, and reads of everything mentioned. */
2375 static void
2376 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2378 rtx dest = XEXP (x, 0);
2379 enum rtx_code code = GET_CODE (x);
2380 bool cslr_p = can_start_lhs_rhs_p;
2382 can_start_lhs_rhs_p = false;
2384 gcc_assert (dest);
2385 if (dest == 0)
2386 return;
2388 if (cslr_p && sched_deps_info->start_lhs)
2389 sched_deps_info->start_lhs (dest);
2391 if (GET_CODE (dest) == PARALLEL)
2393 int i;
2395 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2396 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2397 sched_analyze_1 (deps,
2398 gen_rtx_CLOBBER (VOIDmode,
2399 XEXP (XVECEXP (dest, 0, i), 0)),
2400 insn);
2402 if (cslr_p && sched_deps_info->finish_lhs)
2403 sched_deps_info->finish_lhs ();
2405 if (code == SET)
2407 can_start_lhs_rhs_p = cslr_p;
2409 sched_analyze_2 (deps, SET_SRC (x), insn);
2411 can_start_lhs_rhs_p = false;
2414 return;
2417 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2418 || GET_CODE (dest) == ZERO_EXTRACT)
2420 if (GET_CODE (dest) == STRICT_LOW_PART
2421 || GET_CODE (dest) == ZERO_EXTRACT
2422 || df_read_modify_subreg_p (dest))
2424 /* These both read and modify the result. We must handle
2425 them as writes to get proper dependencies for following
2426 instructions. We must handle them as reads to get proper
2427 dependencies from this to previous instructions.
2428 Thus we need to call sched_analyze_2. */
2430 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2432 if (GET_CODE (dest) == ZERO_EXTRACT)
2434 /* The second and third arguments are values read by this insn. */
2435 sched_analyze_2 (deps, XEXP (dest, 1), insn);
2436 sched_analyze_2 (deps, XEXP (dest, 2), insn);
2438 dest = XEXP (dest, 0);
2441 if (REG_P (dest))
2443 int regno = REGNO (dest);
2444 machine_mode mode = GET_MODE (dest);
2446 sched_analyze_reg (deps, regno, mode, code, insn);
2448 #ifdef STACK_REGS
2449 /* Treat all writes to a stack register as modifying the TOS. */
2450 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2452 /* Avoid analyzing the same register twice. */
2453 if (regno != FIRST_STACK_REG)
2454 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2456 add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2457 FIRST_STACK_REG);
2459 #endif
2461 else if (MEM_P (dest))
2463 /* Writing memory. */
2464 rtx t = dest;
2466 if (sched_deps_info->use_cselib)
2468 machine_mode address_mode = get_address_mode (dest);
2470 t = shallow_copy_rtx (dest);
2471 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2472 GET_MODE (t), insn);
2473 XEXP (t, 0)
2474 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2475 insn);
2477 t = canon_rtx (t);
2479 /* Pending lists can't get larger with a readonly context. */
2480 if (!deps->readonly
2481 && ((deps->pending_read_list_length + deps->pending_write_list_length)
2482 >= MAX_PENDING_LIST_LENGTH))
2484 /* Flush all pending reads and writes to prevent the pending lists
2485 from getting any larger. Insn scheduling runs too slowly when
2486 these lists get long. When compiling GCC with itself,
2487 this flush occurs 8 times for sparc, and 10 times for m88k using
2488 the default value of 32. */
2489 flush_pending_lists (deps, insn, false, true);
2491 else
2493 rtx_insn_list *pending;
2494 rtx_expr_list *pending_mem;
2496 pending = deps->pending_read_insns;
2497 pending_mem = deps->pending_read_mems;
2498 while (pending)
2500 if (anti_dependence (pending_mem->element (), t)
2501 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2502 note_mem_dep (t, pending_mem->element (), pending->insn (),
2503 DEP_ANTI);
2505 pending = pending->next ();
2506 pending_mem = pending_mem->next ();
2509 pending = deps->pending_write_insns;
2510 pending_mem = deps->pending_write_mems;
2511 while (pending)
2513 if (output_dependence (pending_mem->element (), t)
2514 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2515 note_mem_dep (t, pending_mem->element (),
2516 pending->insn (),
2517 DEP_OUTPUT);
2519 pending = pending->next ();
2520 pending_mem = pending_mem-> next ();
2523 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2524 REG_DEP_ANTI, true);
2525 add_dependence_list (insn, deps->pending_jump_insns, 1,
2526 REG_DEP_CONTROL, true);
2528 if (!deps->readonly)
2529 add_insn_mem_dependence (deps, false, insn, dest);
2531 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2534 if (cslr_p && sched_deps_info->finish_lhs)
2535 sched_deps_info->finish_lhs ();
2537 /* Analyze reads. */
2538 if (GET_CODE (x) == SET)
2540 can_start_lhs_rhs_p = cslr_p;
2542 sched_analyze_2 (deps, SET_SRC (x), insn);
2544 can_start_lhs_rhs_p = false;
2548 /* Analyze the uses of memory and registers in rtx X in INSN. */
2549 static void
2550 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2552 int i;
2553 int j;
2554 enum rtx_code code;
2555 const char *fmt;
2556 bool cslr_p = can_start_lhs_rhs_p;
2558 can_start_lhs_rhs_p = false;
2560 gcc_assert (x);
2561 if (x == 0)
2562 return;
2564 if (cslr_p && sched_deps_info->start_rhs)
2565 sched_deps_info->start_rhs (x);
2567 code = GET_CODE (x);
2569 switch (code)
2571 CASE_CONST_ANY:
2572 case SYMBOL_REF:
2573 case CONST:
2574 case LABEL_REF:
2575 /* Ignore constants. */
2576 if (cslr_p && sched_deps_info->finish_rhs)
2577 sched_deps_info->finish_rhs ();
2579 return;
2581 case CC0:
2582 if (!HAVE_cc0)
2583 gcc_unreachable ();
2585 /* User of CC0 depends on immediately preceding insn. */
2586 SCHED_GROUP_P (insn) = 1;
2587 /* Don't move CC0 setter to another block (it can set up the
2588 same flag for previous CC0 users which is safe). */
2589 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2591 if (cslr_p && sched_deps_info->finish_rhs)
2592 sched_deps_info->finish_rhs ();
2594 return;
2596 case REG:
2598 int regno = REGNO (x);
2599 machine_mode mode = GET_MODE (x);
2601 sched_analyze_reg (deps, regno, mode, USE, insn);
2603 #ifdef STACK_REGS
2604 /* Treat all reads of a stack register as modifying the TOS. */
2605 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2607 /* Avoid analyzing the same register twice. */
2608 if (regno != FIRST_STACK_REG)
2609 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2610 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2612 #endif
2614 if (cslr_p && sched_deps_info->finish_rhs)
2615 sched_deps_info->finish_rhs ();
2617 return;
2620 case MEM:
2622 /* Reading memory. */
2623 rtx_insn_list *u;
2624 rtx_insn_list *pending;
2625 rtx_expr_list *pending_mem;
2626 rtx t = x;
2628 if (sched_deps_info->use_cselib)
2630 machine_mode address_mode = get_address_mode (t);
2632 t = shallow_copy_rtx (t);
2633 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2634 GET_MODE (t), insn);
2635 XEXP (t, 0)
2636 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2637 insn);
2640 if (!DEBUG_INSN_P (insn))
2642 t = canon_rtx (t);
2643 pending = deps->pending_read_insns;
2644 pending_mem = deps->pending_read_mems;
2645 while (pending)
2647 if (read_dependence (pending_mem->element (), t)
2648 && ! sched_insns_conditions_mutex_p (insn,
2649 pending->insn ()))
2650 note_mem_dep (t, pending_mem->element (),
2651 pending->insn (),
2652 DEP_ANTI);
2654 pending = pending->next ();
2655 pending_mem = pending_mem->next ();
2658 pending = deps->pending_write_insns;
2659 pending_mem = deps->pending_write_mems;
2660 while (pending)
2662 if (true_dependence (pending_mem->element (), VOIDmode, t)
2663 && ! sched_insns_conditions_mutex_p (insn,
2664 pending->insn ()))
2665 note_mem_dep (t, pending_mem->element (),
2666 pending->insn (),
2667 sched_deps_info->generate_spec_deps
2668 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2670 pending = pending->next ();
2671 pending_mem = pending_mem->next ();
2674 for (u = deps->last_pending_memory_flush; u; u = u->next ())
2675 add_dependence (insn, u->insn (), REG_DEP_ANTI);
2677 for (u = deps->pending_jump_insns; u; u = u->next ())
2678 if (deps_may_trap_p (x))
2680 if ((sched_deps_info->generate_spec_deps)
2681 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2683 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2684 MAX_DEP_WEAK);
2686 note_dep (u->insn (), ds);
2688 else
2689 add_dependence (insn, u->insn (), REG_DEP_CONTROL);
2693 /* Always add these dependencies to pending_reads, since
2694 this insn may be followed by a write. */
2695 if (!deps->readonly)
2697 if ((deps->pending_read_list_length
2698 + deps->pending_write_list_length)
2699 >= MAX_PENDING_LIST_LENGTH
2700 && !DEBUG_INSN_P (insn))
2701 flush_pending_lists (deps, insn, true, true);
2702 add_insn_mem_dependence (deps, true, insn, x);
2705 sched_analyze_2 (deps, XEXP (x, 0), insn);
2707 if (cslr_p && sched_deps_info->finish_rhs)
2708 sched_deps_info->finish_rhs ();
2710 return;
2713 /* Force pending stores to memory in case a trap handler needs them.
2714 Also force pending loads from memory; loads and stores can segfault
2715 and the signal handler won't be triggered if the trap insn was moved
2716 above load or store insn. */
2717 case TRAP_IF:
2718 flush_pending_lists (deps, insn, true, true);
2719 break;
2721 case PREFETCH:
2722 if (PREFETCH_SCHEDULE_BARRIER_P (x))
2723 reg_pending_barrier = TRUE_BARRIER;
2724 /* Prefetch insn contains addresses only. So if the prefetch
2725 address has no registers, there will be no dependencies on
2726 the prefetch insn. This is wrong with result code
2727 correctness point of view as such prefetch can be moved below
2728 a jump insn which usually generates MOVE_BARRIER preventing
2729 to move insns containing registers or memories through the
2730 barrier. It is also wrong with generated code performance
2731 point of view as prefetch withouth dependecies will have a
2732 tendency to be issued later instead of earlier. It is hard
2733 to generate accurate dependencies for prefetch insns as
2734 prefetch has only the start address but it is better to have
2735 something than nothing. */
2736 if (!deps->readonly)
2738 rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2739 if (sched_deps_info->use_cselib)
2740 cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2741 add_insn_mem_dependence (deps, true, insn, x);
2743 break;
2745 case UNSPEC_VOLATILE:
2746 flush_pending_lists (deps, insn, true, true);
2747 /* FALLTHRU */
2749 case ASM_OPERANDS:
2750 case ASM_INPUT:
2752 /* Traditional and volatile asm instructions must be considered to use
2753 and clobber all hard registers, all pseudo-registers and all of
2754 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2756 Consider for instance a volatile asm that changes the fpu rounding
2757 mode. An insn should not be moved across this even if it only uses
2758 pseudo-regs because it might give an incorrectly rounded result. */
2759 if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2760 && !DEBUG_INSN_P (insn))
2761 reg_pending_barrier = TRUE_BARRIER;
2763 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2764 We can not just fall through here since then we would be confused
2765 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2766 traditional asms unlike their normal usage. */
2768 if (code == ASM_OPERANDS)
2770 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2771 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2773 if (cslr_p && sched_deps_info->finish_rhs)
2774 sched_deps_info->finish_rhs ();
2776 return;
2778 break;
2781 case PRE_DEC:
2782 case POST_DEC:
2783 case PRE_INC:
2784 case POST_INC:
2785 /* These both read and modify the result. We must handle them as writes
2786 to get proper dependencies for following instructions. We must handle
2787 them as reads to get proper dependencies from this to previous
2788 instructions. Thus we need to pass them to both sched_analyze_1
2789 and sched_analyze_2. We must call sched_analyze_2 first in order
2790 to get the proper antecedent for the read. */
2791 sched_analyze_2 (deps, XEXP (x, 0), insn);
2792 sched_analyze_1 (deps, x, insn);
2794 if (cslr_p && sched_deps_info->finish_rhs)
2795 sched_deps_info->finish_rhs ();
2797 return;
2799 case POST_MODIFY:
2800 case PRE_MODIFY:
2801 /* op0 = op0 + op1 */
2802 sched_analyze_2 (deps, XEXP (x, 0), insn);
2803 sched_analyze_2 (deps, XEXP (x, 1), insn);
2804 sched_analyze_1 (deps, x, insn);
2806 if (cslr_p && sched_deps_info->finish_rhs)
2807 sched_deps_info->finish_rhs ();
2809 return;
2811 default:
2812 break;
2815 /* Other cases: walk the insn. */
2816 fmt = GET_RTX_FORMAT (code);
2817 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2819 if (fmt[i] == 'e')
2820 sched_analyze_2 (deps, XEXP (x, i), insn);
2821 else if (fmt[i] == 'E')
2822 for (j = 0; j < XVECLEN (x, i); j++)
2823 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2826 if (cslr_p && sched_deps_info->finish_rhs)
2827 sched_deps_info->finish_rhs ();
2830 /* Try to group two fusible insns together to prevent scheduler
2831 from scheduling them apart. */
2833 static void
2834 sched_macro_fuse_insns (rtx_insn *insn)
2836 rtx_insn *prev;
2838 if (any_condjump_p (insn))
2840 unsigned int condreg1, condreg2;
2841 rtx cc_reg_1;
2842 targetm.fixed_condition_code_regs (&condreg1, &condreg2);
2843 cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2844 prev = prev_nonnote_nondebug_insn (insn);
2845 if (!reg_referenced_p (cc_reg_1, PATTERN (insn))
2846 || !prev
2847 || !modified_in_p (cc_reg_1, prev))
2848 return;
2850 else
2852 rtx insn_set = single_set (insn);
2854 prev = prev_nonnote_nondebug_insn (insn);
2855 if (!prev
2856 || !insn_set
2857 || !single_set (prev))
2858 return;
2862 if (targetm.sched.macro_fusion_pair_p (prev, insn))
2863 SCHED_GROUP_P (insn) = 1;
2867 /* Get the implicit reg pending clobbers for INSN and save them in TEMP. */
2868 void
2869 get_implicit_reg_pending_clobbers (HARD_REG_SET *temp, rtx_insn *insn)
2871 extract_insn (insn);
2872 preprocess_constraints (insn);
2873 alternative_mask preferred = get_preferred_alternatives (insn);
2874 ira_implicitly_set_insn_hard_regs (temp, preferred);
2875 AND_COMPL_HARD_REG_SET (*temp, ira_no_alloc_regs);
2878 /* Analyze an INSN with pattern X to find all dependencies. */
2879 static void
2880 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
2882 RTX_CODE code = GET_CODE (x);
2883 rtx link;
2884 unsigned i;
2885 reg_set_iterator rsi;
2887 if (! reload_completed)
2889 HARD_REG_SET temp;
2890 get_implicit_reg_pending_clobbers (&temp, insn);
2891 IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2894 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2895 && code == SET);
2897 /* Group compare and branch insns for macro-fusion. */
2898 if (targetm.sched.macro_fusion_p
2899 && targetm.sched.macro_fusion_p ())
2900 sched_macro_fuse_insns (insn);
2902 if (may_trap_p (x))
2903 /* Avoid moving trapping instructions across function calls that might
2904 not always return. */
2905 add_dependence_list (insn, deps->last_function_call_may_noreturn,
2906 1, REG_DEP_ANTI, true);
2908 /* We must avoid creating a situation in which two successors of the
2909 current block have different unwind info after scheduling. If at any
2910 point the two paths re-join this leads to incorrect unwind info. */
2911 /* ??? There are certain situations involving a forced frame pointer in
2912 which, with extra effort, we could fix up the unwind info at a later
2913 CFG join. However, it seems better to notice these cases earlier
2914 during prologue generation and avoid marking the frame pointer setup
2915 as frame-related at all. */
2916 if (RTX_FRAME_RELATED_P (insn))
2918 /* Make sure prologue insn is scheduled before next jump. */
2919 deps->sched_before_next_jump
2920 = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2922 /* Make sure epilogue insn is scheduled after preceding jumps. */
2923 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2924 true);
2927 if (code == COND_EXEC)
2929 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2931 /* ??? Should be recording conditions so we reduce the number of
2932 false dependencies. */
2933 x = COND_EXEC_CODE (x);
2934 code = GET_CODE (x);
2936 if (code == SET || code == CLOBBER)
2938 sched_analyze_1 (deps, x, insn);
2940 /* Bare clobber insns are used for letting life analysis, reg-stack
2941 and others know that a value is dead. Depend on the last call
2942 instruction so that reg-stack won't get confused. */
2943 if (code == CLOBBER)
2944 add_dependence_list (insn, deps->last_function_call, 1,
2945 REG_DEP_OUTPUT, true);
2947 else if (code == PARALLEL)
2949 for (i = XVECLEN (x, 0); i--;)
2951 rtx sub = XVECEXP (x, 0, i);
2952 code = GET_CODE (sub);
2954 if (code == COND_EXEC)
2956 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2957 sub = COND_EXEC_CODE (sub);
2958 code = GET_CODE (sub);
2960 if (code == SET || code == CLOBBER)
2961 sched_analyze_1 (deps, sub, insn);
2962 else
2963 sched_analyze_2 (deps, sub, insn);
2966 else
2967 sched_analyze_2 (deps, x, insn);
2969 /* Mark registers CLOBBERED or used by called function. */
2970 if (CALL_P (insn))
2972 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2974 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2975 sched_analyze_1 (deps, XEXP (link, 0), insn);
2976 else if (GET_CODE (XEXP (link, 0)) != SET)
2977 sched_analyze_2 (deps, XEXP (link, 0), insn);
2979 /* Don't schedule anything after a tail call, tail call needs
2980 to use at least all call-saved registers. */
2981 if (SIBLING_CALL_P (insn))
2982 reg_pending_barrier = TRUE_BARRIER;
2983 else if (find_reg_note (insn, REG_SETJMP, NULL))
2984 reg_pending_barrier = MOVE_BARRIER;
2987 if (JUMP_P (insn))
2989 rtx_insn *next = next_nonnote_nondebug_insn (insn);
2990 if (next && BARRIER_P (next))
2991 reg_pending_barrier = MOVE_BARRIER;
2992 else
2994 rtx_insn_list *pending;
2995 rtx_expr_list *pending_mem;
2997 if (sched_deps_info->compute_jump_reg_dependencies)
2999 (*sched_deps_info->compute_jump_reg_dependencies)
3000 (insn, reg_pending_control_uses);
3002 /* Make latency of jump equal to 0 by using anti-dependence. */
3003 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3005 struct deps_reg *reg_last = &deps->reg_last[i];
3006 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3007 false);
3008 add_dependence_list (insn, reg_last->implicit_sets,
3009 0, REG_DEP_ANTI, false);
3010 add_dependence_list (insn, reg_last->clobbers, 0,
3011 REG_DEP_ANTI, false);
3015 /* All memory writes and volatile reads must happen before the
3016 jump. Non-volatile reads must happen before the jump iff
3017 the result is needed by the above register used mask. */
3019 pending = deps->pending_write_insns;
3020 pending_mem = deps->pending_write_mems;
3021 while (pending)
3023 if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3024 add_dependence (insn, pending->insn (),
3025 REG_DEP_OUTPUT);
3026 pending = pending->next ();
3027 pending_mem = pending_mem->next ();
3030 pending = deps->pending_read_insns;
3031 pending_mem = deps->pending_read_mems;
3032 while (pending)
3034 if (MEM_VOLATILE_P (pending_mem->element ())
3035 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3036 add_dependence (insn, pending->insn (),
3037 REG_DEP_OUTPUT);
3038 pending = pending->next ();
3039 pending_mem = pending_mem->next ();
3042 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3043 REG_DEP_ANTI, true);
3044 add_dependence_list (insn, deps->pending_jump_insns, 1,
3045 REG_DEP_ANTI, true);
3049 /* If this instruction can throw an exception, then moving it changes
3050 where block boundaries fall. This is mighty confusing elsewhere.
3051 Therefore, prevent such an instruction from being moved. Same for
3052 non-jump instructions that define block boundaries.
3053 ??? Unclear whether this is still necessary in EBB mode. If not,
3054 add_branch_dependences should be adjusted for RGN mode instead. */
3055 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3056 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3057 reg_pending_barrier = MOVE_BARRIER;
3059 if (sched_pressure != SCHED_PRESSURE_NONE)
3061 setup_insn_reg_uses (deps, insn);
3062 init_insn_reg_pressure_info (insn);
3065 /* Add register dependencies for insn. */
3066 if (DEBUG_INSN_P (insn))
3068 rtx_insn *prev = deps->last_debug_insn;
3069 rtx_insn_list *u;
3071 if (!deps->readonly)
3072 deps->last_debug_insn = insn;
3074 if (prev)
3075 add_dependence (insn, prev, REG_DEP_ANTI);
3077 add_dependence_list (insn, deps->last_function_call, 1,
3078 REG_DEP_ANTI, false);
3080 if (!sel_sched_p ())
3081 for (u = deps->last_pending_memory_flush; u; u = u->next ())
3082 add_dependence (insn, u->insn (), REG_DEP_ANTI);
3084 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3086 struct deps_reg *reg_last = &deps->reg_last[i];
3087 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3088 /* There's no point in making REG_DEP_CONTROL dependencies for
3089 debug insns. */
3090 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3091 false);
3093 if (!deps->readonly)
3094 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3096 CLEAR_REG_SET (reg_pending_uses);
3098 /* Quite often, a debug insn will refer to stuff in the
3099 previous instruction, but the reason we want this
3100 dependency here is to make sure the scheduler doesn't
3101 gratuitously move a debug insn ahead. This could dirty
3102 DF flags and cause additional analysis that wouldn't have
3103 occurred in compilation without debug insns, and such
3104 additional analysis can modify the generated code. */
3105 prev = PREV_INSN (insn);
3107 if (prev && NONDEBUG_INSN_P (prev))
3108 add_dependence (insn, prev, REG_DEP_ANTI);
3110 else
3112 regset_head set_or_clobbered;
3114 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3116 struct deps_reg *reg_last = &deps->reg_last[i];
3117 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3118 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3119 false);
3120 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3121 false);
3123 if (!deps->readonly)
3125 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3126 reg_last->uses_length++;
3130 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3131 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3133 struct deps_reg *reg_last = &deps->reg_last[i];
3134 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3135 add_dependence_list (insn, reg_last->implicit_sets, 0,
3136 REG_DEP_ANTI, false);
3137 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3138 false);
3140 if (!deps->readonly)
3142 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3143 reg_last->uses_length++;
3147 if (targetm.sched.exposed_pipeline)
3149 INIT_REG_SET (&set_or_clobbered);
3150 bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3151 reg_pending_sets);
3152 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3154 struct deps_reg *reg_last = &deps->reg_last[i];
3155 rtx list;
3156 for (list = reg_last->uses; list; list = XEXP (list, 1))
3158 rtx other = XEXP (list, 0);
3159 if (INSN_CACHED_COND (other) != const_true_rtx
3160 && refers_to_regno_p (i, INSN_CACHED_COND (other)))
3161 INSN_CACHED_COND (other) = const_true_rtx;
3166 /* If the current insn is conditional, we can't free any
3167 of the lists. */
3168 if (sched_has_condition_p (insn))
3170 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3172 struct deps_reg *reg_last = &deps->reg_last[i];
3173 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3174 false);
3175 add_dependence_list (insn, reg_last->implicit_sets, 0,
3176 REG_DEP_ANTI, false);
3177 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3178 false);
3179 add_dependence_list (insn, reg_last->control_uses, 0,
3180 REG_DEP_CONTROL, false);
3182 if (!deps->readonly)
3184 reg_last->clobbers
3185 = alloc_INSN_LIST (insn, reg_last->clobbers);
3186 reg_last->clobbers_length++;
3189 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3191 struct deps_reg *reg_last = &deps->reg_last[i];
3192 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3193 false);
3194 add_dependence_list (insn, reg_last->implicit_sets, 0,
3195 REG_DEP_ANTI, false);
3196 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3197 false);
3198 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3199 false);
3200 add_dependence_list (insn, reg_last->control_uses, 0,
3201 REG_DEP_CONTROL, false);
3203 if (!deps->readonly)
3204 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3207 else
3209 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3211 struct deps_reg *reg_last = &deps->reg_last[i];
3212 if (reg_last->uses_length >= MAX_PENDING_LIST_LENGTH
3213 || reg_last->clobbers_length >= MAX_PENDING_LIST_LENGTH)
3215 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3216 REG_DEP_OUTPUT, false);
3217 add_dependence_list_and_free (deps, insn,
3218 &reg_last->implicit_sets, 0,
3219 REG_DEP_ANTI, false);
3220 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3221 REG_DEP_ANTI, false);
3222 add_dependence_list_and_free (deps, insn,
3223 &reg_last->control_uses, 0,
3224 REG_DEP_ANTI, false);
3225 add_dependence_list_and_free (deps, insn,
3226 &reg_last->clobbers, 0,
3227 REG_DEP_OUTPUT, false);
3229 if (!deps->readonly)
3231 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3232 reg_last->clobbers_length = 0;
3233 reg_last->uses_length = 0;
3236 else
3238 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3239 false);
3240 add_dependence_list (insn, reg_last->implicit_sets, 0,
3241 REG_DEP_ANTI, false);
3242 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3243 false);
3244 add_dependence_list (insn, reg_last->control_uses, 0,
3245 REG_DEP_CONTROL, false);
3248 if (!deps->readonly)
3250 reg_last->clobbers_length++;
3251 reg_last->clobbers
3252 = alloc_INSN_LIST (insn, reg_last->clobbers);
3255 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3257 struct deps_reg *reg_last = &deps->reg_last[i];
3259 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3260 REG_DEP_OUTPUT, false);
3261 add_dependence_list_and_free (deps, insn,
3262 &reg_last->implicit_sets,
3263 0, REG_DEP_ANTI, false);
3264 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3265 REG_DEP_OUTPUT, false);
3266 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3267 REG_DEP_ANTI, false);
3268 add_dependence_list (insn, reg_last->control_uses, 0,
3269 REG_DEP_CONTROL, false);
3271 if (!deps->readonly)
3273 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3274 reg_last->uses_length = 0;
3275 reg_last->clobbers_length = 0;
3279 if (!deps->readonly)
3281 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3283 struct deps_reg *reg_last = &deps->reg_last[i];
3284 reg_last->control_uses
3285 = alloc_INSN_LIST (insn, reg_last->control_uses);
3290 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3291 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3293 struct deps_reg *reg_last = &deps->reg_last[i];
3294 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3295 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3296 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3297 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3298 false);
3300 if (!deps->readonly)
3301 reg_last->implicit_sets
3302 = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3305 if (!deps->readonly)
3307 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3308 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3309 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3310 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3311 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3312 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3313 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3315 /* Set up the pending barrier found. */
3316 deps->last_reg_pending_barrier = reg_pending_barrier;
3319 CLEAR_REG_SET (reg_pending_uses);
3320 CLEAR_REG_SET (reg_pending_clobbers);
3321 CLEAR_REG_SET (reg_pending_sets);
3322 CLEAR_REG_SET (reg_pending_control_uses);
3323 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3324 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3326 /* Add dependencies if a scheduling barrier was found. */
3327 if (reg_pending_barrier)
3329 /* In the case of barrier the most added dependencies are not
3330 real, so we use anti-dependence here. */
3331 if (sched_has_condition_p (insn))
3333 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3335 struct deps_reg *reg_last = &deps->reg_last[i];
3336 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3337 true);
3338 add_dependence_list (insn, reg_last->sets, 0,
3339 reg_pending_barrier == TRUE_BARRIER
3340 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3341 add_dependence_list (insn, reg_last->implicit_sets, 0,
3342 REG_DEP_ANTI, true);
3343 add_dependence_list (insn, reg_last->clobbers, 0,
3344 reg_pending_barrier == TRUE_BARRIER
3345 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3348 else
3350 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3352 struct deps_reg *reg_last = &deps->reg_last[i];
3353 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3354 REG_DEP_ANTI, true);
3355 add_dependence_list_and_free (deps, insn,
3356 &reg_last->control_uses, 0,
3357 REG_DEP_CONTROL, true);
3358 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3359 reg_pending_barrier == TRUE_BARRIER
3360 ? REG_DEP_TRUE : REG_DEP_ANTI,
3361 true);
3362 add_dependence_list_and_free (deps, insn,
3363 &reg_last->implicit_sets, 0,
3364 REG_DEP_ANTI, true);
3365 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3366 reg_pending_barrier == TRUE_BARRIER
3367 ? REG_DEP_TRUE : REG_DEP_ANTI,
3368 true);
3370 if (!deps->readonly)
3372 reg_last->uses_length = 0;
3373 reg_last->clobbers_length = 0;
3378 if (!deps->readonly)
3379 for (i = 0; i < (unsigned)deps->max_reg; i++)
3381 struct deps_reg *reg_last = &deps->reg_last[i];
3382 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3383 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3386 /* Don't flush pending lists on speculative checks for
3387 selective scheduling. */
3388 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3389 flush_pending_lists (deps, insn, true, true);
3391 reg_pending_barrier = NOT_A_BARRIER;
3394 /* If a post-call group is still open, see if it should remain so.
3395 This insn must be a simple move of a hard reg to a pseudo or
3396 vice-versa.
3398 We must avoid moving these insns for correctness on targets
3399 with small register classes, and for special registers like
3400 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3401 hard regs for all targets. */
3403 if (deps->in_post_call_group_p)
3405 rtx tmp, set = single_set (insn);
3406 int src_regno, dest_regno;
3408 if (set == NULL)
3410 if (DEBUG_INSN_P (insn))
3411 /* We don't want to mark debug insns as part of the same
3412 sched group. We know they really aren't, but if we use
3413 debug insns to tell that a call group is over, we'll
3414 get different code if debug insns are not there and
3415 instructions that follow seem like they should be part
3416 of the call group.
3418 Also, if we did, chain_to_prev_insn would move the
3419 deps of the debug insn to the call insn, modifying
3420 non-debug post-dependency counts of the debug insn
3421 dependencies and otherwise messing with the scheduling
3422 order.
3424 Instead, let such debug insns be scheduled freely, but
3425 keep the call group open in case there are insns that
3426 should be part of it afterwards. Since we grant debug
3427 insns higher priority than even sched group insns, it
3428 will all turn out all right. */
3429 goto debug_dont_end_call_group;
3430 else
3431 goto end_call_group;
3434 tmp = SET_DEST (set);
3435 if (GET_CODE (tmp) == SUBREG)
3436 tmp = SUBREG_REG (tmp);
3437 if (REG_P (tmp))
3438 dest_regno = REGNO (tmp);
3439 else
3440 goto end_call_group;
3442 tmp = SET_SRC (set);
3443 if (GET_CODE (tmp) == SUBREG)
3444 tmp = SUBREG_REG (tmp);
3445 if ((GET_CODE (tmp) == PLUS
3446 || GET_CODE (tmp) == MINUS)
3447 && REG_P (XEXP (tmp, 0))
3448 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3449 && dest_regno == STACK_POINTER_REGNUM)
3450 src_regno = STACK_POINTER_REGNUM;
3451 else if (REG_P (tmp))
3452 src_regno = REGNO (tmp);
3453 else
3454 goto end_call_group;
3456 if (src_regno < FIRST_PSEUDO_REGISTER
3457 || dest_regno < FIRST_PSEUDO_REGISTER)
3459 if (!deps->readonly
3460 && deps->in_post_call_group_p == post_call_initial)
3461 deps->in_post_call_group_p = post_call;
3463 if (!sel_sched_p () || sched_emulate_haifa_p)
3465 SCHED_GROUP_P (insn) = 1;
3466 CANT_MOVE (insn) = 1;
3469 else
3471 end_call_group:
3472 if (!deps->readonly)
3473 deps->in_post_call_group_p = not_post_call;
3477 debug_dont_end_call_group:
3478 if ((current_sched_info->flags & DO_SPECULATION)
3479 && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3480 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3481 be speculated. */
3483 if (sel_sched_p ())
3484 sel_mark_hard_insn (insn);
3485 else
3487 sd_iterator_def sd_it;
3488 dep_t dep;
3490 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3491 sd_iterator_cond (&sd_it, &dep);)
3492 change_spec_dep_to_hard (sd_it);
3496 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3497 honor their original ordering. */
3498 if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3500 if (deps->last_args_size)
3501 add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3502 if (!deps->readonly)
3503 deps->last_args_size = insn;
3506 /* We must not mix prologue and epilogue insns. See PR78029. */
3507 if (prologue_contains (insn))
3509 add_dependence_list (insn, deps->last_epilogue, true, REG_DEP_ANTI, true);
3510 if (!deps->readonly)
3512 if (deps->last_logue_was_epilogue)
3513 free_INSN_LIST_list (&deps->last_prologue);
3514 deps->last_prologue = alloc_INSN_LIST (insn, deps->last_prologue);
3515 deps->last_logue_was_epilogue = false;
3519 if (epilogue_contains (insn))
3521 add_dependence_list (insn, deps->last_prologue, true, REG_DEP_ANTI, true);
3522 if (!deps->readonly)
3524 if (!deps->last_logue_was_epilogue)
3525 free_INSN_LIST_list (&deps->last_epilogue);
3526 deps->last_epilogue = alloc_INSN_LIST (insn, deps->last_epilogue);
3527 deps->last_logue_was_epilogue = true;
3532 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3533 longjmp, loop forever, ...). */
3534 /* FIXME: Why can't this function just use flags_from_decl_or_type and
3535 test for ECF_NORETURN? */
3536 static bool
3537 call_may_noreturn_p (rtx_insn *insn)
3539 rtx call;
3541 /* const or pure calls that aren't looping will always return. */
3542 if (RTL_CONST_OR_PURE_CALL_P (insn)
3543 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3544 return false;
3546 call = get_call_rtx_from (insn);
3547 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3549 rtx symbol = XEXP (XEXP (call, 0), 0);
3550 if (SYMBOL_REF_DECL (symbol)
3551 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3553 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3554 == BUILT_IN_NORMAL)
3555 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3557 case BUILT_IN_BCMP:
3558 case BUILT_IN_BCOPY:
3559 case BUILT_IN_BZERO:
3560 case BUILT_IN_INDEX:
3561 case BUILT_IN_MEMCHR:
3562 case BUILT_IN_MEMCMP:
3563 case BUILT_IN_MEMCPY:
3564 case BUILT_IN_MEMMOVE:
3565 case BUILT_IN_MEMPCPY:
3566 case BUILT_IN_MEMSET:
3567 case BUILT_IN_RINDEX:
3568 case BUILT_IN_STPCPY:
3569 case BUILT_IN_STPNCPY:
3570 case BUILT_IN_STRCAT:
3571 case BUILT_IN_STRCHR:
3572 case BUILT_IN_STRCMP:
3573 case BUILT_IN_STRCPY:
3574 case BUILT_IN_STRCSPN:
3575 case BUILT_IN_STRLEN:
3576 case BUILT_IN_STRNCAT:
3577 case BUILT_IN_STRNCMP:
3578 case BUILT_IN_STRNCPY:
3579 case BUILT_IN_STRPBRK:
3580 case BUILT_IN_STRRCHR:
3581 case BUILT_IN_STRSPN:
3582 case BUILT_IN_STRSTR:
3583 /* Assume certain string/memory builtins always return. */
3584 return false;
3585 default:
3586 break;
3591 /* For all other calls assume that they might not always return. */
3592 return true;
3595 /* Return true if INSN should be made dependent on the previous instruction
3596 group, and if all INSN's dependencies should be moved to the first
3597 instruction of that group. */
3599 static bool
3600 chain_to_prev_insn_p (rtx_insn *insn)
3602 /* INSN forms a group with the previous instruction. */
3603 if (SCHED_GROUP_P (insn))
3604 return true;
3606 /* If the previous instruction clobbers a register R and this one sets
3607 part of R, the clobber was added specifically to help us track the
3608 liveness of R. There's no point scheduling the clobber and leaving
3609 INSN behind, especially if we move the clobber to another block. */
3610 rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
3611 if (prev
3612 && INSN_P (prev)
3613 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3614 && GET_CODE (PATTERN (prev)) == CLOBBER)
3616 rtx x = XEXP (PATTERN (prev), 0);
3617 if (set_of (x, insn))
3618 return true;
3621 return false;
3624 /* Analyze INSN with DEPS as a context. */
3625 void
3626 deps_analyze_insn (struct deps_desc *deps, rtx_insn *insn)
3628 if (sched_deps_info->start_insn)
3629 sched_deps_info->start_insn (insn);
3631 /* Record the condition for this insn. */
3632 if (NONDEBUG_INSN_P (insn))
3634 rtx t;
3635 sched_get_condition_with_rev (insn, NULL);
3636 t = INSN_CACHED_COND (insn);
3637 INSN_COND_DEPS (insn) = NULL;
3638 if (reload_completed
3639 && (current_sched_info->flags & DO_PREDICATION)
3640 && COMPARISON_P (t)
3641 && REG_P (XEXP (t, 0))
3642 && CONSTANT_P (XEXP (t, 1)))
3644 unsigned int regno;
3645 int nregs;
3646 rtx_insn_list *cond_deps = NULL;
3647 t = XEXP (t, 0);
3648 regno = REGNO (t);
3649 nregs = REG_NREGS (t);
3650 while (nregs-- > 0)
3652 struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3653 cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3654 cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3655 cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3657 INSN_COND_DEPS (insn) = cond_deps;
3661 if (JUMP_P (insn))
3663 /* Make each JUMP_INSN (but not a speculative check)
3664 a scheduling barrier for memory references. */
3665 if (!deps->readonly
3666 && !(sel_sched_p ()
3667 && sel_insn_is_speculation_check (insn)))
3669 /* Keep the list a reasonable size. */
3670 if (deps->pending_flush_length++ >= MAX_PENDING_LIST_LENGTH)
3671 flush_pending_lists (deps, insn, true, true);
3672 else
3673 deps->pending_jump_insns
3674 = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3677 /* For each insn which shouldn't cross a jump, add a dependence. */
3678 add_dependence_list_and_free (deps, insn,
3679 &deps->sched_before_next_jump, 1,
3680 REG_DEP_ANTI, true);
3682 sched_analyze_insn (deps, PATTERN (insn), insn);
3684 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3686 sched_analyze_insn (deps, PATTERN (insn), insn);
3688 else if (CALL_P (insn))
3690 int i;
3692 CANT_MOVE (insn) = 1;
3694 if (find_reg_note (insn, REG_SETJMP, NULL))
3696 /* This is setjmp. Assume that all registers, not just
3697 hard registers, may be clobbered by this call. */
3698 reg_pending_barrier = MOVE_BARRIER;
3700 else
3702 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3703 /* A call may read and modify global register variables. */
3704 if (global_regs[i])
3706 SET_REGNO_REG_SET (reg_pending_sets, i);
3707 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3709 /* Other call-clobbered hard regs may be clobbered.
3710 Since we only have a choice between 'might be clobbered'
3711 and 'definitely not clobbered', we must include all
3712 partly call-clobbered registers here. */
3713 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3714 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3715 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3716 /* We don't know what set of fixed registers might be used
3717 by the function, but it is certain that the stack pointer
3718 is among them, but be conservative. */
3719 else if (fixed_regs[i])
3720 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3721 /* The frame pointer is normally not used by the function
3722 itself, but by the debugger. */
3723 /* ??? MIPS o32 is an exception. It uses the frame pointer
3724 in the macro expansion of jal but does not represent this
3725 fact in the call_insn rtl. */
3726 else if (i == FRAME_POINTER_REGNUM
3727 || (i == HARD_FRAME_POINTER_REGNUM
3728 && (! reload_completed || frame_pointer_needed)))
3729 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3732 /* For each insn which shouldn't cross a call, add a dependence
3733 between that insn and this call insn. */
3734 add_dependence_list_and_free (deps, insn,
3735 &deps->sched_before_next_call, 1,
3736 REG_DEP_ANTI, true);
3738 sched_analyze_insn (deps, PATTERN (insn), insn);
3740 /* If CALL would be in a sched group, then this will violate
3741 convention that sched group insns have dependencies only on the
3742 previous instruction.
3744 Of course one can say: "Hey! What about head of the sched group?"
3745 And I will answer: "Basic principles (one dep per insn) are always
3746 the same." */
3747 gcc_assert (!SCHED_GROUP_P (insn));
3749 /* In the absence of interprocedural alias analysis, we must flush
3750 all pending reads and writes, and start new dependencies starting
3751 from here. But only flush writes for constant calls (which may
3752 be passed a pointer to something we haven't written yet). */
3753 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3755 if (!deps->readonly)
3757 /* Remember the last function call for limiting lifetimes. */
3758 free_INSN_LIST_list (&deps->last_function_call);
3759 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3761 if (call_may_noreturn_p (insn))
3763 /* Remember the last function call that might not always return
3764 normally for limiting moves of trapping insns. */
3765 free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3766 deps->last_function_call_may_noreturn
3767 = alloc_INSN_LIST (insn, NULL_RTX);
3770 /* Before reload, begin a post-call group, so as to keep the
3771 lifetimes of hard registers correct. */
3772 if (! reload_completed)
3773 deps->in_post_call_group_p = post_call;
3777 if (sched_deps_info->use_cselib)
3778 cselib_process_insn (insn);
3780 if (sched_deps_info->finish_insn)
3781 sched_deps_info->finish_insn ();
3783 /* Fixup the dependencies in the sched group. */
3784 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3785 && chain_to_prev_insn_p (insn)
3786 && !sel_sched_p ())
3787 chain_to_prev_insn (insn);
3790 /* Initialize DEPS for the new block beginning with HEAD. */
3791 void
3792 deps_start_bb (struct deps_desc *deps, rtx_insn *head)
3794 gcc_assert (!deps->readonly);
3796 /* Before reload, if the previous block ended in a call, show that
3797 we are inside a post-call group, so as to keep the lifetimes of
3798 hard registers correct. */
3799 if (! reload_completed && !LABEL_P (head))
3801 rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3803 if (insn && CALL_P (insn))
3804 deps->in_post_call_group_p = post_call_initial;
3808 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3809 dependencies for each insn. */
3810 void
3811 sched_analyze (struct deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3813 rtx_insn *insn;
3815 if (sched_deps_info->use_cselib)
3816 cselib_init (CSELIB_RECORD_MEMORY);
3818 deps_start_bb (deps, head);
3820 for (insn = head;; insn = NEXT_INSN (insn))
3823 if (INSN_P (insn))
3825 /* And initialize deps_lists. */
3826 sd_init_insn (insn);
3827 /* Clean up SCHED_GROUP_P which may be set by last
3828 scheduler pass. */
3829 if (SCHED_GROUP_P (insn))
3830 SCHED_GROUP_P (insn) = 0;
3833 deps_analyze_insn (deps, insn);
3835 if (insn == tail)
3837 if (sched_deps_info->use_cselib)
3838 cselib_finish ();
3839 return;
3842 gcc_unreachable ();
3845 /* Helper for sched_free_deps ().
3846 Delete INSN's (RESOLVED_P) backward dependencies. */
3847 static void
3848 delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p)
3850 sd_iterator_def sd_it;
3851 dep_t dep;
3852 sd_list_types_def types;
3854 if (resolved_p)
3855 types = SD_LIST_RES_BACK;
3856 else
3857 types = SD_LIST_BACK;
3859 for (sd_it = sd_iterator_start (insn, types);
3860 sd_iterator_cond (&sd_it, &dep);)
3862 dep_link_t link = *sd_it.linkp;
3863 dep_node_t node = DEP_LINK_NODE (link);
3864 deps_list_t back_list;
3865 deps_list_t forw_list;
3867 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3868 remove_from_deps_list (link, back_list);
3869 delete_dep_node (node);
3873 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3874 deps_lists. */
3875 void
3876 sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
3878 rtx_insn *insn;
3879 rtx_insn *next_tail = NEXT_INSN (tail);
3881 /* We make two passes since some insns may be scheduled before their
3882 dependencies are resolved. */
3883 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3884 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3886 /* Clear forward deps and leave the dep_nodes to the
3887 corresponding back_deps list. */
3888 if (resolved_p)
3889 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3890 else
3891 clear_deps_list (INSN_FORW_DEPS (insn));
3893 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3894 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3896 /* Clear resolved back deps together with its dep_nodes. */
3897 delete_dep_nodes_in_back_deps (insn, resolved_p);
3899 sd_finish_insn (insn);
3903 /* Initialize variables for region data dependence analysis.
3904 When LAZY_REG_LAST is true, do not allocate reg_last array
3905 of struct deps_desc immediately. */
3907 void
3908 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3910 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3912 deps->max_reg = max_reg;
3913 if (lazy_reg_last)
3914 deps->reg_last = NULL;
3915 else
3916 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3917 INIT_REG_SET (&deps->reg_last_in_use);
3919 deps->pending_read_insns = 0;
3920 deps->pending_read_mems = 0;
3921 deps->pending_write_insns = 0;
3922 deps->pending_write_mems = 0;
3923 deps->pending_jump_insns = 0;
3924 deps->pending_read_list_length = 0;
3925 deps->pending_write_list_length = 0;
3926 deps->pending_flush_length = 0;
3927 deps->last_pending_memory_flush = 0;
3928 deps->last_function_call = 0;
3929 deps->last_function_call_may_noreturn = 0;
3930 deps->sched_before_next_call = 0;
3931 deps->sched_before_next_jump = 0;
3932 deps->in_post_call_group_p = not_post_call;
3933 deps->last_debug_insn = 0;
3934 deps->last_args_size = 0;
3935 deps->last_prologue = 0;
3936 deps->last_epilogue = 0;
3937 deps->last_logue_was_epilogue = false;
3938 deps->last_reg_pending_barrier = NOT_A_BARRIER;
3939 deps->readonly = 0;
3942 /* Init only reg_last field of DEPS, which was not allocated before as
3943 we inited DEPS lazily. */
3944 void
3945 init_deps_reg_last (struct deps_desc *deps)
3947 gcc_assert (deps && deps->max_reg > 0);
3948 gcc_assert (deps->reg_last == NULL);
3950 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3954 /* Free insn lists found in DEPS. */
3956 void
3957 free_deps (struct deps_desc *deps)
3959 unsigned i;
3960 reg_set_iterator rsi;
3962 /* We set max_reg to 0 when this context was already freed. */
3963 if (deps->max_reg == 0)
3965 gcc_assert (deps->reg_last == NULL);
3966 return;
3968 deps->max_reg = 0;
3970 free_INSN_LIST_list (&deps->pending_read_insns);
3971 free_EXPR_LIST_list (&deps->pending_read_mems);
3972 free_INSN_LIST_list (&deps->pending_write_insns);
3973 free_EXPR_LIST_list (&deps->pending_write_mems);
3974 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3976 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3977 times. For a testcase with 42000 regs and 8000 small basic blocks,
3978 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3979 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3981 struct deps_reg *reg_last = &deps->reg_last[i];
3982 if (reg_last->uses)
3983 free_INSN_LIST_list (&reg_last->uses);
3984 if (reg_last->sets)
3985 free_INSN_LIST_list (&reg_last->sets);
3986 if (reg_last->implicit_sets)
3987 free_INSN_LIST_list (&reg_last->implicit_sets);
3988 if (reg_last->control_uses)
3989 free_INSN_LIST_list (&reg_last->control_uses);
3990 if (reg_last->clobbers)
3991 free_INSN_LIST_list (&reg_last->clobbers);
3993 CLEAR_REG_SET (&deps->reg_last_in_use);
3995 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3996 it at all. */
3997 free (deps->reg_last);
3998 deps->reg_last = NULL;
4000 deps = NULL;
4003 /* Remove INSN from dependence contexts DEPS. */
4004 void
4005 remove_from_deps (struct deps_desc *deps, rtx_insn *insn)
4007 int removed;
4008 unsigned i;
4009 reg_set_iterator rsi;
4011 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4012 &deps->pending_read_mems);
4013 if (!DEBUG_INSN_P (insn))
4014 deps->pending_read_list_length -= removed;
4015 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4016 &deps->pending_write_mems);
4017 deps->pending_write_list_length -= removed;
4019 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4020 deps->pending_flush_length -= removed;
4021 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4022 deps->pending_flush_length -= removed;
4024 unsigned to_clear = -1U;
4025 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4027 if (to_clear != -1U)
4029 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4030 to_clear = -1U;
4032 struct deps_reg *reg_last = &deps->reg_last[i];
4033 if (reg_last->uses)
4034 remove_from_dependence_list (insn, &reg_last->uses);
4035 if (reg_last->sets)
4036 remove_from_dependence_list (insn, &reg_last->sets);
4037 if (reg_last->implicit_sets)
4038 remove_from_dependence_list (insn, &reg_last->implicit_sets);
4039 if (reg_last->clobbers)
4040 remove_from_dependence_list (insn, &reg_last->clobbers);
4041 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4042 && !reg_last->clobbers)
4043 to_clear = i;
4045 if (to_clear != -1U)
4046 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4048 if (CALL_P (insn))
4050 remove_from_dependence_list (insn, &deps->last_function_call);
4051 remove_from_dependence_list (insn,
4052 &deps->last_function_call_may_noreturn);
4054 remove_from_dependence_list (insn, &deps->sched_before_next_call);
4057 /* Init deps data vector. */
4058 static void
4059 init_deps_data_vector (void)
4061 int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4062 if (reserve > 0 && ! h_d_i_d.space (reserve))
4063 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
4066 /* If it is profitable to use them, initialize or extend (depending on
4067 GLOBAL_P) dependency data. */
4068 void
4069 sched_deps_init (bool global_p)
4071 /* Average number of insns in the basic block.
4072 '+ 1' is used to make it nonzero. */
4073 int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4075 init_deps_data_vector ();
4077 /* We use another caching mechanism for selective scheduling, so
4078 we don't use this one. */
4079 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4081 /* ?!? We could save some memory by computing a per-region luid mapping
4082 which could reduce both the number of vectors in the cache and the
4083 size of each vector. Instead we just avoid the cache entirely unless
4084 the average number of instructions in a basic block is very high. See
4085 the comment before the declaration of true_dependency_cache for
4086 what we consider "very high". */
4087 cache_size = 0;
4088 extend_dependency_caches (sched_max_luid, true);
4091 if (global_p)
4093 dl_pool = new object_allocator<_deps_list> ("deps_list");
4094 /* Allocate lists for one block at a time. */
4095 dn_pool = new object_allocator<_dep_node> ("dep_node");
4096 /* Allocate nodes for one block at a time. */
4101 /* Create or extend (depending on CREATE_P) dependency caches to
4102 size N. */
4103 void
4104 extend_dependency_caches (int n, bool create_p)
4106 if (create_p || true_dependency_cache)
4108 int i, luid = cache_size + n;
4110 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4111 luid);
4112 output_dependency_cache = XRESIZEVEC (bitmap_head,
4113 output_dependency_cache, luid);
4114 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4115 luid);
4116 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4117 luid);
4119 if (current_sched_info->flags & DO_SPECULATION)
4120 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4121 luid);
4123 for (i = cache_size; i < luid; i++)
4125 bitmap_initialize (&true_dependency_cache[i], 0);
4126 bitmap_initialize (&output_dependency_cache[i], 0);
4127 bitmap_initialize (&anti_dependency_cache[i], 0);
4128 bitmap_initialize (&control_dependency_cache[i], 0);
4130 if (current_sched_info->flags & DO_SPECULATION)
4131 bitmap_initialize (&spec_dependency_cache[i], 0);
4133 cache_size = luid;
4137 /* Finalize dependency information for the whole function. */
4138 void
4139 sched_deps_finish (void)
4141 gcc_assert (deps_pools_are_empty_p ());
4142 delete dn_pool;
4143 delete dl_pool;
4144 dn_pool = NULL;
4145 dl_pool = NULL;
4147 h_d_i_d.release ();
4148 cache_size = 0;
4150 if (true_dependency_cache)
4152 int i;
4154 for (i = 0; i < cache_size; i++)
4156 bitmap_clear (&true_dependency_cache[i]);
4157 bitmap_clear (&output_dependency_cache[i]);
4158 bitmap_clear (&anti_dependency_cache[i]);
4159 bitmap_clear (&control_dependency_cache[i]);
4161 if (sched_deps_info->generate_spec_deps)
4162 bitmap_clear (&spec_dependency_cache[i]);
4164 free (true_dependency_cache);
4165 true_dependency_cache = NULL;
4166 free (output_dependency_cache);
4167 output_dependency_cache = NULL;
4168 free (anti_dependency_cache);
4169 anti_dependency_cache = NULL;
4170 free (control_dependency_cache);
4171 control_dependency_cache = NULL;
4173 if (sched_deps_info->generate_spec_deps)
4175 free (spec_dependency_cache);
4176 spec_dependency_cache = NULL;
4182 /* Initialize some global variables needed by the dependency analysis
4183 code. */
4185 void
4186 init_deps_global (void)
4188 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4189 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4190 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4191 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4192 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4193 reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4194 reg_pending_barrier = NOT_A_BARRIER;
4196 if (!sel_sched_p () || sched_emulate_haifa_p)
4198 sched_deps_info->start_insn = haifa_start_insn;
4199 sched_deps_info->finish_insn = haifa_finish_insn;
4201 sched_deps_info->note_reg_set = haifa_note_reg_set;
4202 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4203 sched_deps_info->note_reg_use = haifa_note_reg_use;
4205 sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4206 sched_deps_info->note_dep = haifa_note_dep;
4210 /* Free everything used by the dependency analysis code. */
4212 void
4213 finish_deps_global (void)
4215 FREE_REG_SET (reg_pending_sets);
4216 FREE_REG_SET (reg_pending_clobbers);
4217 FREE_REG_SET (reg_pending_uses);
4218 FREE_REG_SET (reg_pending_control_uses);
4221 /* Estimate the weakness of dependence between MEM1 and MEM2. */
4222 dw_t
4223 estimate_dep_weak (rtx mem1, rtx mem2)
4225 if (mem1 == mem2)
4226 /* MEMs are the same - don't speculate. */
4227 return MIN_DEP_WEAK;
4229 rtx r1 = XEXP (mem1, 0);
4230 rtx r2 = XEXP (mem2, 0);
4232 if (sched_deps_info->use_cselib)
4234 /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be
4235 dangling at this point, since we never preserve them. Instead we
4236 canonicalize manually to get stable VALUEs out of hashing. */
4237 if (GET_CODE (r1) == VALUE && CSELIB_VAL_PTR (r1))
4238 r1 = canonical_cselib_val (CSELIB_VAL_PTR (r1))->val_rtx;
4239 if (GET_CODE (r2) == VALUE && CSELIB_VAL_PTR (r2))
4240 r2 = canonical_cselib_val (CSELIB_VAL_PTR (r2))->val_rtx;
4243 if (r1 == r2
4244 || (REG_P (r1) && REG_P (r2) && REGNO (r1) == REGNO (r2)))
4245 /* Again, MEMs are the same. */
4246 return MIN_DEP_WEAK;
4247 else if ((REG_P (r1) && !REG_P (r2)) || (!REG_P (r1) && REG_P (r2)))
4248 /* Different addressing modes - reason to be more speculative,
4249 than usual. */
4250 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4251 else
4252 /* We can't say anything about the dependence. */
4253 return UNCERTAIN_DEP_WEAK;
4256 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4257 This function can handle same INSN and ELEM (INSN == ELEM).
4258 It is a convenience wrapper. */
4259 static void
4260 add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4262 ds_t ds;
4263 bool internal;
4265 if (dep_type == REG_DEP_TRUE)
4266 ds = DEP_TRUE;
4267 else if (dep_type == REG_DEP_OUTPUT)
4268 ds = DEP_OUTPUT;
4269 else if (dep_type == REG_DEP_CONTROL)
4270 ds = DEP_CONTROL;
4271 else
4273 gcc_assert (dep_type == REG_DEP_ANTI);
4274 ds = DEP_ANTI;
4277 /* When add_dependence is called from inside sched-deps.c, we expect
4278 cur_insn to be non-null. */
4279 internal = cur_insn != NULL;
4280 if (internal)
4281 gcc_assert (insn == cur_insn);
4282 else
4283 cur_insn = insn;
4285 note_dep (elem, ds);
4286 if (!internal)
4287 cur_insn = NULL;
4290 /* Return weakness of speculative type TYPE in the dep_status DS,
4291 without checking to prevent ICEs on malformed input. */
4292 static dw_t
4293 get_dep_weak_1 (ds_t ds, ds_t type)
4295 ds = ds & type;
4297 switch (type)
4299 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4300 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4301 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4302 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4303 default: gcc_unreachable ();
4306 return (dw_t) ds;
4309 /* Return weakness of speculative type TYPE in the dep_status DS. */
4310 dw_t
4311 get_dep_weak (ds_t ds, ds_t type)
4313 dw_t dw = get_dep_weak_1 (ds, type);
4315 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4316 return dw;
4319 /* Return the dep_status, which has the same parameters as DS, except for
4320 speculative type TYPE, that will have weakness DW. */
4321 ds_t
4322 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4324 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4326 ds &= ~type;
4327 switch (type)
4329 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4330 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4331 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4332 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4333 default: gcc_unreachable ();
4335 return ds;
4338 /* Return the join of two dep_statuses DS1 and DS2.
4339 If MAX_P is true then choose the greater probability,
4340 otherwise multiply probabilities.
4341 This function assumes that both DS1 and DS2 contain speculative bits. */
4342 static ds_t
4343 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4345 ds_t ds, t;
4347 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4349 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4351 t = FIRST_SPEC_TYPE;
4354 if ((ds1 & t) && !(ds2 & t))
4355 ds |= ds1 & t;
4356 else if (!(ds1 & t) && (ds2 & t))
4357 ds |= ds2 & t;
4358 else if ((ds1 & t) && (ds2 & t))
4360 dw_t dw1 = get_dep_weak (ds1, t);
4361 dw_t dw2 = get_dep_weak (ds2, t);
4362 ds_t dw;
4364 if (!max_p)
4366 dw = ((ds_t) dw1) * ((ds_t) dw2);
4367 dw /= MAX_DEP_WEAK;
4368 if (dw < MIN_DEP_WEAK)
4369 dw = MIN_DEP_WEAK;
4371 else
4373 if (dw1 >= dw2)
4374 dw = dw1;
4375 else
4376 dw = dw2;
4379 ds = set_dep_weak (ds, t, (dw_t) dw);
4382 if (t == LAST_SPEC_TYPE)
4383 break;
4384 t <<= SPEC_TYPE_SHIFT;
4386 while (1);
4388 return ds;
4391 /* Return the join of two dep_statuses DS1 and DS2.
4392 This function assumes that both DS1 and DS2 contain speculative bits. */
4393 ds_t
4394 ds_merge (ds_t ds1, ds_t ds2)
4396 return ds_merge_1 (ds1, ds2, false);
4399 /* Return the join of two dep_statuses DS1 and DS2. */
4400 ds_t
4401 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4403 ds_t new_status = ds | ds2;
4405 if (new_status & SPECULATIVE)
4407 if ((ds && !(ds & SPECULATIVE))
4408 || (ds2 && !(ds2 & SPECULATIVE)))
4409 /* Then this dep can't be speculative. */
4410 new_status &= ~SPECULATIVE;
4411 else
4413 /* Both are speculative. Merging probabilities. */
4414 if (mem1)
4416 dw_t dw;
4418 dw = estimate_dep_weak (mem1, mem2);
4419 ds = set_dep_weak (ds, BEGIN_DATA, dw);
4422 if (!ds)
4423 new_status = ds2;
4424 else if (!ds2)
4425 new_status = ds;
4426 else
4427 new_status = ds_merge (ds2, ds);
4431 return new_status;
4434 /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4435 probabilities. */
4436 ds_t
4437 ds_max_merge (ds_t ds1, ds_t ds2)
4439 if (ds1 == 0 && ds2 == 0)
4440 return 0;
4442 if (ds1 == 0 && ds2 != 0)
4443 return ds2;
4445 if (ds1 != 0 && ds2 == 0)
4446 return ds1;
4448 return ds_merge_1 (ds1, ds2, true);
4451 /* Return the probability of speculation success for the speculation
4452 status DS. */
4453 dw_t
4454 ds_weak (ds_t ds)
4456 ds_t res = 1, dt;
4457 int n = 0;
4459 dt = FIRST_SPEC_TYPE;
4462 if (ds & dt)
4464 res *= (ds_t) get_dep_weak (ds, dt);
4465 n++;
4468 if (dt == LAST_SPEC_TYPE)
4469 break;
4470 dt <<= SPEC_TYPE_SHIFT;
4472 while (1);
4474 gcc_assert (n);
4475 while (--n)
4476 res /= MAX_DEP_WEAK;
4478 if (res < MIN_DEP_WEAK)
4479 res = MIN_DEP_WEAK;
4481 gcc_assert (res <= MAX_DEP_WEAK);
4483 return (dw_t) res;
4486 /* Return a dep status that contains all speculation types of DS. */
4487 ds_t
4488 ds_get_speculation_types (ds_t ds)
4490 if (ds & BEGIN_DATA)
4491 ds |= BEGIN_DATA;
4492 if (ds & BE_IN_DATA)
4493 ds |= BE_IN_DATA;
4494 if (ds & BEGIN_CONTROL)
4495 ds |= BEGIN_CONTROL;
4496 if (ds & BE_IN_CONTROL)
4497 ds |= BE_IN_CONTROL;
4499 return ds & SPECULATIVE;
4502 /* Return a dep status that contains maximal weakness for each speculation
4503 type present in DS. */
4504 ds_t
4505 ds_get_max_dep_weak (ds_t ds)
4507 if (ds & BEGIN_DATA)
4508 ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4509 if (ds & BE_IN_DATA)
4510 ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4511 if (ds & BEGIN_CONTROL)
4512 ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4513 if (ds & BE_IN_CONTROL)
4514 ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4516 return ds;
4519 /* Dump information about the dependence status S. */
4520 static void
4521 dump_ds (FILE *f, ds_t s)
4523 fprintf (f, "{");
4525 if (s & BEGIN_DATA)
4526 fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4527 if (s & BE_IN_DATA)
4528 fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4529 if (s & BEGIN_CONTROL)
4530 fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4531 if (s & BE_IN_CONTROL)
4532 fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4534 if (s & HARD_DEP)
4535 fprintf (f, "HARD_DEP; ");
4537 if (s & DEP_TRUE)
4538 fprintf (f, "DEP_TRUE; ");
4539 if (s & DEP_OUTPUT)
4540 fprintf (f, "DEP_OUTPUT; ");
4541 if (s & DEP_ANTI)
4542 fprintf (f, "DEP_ANTI; ");
4543 if (s & DEP_CONTROL)
4544 fprintf (f, "DEP_CONTROL; ");
4546 fprintf (f, "}");
4549 DEBUG_FUNCTION void
4550 debug_ds (ds_t s)
4552 dump_ds (stderr, s);
4553 fprintf (stderr, "\n");
4556 /* Verify that dependence type and status are consistent.
4557 If RELAXED_P is true, then skip dep_weakness checks. */
4558 static void
4559 check_dep (dep_t dep, bool relaxed_p)
4561 enum reg_note dt = DEP_TYPE (dep);
4562 ds_t ds = DEP_STATUS (dep);
4564 gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4566 if (!(current_sched_info->flags & USE_DEPS_LIST))
4568 gcc_assert (ds == 0);
4569 return;
4572 /* Check that dependence type contains the same bits as the status. */
4573 if (dt == REG_DEP_TRUE)
4574 gcc_assert (ds & DEP_TRUE);
4575 else if (dt == REG_DEP_OUTPUT)
4576 gcc_assert ((ds & DEP_OUTPUT)
4577 && !(ds & DEP_TRUE));
4578 else if (dt == REG_DEP_ANTI)
4579 gcc_assert ((ds & DEP_ANTI)
4580 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4581 else
4582 gcc_assert (dt == REG_DEP_CONTROL
4583 && (ds & DEP_CONTROL)
4584 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4586 /* HARD_DEP can not appear in dep_status of a link. */
4587 gcc_assert (!(ds & HARD_DEP));
4589 /* Check that dependence status is set correctly when speculation is not
4590 supported. */
4591 if (!sched_deps_info->generate_spec_deps)
4592 gcc_assert (!(ds & SPECULATIVE));
4593 else if (ds & SPECULATIVE)
4595 if (!relaxed_p)
4597 ds_t type = FIRST_SPEC_TYPE;
4599 /* Check that dependence weakness is in proper range. */
4602 if (ds & type)
4603 get_dep_weak (ds, type);
4605 if (type == LAST_SPEC_TYPE)
4606 break;
4607 type <<= SPEC_TYPE_SHIFT;
4609 while (1);
4612 if (ds & BEGIN_SPEC)
4614 /* Only true dependence can be data speculative. */
4615 if (ds & BEGIN_DATA)
4616 gcc_assert (ds & DEP_TRUE);
4618 /* Control dependencies in the insn scheduler are represented by
4619 anti-dependencies, therefore only anti dependence can be
4620 control speculative. */
4621 if (ds & BEGIN_CONTROL)
4622 gcc_assert (ds & DEP_ANTI);
4624 else
4626 /* Subsequent speculations should resolve true dependencies. */
4627 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4630 /* Check that true and anti dependencies can't have other speculative
4631 statuses. */
4632 if (ds & DEP_TRUE)
4633 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4634 /* An output dependence can't be speculative at all. */
4635 gcc_assert (!(ds & DEP_OUTPUT));
4636 if (ds & DEP_ANTI)
4637 gcc_assert (ds & BEGIN_CONTROL);
4641 /* The following code discovers opportunities to switch a memory reference
4642 and an increment by modifying the address. We ensure that this is done
4643 only for dependencies that are only used to show a single register
4644 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4645 instruction involved is subject to only one dep that can cause a pattern
4646 change.
4648 When we discover a suitable dependency, we fill in the dep_replacement
4649 structure to show how to modify the memory reference. */
4651 /* Holds information about a pair of memory reference and register increment
4652 insns which depend on each other, but could possibly be interchanged. */
4653 struct mem_inc_info
4655 rtx_insn *inc_insn;
4656 rtx_insn *mem_insn;
4658 rtx *mem_loc;
4659 /* A register occurring in the memory address for which we wish to break
4660 the dependence. This must be identical to the destination register of
4661 the increment. */
4662 rtx mem_reg0;
4663 /* Any kind of index that is added to that register. */
4664 rtx mem_index;
4665 /* The constant offset used in the memory address. */
4666 HOST_WIDE_INT mem_constant;
4667 /* The constant added in the increment insn. Negated if the increment is
4668 after the memory address. */
4669 HOST_WIDE_INT inc_constant;
4670 /* The source register used in the increment. May be different from mem_reg0
4671 if the increment occurs before the memory address. */
4672 rtx inc_input;
4675 /* Verify that the memory location described in MII can be replaced with
4676 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4677 insn remains unchanged by this function. */
4679 static rtx
4680 attempt_change (struct mem_inc_info *mii, rtx new_addr)
4682 rtx mem = *mii->mem_loc;
4683 rtx new_mem;
4685 /* Jump through a lot of hoops to keep the attributes up to date. We
4686 do not want to call one of the change address variants that take
4687 an offset even though we know the offset in many cases. These
4688 assume you are changing where the address is pointing by the
4689 offset. */
4690 new_mem = replace_equiv_address_nv (mem, new_addr);
4691 if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4693 if (sched_verbose >= 5)
4694 fprintf (sched_dump, "validation failure\n");
4695 return NULL_RTX;
4698 /* Put back the old one. */
4699 validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4701 return new_mem;
4704 /* Return true if INSN is of a form "a = b op c" where a and b are
4705 regs. op is + if c is a reg and +|- if c is a const. Fill in
4706 informantion in MII about what is found.
4707 BEFORE_MEM indicates whether the increment is found before or after
4708 a corresponding memory reference. */
4710 static bool
4711 parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem)
4713 rtx pat = single_set (insn);
4714 rtx src, cst;
4715 bool regs_equal;
4717 if (RTX_FRAME_RELATED_P (insn) || !pat)
4718 return false;
4720 /* Result must be single reg. */
4721 if (!REG_P (SET_DEST (pat)))
4722 return false;
4724 if (GET_CODE (SET_SRC (pat)) != PLUS)
4725 return false;
4727 mii->inc_insn = insn;
4728 src = SET_SRC (pat);
4729 mii->inc_input = XEXP (src, 0);
4731 if (!REG_P (XEXP (src, 0)))
4732 return false;
4734 if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4735 return false;
4737 cst = XEXP (src, 1);
4738 if (!CONST_INT_P (cst))
4739 return false;
4740 mii->inc_constant = INTVAL (cst);
4742 regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4744 if (!before_mem)
4746 mii->inc_constant = -mii->inc_constant;
4747 if (!regs_equal)
4748 return false;
4751 if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4753 /* Note that the sign has already been reversed for !before_mem. */
4754 if (STACK_GROWS_DOWNWARD)
4755 return mii->inc_constant > 0;
4756 else
4757 return mii->inc_constant < 0;
4759 return true;
4762 /* Once a suitable mem reference has been found and the corresponding data
4763 in MII has been filled in, this function is called to find a suitable
4764 add or inc insn involving the register we found in the memory
4765 reference. */
4767 static bool
4768 find_inc (struct mem_inc_info *mii, bool backwards)
4770 sd_iterator_def sd_it;
4771 dep_t dep;
4773 sd_it = sd_iterator_start (mii->mem_insn,
4774 backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW);
4775 while (sd_iterator_cond (&sd_it, &dep))
4777 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
4778 rtx_insn *pro = DEP_PRO (dep);
4779 rtx_insn *con = DEP_CON (dep);
4780 rtx_insn *inc_cand = backwards ? pro : con;
4781 if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
4782 goto next;
4783 if (parse_add_or_inc (mii, inc_cand, backwards))
4785 struct dep_replacement *desc;
4786 df_ref def;
4787 rtx newaddr, newmem;
4789 if (sched_verbose >= 5)
4790 fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
4791 INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
4793 /* Need to assure that none of the operands of the inc
4794 instruction are assigned to by the mem insn. */
4795 FOR_EACH_INSN_DEF (def, mii->mem_insn)
4796 if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
4797 || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
4799 if (sched_verbose >= 5)
4800 fprintf (sched_dump,
4801 "inc conflicts with store failure.\n");
4802 goto next;
4805 newaddr = mii->inc_input;
4806 if (mii->mem_index != NULL_RTX)
4807 newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
4808 mii->mem_index);
4809 newaddr = plus_constant (GET_MODE (newaddr), newaddr,
4810 mii->mem_constant + mii->inc_constant);
4811 newmem = attempt_change (mii, newaddr);
4812 if (newmem == NULL_RTX)
4813 goto next;
4814 if (sched_verbose >= 5)
4815 fprintf (sched_dump, "successful address replacement\n");
4816 desc = XCNEW (struct dep_replacement);
4817 DEP_REPLACE (dep) = desc;
4818 desc->loc = mii->mem_loc;
4819 desc->newval = newmem;
4820 desc->orig = *desc->loc;
4821 desc->insn = mii->mem_insn;
4822 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
4823 INSN_SPEC_BACK_DEPS (con));
4824 if (backwards)
4826 FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
4827 add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
4828 REG_DEP_TRUE);
4830 else
4832 FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
4833 add_dependence_1 (DEP_CON (dep), mii->mem_insn,
4834 REG_DEP_ANTI);
4836 return true;
4838 next:
4839 sd_iterator_next (&sd_it);
4841 return false;
4844 /* A recursive function that walks ADDRESS_OF_X to find memory references
4845 which could be modified during scheduling. We call find_inc for each
4846 one we find that has a recognizable form. MII holds information about
4847 the pair of memory/increment instructions.
4848 We ensure that every instruction with a memory reference (which will be
4849 the location of the replacement) is assigned at most one breakable
4850 dependency. */
4852 static bool
4853 find_mem (struct mem_inc_info *mii, rtx *address_of_x)
4855 rtx x = *address_of_x;
4856 enum rtx_code code = GET_CODE (x);
4857 const char *const fmt = GET_RTX_FORMAT (code);
4858 int i;
4860 if (code == MEM)
4862 rtx reg0 = XEXP (x, 0);
4864 mii->mem_loc = address_of_x;
4865 mii->mem_index = NULL_RTX;
4866 mii->mem_constant = 0;
4867 if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
4869 mii->mem_constant = INTVAL (XEXP (reg0, 1));
4870 reg0 = XEXP (reg0, 0);
4872 if (GET_CODE (reg0) == PLUS)
4874 mii->mem_index = XEXP (reg0, 1);
4875 reg0 = XEXP (reg0, 0);
4877 if (REG_P (reg0))
4879 df_ref use;
4880 int occurrences = 0;
4882 /* Make sure this reg appears only once in this insn. Can't use
4883 count_occurrences since that only works for pseudos. */
4884 FOR_EACH_INSN_USE (use, mii->mem_insn)
4885 if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use)))
4886 if (++occurrences > 1)
4888 if (sched_verbose >= 5)
4889 fprintf (sched_dump, "mem count failure\n");
4890 return false;
4893 mii->mem_reg0 = reg0;
4894 return find_inc (mii, true) || find_inc (mii, false);
4896 return false;
4899 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4901 /* If REG occurs inside a MEM used in a bit-field reference,
4902 that is unacceptable. */
4903 return false;
4906 /* Time for some deep diving. */
4907 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4909 if (fmt[i] == 'e')
4911 if (find_mem (mii, &XEXP (x, i)))
4912 return true;
4914 else if (fmt[i] == 'E')
4916 int j;
4917 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4918 if (find_mem (mii, &XVECEXP (x, i, j)))
4919 return true;
4922 return false;
4926 /* Examine the instructions between HEAD and TAIL and try to find
4927 dependencies that can be broken by modifying one of the patterns. */
4929 void
4930 find_modifiable_mems (rtx_insn *head, rtx_insn *tail)
4932 rtx_insn *insn, *next_tail = NEXT_INSN (tail);
4933 int success_in_block = 0;
4935 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4937 struct mem_inc_info mii;
4939 if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
4940 continue;
4942 mii.mem_insn = insn;
4943 if (find_mem (&mii, &PATTERN (insn)))
4944 success_in_block++;
4946 if (success_in_block && sched_verbose >= 5)
4947 fprintf (sched_dump, "%d candidates for address modification found.\n",
4948 success_in_block);
4951 #endif /* INSN_SCHEDULING */