OSDN Git Service

09bf65d9093d3170d0aacde0e3318bca222ac8b7
[pf3gnuchains/gcc-fork.git] / gcc / sched-deps.c
1 /* Instruction scheduling pass.  This file computes dependencies between
2    instructions.
3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
5    2011
6    Free Software Foundation, Inc.
7    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
8    and currently maintained by, Jim Wilson (wilson@cygnus.com)
9
10 This file is part of GCC.
11
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 3, or (at your option) any later
15 version.
16
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
20 for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING3.  If not see
24 <http://www.gnu.org/licenses/>.  */
25 \f
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "diagnostic-core.h"
31 #include "rtl.h"
32 #include "tm_p.h"
33 #include "hard-reg-set.h"
34 #include "regs.h"
35 #include "function.h"
36 #include "flags.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
39 #include "except.h"
40 #include "recog.h"
41 #include "sched-int.h"
42 #include "params.h"
43 #include "cselib.h"
44 #include "ira.h"
45 #include "target.h"
46
47 #ifdef INSN_SCHEDULING
48
49 #ifdef ENABLE_CHECKING
50 #define CHECK (true)
51 #else
52 #define CHECK (false)
53 #endif
54
55 /* In deps->last_pending_memory_flush marks JUMP_INSNs that weren't
56    added to the list because of flush_pending_lists, stands just
57    for itself and not for any other pending memory reads/writes.  */
58 #define NON_FLUSH_JUMP_KIND REG_DEP_ANTI
59 #define NON_FLUSH_JUMP_P(x) (REG_NOTE_KIND (x) == NON_FLUSH_JUMP_KIND)
60
61 /* Holds current parameters for the dependency analyzer.  */
62 struct sched_deps_info_def *sched_deps_info;
63
64 /* The data is specific to the Haifa scheduler.  */
65 VEC(haifa_deps_insn_data_def, heap) *h_d_i_d = NULL;
66
67 /* Return the major type present in the DS.  */
68 enum reg_note
69 ds_to_dk (ds_t ds)
70 {
71   if (ds & DEP_TRUE)
72     return REG_DEP_TRUE;
73
74   if (ds & DEP_OUTPUT)
75     return REG_DEP_OUTPUT;
76
77   gcc_assert (ds & DEP_ANTI);
78
79   return REG_DEP_ANTI;
80 }
81
82 /* Return equivalent dep_status.  */
83 ds_t
84 dk_to_ds (enum reg_note dk)
85 {
86   switch (dk)
87     {
88     case REG_DEP_TRUE:
89       return DEP_TRUE;
90
91     case REG_DEP_OUTPUT:
92       return DEP_OUTPUT;
93
94     default:
95       gcc_assert (dk == REG_DEP_ANTI);
96       return DEP_ANTI;
97     }
98 }
99
100 /* Functions to operate with dependence information container - dep_t.  */
101
102 /* Init DEP with the arguments.  */
103 void
104 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
105 {
106   DEP_PRO (dep) = pro;
107   DEP_CON (dep) = con;
108   DEP_TYPE (dep) = type;
109   DEP_STATUS (dep) = ds;
110 }
111
112 /* Init DEP with the arguments.
113    While most of the scheduler (including targets) only need the major type
114    of the dependency, it is convenient to hide full dep_status from them.  */
115 void
116 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
117 {
118   ds_t ds;
119
120   if ((current_sched_info->flags & USE_DEPS_LIST))
121     ds = dk_to_ds (kind);
122   else
123     ds = -1;
124
125   init_dep_1 (dep, pro, con, kind, ds);
126 }
127
128 /* Make a copy of FROM in TO.  */
129 static void
130 copy_dep (dep_t to, dep_t from)
131 {
132   memcpy (to, from, sizeof (*to));
133 }
134
135 static void dump_ds (FILE *, ds_t);
136
137 /* Define flags for dump_dep ().  */
138
139 /* Dump producer of the dependence.  */
140 #define DUMP_DEP_PRO (2)
141
142 /* Dump consumer of the dependence.  */
143 #define DUMP_DEP_CON (4)
144
145 /* Dump type of the dependence.  */
146 #define DUMP_DEP_TYPE (8)
147
148 /* Dump status of the dependence.  */
149 #define DUMP_DEP_STATUS (16)
150
151 /* Dump all information about the dependence.  */
152 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE       \
153                       |DUMP_DEP_STATUS)
154
155 /* Dump DEP to DUMP.
156    FLAGS is a bit mask specifying what information about DEP needs
157    to be printed.
158    If FLAGS has the very first bit set, then dump all information about DEP
159    and propagate this bit into the callee dump functions.  */
160 static void
161 dump_dep (FILE *dump, dep_t dep, int flags)
162 {
163   if (flags & 1)
164     flags |= DUMP_DEP_ALL;
165
166   fprintf (dump, "<");
167
168   if (flags & DUMP_DEP_PRO)
169     fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
170
171   if (flags & DUMP_DEP_CON)
172     fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
173
174   if (flags & DUMP_DEP_TYPE)
175     {
176       char t;
177       enum reg_note type = DEP_TYPE (dep);
178
179       switch (type)
180         {
181         case REG_DEP_TRUE:
182           t = 't';
183           break;
184
185         case REG_DEP_OUTPUT:
186           t = 'o';
187           break;
188
189         case REG_DEP_ANTI:
190           t = 'a';
191           break;
192
193         default:
194           gcc_unreachable ();
195           break;
196         }
197
198       fprintf (dump, "%c; ", t);
199     }
200
201   if (flags & DUMP_DEP_STATUS)
202     {
203       if (current_sched_info->flags & USE_DEPS_LIST)
204         dump_ds (dump, DEP_STATUS (dep));
205     }
206
207   fprintf (dump, ">");
208 }
209
210 /* Default flags for dump_dep ().  */
211 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
212
213 /* Dump all fields of DEP to STDERR.  */
214 void
215 sd_debug_dep (dep_t dep)
216 {
217   dump_dep (stderr, dep, 1);
218   fprintf (stderr, "\n");
219 }
220
221 /* Determine whether DEP is a dependency link of a non-debug insn on a
222    debug insn.  */
223
224 static inline bool
225 depl_on_debug_p (dep_link_t dep)
226 {
227   return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
228           && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
229 }
230
231 /* Functions to operate with a single link from the dependencies lists -
232    dep_link_t.  */
233
234 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
235    PREV_NEXT_P.  */
236 static void
237 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
238 {
239   dep_link_t next = *prev_nextp;
240
241   gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
242               && DEP_LINK_NEXT (l) == NULL);
243
244   /* Init node being inserted.  */
245   DEP_LINK_PREV_NEXTP (l) = prev_nextp;
246   DEP_LINK_NEXT (l) = next;
247
248   /* Fix next node.  */
249   if (next != NULL)
250     {
251       gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
252
253       DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
254     }
255
256   /* Fix prev node.  */
257   *prev_nextp = l;
258 }
259
260 /* Add dep_link LINK to deps_list L.  */
261 static void
262 add_to_deps_list (dep_link_t link, deps_list_t l)
263 {
264   attach_dep_link (link, &DEPS_LIST_FIRST (l));
265
266   /* Don't count debug deps.  */
267   if (!depl_on_debug_p (link))
268     ++DEPS_LIST_N_LINKS (l);
269 }
270
271 /* Detach dep_link L from the list.  */
272 static void
273 detach_dep_link (dep_link_t l)
274 {
275   dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
276   dep_link_t next = DEP_LINK_NEXT (l);
277
278   *prev_nextp = next;
279
280   if (next != NULL)
281     DEP_LINK_PREV_NEXTP (next) = prev_nextp;
282
283   DEP_LINK_PREV_NEXTP (l) = NULL;
284   DEP_LINK_NEXT (l) = NULL;
285 }
286
287 /* Remove link LINK from list LIST.  */
288 static void
289 remove_from_deps_list (dep_link_t link, deps_list_t list)
290 {
291   detach_dep_link (link);
292
293   /* Don't count debug deps.  */
294   if (!depl_on_debug_p (link))
295     --DEPS_LIST_N_LINKS (list);
296 }
297
298 /* Move link LINK from list FROM to list TO.  */
299 static void
300 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
301 {
302   remove_from_deps_list (link, from);
303   add_to_deps_list (link, to);
304 }
305
306 /* Return true of LINK is not attached to any list.  */
307 static bool
308 dep_link_is_detached_p (dep_link_t link)
309 {
310   return DEP_LINK_PREV_NEXTP (link) == NULL;
311 }
312
313 /* Pool to hold all dependency nodes (dep_node_t).  */
314 static alloc_pool dn_pool;
315
316 /* Number of dep_nodes out there.  */
317 static int dn_pool_diff = 0;
318
319 /* Create a dep_node.  */
320 static dep_node_t
321 create_dep_node (void)
322 {
323   dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
324   dep_link_t back = DEP_NODE_BACK (n);
325   dep_link_t forw = DEP_NODE_FORW (n);
326
327   DEP_LINK_NODE (back) = n;
328   DEP_LINK_NEXT (back) = NULL;
329   DEP_LINK_PREV_NEXTP (back) = NULL;
330
331   DEP_LINK_NODE (forw) = n;
332   DEP_LINK_NEXT (forw) = NULL;
333   DEP_LINK_PREV_NEXTP (forw) = NULL;
334
335   ++dn_pool_diff;
336
337   return n;
338 }
339
340 /* Delete dep_node N.  N must not be connected to any deps_list.  */
341 static void
342 delete_dep_node (dep_node_t n)
343 {
344   gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
345               && dep_link_is_detached_p (DEP_NODE_FORW (n)));
346
347   --dn_pool_diff;
348
349   pool_free (dn_pool, n);
350 }
351
352 /* Pool to hold dependencies lists (deps_list_t).  */
353 static alloc_pool dl_pool;
354
355 /* Number of deps_lists out there.  */
356 static int dl_pool_diff = 0;
357
358 /* Functions to operate with dependences lists - deps_list_t.  */
359
360 /* Return true if list L is empty.  */
361 static bool
362 deps_list_empty_p (deps_list_t l)
363 {
364   return DEPS_LIST_N_LINKS (l) == 0;
365 }
366
367 /* Create a new deps_list.  */
368 static deps_list_t
369 create_deps_list (void)
370 {
371   deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
372
373   DEPS_LIST_FIRST (l) = NULL;
374   DEPS_LIST_N_LINKS (l) = 0;
375
376   ++dl_pool_diff;
377   return l;
378 }
379
380 /* Free deps_list L.  */
381 static void
382 free_deps_list (deps_list_t l)
383 {
384   gcc_assert (deps_list_empty_p (l));
385
386   --dl_pool_diff;
387
388   pool_free (dl_pool, l);
389 }
390
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)
396 {
397   return dn_pool_diff == 0 && dl_pool_diff == 0;
398 }
399
400 /* Remove all elements from L.  */
401 static void
402 clear_deps_list (deps_list_t l)
403 {
404   do
405     {
406       dep_link_t link = DEPS_LIST_FIRST (l);
407
408       if (link == NULL)
409         break;
410
411       remove_from_deps_list (link, l);
412     }
413   while (1);
414 }
415
416 static regset reg_pending_sets;
417 static regset reg_pending_clobbers;
418 static regset reg_pending_uses;
419 static enum reg_pending_barrier_mode reg_pending_barrier;
420
421 /* Hard registers implicitly clobbered or used (or may be implicitly
422    clobbered or used) by the currently analyzed insn.  For example,
423    insn in its constraint has one register class.  Even if there is
424    currently no hard register in the insn, the particular hard
425    register will be in the insn after reload pass because the
426    constraint requires it.  */
427 static HARD_REG_SET implicit_reg_pending_clobbers;
428 static HARD_REG_SET implicit_reg_pending_uses;
429
430 /* To speed up the test for duplicate dependency links we keep a
431    record of dependencies created by add_dependence when the average
432    number of instructions in a basic block is very large.
433
434    Studies have shown that there is typically around 5 instructions between
435    branches for typical C code.  So we can make a guess that the average
436    basic block is approximately 5 instructions long; we will choose 100X
437    the average size as a very large basic block.
438
439    Each insn has associated bitmaps for its dependencies.  Each bitmap
440    has enough entries to represent a dependency on any other insn in
441    the insn chain.  All bitmap for true dependencies cache is
442    allocated then the rest two ones are also allocated.  */
443 static bitmap_head *true_dependency_cache = NULL;
444 static bitmap_head *output_dependency_cache = NULL;
445 static bitmap_head *anti_dependency_cache = NULL;
446 static bitmap_head *spec_dependency_cache = NULL;
447 static int cache_size;
448
449 static int deps_may_trap_p (const_rtx);
450 static void add_dependence_list (rtx, rtx, int, enum reg_note);
451 static void add_dependence_list_and_free (struct deps_desc *, rtx,
452                                           rtx *, int, enum reg_note);
453 static void delete_all_dependences (rtx);
454 static void fixup_sched_groups (rtx);
455
456 static void flush_pending_lists (struct deps_desc *, rtx, int, int);
457 static void sched_analyze_1 (struct deps_desc *, rtx, rtx);
458 static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
459 static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
460
461 static bool sched_has_condition_p (const_rtx);
462 static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
463
464 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
465                                                           rtx, rtx);
466 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
467
468 #ifdef ENABLE_CHECKING
469 static void check_dep (dep_t, bool);
470 #endif
471 \f
472 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
473
474 static int
475 deps_may_trap_p (const_rtx mem)
476 {
477   const_rtx addr = XEXP (mem, 0);
478
479   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
480     {
481       const_rtx t = get_reg_known_value (REGNO (addr));
482       if (t)
483         addr = t;
484     }
485   return rtx_addr_can_trap_p (addr);
486 }
487 \f
488
489 /* Find the condition under which INSN is executed.  If REV is not NULL,
490    it is set to TRUE when the returned comparison should be reversed
491    to get the actual condition.  */
492 static rtx
493 sched_get_condition_with_rev (const_rtx insn, bool *rev)
494 {
495   rtx pat = PATTERN (insn);
496   rtx src;
497
498   if (pat == 0)
499     return 0;
500
501   if (rev)
502     *rev = false;
503
504   if (GET_CODE (pat) == COND_EXEC)
505     return COND_EXEC_TEST (pat);
506
507   if (!any_condjump_p (insn) || !onlyjump_p (insn))
508     return 0;
509
510   src = SET_SRC (pc_set (insn));
511
512   if (XEXP (src, 2) == pc_rtx)
513     return XEXP (src, 0);
514   else if (XEXP (src, 1) == pc_rtx)
515     {
516       rtx cond = XEXP (src, 0);
517       enum rtx_code revcode = reversed_comparison_code (cond, insn);
518
519       if (revcode == UNKNOWN)
520         return 0;
521
522       if (rev)
523         *rev = true;
524       return cond;
525     }
526
527   return 0;
528 }
529
530 /* True when we can find a condition under which INSN is executed.  */
531 static bool
532 sched_has_condition_p (const_rtx insn)
533 {
534   return !! sched_get_condition_with_rev (insn, NULL);
535 }
536
537 \f
538
539 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
540 static int
541 conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
542 {
543   if (COMPARISON_P (cond1)
544       && COMPARISON_P (cond2)
545       && GET_CODE (cond1) ==
546           (rev1==rev2
547           ? reversed_comparison_code (cond2, NULL)
548           : GET_CODE (cond2))
549       && XEXP (cond1, 0) == XEXP (cond2, 0)
550       && XEXP (cond1, 1) == XEXP (cond2, 1))
551     return 1;
552   return 0;
553 }
554
555 /* Return true if insn1 and insn2 can never depend on one another because
556    the conditions under which they are executed are mutually exclusive.  */
557 bool
558 sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
559 {
560   rtx cond1, cond2;
561   bool rev1 = false, rev2 = false;
562
563   /* df doesn't handle conditional lifetimes entirely correctly;
564      calls mess up the conditional lifetimes.  */
565   if (!CALL_P (insn1) && !CALL_P (insn2))
566     {
567       cond1 = sched_get_condition_with_rev (insn1, &rev1);
568       cond2 = sched_get_condition_with_rev (insn2, &rev2);
569       if (cond1 && cond2
570           && conditions_mutex_p (cond1, cond2, rev1, rev2)
571           /* Make sure first instruction doesn't affect condition of second
572              instruction if switched.  */
573           && !modified_in_p (cond1, insn2)
574           /* Make sure second instruction doesn't affect condition of first
575              instruction if switched.  */
576           && !modified_in_p (cond2, insn1))
577         return true;
578     }
579   return false;
580 }
581 \f
582
583 /* Return true if INSN can potentially be speculated with type DS.  */
584 bool
585 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
586 {
587   if (HAS_INTERNAL_DEP (insn))
588     return false;
589
590   if (!NONJUMP_INSN_P (insn))
591     return false;
592
593   if (SCHED_GROUP_P (insn))
594     return false;
595
596   if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
597     return false;
598
599   if (side_effects_p (PATTERN (insn)))
600     return false;
601
602   if (ds & BE_IN_SPEC)
603     /* The following instructions, which depend on a speculatively scheduled
604        instruction, cannot be speculatively scheduled along.  */
605     {
606       if (may_trap_or_fault_p (PATTERN (insn)))
607         /* If instruction might fault, it cannot be speculatively scheduled.
608            For control speculation it's obvious why and for data speculation
609            it's because the insn might get wrong input if speculation
610            wasn't successful.  */
611         return false;
612
613       if ((ds & BE_IN_DATA)
614           && sched_has_condition_p (insn))
615         /* If this is a predicated instruction, then it cannot be
616            speculatively scheduled.  See PR35659.  */
617         return false;
618     }
619
620   return true;
621 }
622
623 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
624    initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
625    and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
626    This function is used to switch sd_iterator to the next list.
627    !!! For internal use only.  Might consider moving it to sched-int.h.  */
628 void
629 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
630               deps_list_t *list_ptr, bool *resolved_p_ptr)
631 {
632   sd_list_types_def types = *types_ptr;
633
634   if (types & SD_LIST_HARD_BACK)
635     {
636       *list_ptr = INSN_HARD_BACK_DEPS (insn);
637       *resolved_p_ptr = false;
638       *types_ptr = types & ~SD_LIST_HARD_BACK;
639     }
640   else if (types & SD_LIST_SPEC_BACK)
641     {
642       *list_ptr = INSN_SPEC_BACK_DEPS (insn);
643       *resolved_p_ptr = false;
644       *types_ptr = types & ~SD_LIST_SPEC_BACK;
645     }
646   else if (types & SD_LIST_FORW)
647     {
648       *list_ptr = INSN_FORW_DEPS (insn);
649       *resolved_p_ptr = false;
650       *types_ptr = types & ~SD_LIST_FORW;
651     }
652   else if (types & SD_LIST_RES_BACK)
653     {
654       *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
655       *resolved_p_ptr = true;
656       *types_ptr = types & ~SD_LIST_RES_BACK;
657     }
658   else if (types & SD_LIST_RES_FORW)
659     {
660       *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
661       *resolved_p_ptr = true;
662       *types_ptr = types & ~SD_LIST_RES_FORW;
663     }
664   else
665     {
666       *list_ptr = NULL;
667       *resolved_p_ptr = false;
668       *types_ptr = SD_LIST_NONE;
669     }
670 }
671
672 /* Return the summary size of INSN's lists defined by LIST_TYPES.  */
673 int
674 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
675 {
676   int size = 0;
677
678   while (list_types != SD_LIST_NONE)
679     {
680       deps_list_t list;
681       bool resolved_p;
682
683       sd_next_list (insn, &list_types, &list, &resolved_p);
684       if (list)
685         size += DEPS_LIST_N_LINKS (list);
686     }
687
688   return size;
689 }
690
691 /* Return true if INSN's lists defined by LIST_TYPES are all empty.  */
692
693 bool
694 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
695 {
696   while (list_types != SD_LIST_NONE)
697     {
698       deps_list_t list;
699       bool resolved_p;
700
701       sd_next_list (insn, &list_types, &list, &resolved_p);
702       if (!deps_list_empty_p (list))
703         return false;
704     }
705
706   return true;
707 }
708
709 /* Initialize data for INSN.  */
710 void
711 sd_init_insn (rtx insn)
712 {
713   INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
714   INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
715   INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
716   INSN_FORW_DEPS (insn) = create_deps_list ();
717   INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
718
719   /* ??? It would be nice to allocate dependency caches here.  */
720 }
721
722 /* Free data for INSN.  */
723 void
724 sd_finish_insn (rtx insn)
725 {
726   /* ??? It would be nice to deallocate dependency caches here.  */
727
728   free_deps_list (INSN_HARD_BACK_DEPS (insn));
729   INSN_HARD_BACK_DEPS (insn) = NULL;
730
731   free_deps_list (INSN_SPEC_BACK_DEPS (insn));
732   INSN_SPEC_BACK_DEPS (insn) = NULL;
733
734   free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
735   INSN_RESOLVED_BACK_DEPS (insn) = NULL;
736
737   free_deps_list (INSN_FORW_DEPS (insn));
738   INSN_FORW_DEPS (insn) = NULL;
739
740   free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
741   INSN_RESOLVED_FORW_DEPS (insn) = NULL;
742 }
743
744 /* Find a dependency between producer PRO and consumer CON.
745    Search through resolved dependency lists if RESOLVED_P is true.
746    If no such dependency is found return NULL,
747    otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
748    with an iterator pointing to it.  */
749 static dep_t
750 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
751                               sd_iterator_def *sd_it_ptr)
752 {
753   sd_list_types_def pro_list_type;
754   sd_list_types_def con_list_type;
755   sd_iterator_def sd_it;
756   dep_t dep;
757   bool found_p = false;
758
759   if (resolved_p)
760     {
761       pro_list_type = SD_LIST_RES_FORW;
762       con_list_type = SD_LIST_RES_BACK;
763     }
764   else
765     {
766       pro_list_type = SD_LIST_FORW;
767       con_list_type = SD_LIST_BACK;
768     }
769
770   /* Walk through either back list of INSN or forw list of ELEM
771      depending on which one is shorter.  */
772   if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
773     {
774       /* Find the dep_link with producer PRO in consumer's back_deps.  */
775       FOR_EACH_DEP (con, con_list_type, sd_it, dep)
776         if (DEP_PRO (dep) == pro)
777           {
778             found_p = true;
779             break;
780           }
781     }
782   else
783     {
784       /* Find the dep_link with consumer CON in producer's forw_deps.  */
785       FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
786         if (DEP_CON (dep) == con)
787           {
788             found_p = true;
789             break;
790           }
791     }
792
793   if (found_p)
794     {
795       if (sd_it_ptr != NULL)
796         *sd_it_ptr = sd_it;
797
798       return dep;
799     }
800
801   return NULL;
802 }
803
804 /* Find a dependency between producer PRO and consumer CON.
805    Use dependency [if available] to check if dependency is present at all.
806    Search through resolved dependency lists if RESOLVED_P is true.
807    If the dependency or NULL if none found.  */
808 dep_t
809 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
810 {
811   if (true_dependency_cache != NULL)
812     /* Avoiding the list walk below can cut compile times dramatically
813        for some code.  */
814     {
815       int elem_luid = INSN_LUID (pro);
816       int insn_luid = INSN_LUID (con);
817
818       gcc_assert (output_dependency_cache != NULL
819                   && anti_dependency_cache != NULL);
820
821       if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
822           && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
823           && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
824         return NULL;
825     }
826
827   return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
828 }
829
830 /* Add or update  a dependence described by DEP.
831    MEM1 and MEM2, if non-null, correspond to memory locations in case of
832    data speculation.
833
834    The function returns a value indicating if an old entry has been changed
835    or a new entry has been added to insn's backward deps.
836
837    This function merely checks if producer and consumer is the same insn
838    and doesn't create a dep in this case.  Actual manipulation of
839    dependence data structures is performed in add_or_update_dep_1.  */
840 static enum DEPS_ADJUST_RESULT
841 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
842 {
843   rtx elem = DEP_PRO (dep);
844   rtx insn = DEP_CON (dep);
845
846   gcc_assert (INSN_P (insn) && INSN_P (elem));
847
848   /* Don't depend an insn on itself.  */
849   if (insn == elem)
850     {
851       if (sched_deps_info->generate_spec_deps)
852         /* INSN has an internal dependence, which we can't overcome.  */
853         HAS_INTERNAL_DEP (insn) = 1;
854
855       return DEP_NODEP;
856     }
857
858   return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
859 }
860
861 /* Ask dependency caches what needs to be done for dependence DEP.
862    Return DEP_CREATED if new dependence should be created and there is no
863    need to try to find one searching the dependencies lists.
864    Return DEP_PRESENT if there already is a dependence described by DEP and
865    hence nothing is to be done.
866    Return DEP_CHANGED if there already is a dependence, but it should be
867    updated to incorporate additional information from DEP.  */
868 static enum DEPS_ADJUST_RESULT
869 ask_dependency_caches (dep_t dep)
870 {
871   int elem_luid = INSN_LUID (DEP_PRO (dep));
872   int insn_luid = INSN_LUID (DEP_CON (dep));
873
874   gcc_assert (true_dependency_cache != NULL
875               && output_dependency_cache != NULL
876               && anti_dependency_cache != NULL);
877
878   if (!(current_sched_info->flags & USE_DEPS_LIST))
879     {
880       enum reg_note present_dep_type;
881
882       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
883         present_dep_type = REG_DEP_TRUE;
884       else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
885         present_dep_type = REG_DEP_OUTPUT;
886       else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
887         present_dep_type = REG_DEP_ANTI;
888       else
889         /* There is no existing dep so it should be created.  */
890         return DEP_CREATED;
891
892       if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
893         /* DEP does not add anything to the existing dependence.  */
894         return DEP_PRESENT;
895     }
896   else
897     {
898       ds_t present_dep_types = 0;
899
900       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
901         present_dep_types |= DEP_TRUE;
902       if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
903         present_dep_types |= DEP_OUTPUT;
904       if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
905         present_dep_types |= DEP_ANTI;
906
907       if (present_dep_types == 0)
908         /* There is no existing dep so it should be created.  */
909         return DEP_CREATED;
910
911       if (!(current_sched_info->flags & DO_SPECULATION)
912           || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
913         {
914           if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
915               == present_dep_types)
916             /* DEP does not add anything to the existing dependence.  */
917             return DEP_PRESENT;
918         }
919       else
920         {
921           /* Only true dependencies can be data speculative and
922              only anti dependencies can be control speculative.  */
923           gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
924                       == present_dep_types);
925
926           /* if (DEP is SPECULATIVE) then
927              ..we should update DEP_STATUS
928              else
929              ..we should reset existing dep to non-speculative.  */
930         }
931     }
932
933   return DEP_CHANGED;
934 }
935
936 /* Set dependency caches according to DEP.  */
937 static void
938 set_dependency_caches (dep_t dep)
939 {
940   int elem_luid = INSN_LUID (DEP_PRO (dep));
941   int insn_luid = INSN_LUID (DEP_CON (dep));
942
943   if (!(current_sched_info->flags & USE_DEPS_LIST))
944     {
945       switch (DEP_TYPE (dep))
946         {
947         case REG_DEP_TRUE:
948           bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
949           break;
950
951         case REG_DEP_OUTPUT:
952           bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
953           break;
954
955         case REG_DEP_ANTI:
956           bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
957           break;
958
959         default:
960           gcc_unreachable ();
961         }
962     }
963   else
964     {
965       ds_t ds = DEP_STATUS (dep);
966
967       if (ds & DEP_TRUE)
968         bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
969       if (ds & DEP_OUTPUT)
970         bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
971       if (ds & DEP_ANTI)
972         bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
973
974       if (ds & SPECULATIVE)
975         {
976           gcc_assert (current_sched_info->flags & DO_SPECULATION);
977           bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
978         }
979     }
980 }
981
982 /* Type of dependence DEP have changed from OLD_TYPE.  Update dependency
983    caches accordingly.  */
984 static void
985 update_dependency_caches (dep_t dep, enum reg_note old_type)
986 {
987   int elem_luid = INSN_LUID (DEP_PRO (dep));
988   int insn_luid = INSN_LUID (DEP_CON (dep));
989
990   /* Clear corresponding cache entry because type of the link
991      may have changed.  Keep them if we use_deps_list.  */
992   if (!(current_sched_info->flags & USE_DEPS_LIST))
993     {
994       switch (old_type)
995         {
996         case REG_DEP_OUTPUT:
997           bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
998           break;
999
1000         case REG_DEP_ANTI:
1001           bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1002           break;
1003
1004         default:
1005           gcc_unreachable ();
1006         }
1007     }
1008
1009   set_dependency_caches (dep);
1010 }
1011
1012 /* Convert a dependence pointed to by SD_IT to be non-speculative.  */
1013 static void
1014 change_spec_dep_to_hard (sd_iterator_def sd_it)
1015 {
1016   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1017   dep_link_t link = DEP_NODE_BACK (node);
1018   dep_t dep = DEP_NODE_DEP (node);
1019   rtx elem = DEP_PRO (dep);
1020   rtx insn = DEP_CON (dep);
1021
1022   move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1023
1024   DEP_STATUS (dep) &= ~SPECULATIVE;
1025
1026   if (true_dependency_cache != NULL)
1027     /* Clear the cache entry.  */
1028     bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1029                       INSN_LUID (elem));
1030 }
1031
1032 /* Update DEP to incorporate information from NEW_DEP.
1033    SD_IT points to DEP in case it should be moved to another list.
1034    MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1035    data-speculative dependence should be updated.  */
1036 static enum DEPS_ADJUST_RESULT
1037 update_dep (dep_t dep, dep_t new_dep,
1038             sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1039             rtx mem1 ATTRIBUTE_UNUSED,
1040             rtx mem2 ATTRIBUTE_UNUSED)
1041 {
1042   enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1043   enum reg_note old_type = DEP_TYPE (dep);
1044
1045   /* If this is a more restrictive type of dependence than the
1046      existing one, then change the existing dependence to this
1047      type.  */
1048   if ((int) DEP_TYPE (new_dep) < (int) old_type)
1049     {
1050       DEP_TYPE (dep) = DEP_TYPE (new_dep);
1051       res = DEP_CHANGED;
1052     }
1053
1054   if (current_sched_info->flags & USE_DEPS_LIST)
1055     /* Update DEP_STATUS.  */
1056     {
1057       ds_t dep_status = DEP_STATUS (dep);
1058       ds_t ds = DEP_STATUS (new_dep);
1059       ds_t new_status = ds | dep_status;
1060
1061       if (new_status & SPECULATIVE)
1062         /* Either existing dep or a dep we're adding or both are
1063            speculative.  */
1064         {
1065           if (!(ds & SPECULATIVE)
1066               || !(dep_status & SPECULATIVE))
1067             /* The new dep can't be speculative.  */
1068             {
1069               new_status &= ~SPECULATIVE;
1070
1071               if (dep_status & SPECULATIVE)
1072                 /* The old dep was speculative, but now it
1073                    isn't.  */
1074                 change_spec_dep_to_hard (sd_it);
1075             }
1076           else
1077             {
1078               /* Both are speculative.  Merge probabilities.  */
1079               if (mem1 != NULL)
1080                 {
1081                   dw_t dw;
1082
1083                   dw = estimate_dep_weak (mem1, mem2);
1084                   ds = set_dep_weak (ds, BEGIN_DATA, dw);
1085                 }
1086
1087               new_status = ds_merge (dep_status, ds);
1088             }
1089         }
1090
1091       ds = new_status;
1092
1093       if (dep_status != ds)
1094         {
1095           DEP_STATUS (dep) = ds;
1096           res = DEP_CHANGED;
1097         }
1098     }
1099
1100   if (true_dependency_cache != NULL
1101       && res == DEP_CHANGED)
1102     update_dependency_caches (dep, old_type);
1103
1104   return res;
1105 }
1106
1107 /* Add or update  a dependence described by DEP.
1108    MEM1 and MEM2, if non-null, correspond to memory locations in case of
1109    data speculation.
1110
1111    The function returns a value indicating if an old entry has been changed
1112    or a new entry has been added to insn's backward deps or nothing has
1113    been updated at all.  */
1114 static enum DEPS_ADJUST_RESULT
1115 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1116                      rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1117 {
1118   bool maybe_present_p = true;
1119   bool present_p = false;
1120
1121   gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1122               && DEP_PRO (new_dep) != DEP_CON (new_dep));
1123
1124 #ifdef ENABLE_CHECKING
1125   check_dep (new_dep, mem1 != NULL);
1126 #endif
1127
1128   if (true_dependency_cache != NULL)
1129     {
1130       switch (ask_dependency_caches (new_dep))
1131         {
1132         case DEP_PRESENT:
1133           return DEP_PRESENT;
1134
1135         case DEP_CHANGED:
1136           maybe_present_p = true;
1137           present_p = true;
1138           break;
1139
1140         case DEP_CREATED:
1141           maybe_present_p = false;
1142           present_p = false;
1143           break;
1144
1145         default:
1146           gcc_unreachable ();
1147           break;
1148         }
1149     }
1150
1151   /* Check that we don't already have this dependence.  */
1152   if (maybe_present_p)
1153     {
1154       dep_t present_dep;
1155       sd_iterator_def sd_it;
1156
1157       gcc_assert (true_dependency_cache == NULL || present_p);
1158
1159       present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1160                                                   DEP_CON (new_dep),
1161                                                   resolved_p, &sd_it);
1162
1163       if (present_dep != NULL)
1164         /* We found an existing dependency between ELEM and INSN.  */
1165         return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1166       else
1167         /* We didn't find a dep, it shouldn't present in the cache.  */
1168         gcc_assert (!present_p);
1169     }
1170
1171   /* Might want to check one level of transitivity to save conses.
1172      This check should be done in maybe_add_or_update_dep_1.
1173      Since we made it to add_or_update_dep_1, we must create
1174      (or update) a link.  */
1175
1176   if (mem1 != NULL_RTX)
1177     {
1178       gcc_assert (sched_deps_info->generate_spec_deps);
1179       DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1180                                            estimate_dep_weak (mem1, mem2));
1181     }
1182
1183   sd_add_dep (new_dep, resolved_p);
1184
1185   return DEP_CREATED;
1186 }
1187
1188 /* Initialize BACK_LIST_PTR with consumer's backward list and
1189    FORW_LIST_PTR with producer's forward list.  If RESOLVED_P is true
1190    initialize with lists that hold resolved deps.  */
1191 static void
1192 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1193                          deps_list_t *back_list_ptr,
1194                          deps_list_t *forw_list_ptr)
1195 {
1196   rtx con = DEP_CON (dep);
1197
1198   if (!resolved_p)
1199     {
1200       if ((current_sched_info->flags & DO_SPECULATION)
1201           && (DEP_STATUS (dep) & SPECULATIVE))
1202         *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1203       else
1204         *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1205
1206       *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1207     }
1208   else
1209     {
1210       *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1211       *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1212     }
1213 }
1214
1215 /* Add dependence described by DEP.
1216    If RESOLVED_P is true treat the dependence as a resolved one.  */
1217 void
1218 sd_add_dep (dep_t dep, bool resolved_p)
1219 {
1220   dep_node_t n = create_dep_node ();
1221   deps_list_t con_back_deps;
1222   deps_list_t pro_forw_deps;
1223   rtx elem = DEP_PRO (dep);
1224   rtx insn = DEP_CON (dep);
1225
1226   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1227
1228   if ((current_sched_info->flags & DO_SPECULATION)
1229       && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1230     DEP_STATUS (dep) &= ~SPECULATIVE;
1231
1232   copy_dep (DEP_NODE_DEP (n), dep);
1233
1234   get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1235
1236   add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1237
1238 #ifdef ENABLE_CHECKING
1239   check_dep (dep, false);
1240 #endif
1241
1242   add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1243
1244   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1245      in the bitmap caches of dependency information.  */
1246   if (true_dependency_cache != NULL)
1247     set_dependency_caches (dep);
1248 }
1249
1250 /* Add or update backward dependence between INSN and ELEM
1251    with given type DEP_TYPE and dep_status DS.
1252    This function is a convenience wrapper.  */
1253 enum DEPS_ADJUST_RESULT
1254 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1255 {
1256   return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1257 }
1258
1259 /* Resolved dependence pointed to by SD_IT.
1260    SD_IT will advance to the next element.  */
1261 void
1262 sd_resolve_dep (sd_iterator_def sd_it)
1263 {
1264   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1265   dep_t dep = DEP_NODE_DEP (node);
1266   rtx pro = DEP_PRO (dep);
1267   rtx con = DEP_CON (dep);
1268
1269   if ((current_sched_info->flags & DO_SPECULATION)
1270       && (DEP_STATUS (dep) & SPECULATIVE))
1271     move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1272                    INSN_RESOLVED_BACK_DEPS (con));
1273   else
1274     move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1275                    INSN_RESOLVED_BACK_DEPS (con));
1276
1277   move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1278                  INSN_RESOLVED_FORW_DEPS (pro));
1279 }
1280
1281 /* Make TO depend on all the FROM's producers.
1282    If RESOLVED_P is true add dependencies to the resolved lists.  */
1283 void
1284 sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
1285 {
1286   sd_list_types_def list_type;
1287   sd_iterator_def sd_it;
1288   dep_t dep;
1289
1290   list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1291
1292   FOR_EACH_DEP (from, list_type, sd_it, dep)
1293     {
1294       dep_def _new_dep, *new_dep = &_new_dep;
1295
1296       copy_dep (new_dep, dep);
1297       DEP_CON (new_dep) = to;
1298       sd_add_dep (new_dep, resolved_p);
1299     }
1300 }
1301
1302 /* Remove a dependency referred to by SD_IT.
1303    SD_IT will point to the next dependence after removal.  */
1304 void
1305 sd_delete_dep (sd_iterator_def sd_it)
1306 {
1307   dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1308   dep_t dep = DEP_NODE_DEP (n);
1309   rtx pro = DEP_PRO (dep);
1310   rtx con = DEP_CON (dep);
1311   deps_list_t con_back_deps;
1312   deps_list_t pro_forw_deps;
1313
1314   if (true_dependency_cache != NULL)
1315     {
1316       int elem_luid = INSN_LUID (pro);
1317       int insn_luid = INSN_LUID (con);
1318
1319       bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1320       bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1321       bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1322
1323       if (current_sched_info->flags & DO_SPECULATION)
1324         bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1325     }
1326
1327   get_back_and_forw_lists (dep, sd_it.resolved_p,
1328                            &con_back_deps, &pro_forw_deps);
1329
1330   remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1331   remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1332
1333   delete_dep_node (n);
1334 }
1335
1336 /* Dump size of the lists.  */
1337 #define DUMP_LISTS_SIZE (2)
1338
1339 /* Dump dependencies of the lists.  */
1340 #define DUMP_LISTS_DEPS (4)
1341
1342 /* Dump all information about the lists.  */
1343 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1344
1345 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1346    FLAGS is a bit mask specifying what information about the lists needs
1347    to be printed.
1348    If FLAGS has the very first bit set, then dump all information about
1349    the lists and propagate this bit into the callee dump functions.  */
1350 static void
1351 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1352 {
1353   sd_iterator_def sd_it;
1354   dep_t dep;
1355   int all;
1356
1357   all = (flags & 1);
1358
1359   if (all)
1360     flags |= DUMP_LISTS_ALL;
1361
1362   fprintf (dump, "[");
1363
1364   if (flags & DUMP_LISTS_SIZE)
1365     fprintf (dump, "%d; ", sd_lists_size (insn, types));
1366
1367   if (flags & DUMP_LISTS_DEPS)
1368     {
1369       FOR_EACH_DEP (insn, types, sd_it, dep)
1370         {
1371           dump_dep (dump, dep, dump_dep_flags | all);
1372           fprintf (dump, " ");
1373         }
1374     }
1375 }
1376
1377 /* Dump all information about deps_lists of INSN specified by TYPES
1378    to STDERR.  */
1379 void
1380 sd_debug_lists (rtx insn, sd_list_types_def types)
1381 {
1382   dump_lists (stderr, insn, types, 1);
1383   fprintf (stderr, "\n");
1384 }
1385
1386 /* A convenience wrapper to operate on an entire list.  */
1387
1388 static void
1389 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
1390 {
1391   for (; list; list = XEXP (list, 1))
1392     {
1393       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1394         add_dependence (insn, XEXP (list, 0), dep_type);
1395     }
1396 }
1397
1398 /* Similar, but free *LISTP at the same time, when the context
1399    is not readonly.  */
1400
1401 static void
1402 add_dependence_list_and_free (struct deps_desc *deps, rtx insn, rtx *listp,
1403                               int uncond, enum reg_note dep_type)
1404 {
1405   rtx list, next;
1406
1407   /* We don't want to short-circuit dependencies involving debug
1408      insns, because they may cause actual dependencies to be
1409      disregarded.  */
1410   if (deps->readonly || DEBUG_INSN_P (insn))
1411     {
1412       add_dependence_list (insn, *listp, uncond, dep_type);
1413       return;
1414     }
1415
1416   for (list = *listp, *listp = NULL; list ; list = next)
1417     {
1418       next = XEXP (list, 1);
1419       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1420         add_dependence (insn, XEXP (list, 0), dep_type);
1421       free_INSN_LIST_node (list);
1422     }
1423 }
1424
1425 /* Remove all occurences of INSN from LIST.  Return the number of
1426    occurences removed.  */
1427
1428 static int
1429 remove_from_dependence_list (rtx insn, rtx* listp)
1430 {
1431   int removed = 0;
1432
1433   while (*listp)
1434     {
1435       if (XEXP (*listp, 0) == insn)
1436         {
1437           remove_free_INSN_LIST_node (listp);
1438           removed++;
1439           continue;
1440         }
1441
1442       listp = &XEXP (*listp, 1);
1443     }
1444
1445   return removed;
1446 }
1447
1448 /* Same as above, but process two lists at once.  */
1449 static int
1450 remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
1451 {
1452   int removed = 0;
1453
1454   while (*listp)
1455     {
1456       if (XEXP (*listp, 0) == insn)
1457         {
1458           remove_free_INSN_LIST_node (listp);
1459           remove_free_EXPR_LIST_node (exprp);
1460           removed++;
1461           continue;
1462         }
1463
1464       listp = &XEXP (*listp, 1);
1465       exprp = &XEXP (*exprp, 1);
1466     }
1467
1468   return removed;
1469 }
1470
1471 /* Clear all dependencies for an insn.  */
1472 static void
1473 delete_all_dependences (rtx insn)
1474 {
1475   sd_iterator_def sd_it;
1476   dep_t dep;
1477
1478   /* The below cycle can be optimized to clear the caches and back_deps
1479      in one call but that would provoke duplication of code from
1480      delete_dep ().  */
1481
1482   for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1483        sd_iterator_cond (&sd_it, &dep);)
1484     sd_delete_dep (sd_it);
1485 }
1486
1487 /* All insns in a scheduling group except the first should only have
1488    dependencies on the previous insn in the group.  So we find the
1489    first instruction in the scheduling group by walking the dependence
1490    chains backwards. Then we add the dependencies for the group to
1491    the previous nonnote insn.  */
1492
1493 static void
1494 fixup_sched_groups (rtx insn)
1495 {
1496   sd_iterator_def sd_it;
1497   dep_t dep;
1498   rtx prev_nonnote;
1499
1500   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1501     {
1502       rtx i = insn;
1503       rtx pro = DEP_PRO (dep);
1504
1505       do
1506         {
1507           i = prev_nonnote_insn (i);
1508
1509           if (pro == i)
1510             goto next_link;
1511         } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1512
1513       if (! sched_insns_conditions_mutex_p (i, pro))
1514         add_dependence (i, pro, DEP_TYPE (dep));
1515     next_link:;
1516     }
1517
1518   delete_all_dependences (insn);
1519
1520   prev_nonnote = prev_nonnote_nondebug_insn (insn);
1521   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1522       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1523     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1524 }
1525 \f
1526 /* Process an insn's memory dependencies.  There are four kinds of
1527    dependencies:
1528
1529    (0) read dependence: read follows read
1530    (1) true dependence: read follows write
1531    (2) output dependence: write follows write
1532    (3) anti dependence: write follows read
1533
1534    We are careful to build only dependencies which actually exist, and
1535    use transitivity to avoid building too many links.  */
1536
1537 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1538    The MEM is a memory reference contained within INSN, which we are saving
1539    so that we can do memory aliasing on it.  */
1540
1541 static void
1542 add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1543                          rtx insn, rtx mem)
1544 {
1545   rtx *insn_list;
1546   rtx *mem_list;
1547   rtx link;
1548
1549   gcc_assert (!deps->readonly);
1550   if (read_p)
1551     {
1552       insn_list = &deps->pending_read_insns;
1553       mem_list = &deps->pending_read_mems;
1554       if (!DEBUG_INSN_P (insn))
1555         deps->pending_read_list_length++;
1556     }
1557   else
1558     {
1559       insn_list = &deps->pending_write_insns;
1560       mem_list = &deps->pending_write_mems;
1561       deps->pending_write_list_length++;
1562     }
1563
1564   link = alloc_INSN_LIST (insn, *insn_list);
1565   *insn_list = link;
1566
1567   if (sched_deps_info->use_cselib)
1568     {
1569       mem = shallow_copy_rtx (mem);
1570       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0), GET_MODE (mem));
1571     }
1572   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1573   *mem_list = link;
1574 }
1575
1576 /* Make a dependency between every memory reference on the pending lists
1577    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
1578    dependencies for a read operation, similarly with FOR_WRITE.  */
1579
1580 static void
1581 flush_pending_lists (struct deps_desc *deps, rtx insn, int for_read,
1582                      int for_write)
1583 {
1584   if (for_write)
1585     {
1586       add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1587                                     1, REG_DEP_ANTI);
1588       if (!deps->readonly)
1589         {
1590           free_EXPR_LIST_list (&deps->pending_read_mems);
1591           deps->pending_read_list_length = 0;
1592         }
1593     }
1594
1595   add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1596                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1597
1598   add_dependence_list_and_free (deps, insn,
1599                                 &deps->last_pending_memory_flush, 1,
1600                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1601   if (!deps->readonly)
1602     {
1603       free_EXPR_LIST_list (&deps->pending_write_mems);
1604       deps->pending_write_list_length = 0;
1605
1606       deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1607       deps->pending_flush_length = 1;
1608     }
1609 }
1610 \f
1611 /* Instruction which dependencies we are analyzing.  */
1612 static rtx cur_insn = NULL_RTX;
1613
1614 /* Implement hooks for haifa scheduler.  */
1615
1616 static void
1617 haifa_start_insn (rtx insn)
1618 {
1619   gcc_assert (insn && !cur_insn);
1620
1621   cur_insn = insn;
1622 }
1623
1624 static void
1625 haifa_finish_insn (void)
1626 {
1627   cur_insn = NULL;
1628 }
1629
1630 void
1631 haifa_note_reg_set (int regno)
1632 {
1633   SET_REGNO_REG_SET (reg_pending_sets, regno);
1634 }
1635
1636 void
1637 haifa_note_reg_clobber (int regno)
1638 {
1639   SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1640 }
1641
1642 void
1643 haifa_note_reg_use (int regno)
1644 {
1645   SET_REGNO_REG_SET (reg_pending_uses, regno);
1646 }
1647
1648 static void
1649 haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx pending_insn, ds_t ds)
1650 {
1651   if (!(ds & SPECULATIVE))
1652     {
1653       mem = NULL_RTX;
1654       pending_mem = NULL_RTX;
1655     }
1656   else
1657     gcc_assert (ds & BEGIN_DATA);
1658
1659   {
1660     dep_def _dep, *dep = &_dep;
1661
1662     init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1663                 current_sched_info->flags & USE_DEPS_LIST ? ds : -1);
1664     maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1665   }
1666
1667 }
1668
1669 static void
1670 haifa_note_dep (rtx elem, ds_t ds)
1671 {
1672   dep_def _dep;
1673   dep_t dep = &_dep;
1674
1675   init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1676   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1677 }
1678
1679 static void
1680 note_reg_use (int r)
1681 {
1682   if (sched_deps_info->note_reg_use)
1683     sched_deps_info->note_reg_use (r);
1684 }
1685
1686 static void
1687 note_reg_set (int r)
1688 {
1689   if (sched_deps_info->note_reg_set)
1690     sched_deps_info->note_reg_set (r);
1691 }
1692
1693 static void
1694 note_reg_clobber (int r)
1695 {
1696   if (sched_deps_info->note_reg_clobber)
1697     sched_deps_info->note_reg_clobber (r);
1698 }
1699
1700 static void
1701 note_mem_dep (rtx m1, rtx m2, rtx e, ds_t ds)
1702 {
1703   if (sched_deps_info->note_mem_dep)
1704     sched_deps_info->note_mem_dep (m1, m2, e, ds);
1705 }
1706
1707 static void
1708 note_dep (rtx e, ds_t ds)
1709 {
1710   if (sched_deps_info->note_dep)
1711     sched_deps_info->note_dep (e, ds);
1712 }
1713
1714 /* Return corresponding to DS reg_note.  */
1715 enum reg_note
1716 ds_to_dt (ds_t ds)
1717 {
1718   if (ds & DEP_TRUE)
1719     return REG_DEP_TRUE;
1720   else if (ds & DEP_OUTPUT)
1721     return REG_DEP_OUTPUT;
1722   else
1723     {
1724       gcc_assert (ds & DEP_ANTI);
1725       return REG_DEP_ANTI;
1726     }
1727 }
1728
1729 \f
1730
1731 /* Functions for computation of info needed for register pressure
1732    sensitive insn scheduling.  */
1733
1734
1735 /* Allocate and return reg_use_data structure for REGNO and INSN.  */
1736 static struct reg_use_data *
1737 create_insn_reg_use (int regno, rtx insn)
1738 {
1739   struct reg_use_data *use;
1740
1741   use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1742   use->regno = regno;
1743   use->insn = insn;
1744   use->next_insn_use = INSN_REG_USE_LIST (insn);
1745   INSN_REG_USE_LIST (insn) = use;
1746   return use;
1747 }
1748
1749 /* Allocate and return reg_set_data structure for REGNO and INSN.  */
1750 static struct reg_set_data *
1751 create_insn_reg_set (int regno, rtx insn)
1752 {
1753   struct reg_set_data *set;
1754
1755   set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1756   set->regno = regno;
1757   set->insn = insn;
1758   set->next_insn_set = INSN_REG_SET_LIST (insn);
1759   INSN_REG_SET_LIST (insn) = set;
1760   return set;
1761 }
1762
1763 /* Set up insn register uses for INSN and dependency context DEPS.  */
1764 static void
1765 setup_insn_reg_uses (struct deps_desc *deps, rtx insn)
1766 {
1767   unsigned i;
1768   reg_set_iterator rsi;
1769   rtx list;
1770   struct reg_use_data *use, *use2, *next;
1771   struct deps_reg *reg_last;
1772
1773   EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1774     {
1775       if (i < FIRST_PSEUDO_REGISTER
1776           && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1777         continue;
1778
1779       if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1780           && ! REGNO_REG_SET_P (reg_pending_sets, i)
1781           && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1782         /* Ignore use which is not dying.  */
1783         continue;
1784
1785       use = create_insn_reg_use (i, insn);
1786       use->next_regno_use = use;
1787       reg_last = &deps->reg_last[i];
1788
1789       /* Create the cycle list of uses.  */
1790       for (list = reg_last->uses; list; list = XEXP (list, 1))
1791         {
1792           use2 = create_insn_reg_use (i, XEXP (list, 0));
1793           next = use->next_regno_use;
1794           use->next_regno_use = use2;
1795           use2->next_regno_use = next;
1796         }
1797     }
1798 }
1799
1800 /* Register pressure info for the currently processed insn.  */
1801 static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1802
1803 /* Return TRUE if INSN has the use structure for REGNO.  */
1804 static bool
1805 insn_use_p (rtx insn, int regno)
1806 {
1807   struct reg_use_data *use;
1808
1809   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1810     if (use->regno == regno)
1811       return true;
1812   return false;
1813 }
1814
1815 /* Update the register pressure info after birth of pseudo register REGNO
1816    in INSN.  Arguments CLOBBER_P and UNUSED_P say correspondingly that
1817    the register is in clobber or unused after the insn.  */
1818 static void
1819 mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
1820 {
1821   int incr, new_incr;
1822   enum reg_class cl;
1823
1824   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
1825   cl = sched_regno_pressure_class[regno];
1826   if (cl != NO_REGS)
1827     {
1828       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
1829       if (clobber_p)
1830         {
1831           new_incr = reg_pressure_info[cl].clobber_increase + incr;
1832           reg_pressure_info[cl].clobber_increase = new_incr;
1833         }
1834       else if (unused_p)
1835         {
1836           new_incr = reg_pressure_info[cl].unused_set_increase + incr;
1837           reg_pressure_info[cl].unused_set_increase = new_incr;
1838         }
1839       else
1840         {
1841           new_incr = reg_pressure_info[cl].set_increase + incr;
1842           reg_pressure_info[cl].set_increase = new_incr;
1843           if (! insn_use_p (insn, regno))
1844             reg_pressure_info[cl].change += incr;
1845           create_insn_reg_set (regno, insn);
1846         }
1847       gcc_assert (new_incr < (1 << INCREASE_BITS));
1848     }
1849 }
1850
1851 /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
1852    hard registers involved in the birth.  */
1853 static void
1854 mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
1855                             bool clobber_p, bool unused_p)
1856 {
1857   enum reg_class cl;
1858   int new_incr, last = regno + nregs;
1859
1860   while (regno < last)
1861     {
1862       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1863       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
1864         {
1865           cl = sched_regno_pressure_class[regno];
1866           if (cl != NO_REGS)
1867             {
1868               if (clobber_p)
1869                 {
1870                   new_incr = reg_pressure_info[cl].clobber_increase + 1;
1871                   reg_pressure_info[cl].clobber_increase = new_incr;
1872                 }
1873               else if (unused_p)
1874                 {
1875                   new_incr = reg_pressure_info[cl].unused_set_increase + 1;
1876                   reg_pressure_info[cl].unused_set_increase = new_incr;
1877                 }
1878               else
1879                 {
1880                   new_incr = reg_pressure_info[cl].set_increase + 1;
1881                   reg_pressure_info[cl].set_increase = new_incr;
1882                   if (! insn_use_p (insn, regno))
1883                     reg_pressure_info[cl].change += 1;
1884                   create_insn_reg_set (regno, insn);
1885                 }
1886               gcc_assert (new_incr < (1 << INCREASE_BITS));
1887             }
1888         }
1889       regno++;
1890     }
1891 }
1892
1893 /* Update the register pressure info after birth of pseudo or hard
1894    register REG in INSN.  Arguments CLOBBER_P and UNUSED_P say
1895    correspondingly that the register is in clobber or unused after the
1896    insn.  */
1897 static void
1898 mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
1899 {
1900   int regno;
1901
1902   if (GET_CODE (reg) == SUBREG)
1903     reg = SUBREG_REG (reg);
1904
1905   if (! REG_P (reg))
1906     return;
1907
1908   regno = REGNO (reg);
1909   if (regno < FIRST_PSEUDO_REGISTER)
1910     mark_insn_hard_regno_birth (insn, regno,
1911                                 hard_regno_nregs[regno][GET_MODE (reg)],
1912                                 clobber_p, unused_p);
1913   else
1914     mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
1915 }
1916
1917 /* Update the register pressure info after death of pseudo register
1918    REGNO.  */
1919 static void
1920 mark_pseudo_death (int regno)
1921 {
1922   int incr;
1923   enum reg_class cl;
1924
1925   gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
1926   cl = sched_regno_pressure_class[regno];
1927   if (cl != NO_REGS)
1928     {
1929       incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
1930       reg_pressure_info[cl].change -= incr;
1931     }
1932 }
1933
1934 /* Like mark_pseudo_death except that NREGS saying how many hard
1935    registers involved in the death.  */
1936 static void
1937 mark_hard_regno_death (int regno, int nregs)
1938 {
1939   enum reg_class cl;
1940   int last = regno + nregs;
1941
1942   while (regno < last)
1943     {
1944       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
1945       if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
1946         {
1947           cl = sched_regno_pressure_class[regno];
1948           if (cl != NO_REGS)
1949             reg_pressure_info[cl].change -= 1;
1950         }
1951       regno++;
1952     }
1953 }
1954
1955 /* Update the register pressure info after death of pseudo or hard
1956    register REG.  */
1957 static void
1958 mark_reg_death (rtx reg)
1959 {
1960   int regno;
1961
1962   if (GET_CODE (reg) == SUBREG)
1963     reg = SUBREG_REG (reg);
1964
1965   if (! REG_P (reg))
1966     return;
1967
1968   regno = REGNO (reg);
1969   if (regno < FIRST_PSEUDO_REGISTER)
1970     mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
1971   else
1972     mark_pseudo_death (regno);
1973 }
1974
1975 /* Process SETTER of REG.  DATA is an insn containing the setter.  */
1976 static void
1977 mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
1978 {
1979   if (setter != NULL_RTX && GET_CODE (setter) != SET)
1980     return;
1981   mark_insn_reg_birth
1982     ((rtx) data, reg, false,
1983      find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
1984 }
1985
1986 /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs.  */
1987 static void
1988 mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
1989 {
1990   if (GET_CODE (setter) == CLOBBER)
1991     mark_insn_reg_birth ((rtx) data, reg, true, false);
1992 }
1993
1994 /* Set up reg pressure info related to INSN.  */
1995 void
1996 init_insn_reg_pressure_info (rtx insn)
1997 {
1998   int i, len;
1999   enum reg_class cl;
2000   static struct reg_pressure_data *pressure_info;
2001   rtx link;
2002
2003   gcc_assert (sched_pressure_p);
2004
2005   if (! INSN_P (insn))
2006     return;
2007
2008   for (i = 0; i < ira_pressure_classes_num; i++)
2009     {
2010       cl = ira_pressure_classes[i];
2011       reg_pressure_info[cl].clobber_increase = 0;
2012       reg_pressure_info[cl].set_increase = 0;
2013       reg_pressure_info[cl].unused_set_increase = 0;
2014       reg_pressure_info[cl].change = 0;
2015     }
2016
2017   note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2018
2019   note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2020
2021 #ifdef AUTO_INC_DEC
2022   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2023     if (REG_NOTE_KIND (link) == REG_INC)
2024       mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2025 #endif
2026
2027   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2028     if (REG_NOTE_KIND (link) == REG_DEAD)
2029       mark_reg_death (XEXP (link, 0));
2030
2031   len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2032   pressure_info
2033     = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2034   INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2035                                                   * sizeof (int), 1);
2036   for (i = 0; i < ira_pressure_classes_num; i++)
2037     {
2038       cl = ira_pressure_classes[i];
2039       pressure_info[i].clobber_increase
2040         = reg_pressure_info[cl].clobber_increase;
2041       pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2042       pressure_info[i].unused_set_increase
2043         = reg_pressure_info[cl].unused_set_increase;
2044       pressure_info[i].change = reg_pressure_info[cl].change;
2045     }
2046 }
2047
2048
2049 \f
2050
2051 /* Internal variable for sched_analyze_[12] () functions.
2052    If it is nonzero, this means that sched_analyze_[12] looks
2053    at the most toplevel SET.  */
2054 static bool can_start_lhs_rhs_p;
2055
2056 /* Extend reg info for the deps context DEPS given that
2057    we have just generated a register numbered REGNO.  */
2058 static void
2059 extend_deps_reg_info (struct deps_desc *deps, int regno)
2060 {
2061   int max_regno = regno + 1;
2062
2063   gcc_assert (!reload_completed);
2064
2065   /* In a readonly context, it would not hurt to extend info,
2066      but it should not be needed.  */
2067   if (reload_completed && deps->readonly)
2068     {
2069       deps->max_reg = max_regno;
2070       return;
2071     }
2072
2073   if (max_regno > deps->max_reg)
2074     {
2075       deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2076                                    max_regno);
2077       memset (&deps->reg_last[deps->max_reg],
2078               0, (max_regno - deps->max_reg)
2079               * sizeof (struct deps_reg));
2080       deps->max_reg = max_regno;
2081     }
2082 }
2083
2084 /* Extends REG_INFO_P if needed.  */
2085 void
2086 maybe_extend_reg_info_p (void)
2087 {
2088   /* Extend REG_INFO_P, if needed.  */
2089   if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2090     {
2091       size_t new_reg_info_p_size = max_regno + 128;
2092
2093       gcc_assert (!reload_completed && sel_sched_p ());
2094
2095       reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2096                                                     new_reg_info_p_size,
2097                                                     reg_info_p_size,
2098                                                     sizeof (*reg_info_p));
2099       reg_info_p_size = new_reg_info_p_size;
2100     }
2101 }
2102
2103 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2104    The type of the reference is specified by REF and can be SET,
2105    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
2106
2107 static void
2108 sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
2109                    enum rtx_code ref, rtx insn)
2110 {
2111   /* We could emit new pseudos in renaming.  Extend the reg structures.  */
2112   if (!reload_completed && sel_sched_p ()
2113       && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2114     extend_deps_reg_info (deps, regno);
2115
2116   maybe_extend_reg_info_p ();
2117
2118   /* A hard reg in a wide mode may really be multiple registers.
2119      If so, mark all of them just like the first.  */
2120   if (regno < FIRST_PSEUDO_REGISTER)
2121     {
2122       int i = hard_regno_nregs[regno][mode];
2123       if (ref == SET)
2124         {
2125           while (--i >= 0)
2126             note_reg_set (regno + i);
2127         }
2128       else if (ref == USE)
2129         {
2130           while (--i >= 0)
2131             note_reg_use (regno + i);
2132         }
2133       else
2134         {
2135           while (--i >= 0)
2136             note_reg_clobber (regno + i);
2137         }
2138     }
2139
2140   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2141      it does not reload.  Ignore these as they have served their
2142      purpose already.  */
2143   else if (regno >= deps->max_reg)
2144     {
2145       enum rtx_code code = GET_CODE (PATTERN (insn));
2146       gcc_assert (code == USE || code == CLOBBER);
2147     }
2148
2149   else
2150     {
2151       if (ref == SET)
2152         note_reg_set (regno);
2153       else if (ref == USE)
2154         note_reg_use (regno);
2155       else
2156         note_reg_clobber (regno);
2157
2158       /* Pseudos that are REG_EQUIV to something may be replaced
2159          by that during reloading.  We need only add dependencies for
2160         the address in the REG_EQUIV note.  */
2161       if (!reload_completed && get_reg_known_equiv_p (regno))
2162         {
2163           rtx t = get_reg_known_value (regno);
2164           if (MEM_P (t))
2165             sched_analyze_2 (deps, XEXP (t, 0), insn);
2166         }
2167
2168       /* Don't let it cross a call after scheduling if it doesn't
2169          already cross one.  */
2170       if (REG_N_CALLS_CROSSED (regno) == 0)
2171         {
2172           if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2173             deps->sched_before_next_call
2174               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2175           else
2176             add_dependence_list (insn, deps->last_function_call, 1,
2177                                  REG_DEP_ANTI);
2178         }
2179     }
2180 }
2181
2182 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2183    rtx, X, creating all dependencies generated by the write to the
2184    destination of X, and reads of everything mentioned.  */
2185
2186 static void
2187 sched_analyze_1 (struct deps_desc *deps, rtx x, rtx insn)
2188 {
2189   rtx dest = XEXP (x, 0);
2190   enum rtx_code code = GET_CODE (x);
2191   bool cslr_p = can_start_lhs_rhs_p;
2192
2193   can_start_lhs_rhs_p = false;
2194
2195   gcc_assert (dest);
2196   if (dest == 0)
2197     return;
2198
2199   if (cslr_p && sched_deps_info->start_lhs)
2200     sched_deps_info->start_lhs (dest);
2201
2202   if (GET_CODE (dest) == PARALLEL)
2203     {
2204       int i;
2205
2206       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2207         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2208           sched_analyze_1 (deps,
2209                            gen_rtx_CLOBBER (VOIDmode,
2210                                             XEXP (XVECEXP (dest, 0, i), 0)),
2211                            insn);
2212
2213       if (cslr_p && sched_deps_info->finish_lhs)
2214         sched_deps_info->finish_lhs ();
2215
2216       if (code == SET)
2217         {
2218           can_start_lhs_rhs_p = cslr_p;
2219
2220           sched_analyze_2 (deps, SET_SRC (x), insn);
2221
2222           can_start_lhs_rhs_p = false;
2223         }
2224
2225       return;
2226     }
2227
2228   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2229          || GET_CODE (dest) == ZERO_EXTRACT)
2230     {
2231       if (GET_CODE (dest) == STRICT_LOW_PART
2232          || GET_CODE (dest) == ZERO_EXTRACT
2233          || df_read_modify_subreg_p (dest))
2234         {
2235           /* These both read and modify the result.  We must handle
2236              them as writes to get proper dependencies for following
2237              instructions.  We must handle them as reads to get proper
2238              dependencies from this to previous instructions.
2239              Thus we need to call sched_analyze_2.  */
2240
2241           sched_analyze_2 (deps, XEXP (dest, 0), insn);
2242         }
2243       if (GET_CODE (dest) == ZERO_EXTRACT)
2244         {
2245           /* The second and third arguments are values read by this insn.  */
2246           sched_analyze_2 (deps, XEXP (dest, 1), insn);
2247           sched_analyze_2 (deps, XEXP (dest, 2), insn);
2248         }
2249       dest = XEXP (dest, 0);
2250     }
2251
2252   if (REG_P (dest))
2253     {
2254       int regno = REGNO (dest);
2255       enum machine_mode mode = GET_MODE (dest);
2256
2257       sched_analyze_reg (deps, regno, mode, code, insn);
2258
2259 #ifdef STACK_REGS
2260       /* Treat all writes to a stack register as modifying the TOS.  */
2261       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2262         {
2263           /* Avoid analyzing the same register twice.  */
2264           if (regno != FIRST_STACK_REG)
2265             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2266
2267           add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2268                                FIRST_STACK_REG);
2269         }
2270 #endif
2271     }
2272   else if (MEM_P (dest))
2273     {
2274       /* Writing memory.  */
2275       rtx t = dest;
2276
2277       if (sched_deps_info->use_cselib)
2278         {
2279           enum machine_mode address_mode
2280             = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest));
2281
2282           t = shallow_copy_rtx (dest);
2283           cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2284                                    GET_MODE (t), insn);
2285           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0), GET_MODE (t));
2286         }
2287       t = canon_rtx (t);
2288
2289       /* Pending lists can't get larger with a readonly context.  */
2290       if (!deps->readonly
2291           && ((deps->pending_read_list_length + deps->pending_write_list_length)
2292               > MAX_PENDING_LIST_LENGTH))
2293         {
2294           /* Flush all pending reads and writes to prevent the pending lists
2295              from getting any larger.  Insn scheduling runs too slowly when
2296              these lists get long.  When compiling GCC with itself,
2297              this flush occurs 8 times for sparc, and 10 times for m88k using
2298              the default value of 32.  */
2299           flush_pending_lists (deps, insn, false, true);
2300         }
2301       else
2302         {
2303           rtx pending, pending_mem;
2304
2305           pending = deps->pending_read_insns;
2306           pending_mem = deps->pending_read_mems;
2307           while (pending)
2308             {
2309               if (anti_dependence (XEXP (pending_mem, 0), t)
2310                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2311                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2312                               DEP_ANTI);
2313
2314               pending = XEXP (pending, 1);
2315               pending_mem = XEXP (pending_mem, 1);
2316             }
2317
2318           pending = deps->pending_write_insns;
2319           pending_mem = deps->pending_write_mems;
2320           while (pending)
2321             {
2322               if (output_dependence (XEXP (pending_mem, 0), t)
2323                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2324                 note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2325                               DEP_OUTPUT);
2326
2327               pending = XEXP (pending, 1);
2328               pending_mem = XEXP (pending_mem, 1);
2329             }
2330
2331           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2332                                REG_DEP_ANTI);
2333
2334           if (!deps->readonly)
2335             add_insn_mem_dependence (deps, false, insn, dest);
2336         }
2337       sched_analyze_2 (deps, XEXP (dest, 0), insn);
2338     }
2339
2340   if (cslr_p && sched_deps_info->finish_lhs)
2341     sched_deps_info->finish_lhs ();
2342
2343   /* Analyze reads.  */
2344   if (GET_CODE (x) == SET)
2345     {
2346       can_start_lhs_rhs_p = cslr_p;
2347
2348       sched_analyze_2 (deps, SET_SRC (x), insn);
2349
2350       can_start_lhs_rhs_p = false;
2351     }
2352 }
2353
2354 /* Analyze the uses of memory and registers in rtx X in INSN.  */
2355 static void
2356 sched_analyze_2 (struct deps_desc *deps, rtx x, rtx insn)
2357 {
2358   int i;
2359   int j;
2360   enum rtx_code code;
2361   const char *fmt;
2362   bool cslr_p = can_start_lhs_rhs_p;
2363
2364   can_start_lhs_rhs_p = false;
2365
2366   gcc_assert (x);
2367   if (x == 0)
2368     return;
2369
2370   if (cslr_p && sched_deps_info->start_rhs)
2371     sched_deps_info->start_rhs (x);
2372
2373   code = GET_CODE (x);
2374
2375   switch (code)
2376     {
2377     case CONST_INT:
2378     case CONST_DOUBLE:
2379     case CONST_FIXED:
2380     case CONST_VECTOR:
2381     case SYMBOL_REF:
2382     case CONST:
2383     case LABEL_REF:
2384       /* Ignore constants.  */
2385       if (cslr_p && sched_deps_info->finish_rhs)
2386         sched_deps_info->finish_rhs ();
2387
2388       return;
2389
2390 #ifdef HAVE_cc0
2391     case CC0:
2392       /* User of CC0 depends on immediately preceding insn.  */
2393       SCHED_GROUP_P (insn) = 1;
2394        /* Don't move CC0 setter to another block (it can set up the
2395         same flag for previous CC0 users which is safe).  */
2396       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2397
2398       if (cslr_p && sched_deps_info->finish_rhs)
2399         sched_deps_info->finish_rhs ();
2400
2401       return;
2402 #endif
2403
2404     case REG:
2405       {
2406         int regno = REGNO (x);
2407         enum machine_mode mode = GET_MODE (x);
2408
2409         sched_analyze_reg (deps, regno, mode, USE, insn);
2410
2411 #ifdef STACK_REGS
2412       /* Treat all reads of a stack register as modifying the TOS.  */
2413       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2414         {
2415           /* Avoid analyzing the same register twice.  */
2416           if (regno != FIRST_STACK_REG)
2417             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2418           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2419         }
2420 #endif
2421
2422         if (cslr_p && sched_deps_info->finish_rhs)
2423           sched_deps_info->finish_rhs ();
2424
2425         return;
2426       }
2427
2428     case MEM:
2429       {
2430         /* Reading memory.  */
2431         rtx u;
2432         rtx pending, pending_mem;
2433         rtx t = x;
2434
2435         if (sched_deps_info->use_cselib)
2436           {
2437             enum machine_mode address_mode
2438               = targetm.addr_space.address_mode (MEM_ADDR_SPACE (t));
2439
2440             t = shallow_copy_rtx (t);
2441             cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2442                                      GET_MODE (t), insn);
2443             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0), GET_MODE (t));
2444           }
2445
2446         if (!DEBUG_INSN_P (insn))
2447           {
2448             t = canon_rtx (t);
2449             pending = deps->pending_read_insns;
2450             pending_mem = deps->pending_read_mems;
2451             while (pending)
2452               {
2453                 if (read_dependence (XEXP (pending_mem, 0), t)
2454                     && ! sched_insns_conditions_mutex_p (insn,
2455                                                          XEXP (pending, 0)))
2456                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2457                                 DEP_ANTI);
2458
2459                 pending = XEXP (pending, 1);
2460                 pending_mem = XEXP (pending_mem, 1);
2461               }
2462
2463             pending = deps->pending_write_insns;
2464             pending_mem = deps->pending_write_mems;
2465             while (pending)
2466               {
2467                 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
2468                                      t, rtx_varies_p)
2469                     && ! sched_insns_conditions_mutex_p (insn,
2470                                                          XEXP (pending, 0)))
2471                   note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
2472                                 sched_deps_info->generate_spec_deps
2473                                 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2474
2475                 pending = XEXP (pending, 1);
2476                 pending_mem = XEXP (pending_mem, 1);
2477               }
2478
2479             for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2480               {
2481                 if (! NON_FLUSH_JUMP_P (u))
2482                   add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2483                 else if (deps_may_trap_p (x))
2484                   {
2485                     if ((sched_deps_info->generate_spec_deps)
2486                         && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2487                       {
2488                         ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2489                                                 MAX_DEP_WEAK);
2490
2491                         note_dep (XEXP (u, 0), ds);
2492                       }
2493                     else
2494                       add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2495                   }
2496               }
2497           }
2498
2499         /* Always add these dependencies to pending_reads, since
2500            this insn may be followed by a write.  */
2501         if (!deps->readonly)
2502           add_insn_mem_dependence (deps, true, insn, x);
2503
2504         sched_analyze_2 (deps, XEXP (x, 0), insn);
2505
2506         if (cslr_p && sched_deps_info->finish_rhs)
2507           sched_deps_info->finish_rhs ();
2508
2509         return;
2510       }
2511
2512     /* Force pending stores to memory in case a trap handler needs them.  */
2513     case TRAP_IF:
2514       flush_pending_lists (deps, insn, true, false);
2515       break;
2516
2517     case PREFETCH:
2518       if (PREFETCH_SCHEDULE_BARRIER_P (x))
2519         reg_pending_barrier = TRUE_BARRIER;
2520       break;
2521
2522     case UNSPEC_VOLATILE:
2523       flush_pending_lists (deps, insn, true, true);
2524       /* FALLTHRU */
2525
2526     case ASM_OPERANDS:
2527     case ASM_INPUT:
2528       {
2529         /* Traditional and volatile asm instructions must be considered to use
2530            and clobber all hard registers, all pseudo-registers and all of
2531            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
2532
2533            Consider for instance a volatile asm that changes the fpu rounding
2534            mode.  An insn should not be moved across this even if it only uses
2535            pseudo-regs because it might give an incorrectly rounded result.  */
2536         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2537           reg_pending_barrier = TRUE_BARRIER;
2538
2539         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2540            We can not just fall through here since then we would be confused
2541            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2542            traditional asms unlike their normal usage.  */
2543
2544         if (code == ASM_OPERANDS)
2545           {
2546             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2547               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2548
2549             if (cslr_p && sched_deps_info->finish_rhs)
2550               sched_deps_info->finish_rhs ();
2551
2552             return;
2553           }
2554         break;
2555       }
2556
2557     case PRE_DEC:
2558     case POST_DEC:
2559     case PRE_INC:
2560     case POST_INC:
2561       /* These both read and modify the result.  We must handle them as writes
2562          to get proper dependencies for following instructions.  We must handle
2563          them as reads to get proper dependencies from this to previous
2564          instructions.  Thus we need to pass them to both sched_analyze_1
2565          and sched_analyze_2.  We must call sched_analyze_2 first in order
2566          to get the proper antecedent for the read.  */
2567       sched_analyze_2 (deps, XEXP (x, 0), insn);
2568       sched_analyze_1 (deps, x, insn);
2569
2570       if (cslr_p && sched_deps_info->finish_rhs)
2571         sched_deps_info->finish_rhs ();
2572
2573       return;
2574
2575     case POST_MODIFY:
2576     case PRE_MODIFY:
2577       /* op0 = op0 + op1 */
2578       sched_analyze_2 (deps, XEXP (x, 0), insn);
2579       sched_analyze_2 (deps, XEXP (x, 1), insn);
2580       sched_analyze_1 (deps, x, insn);
2581
2582       if (cslr_p && sched_deps_info->finish_rhs)
2583         sched_deps_info->finish_rhs ();
2584
2585       return;
2586
2587     default:
2588       break;
2589     }
2590
2591   /* Other cases: walk the insn.  */
2592   fmt = GET_RTX_FORMAT (code);
2593   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2594     {
2595       if (fmt[i] == 'e')
2596         sched_analyze_2 (deps, XEXP (x, i), insn);
2597       else if (fmt[i] == 'E')
2598         for (j = 0; j < XVECLEN (x, i); j++)
2599           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2600     }
2601
2602   if (cslr_p && sched_deps_info->finish_rhs)
2603     sched_deps_info->finish_rhs ();
2604 }
2605
2606 /* Analyze an INSN with pattern X to find all dependencies.  */
2607 static void
2608 sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
2609 {
2610   RTX_CODE code = GET_CODE (x);
2611   rtx link;
2612   unsigned i;
2613   reg_set_iterator rsi;
2614
2615   if (! reload_completed)
2616     {
2617       HARD_REG_SET temp;
2618
2619       extract_insn (insn);
2620       preprocess_constraints ();
2621       ira_implicitly_set_insn_hard_regs (&temp);
2622       AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2623       IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2624     }
2625
2626   can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2627                          && code == SET);
2628
2629   if (may_trap_p (x))
2630     /* Avoid moving trapping instructions accross function calls that might
2631        not always return.  */
2632     add_dependence_list (insn, deps->last_function_call_may_noreturn,
2633                          1, REG_DEP_ANTI);
2634
2635   if (code == COND_EXEC)
2636     {
2637       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2638
2639       /* ??? Should be recording conditions so we reduce the number of
2640          false dependencies.  */
2641       x = COND_EXEC_CODE (x);
2642       code = GET_CODE (x);
2643     }
2644   if (code == SET || code == CLOBBER)
2645     {
2646       sched_analyze_1 (deps, x, insn);
2647
2648       /* Bare clobber insns are used for letting life analysis, reg-stack
2649          and others know that a value is dead.  Depend on the last call
2650          instruction so that reg-stack won't get confused.  */
2651       if (code == CLOBBER)
2652         add_dependence_list (insn, deps->last_function_call, 1,
2653                              REG_DEP_OUTPUT);
2654     }
2655   else if (code == PARALLEL)
2656     {
2657       for (i = XVECLEN (x, 0); i--;)
2658         {
2659           rtx sub = XVECEXP (x, 0, i);
2660           code = GET_CODE (sub);
2661
2662           if (code == COND_EXEC)
2663             {
2664               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2665               sub = COND_EXEC_CODE (sub);
2666               code = GET_CODE (sub);
2667             }
2668           if (code == SET || code == CLOBBER)
2669             sched_analyze_1 (deps, sub, insn);
2670           else
2671             sched_analyze_2 (deps, sub, insn);
2672         }
2673     }
2674   else
2675     sched_analyze_2 (deps, x, insn);
2676
2677   /* Mark registers CLOBBERED or used by called function.  */
2678   if (CALL_P (insn))
2679     {
2680       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2681         {
2682           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2683             sched_analyze_1 (deps, XEXP (link, 0), insn);
2684           else
2685             sched_analyze_2 (deps, XEXP (link, 0), insn);
2686         }
2687       if (find_reg_note (insn, REG_SETJMP, NULL))
2688         reg_pending_barrier = MOVE_BARRIER;
2689     }
2690
2691   if (JUMP_P (insn))
2692     {
2693       rtx next;
2694       next = next_nonnote_nondebug_insn (insn);
2695       if (next && BARRIER_P (next))
2696         reg_pending_barrier = MOVE_BARRIER;
2697       else
2698         {
2699           rtx pending, pending_mem;
2700
2701           if (sched_deps_info->compute_jump_reg_dependencies)
2702             {
2703               regset_head tmp_uses, tmp_sets;
2704               INIT_REG_SET (&tmp_uses);
2705               INIT_REG_SET (&tmp_sets);
2706
2707               (*sched_deps_info->compute_jump_reg_dependencies)
2708                 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
2709               /* Make latency of jump equal to 0 by using anti-dependence.  */
2710               EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
2711                 {
2712                   struct deps_reg *reg_last = &deps->reg_last[i];
2713                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2714                   add_dependence_list (insn, reg_last->implicit_sets,
2715                                        0, REG_DEP_ANTI);
2716                   add_dependence_list (insn, reg_last->clobbers, 0,
2717                                        REG_DEP_ANTI);
2718
2719                   if (!deps->readonly)
2720                     {
2721                       reg_last->uses_length++;
2722                       reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2723                     }
2724                 }
2725               IOR_REG_SET (reg_pending_sets, &tmp_sets);
2726
2727               CLEAR_REG_SET (&tmp_uses);
2728               CLEAR_REG_SET (&tmp_sets);
2729             }
2730
2731           /* All memory writes and volatile reads must happen before the
2732              jump.  Non-volatile reads must happen before the jump iff
2733              the result is needed by the above register used mask.  */
2734
2735           pending = deps->pending_write_insns;
2736           pending_mem = deps->pending_write_mems;
2737           while (pending)
2738             {
2739               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2740                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2741               pending = XEXP (pending, 1);
2742               pending_mem = XEXP (pending_mem, 1);
2743             }
2744
2745           pending = deps->pending_read_insns;
2746           pending_mem = deps->pending_read_mems;
2747           while (pending)
2748             {
2749               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
2750                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
2751                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
2752               pending = XEXP (pending, 1);
2753               pending_mem = XEXP (pending_mem, 1);
2754             }
2755
2756           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2757                                REG_DEP_ANTI);
2758         }
2759     }
2760
2761   /* If this instruction can throw an exception, then moving it changes
2762      where block boundaries fall.  This is mighty confusing elsewhere.
2763      Therefore, prevent such an instruction from being moved.  Same for
2764      non-jump instructions that define block boundaries.
2765      ??? Unclear whether this is still necessary in EBB mode.  If not,
2766      add_branch_dependences should be adjusted for RGN mode instead.  */
2767   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
2768       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
2769     reg_pending_barrier = MOVE_BARRIER;
2770
2771   if (sched_pressure_p)
2772     {
2773       setup_insn_reg_uses (deps, insn);
2774       init_insn_reg_pressure_info (insn);
2775     }
2776
2777   /* Add register dependencies for insn.  */
2778   if (DEBUG_INSN_P (insn))
2779     {
2780       rtx prev = deps->last_debug_insn;
2781       rtx u;
2782
2783       if (!deps->readonly)
2784         deps->last_debug_insn = insn;
2785
2786       if (prev)
2787         add_dependence (insn, prev, REG_DEP_ANTI);
2788
2789       add_dependence_list (insn, deps->last_function_call, 1,
2790                            REG_DEP_ANTI);
2791
2792       for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
2793         if (! NON_FLUSH_JUMP_P (u) || !sel_sched_p ())
2794           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2795
2796       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2797         {
2798           struct deps_reg *reg_last = &deps->reg_last[i];
2799           add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
2800           add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
2801
2802           if (!deps->readonly)
2803             reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2804         }
2805       CLEAR_REG_SET (reg_pending_uses);
2806
2807       /* Quite often, a debug insn will refer to stuff in the
2808          previous instruction, but the reason we want this
2809          dependency here is to make sure the scheduler doesn't
2810          gratuitously move a debug insn ahead.  This could dirty
2811          DF flags and cause additional analysis that wouldn't have
2812          occurred in compilation without debug insns, and such
2813          additional analysis can modify the generated code.  */
2814       prev = PREV_INSN (insn);
2815
2816       if (prev && NONDEBUG_INSN_P (prev))
2817         add_dependence (insn, prev, REG_DEP_ANTI);
2818     }
2819   else
2820     {
2821       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2822         {
2823           struct deps_reg *reg_last = &deps->reg_last[i];
2824           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2825           add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI);
2826           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2827
2828           if (!deps->readonly)
2829             {
2830               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2831               reg_last->uses_length++;
2832             }
2833         }
2834
2835       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2836         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
2837           {
2838             struct deps_reg *reg_last = &deps->reg_last[i];
2839             add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2840             add_dependence_list (insn, reg_last->implicit_sets, 0,
2841                                  REG_DEP_ANTI);
2842             add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2843
2844             if (!deps->readonly)
2845               {
2846                 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2847                 reg_last->uses_length++;
2848               }
2849           }
2850
2851       /* If the current insn is conditional, we can't free any
2852          of the lists.  */
2853       if (sched_has_condition_p (insn))
2854         {
2855           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2856             {
2857               struct deps_reg *reg_last = &deps->reg_last[i];
2858               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2859               add_dependence_list (insn, reg_last->implicit_sets, 0,
2860                                    REG_DEP_ANTI);
2861               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2862
2863               if (!deps->readonly)
2864                 {
2865                   reg_last->clobbers
2866                     = alloc_INSN_LIST (insn, reg_last->clobbers);
2867                   reg_last->clobbers_length++;
2868                 }
2869             }
2870           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2871             {
2872               struct deps_reg *reg_last = &deps->reg_last[i];
2873               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2874               add_dependence_list (insn, reg_last->implicit_sets, 0,
2875                                    REG_DEP_ANTI);
2876               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
2877               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2878
2879               if (!deps->readonly)
2880                 {
2881                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2882                   SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2883                 }
2884             }
2885         }
2886       else
2887         {
2888           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2889             {
2890               struct deps_reg *reg_last = &deps->reg_last[i];
2891               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
2892                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
2893                 {
2894                   add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
2895                                                 REG_DEP_OUTPUT);
2896                   add_dependence_list_and_free (deps, insn,
2897                                                 &reg_last->implicit_sets, 0,
2898                                                 REG_DEP_ANTI);
2899                   add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
2900                                                 REG_DEP_ANTI);
2901                   add_dependence_list_and_free
2902                     (deps, insn, &reg_last->clobbers, 0, REG_DEP_OUTPUT);
2903
2904                   if (!deps->readonly)
2905                     {
2906                       reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2907                       reg_last->clobbers_length = 0;
2908                       reg_last->uses_length = 0;
2909                     }
2910                 }
2911               else
2912                 {
2913                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2914                   add_dependence_list (insn, reg_last->implicit_sets, 0,
2915                                        REG_DEP_ANTI);
2916                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2917                 }
2918
2919               if (!deps->readonly)
2920                 {
2921                   reg_last->clobbers_length++;
2922                   reg_last->clobbers
2923                     = alloc_INSN_LIST (insn, reg_last->clobbers);
2924                 }
2925             }
2926           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2927             {
2928               struct deps_reg *reg_last = &deps->reg_last[i];
2929
2930               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
2931                                             REG_DEP_OUTPUT);
2932               add_dependence_list_and_free (deps, insn,
2933                                             &reg_last->implicit_sets,
2934                                             0, REG_DEP_ANTI);
2935               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
2936                                             REG_DEP_OUTPUT);
2937               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
2938                                             REG_DEP_ANTI);
2939
2940               if (!deps->readonly)
2941                 {
2942                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2943                   reg_last->uses_length = 0;
2944                   reg_last->clobbers_length = 0;
2945                   CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2946                 }
2947             }
2948         }
2949     }
2950
2951   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2952     if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
2953       {
2954         struct deps_reg *reg_last = &deps->reg_last[i];
2955         add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
2956         add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
2957         add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2958
2959         if (!deps->readonly)
2960           reg_last->implicit_sets
2961             = alloc_INSN_LIST (insn, reg_last->implicit_sets);
2962       }
2963
2964   if (!deps->readonly)
2965     {
2966       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
2967       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
2968       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
2969       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2970         if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
2971             || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
2972           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2973
2974       /* Set up the pending barrier found.  */
2975       deps->last_reg_pending_barrier = reg_pending_barrier;
2976     }
2977
2978   CLEAR_REG_SET (reg_pending_uses);
2979   CLEAR_REG_SET (reg_pending_clobbers);
2980   CLEAR_REG_SET (reg_pending_sets);
2981   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
2982   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
2983
2984   /* Add dependencies if a scheduling barrier was found.  */
2985   if (reg_pending_barrier)
2986     {
2987       /* In the case of barrier the most added dependencies are not
2988          real, so we use anti-dependence here.  */
2989       if (sched_has_condition_p (insn))
2990         {
2991           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2992             {
2993               struct deps_reg *reg_last = &deps->reg_last[i];
2994               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2995               add_dependence_list (insn, reg_last->sets, 0,
2996                                    reg_pending_barrier == TRUE_BARRIER
2997                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
2998               add_dependence_list (insn, reg_last->implicit_sets, 0,
2999                                    REG_DEP_ANTI);
3000               add_dependence_list (insn, reg_last->clobbers, 0,
3001                                    reg_pending_barrier == TRUE_BARRIER
3002                                    ? REG_DEP_TRUE : REG_DEP_ANTI);
3003             }
3004         }
3005       else
3006         {
3007           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3008             {
3009               struct deps_reg *reg_last = &deps->reg_last[i];
3010               add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3011                                             REG_DEP_ANTI);
3012               add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3013                                             reg_pending_barrier == TRUE_BARRIER
3014                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3015               add_dependence_list_and_free (deps, insn,
3016                                             &reg_last->implicit_sets, 0,
3017                                             REG_DEP_ANTI);
3018               add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3019                                             reg_pending_barrier == TRUE_BARRIER
3020                                             ? REG_DEP_TRUE : REG_DEP_ANTI);
3021
3022               if (!deps->readonly)
3023                 {
3024                   reg_last->uses_length = 0;
3025                   reg_last->clobbers_length = 0;
3026                 }
3027             }
3028         }
3029
3030       if (!deps->readonly)
3031         for (i = 0; i < (unsigned)deps->max_reg; i++)
3032           {
3033             struct deps_reg *reg_last = &deps->reg_last[i];
3034             reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3035             SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3036           }
3037
3038       /* Flush pending lists on jumps, but not on speculative checks.  */
3039       if (JUMP_P (insn) && !(sel_sched_p ()
3040                              && sel_insn_is_speculation_check (insn)))
3041         flush_pending_lists (deps, insn, true, true);
3042
3043       if (!deps->readonly)
3044         CLEAR_REG_SET (&deps->reg_conditional_sets);
3045       reg_pending_barrier = NOT_A_BARRIER;
3046     }
3047
3048   /* If a post-call group is still open, see if it should remain so.
3049      This insn must be a simple move of a hard reg to a pseudo or
3050      vice-versa.
3051
3052      We must avoid moving these insns for correctness on targets
3053      with small register classes, and for special registers like
3054      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
3055      hard regs for all targets.  */
3056
3057   if (deps->in_post_call_group_p)
3058     {
3059       rtx tmp, set = single_set (insn);
3060       int src_regno, dest_regno;
3061
3062       if (set == NULL)
3063         {
3064           if (DEBUG_INSN_P (insn))
3065             /* We don't want to mark debug insns as part of the same
3066                sched group.  We know they really aren't, but if we use
3067                debug insns to tell that a call group is over, we'll
3068                get different code if debug insns are not there and
3069                instructions that follow seem like they should be part
3070                of the call group.
3071
3072                Also, if we did, fixup_sched_groups() would move the
3073                deps of the debug insn to the call insn, modifying
3074                non-debug post-dependency counts of the debug insn
3075                dependencies and otherwise messing with the scheduling
3076                order.
3077
3078                Instead, let such debug insns be scheduled freely, but
3079                keep the call group open in case there are insns that
3080                should be part of it afterwards.  Since we grant debug
3081                insns higher priority than even sched group insns, it
3082                will all turn out all right.  */
3083             goto debug_dont_end_call_group;
3084           else
3085             goto end_call_group;
3086         }
3087
3088       tmp = SET_DEST (set);
3089       if (GET_CODE (tmp) == SUBREG)
3090         tmp = SUBREG_REG (tmp);
3091       if (REG_P (tmp))
3092         dest_regno = REGNO (tmp);
3093       else
3094         goto end_call_group;
3095
3096       tmp = SET_SRC (set);
3097       if (GET_CODE (tmp) == SUBREG)
3098         tmp = SUBREG_REG (tmp);
3099       if ((GET_CODE (tmp) == PLUS
3100            || GET_CODE (tmp) == MINUS)
3101           && REG_P (XEXP (tmp, 0))
3102           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3103           && dest_regno == STACK_POINTER_REGNUM)
3104         src_regno = STACK_POINTER_REGNUM;
3105       else if (REG_P (tmp))
3106         src_regno = REGNO (tmp);
3107       else
3108         goto end_call_group;
3109
3110       if (src_regno < FIRST_PSEUDO_REGISTER
3111           || dest_regno < FIRST_PSEUDO_REGISTER)
3112         {
3113           if (!deps->readonly
3114               && deps->in_post_call_group_p == post_call_initial)
3115             deps->in_post_call_group_p = post_call;
3116
3117           if (!sel_sched_p () || sched_emulate_haifa_p)
3118             {
3119               SCHED_GROUP_P (insn) = 1;
3120               CANT_MOVE (insn) = 1;
3121             }
3122         }
3123       else
3124         {
3125         end_call_group:
3126           if (!deps->readonly)
3127             deps->in_post_call_group_p = not_post_call;
3128         }
3129     }
3130
3131  debug_dont_end_call_group:
3132   if ((current_sched_info->flags & DO_SPECULATION)
3133       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3134     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3135        be speculated.  */
3136     {
3137       if (sel_sched_p ())
3138         sel_mark_hard_insn (insn);
3139       else
3140         {
3141           sd_iterator_def sd_it;
3142           dep_t dep;
3143
3144           for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3145                sd_iterator_cond (&sd_it, &dep);)
3146             change_spec_dep_to_hard (sd_it);
3147         }
3148     }
3149 }
3150
3151 /* Return TRUE if INSN might not always return normally (e.g. call exit,
3152    longjmp, loop forever, ...).  */
3153 static bool
3154 call_may_noreturn_p (rtx insn)
3155 {
3156   rtx call;
3157
3158   /* const or pure calls that aren't looping will always return.  */
3159   if (RTL_CONST_OR_PURE_CALL_P (insn)
3160       && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3161     return false;
3162
3163   call = PATTERN (insn);
3164   if (GET_CODE (call) == PARALLEL)
3165     call = XVECEXP (call, 0, 0);
3166   if (GET_CODE (call) == SET)
3167     call = SET_SRC (call);
3168   if (GET_CODE (call) == CALL
3169       && MEM_P (XEXP (call, 0))
3170       && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3171     {
3172       rtx symbol = XEXP (XEXP (call, 0), 0);
3173       if (SYMBOL_REF_DECL (symbol)
3174           && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3175         {
3176           if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3177               == BUILT_IN_NORMAL)
3178             switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3179               {
3180               case BUILT_IN_BCMP:
3181               case BUILT_IN_BCOPY:
3182               case BUILT_IN_BZERO:
3183               case BUILT_IN_INDEX:
3184               case BUILT_IN_MEMCHR:
3185               case BUILT_IN_MEMCMP:
3186               case BUILT_IN_MEMCPY:
3187               case BUILT_IN_MEMMOVE:
3188               case BUILT_IN_MEMPCPY:
3189               case BUILT_IN_MEMSET:
3190               case BUILT_IN_RINDEX:
3191               case BUILT_IN_STPCPY:
3192               case BUILT_IN_STPNCPY:
3193               case BUILT_IN_STRCAT:
3194               case BUILT_IN_STRCHR:
3195               case BUILT_IN_STRCMP:
3196               case BUILT_IN_STRCPY:
3197               case BUILT_IN_STRCSPN:
3198               case BUILT_IN_STRLEN:
3199               case BUILT_IN_STRNCAT:
3200               case BUILT_IN_STRNCMP:
3201               case BUILT_IN_STRNCPY:
3202               case BUILT_IN_STRPBRK:
3203               case BUILT_IN_STRRCHR:
3204               case BUILT_IN_STRSPN:
3205               case BUILT_IN_STRSTR:
3206                 /* Assume certain string/memory builtins always return.  */
3207                 return false;
3208               default:
3209                 break;
3210               }
3211         }
3212     }
3213
3214   /* For all other calls assume that they might not always return.  */
3215   return true;
3216 }
3217
3218 /* Analyze INSN with DEPS as a context.  */
3219 void
3220 deps_analyze_insn (struct deps_desc *deps, rtx insn)
3221 {
3222   if (sched_deps_info->start_insn)
3223     sched_deps_info->start_insn (insn);
3224
3225   if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn) || JUMP_P (insn))
3226     {
3227       /* Make each JUMP_INSN (but not a speculative check)
3228          a scheduling barrier for memory references.  */
3229       if (!deps->readonly
3230           && JUMP_P (insn)
3231           && !(sel_sched_p ()
3232                && sel_insn_is_speculation_check (insn)))
3233         {
3234           /* Keep the list a reasonable size.  */
3235           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
3236             flush_pending_lists (deps, insn, true, true);
3237           else
3238             {
3239               deps->last_pending_memory_flush
3240                 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
3241               /* Signal to sched_analyze_insn that this jump stands
3242                  just for its own, not any other pending memory
3243                  reads/writes flush_pending_lists had to flush.  */
3244               PUT_REG_NOTE_KIND (deps->last_pending_memory_flush,
3245                                  NON_FLUSH_JUMP_KIND);
3246             }
3247         }
3248
3249       sched_analyze_insn (deps, PATTERN (insn), insn);
3250     }
3251   else if (CALL_P (insn))
3252     {
3253       int i;
3254
3255       CANT_MOVE (insn) = 1;
3256
3257       if (find_reg_note (insn, REG_SETJMP, NULL))
3258         {
3259           /* This is setjmp.  Assume that all registers, not just
3260              hard registers, may be clobbered by this call.  */
3261           reg_pending_barrier = MOVE_BARRIER;
3262         }
3263       else
3264         {
3265           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3266             /* A call may read and modify global register variables.  */
3267             if (global_regs[i])
3268               {
3269                 SET_REGNO_REG_SET (reg_pending_sets, i);
3270                 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3271               }
3272           /* Other call-clobbered hard regs may be clobbered.
3273              Since we only have a choice between 'might be clobbered'
3274              and 'definitely not clobbered', we must include all
3275              partly call-clobbered registers here.  */
3276             else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
3277                      || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3278               SET_REGNO_REG_SET (reg_pending_clobbers, i);
3279           /* We don't know what set of fixed registers might be used
3280              by the function, but it is certain that the stack pointer
3281              is among them, but be conservative.  */
3282             else if (fixed_regs[i])
3283               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3284           /* The frame pointer is normally not used by the function
3285              itself, but by the debugger.  */
3286           /* ??? MIPS o32 is an exception.  It uses the frame pointer
3287              in the macro expansion of jal but does not represent this
3288              fact in the call_insn rtl.  */
3289             else if (i == FRAME_POINTER_REGNUM
3290                      || (i == HARD_FRAME_POINTER_REGNUM
3291                          && (! reload_completed || frame_pointer_needed)))
3292               SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3293         }
3294
3295       /* For each insn which shouldn't cross a call, add a dependence
3296          between that insn and this call insn.  */
3297       add_dependence_list_and_free (deps, insn,
3298                                     &deps->sched_before_next_call, 1,
3299                                     REG_DEP_ANTI);
3300
3301       sched_analyze_insn (deps, PATTERN (insn), insn);
3302
3303       /* If CALL would be in a sched group, then this will violate
3304          convention that sched group insns have dependencies only on the
3305          previous instruction.
3306
3307          Of course one can say: "Hey!  What about head of the sched group?"
3308          And I will answer: "Basic principles (one dep per insn) are always
3309          the same."  */
3310       gcc_assert (!SCHED_GROUP_P (insn));
3311
3312       /* In the absence of interprocedural alias analysis, we must flush
3313          all pending reads and writes, and start new dependencies starting
3314          from here.  But only flush writes for constant calls (which may
3315          be passed a pointer to something we haven't written yet).  */
3316       flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3317
3318       if (!deps->readonly)
3319         {
3320           /* Remember the last function call for limiting lifetimes.  */
3321           free_INSN_LIST_list (&deps->last_function_call);
3322           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3323
3324           if (call_may_noreturn_p (insn))
3325             {
3326               /* Remember the last function call that might not always return
3327                  normally for limiting moves of trapping insns.  */
3328               free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3329               deps->last_function_call_may_noreturn
3330                 = alloc_INSN_LIST (insn, NULL_RTX);
3331             }
3332
3333           /* Before reload, begin a post-call group, so as to keep the
3334              lifetimes of hard registers correct.  */
3335           if (! reload_completed)
3336             deps->in_post_call_group_p = post_call;
3337         }
3338     }
3339
3340   if (sched_deps_info->use_cselib)
3341     cselib_process_insn (insn);
3342
3343   /* EH_REGION insn notes can not appear until well after we complete
3344      scheduling.  */
3345   if (NOTE_P (insn))
3346     gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
3347                 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
3348
3349   if (sched_deps_info->finish_insn)
3350     sched_deps_info->finish_insn ();
3351
3352   /* Fixup the dependencies in the sched group.  */
3353   if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3354       && SCHED_GROUP_P (insn) && !sel_sched_p ())
3355     fixup_sched_groups (insn);
3356 }
3357
3358 /* Initialize DEPS for the new block beginning with HEAD.  */
3359 void
3360 deps_start_bb (struct deps_desc *deps, rtx head)
3361 {
3362   gcc_assert (!deps->readonly);
3363
3364   /* Before reload, if the previous block ended in a call, show that
3365      we are inside a post-call group, so as to keep the lifetimes of
3366      hard registers correct.  */
3367   if (! reload_completed && !LABEL_P (head))
3368     {
3369       rtx insn = prev_nonnote_nondebug_insn (head);
3370
3371       if (insn && CALL_P (insn))
3372         deps->in_post_call_group_p = post_call_initial;
3373     }
3374 }
3375
3376 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3377    dependencies for each insn.  */
3378 void
3379 sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
3380 {
3381   rtx insn;
3382
3383   if (sched_deps_info->use_cselib)
3384     cselib_init (CSELIB_RECORD_MEMORY);
3385
3386   deps_start_bb (deps, head);
3387
3388   for (insn = head;; insn = NEXT_INSN (insn))
3389     {
3390
3391       if (INSN_P (insn))
3392         {
3393           /* And initialize deps_lists.  */
3394           sd_init_insn (insn);
3395         }
3396
3397       deps_analyze_insn (deps, insn);
3398
3399       if (insn == tail)
3400         {
3401           if (sched_deps_info->use_cselib)
3402             cselib_finish ();
3403           return;
3404         }
3405     }
3406   gcc_unreachable ();
3407 }
3408
3409 /* Helper for sched_free_deps ().
3410    Delete INSN's (RESOLVED_P) backward dependencies.  */
3411 static void
3412 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
3413 {
3414   sd_iterator_def sd_it;
3415   dep_t dep;
3416   sd_list_types_def types;
3417
3418   if (resolved_p)
3419     types = SD_LIST_RES_BACK;
3420   else
3421     types = SD_LIST_BACK;
3422
3423   for (sd_it = sd_iterator_start (insn, types);
3424        sd_iterator_cond (&sd_it, &dep);)
3425     {
3426       dep_link_t link = *sd_it.linkp;
3427       dep_node_t node = DEP_LINK_NODE (link);
3428       deps_list_t back_list;
3429       deps_list_t forw_list;
3430
3431       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3432       remove_from_deps_list (link, back_list);
3433       delete_dep_node (node);
3434     }
3435 }
3436
3437 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3438    deps_lists.  */
3439 void
3440 sched_free_deps (rtx head, rtx tail, bool resolved_p)
3441 {
3442   rtx insn;
3443   rtx next_tail = NEXT_INSN (tail);
3444
3445   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3446     if (INSN_P (insn) && INSN_LUID (insn) > 0)
3447       {
3448         /* Clear resolved back deps together with its dep_nodes.  */
3449         delete_dep_nodes_in_back_deps (insn, resolved_p);
3450
3451         /* Clear forward deps and leave the dep_nodes to the
3452            corresponding back_deps list.  */
3453         if (resolved_p)
3454           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3455         else
3456           clear_deps_list (INSN_FORW_DEPS (insn));
3457
3458         sd_finish_insn (insn);
3459       }
3460 }
3461 \f
3462 /* Initialize variables for region data dependence analysis.
3463    When LAZY_REG_LAST is true, do not allocate reg_last array
3464    of struct deps_desc immediately.  */
3465
3466 void
3467 init_deps (struct deps_desc *deps, bool lazy_reg_last)
3468 {
3469   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3470
3471   deps->max_reg = max_reg;
3472   if (lazy_reg_last)
3473     deps->reg_last = NULL;
3474   else
3475     deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3476   INIT_REG_SET (&deps->reg_last_in_use);
3477   INIT_REG_SET (&deps->reg_conditional_sets);
3478
3479   deps->pending_read_insns = 0;
3480   deps->pending_read_mems = 0;
3481   deps->pending_write_insns = 0;
3482   deps->pending_write_mems = 0;
3483   deps->pending_read_list_length = 0;
3484   deps->pending_write_list_length = 0;
3485   deps->pending_flush_length = 0;
3486   deps->last_pending_memory_flush = 0;
3487   deps->last_function_call = 0;
3488   deps->last_function_call_may_noreturn = 0;
3489   deps->sched_before_next_call = 0;
3490   deps->in_post_call_group_p = not_post_call;
3491   deps->last_debug_insn = 0;
3492   deps->last_reg_pending_barrier = NOT_A_BARRIER;
3493   deps->readonly = 0;
3494 }
3495
3496 /* Init only reg_last field of DEPS, which was not allocated before as
3497    we inited DEPS lazily.  */
3498 void
3499 init_deps_reg_last (struct deps_desc *deps)
3500 {
3501   gcc_assert (deps && deps->max_reg > 0);
3502   gcc_assert (deps->reg_last == NULL);
3503
3504   deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3505 }
3506
3507
3508 /* Free insn lists found in DEPS.  */
3509
3510 void
3511 free_deps (struct deps_desc *deps)
3512 {
3513   unsigned i;
3514   reg_set_iterator rsi;
3515
3516   /* We set max_reg to 0 when this context was already freed.  */
3517   if (deps->max_reg == 0)
3518     {
3519       gcc_assert (deps->reg_last == NULL);
3520       return;
3521     }
3522   deps->max_reg = 0;
3523
3524   free_INSN_LIST_list (&deps->pending_read_insns);
3525   free_EXPR_LIST_list (&deps->pending_read_mems);
3526   free_INSN_LIST_list (&deps->pending_write_insns);
3527   free_EXPR_LIST_list (&deps->pending_write_mems);
3528   free_INSN_LIST_list (&deps->last_pending_memory_flush);
3529
3530   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3531      times.  For a testcase with 42000 regs and 8000 small basic blocks,
3532      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
3533   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3534     {
3535       struct deps_reg *reg_last = &deps->reg_last[i];
3536       if (reg_last->uses)
3537         free_INSN_LIST_list (&reg_last->uses);
3538       if (reg_last->sets)
3539         free_INSN_LIST_list (&reg_last->sets);
3540       if (reg_last->implicit_sets)
3541         free_INSN_LIST_list (&reg_last->implicit_sets);
3542       if (reg_last->clobbers)
3543         free_INSN_LIST_list (&reg_last->clobbers);
3544     }
3545   CLEAR_REG_SET (&deps->reg_last_in_use);
3546   CLEAR_REG_SET (&deps->reg_conditional_sets);
3547
3548   /* As we initialize reg_last lazily, it is possible that we didn't allocate
3549      it at all.  */
3550   free (deps->reg_last);
3551   deps->reg_last = NULL;
3552
3553   deps = NULL;
3554 }
3555
3556 /* Remove INSN from dependence contexts DEPS.  Caution: reg_conditional_sets
3557    is not handled.  */
3558 void
3559 remove_from_deps (struct deps_desc *deps, rtx insn)
3560 {
3561   int removed;
3562   unsigned i;
3563   reg_set_iterator rsi;
3564
3565   removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
3566                                                &deps->pending_read_mems);
3567   if (!DEBUG_INSN_P (insn))
3568     deps->pending_read_list_length -= removed;
3569   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
3570                                                &deps->pending_write_mems);
3571   deps->pending_write_list_length -= removed;
3572   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
3573   deps->pending_flush_length -= removed;
3574
3575   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3576     {
3577       struct deps_reg *reg_last = &deps->reg_last[i];
3578       if (reg_last->uses)
3579         remove_from_dependence_list (insn, &reg_last->uses);
3580       if (reg_last->sets)
3581         remove_from_dependence_list (insn, &reg_last->sets);
3582       if (reg_last->implicit_sets)
3583         remove_from_dependence_list (insn, &reg_last->implicit_sets);
3584       if (reg_last->clobbers)
3585         remove_from_dependence_list (insn, &reg_last->clobbers);
3586       if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
3587           && !reg_last->clobbers)
3588         CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
3589     }
3590
3591   if (CALL_P (insn))
3592     {
3593       remove_from_dependence_list (insn, &deps->last_function_call);
3594       remove_from_dependence_list (insn,
3595                                    &deps->last_function_call_may_noreturn);
3596     }
3597   remove_from_dependence_list (insn, &deps->sched_before_next_call);
3598 }
3599
3600 /* Init deps data vector.  */
3601 static void
3602 init_deps_data_vector (void)
3603 {
3604   int reserve = (sched_max_luid + 1
3605                  - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
3606   if (reserve > 0
3607       && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
3608     VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
3609                            3 * sched_max_luid / 2);
3610 }
3611
3612 /* If it is profitable to use them, initialize or extend (depending on
3613    GLOBAL_P) dependency data.  */
3614 void
3615 sched_deps_init (bool global_p)
3616 {
3617   /* Average number of insns in the basic block.
3618      '+ 1' is used to make it nonzero.  */
3619   int insns_in_block = sched_max_luid / n_basic_blocks + 1;
3620
3621   init_deps_data_vector ();
3622
3623   /* We use another caching mechanism for selective scheduling, so
3624      we don't use this one.  */
3625   if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
3626     {
3627       /* ?!? We could save some memory by computing a per-region luid mapping
3628          which could reduce both the number of vectors in the cache and the
3629          size of each vector.  Instead we just avoid the cache entirely unless
3630          the average number of instructions in a basic block is very high.  See
3631          the comment before the declaration of true_dependency_cache for
3632          what we consider "very high".  */
3633       cache_size = 0;
3634       extend_dependency_caches (sched_max_luid, true);
3635     }
3636
3637   if (global_p)
3638     {
3639       dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
3640                                    /* Allocate lists for one block at a time.  */
3641                                    insns_in_block);
3642       dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
3643                                    /* Allocate nodes for one block at a time.
3644                                       We assume that average insn has
3645                                       5 producers.  */
3646                                    5 * insns_in_block);
3647     }
3648 }
3649
3650
3651 /* Create or extend (depending on CREATE_P) dependency caches to
3652    size N.  */
3653 void
3654 extend_dependency_caches (int n, bool create_p)
3655 {
3656   if (create_p || true_dependency_cache)
3657     {
3658       int i, luid = cache_size + n;
3659
3660       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
3661                                           luid);
3662       output_dependency_cache = XRESIZEVEC (bitmap_head,
3663                                             output_dependency_cache, luid);
3664       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
3665                                           luid);
3666
3667       if (current_sched_info->flags & DO_SPECULATION)
3668         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
3669                                             luid);
3670
3671       for (i = cache_size; i < luid; i++)
3672         {
3673           bitmap_initialize (&true_dependency_cache[i], 0);
3674           bitmap_initialize (&output_dependency_cache[i], 0);
3675           bitmap_initialize (&anti_dependency_cache[i], 0);
3676
3677           if (current_sched_info->flags & DO_SPECULATION)
3678             bitmap_initialize (&spec_dependency_cache[i], 0);
3679         }
3680       cache_size = luid;
3681     }
3682 }
3683
3684 /* Finalize dependency information for the whole function.  */
3685 void
3686 sched_deps_finish (void)
3687 {
3688   gcc_assert (deps_pools_are_empty_p ());
3689   free_alloc_pool_if_empty (&dn_pool);
3690   free_alloc_pool_if_empty (&dl_pool);
3691   gcc_assert (dn_pool == NULL && dl_pool == NULL);
3692
3693   VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
3694   cache_size = 0;
3695
3696   if (true_dependency_cache)
3697     {
3698       int i;
3699
3700       for (i = 0; i < cache_size; i++)
3701         {
3702           bitmap_clear (&true_dependency_cache[i]);
3703           bitmap_clear (&output_dependency_cache[i]);
3704           bitmap_clear (&anti_dependency_cache[i]);
3705
3706           if (sched_deps_info->generate_spec_deps)
3707             bitmap_clear (&spec_dependency_cache[i]);
3708         }
3709       free (true_dependency_cache);
3710       true_dependency_cache = NULL;
3711       free (output_dependency_cache);
3712       output_dependency_cache = NULL;
3713       free (anti_dependency_cache);
3714       anti_dependency_cache = NULL;
3715
3716       if (sched_deps_info->generate_spec_deps)
3717         {
3718           free (spec_dependency_cache);
3719           spec_dependency_cache = NULL;
3720         }
3721
3722     }
3723 }
3724
3725 /* Initialize some global variables needed by the dependency analysis
3726    code.  */
3727
3728 void
3729 init_deps_global (void)
3730 {
3731   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3732   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3733   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
3734   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
3735   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
3736   reg_pending_barrier = NOT_A_BARRIER;
3737
3738   if (!sel_sched_p () || sched_emulate_haifa_p)
3739     {
3740       sched_deps_info->start_insn = haifa_start_insn;
3741       sched_deps_info->finish_insn = haifa_finish_insn;
3742
3743       sched_deps_info->note_reg_set = haifa_note_reg_set;
3744       sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
3745       sched_deps_info->note_reg_use = haifa_note_reg_use;
3746
3747       sched_deps_info->note_mem_dep = haifa_note_mem_dep;
3748       sched_deps_info->note_dep = haifa_note_dep;
3749    }
3750 }
3751
3752 /* Free everything used by the dependency analysis code.  */
3753
3754 void
3755 finish_deps_global (void)
3756 {
3757   FREE_REG_SET (reg_pending_sets);
3758   FREE_REG_SET (reg_pending_clobbers);
3759   FREE_REG_SET (reg_pending_uses);
3760 }
3761
3762 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
3763 dw_t
3764 estimate_dep_weak (rtx mem1, rtx mem2)
3765 {
3766   rtx r1, r2;
3767
3768   if (mem1 == mem2)
3769     /* MEMs are the same - don't speculate.  */
3770     return MIN_DEP_WEAK;
3771
3772   r1 = XEXP (mem1, 0);
3773   r2 = XEXP (mem2, 0);
3774
3775   if (r1 == r2
3776       || (REG_P (r1) && REG_P (r2)
3777           && REGNO (r1) == REGNO (r2)))
3778     /* Again, MEMs are the same.  */
3779     return MIN_DEP_WEAK;
3780   else if ((REG_P (r1) && !REG_P (r2))
3781            || (!REG_P (r1) && REG_P (r2)))
3782     /* Different addressing modes - reason to be more speculative,
3783        than usual.  */
3784     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
3785   else
3786     /* We can't say anything about the dependence.  */
3787     return UNCERTAIN_DEP_WEAK;
3788 }
3789
3790 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
3791    This function can handle same INSN and ELEM (INSN == ELEM).
3792    It is a convenience wrapper.  */
3793 void
3794 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
3795 {
3796   ds_t ds;
3797   bool internal;
3798
3799   if (dep_type == REG_DEP_TRUE)
3800     ds = DEP_TRUE;
3801   else if (dep_type == REG_DEP_OUTPUT)
3802     ds = DEP_OUTPUT;
3803   else
3804     {
3805       gcc_assert (dep_type == REG_DEP_ANTI);
3806       ds = DEP_ANTI;
3807     }
3808
3809   /* When add_dependence is called from inside sched-deps.c, we expect
3810      cur_insn to be non-null.  */
3811   internal = cur_insn != NULL;
3812   if (internal)
3813     gcc_assert (insn == cur_insn);
3814   else
3815     cur_insn = insn;
3816
3817   note_dep (elem, ds);
3818   if (!internal)
3819     cur_insn = NULL;
3820 }
3821
3822 /* Return weakness of speculative type TYPE in the dep_status DS.  */
3823 dw_t
3824 get_dep_weak_1 (ds_t ds, ds_t type)
3825 {
3826   ds = ds & type;
3827
3828   switch (type)
3829     {
3830     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
3831     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
3832     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
3833     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
3834     default: gcc_unreachable ();
3835     }
3836
3837   return (dw_t) ds;
3838 }
3839
3840 dw_t
3841 get_dep_weak (ds_t ds, ds_t type)
3842 {
3843   dw_t dw = get_dep_weak_1 (ds, type);
3844
3845   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3846   return dw;
3847 }
3848
3849 /* Return the dep_status, which has the same parameters as DS, except for
3850    speculative type TYPE, that will have weakness DW.  */
3851 ds_t
3852 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
3853 {
3854   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
3855
3856   ds &= ~type;
3857   switch (type)
3858     {
3859     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
3860     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
3861     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
3862     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
3863     default: gcc_unreachable ();
3864     }
3865   return ds;
3866 }
3867
3868 /* Return the join of two dep_statuses DS1 and DS2.
3869    If MAX_P is true then choose the greater probability,
3870    otherwise multiply probabilities.
3871    This function assumes that both DS1 and DS2 contain speculative bits.  */
3872 static ds_t
3873 ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
3874 {
3875   ds_t ds, t;
3876
3877   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
3878
3879   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
3880
3881   t = FIRST_SPEC_TYPE;
3882   do
3883     {
3884       if ((ds1 & t) && !(ds2 & t))
3885         ds |= ds1 & t;
3886       else if (!(ds1 & t) && (ds2 & t))
3887         ds |= ds2 & t;
3888       else if ((ds1 & t) && (ds2 & t))
3889         {
3890           dw_t dw1 = get_dep_weak (ds1, t);
3891           dw_t dw2 = get_dep_weak (ds2, t);
3892           ds_t dw;
3893
3894           if (!max_p)
3895             {
3896               dw = ((ds_t) dw1) * ((ds_t) dw2);
3897               dw /= MAX_DEP_WEAK;
3898               if (dw < MIN_DEP_WEAK)
3899                 dw = MIN_DEP_WEAK;
3900             }
3901           else
3902             {
3903               if (dw1 >= dw2)
3904                 dw = dw1;
3905               else
3906                 dw = dw2;
3907             }
3908
3909           ds = set_dep_weak (ds, t, (dw_t) dw);
3910         }
3911
3912       if (t == LAST_SPEC_TYPE)
3913         break;
3914       t <<= SPEC_TYPE_SHIFT;
3915     }
3916   while (1);
3917
3918   return ds;
3919 }
3920
3921 /* Return the join of two dep_statuses DS1 and DS2.
3922    This function assumes that both DS1 and DS2 contain speculative bits.  */
3923 ds_t
3924 ds_merge (ds_t ds1, ds_t ds2)
3925 {
3926   return ds_merge_1 (ds1, ds2, false);
3927 }
3928
3929 /* Return the join of two dep_statuses DS1 and DS2.  */
3930 ds_t
3931 ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
3932 {
3933   ds_t new_status = ds | ds2;
3934
3935   if (new_status & SPECULATIVE)
3936     {
3937       if ((ds && !(ds & SPECULATIVE))
3938           || (ds2 && !(ds2 & SPECULATIVE)))
3939         /* Then this dep can't be speculative.  */
3940         new_status &= ~SPECULATIVE;
3941       else
3942         {
3943           /* Both are speculative.  Merging probabilities.  */
3944           if (mem1)
3945             {
3946               dw_t dw;
3947
3948               dw = estimate_dep_weak (mem1, mem2);
3949               ds = set_dep_weak (ds, BEGIN_DATA, dw);
3950             }
3951
3952           if (!ds)
3953             new_status = ds2;
3954           else if (!ds2)
3955             new_status = ds;
3956           else
3957             new_status = ds_merge (ds2, ds);
3958         }
3959     }
3960
3961   return new_status;
3962 }
3963
3964 /* Return the join of DS1 and DS2.  Use maximum instead of multiplying
3965    probabilities.  */
3966 ds_t
3967 ds_max_merge (ds_t ds1, ds_t ds2)
3968 {
3969   if (ds1 == 0 && ds2 == 0)
3970     return 0;
3971
3972   if (ds1 == 0 && ds2 != 0)
3973     return ds2;
3974
3975   if (ds1 != 0 && ds2 == 0)
3976     return ds1;
3977
3978   return ds_merge_1 (ds1, ds2, true);
3979 }
3980
3981 /* Return the probability of speculation success for the speculation
3982    status DS.  */
3983 dw_t
3984 ds_weak (ds_t ds)
3985 {
3986   ds_t res = 1, dt;
3987   int n = 0;
3988
3989   dt = FIRST_SPEC_TYPE;
3990   do
3991     {
3992       if (ds & dt)
3993         {
3994           res *= (ds_t) get_dep_weak (ds, dt);
3995           n++;
3996         }
3997
3998       if (dt == LAST_SPEC_TYPE)
3999         break;
4000       dt <<= SPEC_TYPE_SHIFT;
4001     }
4002   while (1);
4003
4004   gcc_assert (n);
4005   while (--n)
4006     res /= MAX_DEP_WEAK;
4007
4008   if (res < MIN_DEP_WEAK)
4009     res = MIN_DEP_WEAK;
4010
4011   gcc_assert (res <= MAX_DEP_WEAK);
4012
4013   return (dw_t) res;
4014 }
4015
4016 /* Return a dep status that contains all speculation types of DS.  */
4017 ds_t
4018 ds_get_speculation_types (ds_t ds)
4019 {
4020   if (ds & BEGIN_DATA)
4021     ds |= BEGIN_DATA;
4022   if (ds & BE_IN_DATA)
4023     ds |= BE_IN_DATA;
4024   if (ds & BEGIN_CONTROL)
4025     ds |= BEGIN_CONTROL;
4026   if (ds & BE_IN_CONTROL)
4027     ds |= BE_IN_CONTROL;
4028
4029   return ds & SPECULATIVE;
4030 }
4031
4032 /* Return a dep status that contains maximal weakness for each speculation
4033    type present in DS.  */
4034 ds_t
4035 ds_get_max_dep_weak (ds_t ds)
4036 {
4037   if (ds & BEGIN_DATA)
4038     ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4039   if (ds & BE_IN_DATA)
4040     ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4041   if (ds & BEGIN_CONTROL)
4042     ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4043   if (ds & BE_IN_CONTROL)
4044     ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4045
4046   return ds;
4047 }
4048
4049 /* Dump information about the dependence status S.  */
4050 static void
4051 dump_ds (FILE *f, ds_t s)
4052 {
4053   fprintf (f, "{");
4054
4055   if (s & BEGIN_DATA)
4056     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4057   if (s & BE_IN_DATA)
4058     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4059   if (s & BEGIN_CONTROL)
4060     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4061   if (s & BE_IN_CONTROL)
4062     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4063
4064   if (s & HARD_DEP)
4065     fprintf (f, "HARD_DEP; ");
4066
4067   if (s & DEP_TRUE)
4068     fprintf (f, "DEP_TRUE; ");
4069   if (s & DEP_ANTI)
4070     fprintf (f, "DEP_ANTI; ");
4071   if (s & DEP_OUTPUT)
4072     fprintf (f, "DEP_OUTPUT; ");
4073
4074   fprintf (f, "}");
4075 }
4076
4077 DEBUG_FUNCTION void
4078 debug_ds (ds_t s)
4079 {
4080   dump_ds (stderr, s);
4081   fprintf (stderr, "\n");
4082 }
4083
4084 #ifdef ENABLE_CHECKING
4085 /* Verify that dependence type and status are consistent.
4086    If RELAXED_P is true, then skip dep_weakness checks.  */
4087 static void
4088 check_dep (dep_t dep, bool relaxed_p)
4089 {
4090   enum reg_note dt = DEP_TYPE (dep);
4091   ds_t ds = DEP_STATUS (dep);
4092
4093   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4094
4095   if (!(current_sched_info->flags & USE_DEPS_LIST))
4096     {
4097       gcc_assert (ds == -1);
4098       return;
4099     }
4100
4101   /* Check that dependence type contains the same bits as the status.  */
4102   if (dt == REG_DEP_TRUE)
4103     gcc_assert (ds & DEP_TRUE);
4104   else if (dt == REG_DEP_OUTPUT)
4105     gcc_assert ((ds & DEP_OUTPUT)
4106                 && !(ds & DEP_TRUE));
4107   else
4108     gcc_assert ((dt == REG_DEP_ANTI)
4109                 && (ds & DEP_ANTI)
4110                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4111
4112   /* HARD_DEP can not appear in dep_status of a link.  */
4113   gcc_assert (!(ds & HARD_DEP));
4114
4115   /* Check that dependence status is set correctly when speculation is not
4116      supported.  */
4117   if (!sched_deps_info->generate_spec_deps)
4118     gcc_assert (!(ds & SPECULATIVE));
4119   else if (ds & SPECULATIVE)
4120     {
4121       if (!relaxed_p)
4122         {
4123           ds_t type = FIRST_SPEC_TYPE;
4124
4125           /* Check that dependence weakness is in proper range.  */
4126           do
4127             {
4128               if (ds & type)
4129                 get_dep_weak (ds, type);
4130
4131               if (type == LAST_SPEC_TYPE)
4132                 break;
4133               type <<= SPEC_TYPE_SHIFT;
4134             }
4135           while (1);
4136         }
4137
4138       if (ds & BEGIN_SPEC)
4139         {
4140           /* Only true dependence can be data speculative.  */
4141           if (ds & BEGIN_DATA)
4142             gcc_assert (ds & DEP_TRUE);
4143
4144           /* Control dependencies in the insn scheduler are represented by
4145              anti-dependencies, therefore only anti dependence can be
4146              control speculative.  */
4147           if (ds & BEGIN_CONTROL)
4148             gcc_assert (ds & DEP_ANTI);
4149         }
4150       else
4151         {
4152           /* Subsequent speculations should resolve true dependencies.  */
4153           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4154         }
4155
4156       /* Check that true and anti dependencies can't have other speculative
4157          statuses.  */
4158       if (ds & DEP_TRUE)
4159         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4160       /* An output dependence can't be speculative at all.  */
4161       gcc_assert (!(ds & DEP_OUTPUT));
4162       if (ds & DEP_ANTI)
4163         gcc_assert (ds & BEGIN_CONTROL);
4164     }
4165 }
4166 #endif /* ENABLE_CHECKING */
4167
4168 #endif /* INSN_SCHEDULING */