OSDN Git Service

Remove libcall notes.
[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
5    Free Software Foundation, Inc.
6    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
7    and currently maintained by, Jim Wilson (wilson@cygnus.com)
8
9 This file is part of GCC.
10
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 3, or (at your option) any later
14 version.
15
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
19 for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING3.  If not see
23 <http://www.gnu.org/licenses/>.  */
24 \f
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "tm.h"
29 #include "toplev.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "hard-reg-set.h"
33 #include "regs.h"
34 #include "function.h"
35 #include "flags.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
38 #include "except.h"
39 #include "toplev.h"
40 #include "recog.h"
41 #include "sched-int.h"
42 #include "params.h"
43 #include "cselib.h"
44
45 #ifdef INSN_SCHEDULING
46
47 #ifdef ENABLE_CHECKING
48 #define CHECK (true)
49 #else
50 #define CHECK (false)
51 #endif
52
53 /* Return the major type present in the DS.  */
54 enum reg_note
55 ds_to_dk (ds_t ds)
56 {
57   if (ds & DEP_TRUE)
58     return REG_DEP_TRUE;
59
60   if (ds & DEP_OUTPUT)
61     return REG_DEP_OUTPUT;
62
63   gcc_assert (ds & DEP_ANTI);
64
65   return REG_DEP_ANTI;
66 }
67
68 /* Return equivalent dep_status.  */
69 ds_t
70 dk_to_ds (enum reg_note dk)
71 {
72   switch (dk)
73     {
74     case REG_DEP_TRUE:
75       return DEP_TRUE;
76
77     case REG_DEP_OUTPUT:
78       return DEP_OUTPUT;
79
80     default:
81       gcc_assert (dk == REG_DEP_ANTI);
82       return DEP_ANTI;
83     }
84 }
85
86 /* Functions to operate with dependence information container - dep_t.  */
87
88 /* Init DEP with the arguments.  */
89 void
90 init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
91 {
92   DEP_PRO (dep) = pro;
93   DEP_CON (dep) = con;
94   DEP_TYPE (dep) = type;
95   DEP_STATUS (dep) = ds;
96 }
97
98 /* Init DEP with the arguments.
99    While most of the scheduler (including targets) only need the major type
100    of the dependency, it is convenient to hide full dep_status from them.  */
101 void
102 init_dep (dep_t dep, rtx pro, rtx con, enum reg_note kind)
103 {
104   ds_t ds;
105
106   if ((current_sched_info->flags & USE_DEPS_LIST))
107     ds = dk_to_ds (kind);
108   else
109     ds = -1;
110
111   init_dep_1 (dep, pro, con, kind, ds);
112 }
113
114 /* Make a copy of FROM in TO.  */
115 static void
116 copy_dep (dep_t to, dep_t from)
117 {
118   memcpy (to, from, sizeof (*to));
119 }
120
121 static void dump_ds (FILE *, ds_t);
122
123 /* Define flags for dump_dep ().  */
124
125 /* Dump producer of the dependence.  */
126 #define DUMP_DEP_PRO (2)
127
128 /* Dump consumer of the dependence.  */
129 #define DUMP_DEP_CON (4)
130
131 /* Dump type of the dependence.  */
132 #define DUMP_DEP_TYPE (8)
133
134 /* Dump status of the dependence.  */
135 #define DUMP_DEP_STATUS (16)
136
137 /* Dump all information about the dependence.  */
138 #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE       \
139                       |DUMP_DEP_STATUS)
140
141 /* Dump DEP to DUMP.
142    FLAGS is a bit mask specifying what information about DEP needs
143    to be printed.
144    If FLAGS has the very first bit set, then dump all information about DEP
145    and propagate this bit into the callee dump functions.  */
146 static void
147 dump_dep (FILE *dump, dep_t dep, int flags)
148 {
149   if (flags & 1)
150     flags |= DUMP_DEP_ALL;
151
152   fprintf (dump, "<");
153
154   if (flags & DUMP_DEP_PRO)
155     fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
156
157   if (flags & DUMP_DEP_CON)
158     fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
159
160   if (flags & DUMP_DEP_TYPE)
161     {
162       char t;
163       enum reg_note type = DEP_TYPE (dep);
164
165       switch (type)
166         {
167         case REG_DEP_TRUE:
168           t = 't';
169           break;
170
171         case REG_DEP_OUTPUT:
172           t = 'o';
173           break;
174
175         case REG_DEP_ANTI:
176           t = 'a';
177           break;
178
179         default:
180           gcc_unreachable ();
181           break;
182         }
183
184       fprintf (dump, "%c; ", t);
185     }
186
187   if (flags & DUMP_DEP_STATUS)
188     {
189       if (current_sched_info->flags & USE_DEPS_LIST)
190         dump_ds (dump, DEP_STATUS (dep));
191     }
192
193   fprintf (dump, ">");
194 }
195
196 /* Default flags for dump_dep ().  */
197 static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
198
199 /* Dump all fields of DEP to STDERR.  */
200 void
201 sd_debug_dep (dep_t dep)
202 {
203   dump_dep (stderr, dep, 1);
204   fprintf (stderr, "\n");
205 }
206
207 /* Functions to operate with a single link from the dependencies lists -
208    dep_link_t.  */
209
210 /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
211    PREV_NEXT_P.  */
212 static void
213 attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
214 {
215   dep_link_t next = *prev_nextp;
216
217   gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
218               && DEP_LINK_NEXT (l) == NULL);
219
220   /* Init node being inserted.  */
221   DEP_LINK_PREV_NEXTP (l) = prev_nextp;
222   DEP_LINK_NEXT (l) = next;
223
224   /* Fix next node.  */
225   if (next != NULL)
226     {
227       gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
228
229       DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
230     }
231
232   /* Fix prev node.  */
233   *prev_nextp = l;
234 }
235
236 /* Add dep_link LINK to deps_list L.  */
237 static void
238 add_to_deps_list (dep_link_t link, deps_list_t l)
239 {
240   attach_dep_link (link, &DEPS_LIST_FIRST (l));
241
242   ++DEPS_LIST_N_LINKS (l);
243 }
244
245 /* Detach dep_link L from the list.  */
246 static void
247 detach_dep_link (dep_link_t l)
248 {
249   dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
250   dep_link_t next = DEP_LINK_NEXT (l);
251
252   *prev_nextp = next;
253
254   if (next != NULL)
255     DEP_LINK_PREV_NEXTP (next) = prev_nextp;
256
257   DEP_LINK_PREV_NEXTP (l) = NULL;
258   DEP_LINK_NEXT (l) = NULL;
259 }
260
261 /* Remove link LINK from list LIST.  */
262 static void
263 remove_from_deps_list (dep_link_t link, deps_list_t list)
264 {
265   detach_dep_link (link);
266
267   --DEPS_LIST_N_LINKS (list);
268 }
269
270 /* Move link LINK from list FROM to list TO.  */
271 static void
272 move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
273 {
274   remove_from_deps_list (link, from);
275   add_to_deps_list (link, to);
276 }
277
278 /* Return true of LINK is not attached to any list.  */
279 static bool
280 dep_link_is_detached_p (dep_link_t link)
281 {
282   return DEP_LINK_PREV_NEXTP (link) == NULL;
283 }
284
285 /* Pool to hold all dependency nodes (dep_node_t).  */
286 static alloc_pool dn_pool;
287
288 /* Number of dep_nodes out there.  */
289 static int dn_pool_diff = 0;
290
291 /* Create a dep_node.  */
292 static dep_node_t
293 create_dep_node (void)
294 {
295   dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
296   dep_link_t back = DEP_NODE_BACK (n);
297   dep_link_t forw = DEP_NODE_FORW (n);
298
299   DEP_LINK_NODE (back) = n;
300   DEP_LINK_NEXT (back) = NULL;
301   DEP_LINK_PREV_NEXTP (back) = NULL;
302
303   DEP_LINK_NODE (forw) = n;
304   DEP_LINK_NEXT (forw) = NULL;
305   DEP_LINK_PREV_NEXTP (forw) = NULL;
306
307   ++dn_pool_diff;
308
309   return n;
310 }
311
312 /* Delete dep_node N.  N must not be connected to any deps_list.  */
313 static void
314 delete_dep_node (dep_node_t n)
315 {
316   gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
317               && dep_link_is_detached_p (DEP_NODE_FORW (n)));
318
319   --dn_pool_diff;
320
321   pool_free (dn_pool, n);
322 }
323
324 /* Pool to hold dependencies lists (deps_list_t).  */
325 static alloc_pool dl_pool;
326
327 /* Number of deps_lists out there.  */
328 static int dl_pool_diff = 0;
329
330 /* Functions to operate with dependences lists - deps_list_t.  */
331
332 /* Return true if list L is empty.  */
333 static bool
334 deps_list_empty_p (deps_list_t l)
335 {
336   return DEPS_LIST_N_LINKS (l) == 0;
337 }
338
339 /* Create a new deps_list.  */
340 static deps_list_t
341 create_deps_list (void)
342 {
343   deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
344
345   DEPS_LIST_FIRST (l) = NULL;
346   DEPS_LIST_N_LINKS (l) = 0;
347
348   ++dl_pool_diff;
349   return l;
350 }
351
352 /* Free deps_list L.  */
353 static void
354 free_deps_list (deps_list_t l)
355 {
356   gcc_assert (deps_list_empty_p (l));
357
358   --dl_pool_diff;
359
360   pool_free (dl_pool, l);
361 }
362
363 /* Return true if there is no dep_nodes and deps_lists out there.
364    After the region is scheduled all the dependency nodes and lists
365    should [generally] be returned to pool.  */
366 bool
367 deps_pools_are_empty_p (void)
368 {
369   return dn_pool_diff == 0 && dl_pool_diff == 0;
370 }
371
372 /* Remove all elements from L.  */
373 static void
374 clear_deps_list (deps_list_t l)
375 {
376   do
377     {
378       dep_link_t link = DEPS_LIST_FIRST (l);
379
380       if (link == NULL)
381         break;
382
383       remove_from_deps_list (link, l);
384     }
385   while (1);
386 }
387
388 static regset reg_pending_sets;
389 static regset reg_pending_clobbers;
390 static regset reg_pending_uses;
391
392 /* The following enumeration values tell us what dependencies we
393    should use to implement the barrier.  We use true-dependencies for
394    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
395 enum reg_pending_barrier_mode
396 {
397   NOT_A_BARRIER = 0,
398   MOVE_BARRIER,
399   TRUE_BARRIER
400 };
401
402 static enum reg_pending_barrier_mode reg_pending_barrier;
403
404 /* To speed up the test for duplicate dependency links we keep a
405    record of dependencies created by add_dependence when the average
406    number of instructions in a basic block is very large.
407
408    Studies have shown that there is typically around 5 instructions between
409    branches for typical C code.  So we can make a guess that the average
410    basic block is approximately 5 instructions long; we will choose 100X
411    the average size as a very large basic block.
412
413    Each insn has associated bitmaps for its dependencies.  Each bitmap
414    has enough entries to represent a dependency on any other insn in
415    the insn chain.  All bitmap for true dependencies cache is
416    allocated then the rest two ones are also allocated.  */
417 static bitmap_head *true_dependency_cache;
418 static bitmap_head *output_dependency_cache;
419 static bitmap_head *anti_dependency_cache;
420 static bitmap_head *spec_dependency_cache;
421 static int cache_size;
422
423 static int deps_may_trap_p (const_rtx);
424 static void add_dependence_list (rtx, rtx, int, enum reg_note);
425 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
426 static void delete_all_dependences (rtx);
427 static void fixup_sched_groups (rtx);
428
429 static void flush_pending_lists (struct deps *, rtx, int, int);
430 static void sched_analyze_1 (struct deps *, rtx, rtx);
431 static void sched_analyze_2 (struct deps *, rtx, rtx);
432 static void sched_analyze_insn (struct deps *, rtx, rtx);
433
434 static rtx sched_get_condition (const_rtx);
435 static int conditions_mutex_p (const_rtx, const_rtx);
436
437 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
438                                                           rtx, rtx);
439 static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
440
441 static dw_t estimate_dep_weak (rtx, rtx);
442 #ifdef ENABLE_CHECKING
443 static void check_dep (dep_t, bool);
444 #endif
445 \f
446 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
447
448 static int
449 deps_may_trap_p (const_rtx mem)
450 {
451   const_rtx addr = XEXP (mem, 0);
452
453   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
454     {
455       const_rtx t = get_reg_known_value (REGNO (addr));
456       if (t)
457         addr = t;
458     }
459   return rtx_addr_can_trap_p (addr);
460 }
461 \f
462 /* Find the condition under which INSN is executed.  */
463
464 static rtx
465 sched_get_condition (const_rtx insn)
466 {
467   rtx pat = PATTERN (insn);
468   rtx src;
469
470   if (pat == 0)
471     return 0;
472
473   if (GET_CODE (pat) == COND_EXEC)
474     return COND_EXEC_TEST (pat);
475
476   if (!any_condjump_p (insn) || !onlyjump_p (insn))
477     return 0;
478
479   src = SET_SRC (pc_set (insn));
480
481   if (XEXP (src, 2) == pc_rtx)
482     return XEXP (src, 0);
483   else if (XEXP (src, 1) == pc_rtx)
484     {
485       rtx cond = XEXP (src, 0);
486       enum rtx_code revcode = reversed_comparison_code (cond, insn);
487
488       if (revcode == UNKNOWN)
489         return 0;
490       return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
491                              XEXP (cond, 1));
492     }
493
494   return 0;
495 }
496
497 \f
498 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
499
500 static int
501 conditions_mutex_p (const_rtx cond1, const_rtx cond2)
502 {
503   if (COMPARISON_P (cond1)
504       && COMPARISON_P (cond2)
505       && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
506       && XEXP (cond1, 0) == XEXP (cond2, 0)
507       && XEXP (cond1, 1) == XEXP (cond2, 1))
508     return 1;
509   return 0;
510 }
511
512 /* Return true if insn1 and insn2 can never depend on one another because
513    the conditions under which they are executed are mutually exclusive.  */
514 bool
515 sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
516 {
517   rtx cond1, cond2;
518
519   /* df doesn't handle conditional lifetimes entirely correctly;
520      calls mess up the conditional lifetimes.  */
521   if (!CALL_P (insn1) && !CALL_P (insn2))
522     {
523       cond1 = sched_get_condition (insn1);
524       cond2 = sched_get_condition (insn2);
525       if (cond1 && cond2
526           && conditions_mutex_p (cond1, cond2)
527           /* Make sure first instruction doesn't affect condition of second
528              instruction if switched.  */
529           && !modified_in_p (cond1, insn2)
530           /* Make sure second instruction doesn't affect condition of first
531              instruction if switched.  */
532           && !modified_in_p (cond2, insn1))
533         return true;
534     }
535   return false;
536 }
537 \f
538
539 /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
540    initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
541    and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
542    This function is used to switch sd_iterator to the next list.
543    !!! For internal use only.  Might consider moving it to sched-int.h.  */
544 void
545 sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
546               deps_list_t *list_ptr, bool *resolved_p_ptr)
547 {
548   sd_list_types_def types = *types_ptr;
549
550   if (types & SD_LIST_HARD_BACK)
551     {
552       *list_ptr = INSN_HARD_BACK_DEPS (insn);
553       *resolved_p_ptr = false;
554       *types_ptr = types & ~SD_LIST_HARD_BACK;
555     }
556   else if (types & SD_LIST_SPEC_BACK)
557     {
558       *list_ptr = INSN_SPEC_BACK_DEPS (insn);
559       *resolved_p_ptr = false;
560       *types_ptr = types & ~SD_LIST_SPEC_BACK;
561     }
562   else if (types & SD_LIST_FORW)
563     {
564       *list_ptr = INSN_FORW_DEPS (insn);
565       *resolved_p_ptr = false;
566       *types_ptr = types & ~SD_LIST_FORW;
567     }
568   else if (types & SD_LIST_RES_BACK)
569     {
570       *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
571       *resolved_p_ptr = true;
572       *types_ptr = types & ~SD_LIST_RES_BACK;
573     }
574   else if (types & SD_LIST_RES_FORW)
575     {
576       *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
577       *resolved_p_ptr = true;
578       *types_ptr = types & ~SD_LIST_RES_FORW;
579     }
580   else
581     {
582       *list_ptr = NULL;
583       *resolved_p_ptr = false;
584       *types_ptr = SD_LIST_NONE;
585     }
586 }
587
588 /* Return the summary size of INSN's lists defined by LIST_TYPES.  */
589 int
590 sd_lists_size (const_rtx insn, sd_list_types_def list_types)
591 {
592   int size = 0;
593
594   while (list_types != SD_LIST_NONE)
595     {
596       deps_list_t list;
597       bool resolved_p;
598
599       sd_next_list (insn, &list_types, &list, &resolved_p);
600       size += DEPS_LIST_N_LINKS (list);
601     }
602
603   return size;
604 }
605
606 /* Return true if INSN's lists defined by LIST_TYPES are all empty.  */
607 bool
608 sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
609 {
610   return sd_lists_size (insn, list_types) == 0;
611 }
612
613 /* Initialize data for INSN.  */
614 void
615 sd_init_insn (rtx insn)
616 {
617   INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
618   INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
619   INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
620   INSN_FORW_DEPS (insn) = create_deps_list ();
621   INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
622
623   /* ??? It would be nice to allocate dependency caches here.  */
624 }
625
626 /* Free data for INSN.  */
627 void
628 sd_finish_insn (rtx insn)
629 {
630   /* ??? It would be nice to deallocate dependency caches here.  */
631
632   free_deps_list (INSN_HARD_BACK_DEPS (insn));
633   INSN_HARD_BACK_DEPS (insn) = NULL;
634
635   free_deps_list (INSN_SPEC_BACK_DEPS (insn));
636   INSN_SPEC_BACK_DEPS (insn) = NULL;
637
638   free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
639   INSN_RESOLVED_BACK_DEPS (insn) = NULL;
640
641   free_deps_list (INSN_FORW_DEPS (insn));
642   INSN_FORW_DEPS (insn) = NULL;
643
644   free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
645   INSN_RESOLVED_FORW_DEPS (insn) = NULL;
646 }
647
648 /* Find a dependency between producer PRO and consumer CON.
649    Search through resolved dependency lists if RESOLVED_P is true.
650    If no such dependency is found return NULL,
651    otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
652    with an iterator pointing to it.  */
653 static dep_t
654 sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
655                               sd_iterator_def *sd_it_ptr)
656 {
657   sd_list_types_def pro_list_type;
658   sd_list_types_def con_list_type;
659   sd_iterator_def sd_it;
660   dep_t dep;
661   bool found_p = false;
662
663   if (resolved_p)
664     {
665       pro_list_type = SD_LIST_RES_FORW;
666       con_list_type = SD_LIST_RES_BACK;
667     }
668   else
669     {
670       pro_list_type = SD_LIST_FORW;
671       con_list_type = SD_LIST_BACK;
672     }
673
674   /* Walk through either back list of INSN or forw list of ELEM
675      depending on which one is shorter.  */
676   if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
677     {
678       /* Find the dep_link with producer PRO in consumer's back_deps.  */
679       FOR_EACH_DEP (con, con_list_type, sd_it, dep)
680         if (DEP_PRO (dep) == pro)
681           {
682             found_p = true;
683             break;
684           }
685     }
686   else
687     {
688       /* Find the dep_link with consumer CON in producer's forw_deps.  */
689       FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
690         if (DEP_CON (dep) == con)
691           {
692             found_p = true;
693             break;
694           }
695     }
696
697   if (found_p)
698     {
699       if (sd_it_ptr != NULL)
700         *sd_it_ptr = sd_it;
701
702       return dep;
703     }
704
705   return NULL;
706 }
707
708 /* Find a dependency between producer PRO and consumer CON.
709    Use dependency [if available] to check if dependency is present at all.
710    Search through resolved dependency lists if RESOLVED_P is true.
711    If the dependency or NULL if none found.  */
712 dep_t
713 sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
714 {
715   if (true_dependency_cache != NULL)
716     /* Avoiding the list walk below can cut compile times dramatically
717        for some code.  */
718     {
719       int elem_luid = INSN_LUID (pro);
720       int insn_luid = INSN_LUID (con);
721
722       gcc_assert (output_dependency_cache != NULL
723                   && anti_dependency_cache != NULL);
724
725       if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
726           && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
727           && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
728         return NULL;
729     }
730
731   return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
732 }
733
734 /* Add or update  a dependence described by DEP.
735    MEM1 and MEM2, if non-null, correspond to memory locations in case of
736    data speculation.
737
738    The function returns a value indicating if an old entry has been changed
739    or a new entry has been added to insn's backward deps.
740
741    This function merely checks if producer and consumer is the same insn
742    and doesn't create a dep in this case.  Actual manipulation of
743    dependence data structures is performed in add_or_update_dep_1.  */
744 static enum DEPS_ADJUST_RESULT
745 maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
746 {
747   rtx elem = DEP_PRO (dep);
748   rtx insn = DEP_CON (dep);
749
750   gcc_assert (INSN_P (insn) && INSN_P (elem));
751
752   /* Don't depend an insn on itself.  */
753   if (insn == elem)
754     {
755       if (current_sched_info->flags & DO_SPECULATION)
756         /* INSN has an internal dependence, which we can't overcome.  */
757         HAS_INTERNAL_DEP (insn) = 1;
758
759       return DEP_NODEP;
760     }
761
762   return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
763 }
764
765 /* Ask dependency caches what needs to be done for dependence DEP.
766    Return DEP_CREATED if new dependence should be created and there is no
767    need to try to find one searching the dependencies lists.
768    Return DEP_PRESENT if there already is a dependence described by DEP and
769    hence nothing is to be done.
770    Return DEP_CHANGED if there already is a dependence, but it should be
771    updated to incorporate additional information from DEP.  */
772 static enum DEPS_ADJUST_RESULT
773 ask_dependency_caches (dep_t dep)
774 {
775   int elem_luid = INSN_LUID (DEP_PRO (dep));
776   int insn_luid = INSN_LUID (DEP_CON (dep));
777
778   gcc_assert (true_dependency_cache != NULL
779               && output_dependency_cache != NULL
780               && anti_dependency_cache != NULL);
781
782   if (!(current_sched_info->flags & USE_DEPS_LIST))
783     {          
784       enum reg_note present_dep_type;
785
786       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
787         present_dep_type = REG_DEP_TRUE;
788       else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
789         present_dep_type = REG_DEP_OUTPUT;
790       else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
791         present_dep_type = REG_DEP_ANTI;
792       else
793         /* There is no existing dep so it should be created.  */
794         return DEP_CREATED;
795
796       if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
797         /* DEP does not add anything to the existing dependence.  */
798         return DEP_PRESENT;
799     }
800   else
801     {      
802       ds_t present_dep_types = 0;
803           
804       if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
805         present_dep_types |= DEP_TRUE;
806       if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
807         present_dep_types |= DEP_OUTPUT;
808       if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
809         present_dep_types |= DEP_ANTI;
810
811       if (present_dep_types == 0)
812         /* There is no existing dep so it should be created.  */
813         return DEP_CREATED;
814
815       if (!(current_sched_info->flags & DO_SPECULATION)
816           || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
817         {
818           if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
819               == present_dep_types)
820             /* DEP does not add anything to the existing dependence.  */
821             return DEP_PRESENT;
822         }
823       else
824         {
825           /* Only true dependencies can be data speculative and
826              only anti dependencies can be control speculative.  */
827           gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
828                       == present_dep_types);
829
830           /* if (DEP is SPECULATIVE) then
831              ..we should update DEP_STATUS
832              else
833              ..we should reset existing dep to non-speculative.  */
834         }
835     }
836
837   return DEP_CHANGED;
838 }
839
840 /* Set dependency caches according to DEP.  */
841 static void
842 set_dependency_caches (dep_t dep)
843 {
844   int elem_luid = INSN_LUID (DEP_PRO (dep));
845   int insn_luid = INSN_LUID (DEP_CON (dep));
846
847   if (!(current_sched_info->flags & USE_DEPS_LIST))
848     {
849       switch (DEP_TYPE (dep))
850         {
851         case REG_DEP_TRUE:
852           bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
853           break;
854
855         case REG_DEP_OUTPUT:
856           bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
857           break;
858
859         case REG_DEP_ANTI:
860           bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
861           break;
862
863         default:
864           gcc_unreachable ();
865         }
866     }
867   else
868     {
869       ds_t ds = DEP_STATUS (dep);
870
871       if (ds & DEP_TRUE)
872         bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
873       if (ds & DEP_OUTPUT)
874         bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
875       if (ds & DEP_ANTI)
876         bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
877
878       if (ds & SPECULATIVE)
879         {
880           gcc_assert (current_sched_info->flags & DO_SPECULATION);
881           bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
882         }
883     }
884 }
885
886 /* Type of dependence DEP have changed from OLD_TYPE.  Update dependency
887    caches accordingly.  */
888 static void
889 update_dependency_caches (dep_t dep, enum reg_note old_type)
890 {
891   int elem_luid = INSN_LUID (DEP_PRO (dep));
892   int insn_luid = INSN_LUID (DEP_CON (dep));
893
894   /* Clear corresponding cache entry because type of the link
895      may have changed.  Keep them if we use_deps_list.  */
896   if (!(current_sched_info->flags & USE_DEPS_LIST))
897     {
898       switch (old_type)
899         {
900         case REG_DEP_OUTPUT:
901           bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
902           break;
903
904         case REG_DEP_ANTI:
905           bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
906           break;
907
908         default:
909           gcc_unreachable ();                        
910         }
911     }
912
913   set_dependency_caches (dep);
914 }
915
916 /* Convert a dependence pointed to by SD_IT to be non-speculative.  */
917 static void
918 change_spec_dep_to_hard (sd_iterator_def sd_it)
919 {
920   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
921   dep_link_t link = DEP_NODE_BACK (node);
922   dep_t dep = DEP_NODE_DEP (node);
923   rtx elem = DEP_PRO (dep);
924   rtx insn = DEP_CON (dep);
925
926   move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
927
928   DEP_STATUS (dep) &= ~SPECULATIVE;
929
930   if (true_dependency_cache != NULL)
931     /* Clear the cache entry.  */
932     bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
933                       INSN_LUID (elem));
934 }
935
936 /* Update DEP to incorporate information from NEW_DEP.
937    SD_IT points to DEP in case it should be moved to another list.
938    MEM1 and MEM2, if nonnull, correspond to memory locations in case if
939    data-speculative dependence should be updated.  */
940 static enum DEPS_ADJUST_RESULT
941 update_dep (dep_t dep, dep_t new_dep,
942             sd_iterator_def sd_it ATTRIBUTE_UNUSED,
943             rtx mem1 ATTRIBUTE_UNUSED,
944             rtx mem2 ATTRIBUTE_UNUSED)
945 {
946   enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
947   enum reg_note old_type = DEP_TYPE (dep);
948
949   /* If this is a more restrictive type of dependence than the
950      existing one, then change the existing dependence to this
951      type.  */
952   if ((int) DEP_TYPE (new_dep) < (int) old_type)
953     {
954       DEP_TYPE (dep) = DEP_TYPE (new_dep);
955       res = DEP_CHANGED;
956     }
957
958   if (current_sched_info->flags & USE_DEPS_LIST)
959     /* Update DEP_STATUS.  */
960     {
961       ds_t dep_status = DEP_STATUS (dep);
962       ds_t ds = DEP_STATUS (new_dep);
963       ds_t new_status = ds | dep_status;
964
965       if (new_status & SPECULATIVE)
966         /* Either existing dep or a dep we're adding or both are
967            speculative.  */
968         {
969           if (!(ds & SPECULATIVE)
970               || !(dep_status & SPECULATIVE))
971             /* The new dep can't be speculative.  */
972             {
973               new_status &= ~SPECULATIVE;
974
975               if (dep_status & SPECULATIVE)
976                 /* The old dep was speculative, but now it
977                    isn't.  */
978                 change_spec_dep_to_hard (sd_it);
979             }
980           else
981             {
982               /* Both are speculative.  Merge probabilities.  */
983               if (mem1 != NULL)
984                 {
985                   dw_t dw;
986
987                   dw = estimate_dep_weak (mem1, mem2);
988                   ds = set_dep_weak (ds, BEGIN_DATA, dw);
989                 }
990                                                          
991               new_status = ds_merge (dep_status, ds);
992             }
993         }
994
995       ds = new_status;
996
997       if (dep_status != ds)
998         {
999           DEP_STATUS (dep) = ds;
1000           res = DEP_CHANGED;
1001         }
1002     }
1003
1004   if (true_dependency_cache != NULL
1005       && res == DEP_CHANGED)
1006     update_dependency_caches (dep, old_type);
1007
1008   return res;
1009 }
1010
1011 /* Add or update  a dependence described by DEP.
1012    MEM1 and MEM2, if non-null, correspond to memory locations in case of
1013    data speculation.
1014
1015    The function returns a value indicating if an old entry has been changed
1016    or a new entry has been added to insn's backward deps or nothing has
1017    been updated at all.  */
1018 static enum DEPS_ADJUST_RESULT
1019 add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1020                      rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1021 {
1022   bool maybe_present_p = true;
1023   bool present_p = false;
1024
1025   gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1026               && DEP_PRO (new_dep) != DEP_CON (new_dep));
1027   
1028 #ifdef ENABLE_CHECKING
1029   check_dep (new_dep, mem1 != NULL);
1030 #endif
1031
1032   if (true_dependency_cache != NULL)
1033     {
1034       switch (ask_dependency_caches (new_dep))
1035         {
1036         case DEP_PRESENT:
1037           return DEP_PRESENT;
1038
1039         case DEP_CHANGED:
1040           maybe_present_p = true;
1041           present_p = true;
1042           break;
1043
1044         case DEP_CREATED:
1045           maybe_present_p = false;
1046           present_p = false;
1047           break;
1048
1049         default:
1050           gcc_unreachable ();
1051           break;
1052         }
1053     }
1054
1055   /* Check that we don't already have this dependence.  */
1056   if (maybe_present_p)
1057     {
1058       dep_t present_dep;
1059       sd_iterator_def sd_it;
1060
1061       gcc_assert (true_dependency_cache == NULL || present_p);
1062
1063       present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1064                                                   DEP_CON (new_dep),
1065                                                   resolved_p, &sd_it);
1066
1067       if (present_dep != NULL)
1068         /* We found an existing dependency between ELEM and INSN.  */
1069         return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1070       else
1071         /* We didn't find a dep, it shouldn't present in the cache.  */
1072         gcc_assert (!present_p);
1073     }
1074
1075   /* Might want to check one level of transitivity to save conses.
1076      This check should be done in maybe_add_or_update_dep_1.
1077      Since we made it to add_or_update_dep_1, we must create
1078      (or update) a link.  */
1079
1080   if (mem1 != NULL_RTX)
1081     {
1082       gcc_assert (current_sched_info->flags & DO_SPECULATION);
1083       DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1084                                            estimate_dep_weak (mem1, mem2));
1085     }
1086
1087   sd_add_dep (new_dep, resolved_p);
1088   
1089   return DEP_CREATED;
1090 }
1091
1092 /* Initialize BACK_LIST_PTR with consumer's backward list and
1093    FORW_LIST_PTR with producer's forward list.  If RESOLVED_P is true
1094    initialize with lists that hold resolved deps.  */
1095 static void
1096 get_back_and_forw_lists (dep_t dep, bool resolved_p,
1097                          deps_list_t *back_list_ptr,
1098                          deps_list_t *forw_list_ptr)
1099 {
1100   rtx con = DEP_CON (dep);
1101
1102   if (!resolved_p)
1103     {
1104       if ((current_sched_info->flags & DO_SPECULATION)
1105           && (DEP_STATUS (dep) & SPECULATIVE))
1106         *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1107       else
1108         *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1109
1110       *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1111     }
1112   else
1113     {
1114       *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1115       *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1116     }
1117 }
1118
1119 /* Add dependence described by DEP.
1120    If RESOLVED_P is true treat the dependence as a resolved one.  */
1121 void
1122 sd_add_dep (dep_t dep, bool resolved_p)
1123 {
1124   dep_node_t n = create_dep_node ();
1125   deps_list_t con_back_deps;
1126   deps_list_t pro_forw_deps;
1127   rtx elem = DEP_PRO (dep);
1128   rtx insn = DEP_CON (dep);
1129
1130   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1131
1132   if ((current_sched_info->flags & DO_SPECULATION)
1133       && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1134     DEP_STATUS (dep) &= ~SPECULATIVE;
1135
1136   copy_dep (DEP_NODE_DEP (n), dep);
1137
1138   get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1139
1140   add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1141
1142 #ifdef ENABLE_CHECKING
1143   check_dep (dep, false);
1144 #endif
1145
1146   add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1147
1148   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1149      in the bitmap caches of dependency information.  */
1150   if (true_dependency_cache != NULL)
1151     set_dependency_caches (dep);
1152 }
1153
1154 /* Add or update backward dependence between INSN and ELEM
1155    with given type DEP_TYPE and dep_status DS.
1156    This function is a convenience wrapper.  */
1157 enum DEPS_ADJUST_RESULT
1158 sd_add_or_update_dep (dep_t dep, bool resolved_p)
1159 {
1160   return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1161 }
1162
1163 /* Resolved dependence pointed to by SD_IT.
1164    SD_IT will advance to the next element.  */
1165 void
1166 sd_resolve_dep (sd_iterator_def sd_it)
1167 {
1168   dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1169   dep_t dep = DEP_NODE_DEP (node);
1170   rtx pro = DEP_PRO (dep);
1171   rtx con = DEP_CON (dep);
1172
1173   if ((current_sched_info->flags & DO_SPECULATION)
1174       && (DEP_STATUS (dep) & SPECULATIVE))
1175     move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1176                    INSN_RESOLVED_BACK_DEPS (con));
1177   else
1178     move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1179                    INSN_RESOLVED_BACK_DEPS (con));
1180
1181   move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1182                  INSN_RESOLVED_FORW_DEPS (pro));
1183 }
1184
1185 /* Make TO depend on all the FROM's producers.
1186    If RESOLVED_P is true add dependencies to the resolved lists.  */
1187 void
1188 sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
1189 {
1190   sd_list_types_def list_type;
1191   sd_iterator_def sd_it;
1192   dep_t dep;
1193
1194   list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1195
1196   FOR_EACH_DEP (from, list_type, sd_it, dep)
1197     {
1198       dep_def _new_dep, *new_dep = &_new_dep;
1199
1200       copy_dep (new_dep, dep);
1201       DEP_CON (new_dep) = to;
1202       sd_add_dep (new_dep, resolved_p);
1203     }
1204 }
1205
1206 /* Remove a dependency referred to by SD_IT.
1207    SD_IT will point to the next dependence after removal.  */
1208 void
1209 sd_delete_dep (sd_iterator_def sd_it)
1210 {
1211   dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1212   dep_t dep = DEP_NODE_DEP (n);
1213   rtx pro = DEP_PRO (dep);
1214   rtx con = DEP_CON (dep);
1215   deps_list_t con_back_deps;
1216   deps_list_t pro_forw_deps;
1217
1218   if (true_dependency_cache != NULL)
1219     {
1220       int elem_luid = INSN_LUID (pro);
1221       int insn_luid = INSN_LUID (con);
1222
1223       bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1224       bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1225       bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1226
1227       if (current_sched_info->flags & DO_SPECULATION)
1228         bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1229     }
1230
1231   get_back_and_forw_lists (dep, sd_it.resolved_p,
1232                            &con_back_deps, &pro_forw_deps);
1233
1234   remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1235   remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1236
1237   delete_dep_node (n);
1238 }
1239
1240 /* Dump size of the lists.  */
1241 #define DUMP_LISTS_SIZE (2)
1242
1243 /* Dump dependencies of the lists.  */
1244 #define DUMP_LISTS_DEPS (4)
1245
1246 /* Dump all information about the lists.  */
1247 #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1248
1249 /* Dump deps_lists of INSN specified by TYPES to DUMP.
1250    FLAGS is a bit mask specifying what information about the lists needs
1251    to be printed.
1252    If FLAGS has the very first bit set, then dump all information about
1253    the lists and propagate this bit into the callee dump functions.  */
1254 static void
1255 dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1256 {
1257   sd_iterator_def sd_it;
1258   dep_t dep;
1259   int all;
1260
1261   all = (flags & 1);
1262
1263   if (all)
1264     flags |= DUMP_LISTS_ALL;
1265
1266   fprintf (dump, "[");
1267
1268   if (flags & DUMP_LISTS_SIZE)
1269     fprintf (dump, "%d; ", sd_lists_size (insn, types));
1270
1271   if (flags & DUMP_LISTS_DEPS)
1272     {
1273       FOR_EACH_DEP (insn, types, sd_it, dep)
1274         {
1275           dump_dep (dump, dep, dump_dep_flags | all);
1276           fprintf (dump, " ");
1277         }
1278     }
1279 }
1280
1281 /* Dump all information about deps_lists of INSN specified by TYPES
1282    to STDERR.  */
1283 void
1284 sd_debug_lists (rtx insn, sd_list_types_def types)
1285 {
1286   dump_lists (stderr, insn, types, 1);
1287   fprintf (stderr, "\n");
1288 }
1289
1290 /* A convenience wrapper to operate on an entire list.  */
1291
1292 static void
1293 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
1294 {
1295   for (; list; list = XEXP (list, 1))
1296     {
1297       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1298         add_dependence (insn, XEXP (list, 0), dep_type);
1299     }
1300 }
1301
1302 /* Similar, but free *LISTP at the same time.  */
1303
1304 static void
1305 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
1306                               enum reg_note dep_type)
1307 {
1308   rtx list, next;
1309   for (list = *listp, *listp = NULL; list ; list = next)
1310     {
1311       next = XEXP (list, 1);
1312       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
1313         add_dependence (insn, XEXP (list, 0), dep_type);
1314       free_INSN_LIST_node (list);
1315     }
1316 }
1317
1318 /* Clear all dependencies for an insn.  */
1319 static void
1320 delete_all_dependences (rtx insn)
1321 {
1322   sd_iterator_def sd_it;
1323   dep_t dep;
1324
1325   /* The below cycle can be optimized to clear the caches and back_deps
1326      in one call but that would provoke duplication of code from
1327      delete_dep ().  */
1328
1329   for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1330        sd_iterator_cond (&sd_it, &dep);)
1331     sd_delete_dep (sd_it);
1332 }
1333
1334 /* All insns in a scheduling group except the first should only have
1335    dependencies on the previous insn in the group.  So we find the
1336    first instruction in the scheduling group by walking the dependence
1337    chains backwards. Then we add the dependencies for the group to
1338    the previous nonnote insn.  */
1339
1340 static void
1341 fixup_sched_groups (rtx insn)
1342 {
1343   sd_iterator_def sd_it;
1344   dep_t dep;
1345   rtx prev_nonnote;
1346
1347   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1348     {
1349       rtx i = insn;
1350       rtx pro = DEP_PRO (dep);
1351
1352       do
1353         {
1354           i = prev_nonnote_insn (i);
1355
1356           if (pro == i)
1357             goto next_link;
1358         } while (SCHED_GROUP_P (i));
1359
1360       if (! sched_insns_conditions_mutex_p (i, pro))
1361         add_dependence (i, pro, DEP_TYPE (dep));
1362     next_link:;
1363     }
1364
1365   delete_all_dependences (insn);
1366
1367   prev_nonnote = prev_nonnote_insn (insn);
1368   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1369       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1370     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1371 }
1372 \f
1373 /* Process an insn's memory dependencies.  There are four kinds of
1374    dependencies:
1375
1376    (0) read dependence: read follows read
1377    (1) true dependence: read follows write
1378    (2) output dependence: write follows write
1379    (3) anti dependence: write follows read
1380
1381    We are careful to build only dependencies which actually exist, and
1382    use transitivity to avoid building too many links.  */
1383
1384 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1385    The MEM is a memory reference contained within INSN, which we are saving
1386    so that we can do memory aliasing on it.  */
1387
1388 static void
1389 add_insn_mem_dependence (struct deps *deps, bool read_p,
1390                          rtx insn, rtx mem)
1391 {
1392   rtx *insn_list;
1393   rtx *mem_list;
1394   rtx link;
1395
1396   if (read_p)
1397     {
1398       insn_list = &deps->pending_read_insns;
1399       mem_list = &deps->pending_read_mems;
1400       deps->pending_read_list_length++;
1401     }
1402   else
1403     {
1404       insn_list = &deps->pending_write_insns;
1405       mem_list = &deps->pending_write_mems;
1406       deps->pending_write_list_length++;
1407     }
1408
1409   link = alloc_INSN_LIST (insn, *insn_list);
1410   *insn_list = link;
1411
1412   if (current_sched_info->use_cselib)
1413     {
1414       mem = shallow_copy_rtx (mem);
1415       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
1416     }
1417   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1418   *mem_list = link;
1419 }
1420
1421 /* Make a dependency between every memory reference on the pending lists
1422    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
1423    dependencies for a read operation, similarly with FOR_WRITE.  */
1424
1425 static void
1426 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
1427                      int for_write)
1428 {
1429   if (for_write)
1430     {
1431       add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
1432                                     REG_DEP_ANTI);
1433       free_EXPR_LIST_list (&deps->pending_read_mems);
1434       deps->pending_read_list_length = 0;
1435     }
1436
1437   add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
1438                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1439   free_EXPR_LIST_list (&deps->pending_write_mems);
1440   deps->pending_write_list_length = 0;
1441
1442   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
1443                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
1444   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1445   deps->pending_flush_length = 1;
1446 }
1447 \f
1448 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
1449    The type of the reference is specified by REF and can be SET,
1450    CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE.  */
1451
1452 static void
1453 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
1454                    enum rtx_code ref, rtx insn)
1455 {
1456   /* A hard reg in a wide mode may really be multiple registers.
1457      If so, mark all of them just like the first.  */
1458   if (regno < FIRST_PSEUDO_REGISTER)
1459     {
1460       int i = hard_regno_nregs[regno][mode];
1461       if (ref == SET)
1462         {
1463           while (--i >= 0)
1464             SET_REGNO_REG_SET (reg_pending_sets, regno + i);
1465         }
1466       else if (ref == USE)
1467         {
1468           while (--i >= 0)
1469             SET_REGNO_REG_SET (reg_pending_uses, regno + i);
1470         }
1471       else
1472         {
1473           while (--i >= 0)
1474             SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
1475         }
1476     }
1477
1478   /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
1479      it does not reload.  Ignore these as they have served their
1480      purpose already.  */
1481   else if (regno >= deps->max_reg)
1482     {
1483       enum rtx_code code = GET_CODE (PATTERN (insn));
1484       gcc_assert (code == USE || code == CLOBBER);
1485     }
1486
1487   else
1488     {
1489       if (ref == SET)
1490         SET_REGNO_REG_SET (reg_pending_sets, regno);
1491       else if (ref == USE)
1492         SET_REGNO_REG_SET (reg_pending_uses, regno);
1493       else
1494         SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1495
1496       /* Pseudos that are REG_EQUIV to something may be replaced
1497          by that during reloading.  We need only add dependencies for
1498         the address in the REG_EQUIV note.  */
1499       if (!reload_completed && get_reg_known_equiv_p (regno))
1500         {
1501           rtx t = get_reg_known_value (regno);
1502           if (MEM_P (t))
1503             sched_analyze_2 (deps, XEXP (t, 0), insn);
1504         }
1505
1506       /* Don't let it cross a call after scheduling if it doesn't
1507          already cross one.  */
1508       if (REG_N_CALLS_CROSSED (regno) == 0)
1509         {
1510           if (ref == USE)
1511             deps->sched_before_next_call
1512               = alloc_INSN_LIST (insn, deps->sched_before_next_call);
1513           else
1514             add_dependence_list (insn, deps->last_function_call, 1,
1515                                  REG_DEP_ANTI);
1516         }
1517     }
1518 }
1519
1520 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
1521    rtx, X, creating all dependencies generated by the write to the
1522    destination of X, and reads of everything mentioned.  */
1523
1524 static void
1525 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
1526 {
1527   rtx dest = XEXP (x, 0);
1528   enum rtx_code code = GET_CODE (x);
1529
1530   if (dest == 0)
1531     return;
1532
1533   if (GET_CODE (dest) == PARALLEL)
1534     {
1535       int i;
1536
1537       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1538         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1539           sched_analyze_1 (deps,
1540                            gen_rtx_CLOBBER (VOIDmode,
1541                                             XEXP (XVECEXP (dest, 0, i), 0)),
1542                            insn);
1543
1544       if (GET_CODE (x) == SET)
1545         sched_analyze_2 (deps, SET_SRC (x), insn);
1546       return;
1547     }
1548
1549   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1550          || GET_CODE (dest) == ZERO_EXTRACT)
1551     {
1552       if (GET_CODE (dest) == STRICT_LOW_PART
1553          || GET_CODE (dest) == ZERO_EXTRACT
1554          || df_read_modify_subreg_p (dest))
1555         {
1556           /* These both read and modify the result.  We must handle
1557              them as writes to get proper dependencies for following
1558              instructions.  We must handle them as reads to get proper
1559              dependencies from this to previous instructions.
1560              Thus we need to call sched_analyze_2.  */
1561
1562           sched_analyze_2 (deps, XEXP (dest, 0), insn);
1563         }
1564       if (GET_CODE (dest) == ZERO_EXTRACT)
1565         {
1566           /* The second and third arguments are values read by this insn.  */
1567           sched_analyze_2 (deps, XEXP (dest, 1), insn);
1568           sched_analyze_2 (deps, XEXP (dest, 2), insn);
1569         }
1570       dest = XEXP (dest, 0);
1571     }
1572
1573   if (REG_P (dest))
1574     {
1575       int regno = REGNO (dest);
1576       enum machine_mode mode = GET_MODE (dest);
1577
1578       sched_analyze_reg (deps, regno, mode, code, insn);
1579
1580 #ifdef STACK_REGS
1581       /* Treat all writes to a stack register as modifying the TOS.  */
1582       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
1583         {
1584           /* Avoid analyzing the same register twice.  */
1585           if (regno != FIRST_STACK_REG)
1586             sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
1587           sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
1588         }
1589 #endif
1590     }
1591   else if (MEM_P (dest))
1592     {
1593       /* Writing memory.  */
1594       rtx t = dest;
1595
1596       if (current_sched_info->use_cselib)
1597         {
1598           t = shallow_copy_rtx (dest);
1599           cselib_lookup (XEXP (t, 0), Pmode, 1);
1600           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
1601         }
1602       t = canon_rtx (t);
1603
1604       if ((deps->pending_read_list_length + deps->pending_write_list_length)
1605           > MAX_PENDING_LIST_LENGTH)
1606         {
1607           /* Flush all pending reads and writes to prevent the pending lists
1608              from getting any larger.  Insn scheduling runs too slowly when
1609              these lists get long.  When compiling GCC with itself,
1610              this flush occurs 8 times for sparc, and 10 times for m88k using
1611              the default value of 32.  */
1612           flush_pending_lists (deps, insn, false, true);
1613         }
1614       else
1615         {
1616           rtx pending, pending_mem;
1617
1618           pending = deps->pending_read_insns;
1619           pending_mem = deps->pending_read_mems;
1620           while (pending)
1621             {
1622               if (anti_dependence (XEXP (pending_mem, 0), t)
1623                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1624                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1625
1626               pending = XEXP (pending, 1);
1627               pending_mem = XEXP (pending_mem, 1);
1628             }
1629
1630           pending = deps->pending_write_insns;
1631           pending_mem = deps->pending_write_mems;
1632           while (pending)
1633             {
1634               if (output_dependence (XEXP (pending_mem, 0), t)
1635                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1636                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1637
1638               pending = XEXP (pending, 1);
1639               pending_mem = XEXP (pending_mem, 1);
1640             }
1641
1642           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1643                                REG_DEP_ANTI);
1644
1645           add_insn_mem_dependence (deps, false, insn, dest);
1646         }
1647       sched_analyze_2 (deps, XEXP (dest, 0), insn);
1648     }
1649
1650   /* Analyze reads.  */
1651   if (GET_CODE (x) == SET)
1652     sched_analyze_2 (deps, SET_SRC (x), insn);
1653 }
1654
1655 /* Analyze the uses of memory and registers in rtx X in INSN.  */
1656
1657 static void
1658 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
1659 {
1660   int i;
1661   int j;
1662   enum rtx_code code;
1663   const char *fmt;
1664
1665   if (x == 0)
1666     return;
1667
1668   code = GET_CODE (x);
1669
1670   switch (code)
1671     {
1672     case CONST_INT:
1673     case CONST_DOUBLE:
1674     case CONST_FIXED:
1675     case CONST_VECTOR:
1676     case SYMBOL_REF:
1677     case CONST:
1678     case LABEL_REF:
1679       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
1680          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1681          this does not mean that this insn is using cc0.  */
1682       return;
1683
1684 #ifdef HAVE_cc0
1685     case CC0:
1686       /* User of CC0 depends on immediately preceding insn.  */
1687       SCHED_GROUP_P (insn) = 1;
1688        /* Don't move CC0 setter to another block (it can set up the
1689         same flag for previous CC0 users which is safe).  */
1690       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
1691       return;
1692 #endif
1693
1694     case REG:
1695       {
1696         int regno = REGNO (x);
1697         enum machine_mode mode = GET_MODE (x);
1698
1699         sched_analyze_reg (deps, regno, mode, USE, insn);
1700
1701 #ifdef STACK_REGS
1702       /* Treat all reads of a stack register as modifying the TOS.  */
1703       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
1704         {
1705           /* Avoid analyzing the same register twice.  */
1706           if (regno != FIRST_STACK_REG)
1707             sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
1708           sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
1709         }
1710 #endif
1711         return;
1712       }
1713
1714     case MEM:
1715       {
1716         /* Reading memory.  */
1717         rtx u;
1718         rtx pending, pending_mem;
1719         rtx t = x;
1720
1721         if (current_sched_info->use_cselib)
1722           {
1723             t = shallow_copy_rtx (t);
1724             cselib_lookup (XEXP (t, 0), Pmode, 1);
1725             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
1726           }
1727         t = canon_rtx (t);
1728         pending = deps->pending_read_insns;
1729         pending_mem = deps->pending_read_mems;
1730         while (pending)
1731           {
1732             if (read_dependence (XEXP (pending_mem, 0), t)
1733                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1734               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1735
1736             pending = XEXP (pending, 1);
1737             pending_mem = XEXP (pending_mem, 1);
1738           }
1739
1740         pending = deps->pending_write_insns;
1741         pending_mem = deps->pending_write_mems;
1742         while (pending)
1743           {
1744             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1745                                  t, rtx_varies_p)
1746                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1747               {
1748                 if ((current_sched_info->flags & DO_SPECULATION)
1749                     && (spec_info->mask & BEGIN_DATA))
1750                   /* Create a data-speculative dependence between producer
1751                      and consumer.  */
1752                   {
1753                     dep_def _dep, *dep = &_dep;
1754
1755                     init_dep_1 (dep, XEXP (pending, 0), insn, REG_DEP_TRUE,
1756                                 BEGIN_DATA | DEP_TRUE);
1757
1758                     maybe_add_or_update_dep_1 (dep, false,
1759                                                XEXP (pending_mem, 0), t);
1760                   }
1761                 else
1762                   add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
1763               }
1764
1765             pending = XEXP (pending, 1);
1766             pending_mem = XEXP (pending_mem, 1);
1767           }
1768
1769         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
1770           if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
1771             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1772
1773         /* Always add these dependencies to pending_reads, since
1774            this insn may be followed by a write.  */
1775         add_insn_mem_dependence (deps, true, insn, x);
1776
1777         /* Take advantage of tail recursion here.  */
1778         sched_analyze_2 (deps, XEXP (x, 0), insn);
1779         return;
1780       }
1781
1782     /* Force pending stores to memory in case a trap handler needs them.  */
1783     case TRAP_IF:
1784       flush_pending_lists (deps, insn, true, false);
1785       break;
1786
1787     case ASM_OPERANDS:
1788     case ASM_INPUT:
1789     case UNSPEC_VOLATILE:
1790       {
1791         /* Traditional and volatile asm instructions must be considered to use
1792            and clobber all hard registers, all pseudo-registers and all of
1793            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
1794
1795            Consider for instance a volatile asm that changes the fpu rounding
1796            mode.  An insn should not be moved across this even if it only uses
1797            pseudo-regs because it might give an incorrectly rounded result.  */
1798         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1799           reg_pending_barrier = TRUE_BARRIER;
1800
1801         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1802            We can not just fall through here since then we would be confused
1803            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1804            traditional asms unlike their normal usage.  */
1805
1806         if (code == ASM_OPERANDS)
1807           {
1808             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1809               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
1810             return;
1811           }
1812         break;
1813       }
1814
1815     case PRE_DEC:
1816     case POST_DEC:
1817     case PRE_INC:
1818     case POST_INC:
1819       /* These both read and modify the result.  We must handle them as writes
1820          to get proper dependencies for following instructions.  We must handle
1821          them as reads to get proper dependencies from this to previous
1822          instructions.  Thus we need to pass them to both sched_analyze_1
1823          and sched_analyze_2.  We must call sched_analyze_2 first in order
1824          to get the proper antecedent for the read.  */
1825       sched_analyze_2 (deps, XEXP (x, 0), insn);
1826       sched_analyze_1 (deps, x, insn);
1827       return;
1828
1829     case POST_MODIFY:
1830     case PRE_MODIFY:
1831       /* op0 = op0 + op1 */
1832       sched_analyze_2 (deps, XEXP (x, 0), insn);
1833       sched_analyze_2 (deps, XEXP (x, 1), insn);
1834       sched_analyze_1 (deps, x, insn);
1835       return;
1836
1837     default:
1838       break;
1839     }
1840
1841   /* Other cases: walk the insn.  */
1842   fmt = GET_RTX_FORMAT (code);
1843   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1844     {
1845       if (fmt[i] == 'e')
1846         sched_analyze_2 (deps, XEXP (x, i), insn);
1847       else if (fmt[i] == 'E')
1848         for (j = 0; j < XVECLEN (x, i); j++)
1849           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
1850     }
1851 }
1852
1853 /* Analyze an INSN with pattern X to find all dependencies.  */
1854
1855 static void
1856 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
1857 {
1858   RTX_CODE code = GET_CODE (x);
1859   rtx link;
1860   unsigned i;
1861   reg_set_iterator rsi;
1862
1863   if (code == COND_EXEC)
1864     {
1865       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
1866
1867       /* ??? Should be recording conditions so we reduce the number of
1868          false dependencies.  */
1869       x = COND_EXEC_CODE (x);
1870       code = GET_CODE (x);
1871     }
1872   if (code == SET || code == CLOBBER)
1873     {
1874       sched_analyze_1 (deps, x, insn);
1875
1876       /* Bare clobber insns are used for letting life analysis, reg-stack
1877          and others know that a value is dead.  Depend on the last call
1878          instruction so that reg-stack won't get confused.  */
1879       if (code == CLOBBER)
1880         add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
1881     }
1882   else if (code == PARALLEL)
1883     {
1884       for (i = XVECLEN (x, 0); i--;)
1885         {
1886           rtx sub = XVECEXP (x, 0, i);
1887           code = GET_CODE (sub);
1888
1889           if (code == COND_EXEC)
1890             {
1891               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
1892               sub = COND_EXEC_CODE (sub);
1893               code = GET_CODE (sub);
1894             }
1895           if (code == SET || code == CLOBBER)
1896             sched_analyze_1 (deps, sub, insn);
1897           else
1898             sched_analyze_2 (deps, sub, insn);
1899         }
1900     }
1901   else
1902     sched_analyze_2 (deps, x, insn);
1903
1904   /* Mark registers CLOBBERED or used by called function.  */
1905   if (CALL_P (insn))
1906     {
1907       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1908         {
1909           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1910             sched_analyze_1 (deps, XEXP (link, 0), insn);
1911           else
1912             sched_analyze_2 (deps, XEXP (link, 0), insn);
1913         }
1914       if (find_reg_note (insn, REG_SETJMP, NULL))
1915         reg_pending_barrier = MOVE_BARRIER;
1916     }
1917
1918   if (JUMP_P (insn))
1919     {
1920       rtx next;
1921       next = next_nonnote_insn (insn);
1922       if (next && BARRIER_P (next))
1923         reg_pending_barrier = MOVE_BARRIER;
1924       else
1925         {
1926           rtx pending, pending_mem;
1927           regset_head tmp_uses, tmp_sets;
1928           INIT_REG_SET (&tmp_uses);
1929           INIT_REG_SET (&tmp_sets);
1930
1931           (*current_sched_info->compute_jump_reg_dependencies)
1932             (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
1933           /* Make latency of jump equal to 0 by using anti-dependence.  */
1934           EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
1935             {
1936               struct deps_reg *reg_last = &deps->reg_last[i];
1937               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
1938               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
1939               reg_last->uses_length++;
1940               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1941             }
1942           IOR_REG_SET (reg_pending_sets, &tmp_sets);
1943
1944           CLEAR_REG_SET (&tmp_uses);
1945           CLEAR_REG_SET (&tmp_sets);
1946
1947           /* All memory writes and volatile reads must happen before the
1948              jump.  Non-volatile reads must happen before the jump iff
1949              the result is needed by the above register used mask.  */
1950
1951           pending = deps->pending_write_insns;
1952           pending_mem = deps->pending_write_mems;
1953           while (pending)
1954             {
1955               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1956                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1957               pending = XEXP (pending, 1);
1958               pending_mem = XEXP (pending_mem, 1);
1959             }
1960
1961           pending = deps->pending_read_insns;
1962           pending_mem = deps->pending_read_mems;
1963           while (pending)
1964             {
1965               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
1966                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1967                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1968               pending = XEXP (pending, 1);
1969               pending_mem = XEXP (pending_mem, 1);
1970             }
1971
1972           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1973                                REG_DEP_ANTI);
1974         }
1975     }
1976
1977   /* If this instruction can throw an exception, then moving it changes
1978      where block boundaries fall.  This is mighty confusing elsewhere.
1979      Therefore, prevent such an instruction from being moved.  Same for
1980      non-jump instructions that define block boundaries.
1981      ??? Unclear whether this is still necessary in EBB mode.  If not,
1982      add_branch_dependences should be adjusted for RGN mode instead.  */
1983   if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
1984       || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
1985     reg_pending_barrier = MOVE_BARRIER;
1986
1987   /* Add register dependencies for insn.
1988      If the current insn is conditional, we can't free any of the lists.  */
1989   if (sched_get_condition (insn))
1990     {
1991       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1992         {
1993           struct deps_reg *reg_last = &deps->reg_last[i];
1994           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1995           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1996           reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1997           reg_last->uses_length++;
1998         }
1999       EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2000         {
2001           struct deps_reg *reg_last = &deps->reg_last[i];
2002           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2003           add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2004           reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
2005           reg_last->clobbers_length++;
2006         }
2007       EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2008         {
2009           struct deps_reg *reg_last = &deps->reg_last[i];
2010           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2011           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
2012           add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2013           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2014           SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2015         }
2016     }
2017   else
2018     {
2019       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
2020         {
2021           struct deps_reg *reg_last = &deps->reg_last[i];
2022           add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
2023           add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
2024           reg_last->uses_length++;
2025           reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
2026         }
2027       EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
2028         {
2029           struct deps_reg *reg_last = &deps->reg_last[i];
2030           if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
2031               || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
2032             {
2033               add_dependence_list_and_free (insn, &reg_last->sets, 0,
2034                                             REG_DEP_OUTPUT);
2035               add_dependence_list_and_free (insn, &reg_last->uses, 0,
2036                                             REG_DEP_ANTI);
2037               add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
2038                                             REG_DEP_OUTPUT);
2039               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2040               reg_last->clobbers_length = 0;
2041               reg_last->uses_length = 0;
2042             }
2043           else
2044             {
2045               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
2046               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2047             }
2048           reg_last->clobbers_length++;
2049           reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
2050         }
2051       EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
2052         {
2053           struct deps_reg *reg_last = &deps->reg_last[i];
2054           add_dependence_list_and_free (insn, &reg_last->sets, 0,
2055                                         REG_DEP_OUTPUT);
2056           add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
2057                                         REG_DEP_OUTPUT);
2058           add_dependence_list_and_free (insn, &reg_last->uses, 0,
2059                                         REG_DEP_ANTI);
2060           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2061           reg_last->uses_length = 0;
2062           reg_last->clobbers_length = 0;
2063           CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
2064         }
2065     }
2066
2067   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
2068   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
2069   IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
2070
2071   CLEAR_REG_SET (reg_pending_uses);
2072   CLEAR_REG_SET (reg_pending_clobbers);
2073   CLEAR_REG_SET (reg_pending_sets);
2074
2075   /* Add dependencies if a scheduling barrier was found.  */
2076   if (reg_pending_barrier)
2077     {
2078       /* In the case of barrier the most added dependencies are not
2079          real, so we use anti-dependence here.  */
2080       if (sched_get_condition (insn))
2081         {
2082           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2083             {
2084               struct deps_reg *reg_last = &deps->reg_last[i];
2085               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
2086               add_dependence_list
2087                 (insn, reg_last->sets, 0,
2088                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2089               add_dependence_list
2090                 (insn, reg_last->clobbers, 0,
2091                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2092             }
2093         }
2094       else
2095         {
2096           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2097             {
2098               struct deps_reg *reg_last = &deps->reg_last[i];
2099               add_dependence_list_and_free (insn, &reg_last->uses, 0,
2100                                             REG_DEP_ANTI);
2101               add_dependence_list_and_free
2102                 (insn, &reg_last->sets, 0,
2103                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2104               add_dependence_list_and_free
2105                 (insn, &reg_last->clobbers, 0,
2106                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
2107               reg_last->uses_length = 0;
2108               reg_last->clobbers_length = 0;
2109             }
2110         }
2111
2112       for (i = 0; i < (unsigned)deps->max_reg; i++)
2113         {
2114           struct deps_reg *reg_last = &deps->reg_last[i];
2115           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
2116           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2117         }
2118
2119       flush_pending_lists (deps, insn, true, true);
2120       CLEAR_REG_SET (&deps->reg_conditional_sets);
2121       reg_pending_barrier = NOT_A_BARRIER;
2122     }
2123
2124   /* If a post-call group is still open, see if it should remain so.
2125      This insn must be a simple move of a hard reg to a pseudo or
2126      vice-versa.
2127
2128      We must avoid moving these insns for correctness on
2129      SMALL_REGISTER_CLASS machines, and for special registers like
2130      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
2131      hard regs for all targets.  */
2132
2133   if (deps->in_post_call_group_p)
2134     {
2135       rtx tmp, set = single_set (insn);
2136       int src_regno, dest_regno;
2137
2138       if (set == NULL)
2139         goto end_call_group;
2140
2141       tmp = SET_DEST (set);
2142       if (GET_CODE (tmp) == SUBREG)
2143         tmp = SUBREG_REG (tmp);
2144       if (REG_P (tmp))
2145         dest_regno = REGNO (tmp);
2146       else
2147         goto end_call_group;
2148
2149       tmp = SET_SRC (set);
2150       if (GET_CODE (tmp) == SUBREG)
2151         tmp = SUBREG_REG (tmp);
2152       if ((GET_CODE (tmp) == PLUS
2153            || GET_CODE (tmp) == MINUS)
2154           && REG_P (XEXP (tmp, 0))
2155           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
2156           && dest_regno == STACK_POINTER_REGNUM)
2157         src_regno = STACK_POINTER_REGNUM;
2158       else if (REG_P (tmp))
2159         src_regno = REGNO (tmp);
2160       else
2161         goto end_call_group;
2162
2163       if (src_regno < FIRST_PSEUDO_REGISTER
2164           || dest_regno < FIRST_PSEUDO_REGISTER)
2165         {
2166           if (deps->in_post_call_group_p == post_call_initial)
2167             deps->in_post_call_group_p = post_call;
2168
2169           SCHED_GROUP_P (insn) = 1;
2170           CANT_MOVE (insn) = 1;
2171         }
2172       else
2173         {
2174         end_call_group:
2175           deps->in_post_call_group_p = not_post_call;
2176         }
2177     }
2178
2179   /* Fixup the dependencies in the sched group.  */
2180   if (SCHED_GROUP_P (insn))
2181     fixup_sched_groups (insn);
2182
2183   if ((current_sched_info->flags & DO_SPECULATION)
2184       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
2185     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
2186        be speculated.  */
2187     {
2188       sd_iterator_def sd_it;
2189       dep_t dep;
2190
2191       for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
2192            sd_iterator_cond (&sd_it, &dep);)
2193         change_spec_dep_to_hard (sd_it);
2194     }
2195 }
2196
2197 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
2198    dependencies for each insn.  */
2199
2200 void
2201 sched_analyze (struct deps *deps, rtx head, rtx tail)
2202 {
2203   rtx insn;
2204
2205   if (current_sched_info->use_cselib)
2206     cselib_init (true);
2207
2208   /* Before reload, if the previous block ended in a call, show that
2209      we are inside a post-call group, so as to keep the lifetimes of
2210      hard registers correct.  */
2211   if (! reload_completed && !LABEL_P (head))
2212     {
2213       insn = prev_nonnote_insn (head);
2214       if (insn && CALL_P (insn))
2215         deps->in_post_call_group_p = post_call_initial;
2216     }
2217   for (insn = head;; insn = NEXT_INSN (insn))
2218     {
2219       if (INSN_P (insn))
2220         {
2221           /* And initialize deps_lists.  */
2222           sd_init_insn (insn);
2223         }
2224
2225       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
2226         {
2227           /* Make each JUMP_INSN a scheduling barrier for memory
2228              references.  */
2229           if (JUMP_P (insn))
2230             {
2231               /* Keep the list a reasonable size.  */
2232               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
2233                 flush_pending_lists (deps, insn, true, true);
2234               else
2235                 deps->last_pending_memory_flush
2236                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
2237             }
2238           sched_analyze_insn (deps, PATTERN (insn), insn);
2239         }
2240       else if (CALL_P (insn))
2241         {
2242           int i;
2243
2244           CANT_MOVE (insn) = 1;
2245
2246           if (find_reg_note (insn, REG_SETJMP, NULL))
2247             {
2248               /* This is setjmp.  Assume that all registers, not just
2249                  hard registers, may be clobbered by this call.  */
2250               reg_pending_barrier = MOVE_BARRIER;
2251             }
2252           else
2253             {
2254               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2255                 /* A call may read and modify global register variables.  */
2256                 if (global_regs[i])
2257                   {
2258                     SET_REGNO_REG_SET (reg_pending_sets, i);
2259                     SET_REGNO_REG_SET (reg_pending_uses, i);
2260                   }
2261                 /* Other call-clobbered hard regs may be clobbered.
2262                    Since we only have a choice between 'might be clobbered'
2263                    and 'definitely not clobbered', we must include all
2264                    partly call-clobbered registers here.  */
2265                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
2266                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2267                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
2268                 /* We don't know what set of fixed registers might be used
2269                    by the function, but it is certain that the stack pointer
2270                    is among them, but be conservative.  */
2271                 else if (fixed_regs[i])
2272                   SET_REGNO_REG_SET (reg_pending_uses, i);
2273                 /* The frame pointer is normally not used by the function
2274                    itself, but by the debugger.  */
2275                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
2276                    in the macro expansion of jal but does not represent this
2277                    fact in the call_insn rtl.  */
2278                 else if (i == FRAME_POINTER_REGNUM
2279                          || (i == HARD_FRAME_POINTER_REGNUM
2280                              && (! reload_completed || frame_pointer_needed)))
2281                   SET_REGNO_REG_SET (reg_pending_uses, i);
2282             }
2283
2284           /* For each insn which shouldn't cross a call, add a dependence
2285              between that insn and this call insn.  */
2286           add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
2287                                         REG_DEP_ANTI);
2288
2289           sched_analyze_insn (deps, PATTERN (insn), insn);
2290
2291           /* In the absence of interprocedural alias analysis, we must flush
2292              all pending reads and writes, and start new dependencies starting
2293              from here.  But only flush writes for constant calls (which may
2294              be passed a pointer to something we haven't written yet).  */
2295           flush_pending_lists (deps, insn, true, 
2296                                ! RTL_CONST_OR_PURE_CALL_P (insn));
2297
2298           /* Remember the last function call for limiting lifetimes.  */
2299           free_INSN_LIST_list (&deps->last_function_call);
2300           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
2301
2302           /* Before reload, begin a post-call group, so as to keep the
2303              lifetimes of hard registers correct.  */
2304           if (! reload_completed)
2305             deps->in_post_call_group_p = post_call;
2306         }
2307
2308       /* EH_REGION insn notes can not appear until well after we complete
2309          scheduling.  */
2310       if (NOTE_P (insn))
2311         gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
2312                     && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
2313
2314       if (current_sched_info->use_cselib)
2315         cselib_process_insn (insn);
2316
2317       if (insn == tail)
2318         {
2319           if (current_sched_info->use_cselib)
2320             cselib_finish ();
2321           return;
2322         }
2323     }
2324   gcc_unreachable ();
2325 }
2326
2327 /* Helper for sched_free_deps ().
2328    Delete INSN's (RESOLVED_P) backward dependencies.  */
2329 static void
2330 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
2331 {
2332   sd_iterator_def sd_it;
2333   dep_t dep;
2334   sd_list_types_def types;
2335
2336   if (resolved_p)
2337     types = SD_LIST_RES_BACK;
2338   else
2339     types = SD_LIST_BACK;
2340
2341   for (sd_it = sd_iterator_start (insn, types);
2342        sd_iterator_cond (&sd_it, &dep);)
2343     {
2344       dep_link_t link = *sd_it.linkp;
2345       dep_node_t node = DEP_LINK_NODE (link);
2346       deps_list_t back_list;
2347       deps_list_t forw_list;
2348
2349       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
2350       remove_from_deps_list (link, back_list);
2351       delete_dep_node (node);
2352     }
2353 }
2354
2355 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
2356    deps_lists.  */
2357 void
2358 sched_free_deps (rtx head, rtx tail, bool resolved_p)
2359 {
2360   rtx insn;
2361   rtx next_tail = NEXT_INSN (tail);
2362
2363   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2364     if (INSN_P (insn) && INSN_LUID (insn) > 0)
2365       {
2366         /* Clear resolved back deps together with its dep_nodes.  */
2367         delete_dep_nodes_in_back_deps (insn, resolved_p);
2368
2369         /* Clear forward deps and leave the dep_nodes to the
2370            corresponding back_deps list.  */
2371         if (resolved_p)
2372           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
2373         else
2374           clear_deps_list (INSN_FORW_DEPS (insn));
2375
2376         sd_finish_insn (insn);
2377       }
2378 }
2379 \f
2380 /* Initialize variables for region data dependence analysis.
2381    n_bbs is the number of region blocks.  */
2382
2383 void
2384 init_deps (struct deps *deps)
2385 {
2386   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
2387
2388   deps->max_reg = max_reg;
2389   deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
2390   INIT_REG_SET (&deps->reg_last_in_use);
2391   INIT_REG_SET (&deps->reg_conditional_sets);
2392
2393   deps->pending_read_insns = 0;
2394   deps->pending_read_mems = 0;
2395   deps->pending_write_insns = 0;
2396   deps->pending_write_mems = 0;
2397   deps->pending_read_list_length = 0;
2398   deps->pending_write_list_length = 0;
2399   deps->pending_flush_length = 0;
2400   deps->last_pending_memory_flush = 0;
2401   deps->last_function_call = 0;
2402   deps->sched_before_next_call = 0;
2403   deps->in_post_call_group_p = not_post_call;
2404 }
2405
2406 /* Free insn lists found in DEPS.  */
2407
2408 void
2409 free_deps (struct deps *deps)
2410 {
2411   unsigned i;
2412   reg_set_iterator rsi;
2413
2414   free_INSN_LIST_list (&deps->pending_read_insns);
2415   free_EXPR_LIST_list (&deps->pending_read_mems);
2416   free_INSN_LIST_list (&deps->pending_write_insns);
2417   free_EXPR_LIST_list (&deps->pending_write_mems);
2418   free_INSN_LIST_list (&deps->last_pending_memory_flush);
2419
2420   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
2421      times.  For a testcase with 42000 regs and 8000 small basic blocks,
2422      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
2423   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2424     {
2425       struct deps_reg *reg_last = &deps->reg_last[i];
2426       if (reg_last->uses)
2427         free_INSN_LIST_list (&reg_last->uses);
2428       if (reg_last->sets)
2429         free_INSN_LIST_list (&reg_last->sets);
2430       if (reg_last->clobbers)
2431         free_INSN_LIST_list (&reg_last->clobbers);
2432     }
2433   CLEAR_REG_SET (&deps->reg_last_in_use);
2434   CLEAR_REG_SET (&deps->reg_conditional_sets);
2435
2436   free (deps->reg_last);
2437 }
2438
2439 /* If it is profitable to use them, initialize caches for tracking
2440    dependency information.  LUID is the number of insns to be scheduled,
2441    it is used in the estimate of profitability.  */
2442
2443 void
2444 init_dependency_caches (int luid)
2445 {
2446   /* Average number of insns in the basic block.
2447      '+ 1' is used to make it nonzero.  */
2448   int insns_in_block = luid / n_basic_blocks + 1;
2449
2450   /* ?!? We could save some memory by computing a per-region luid mapping
2451      which could reduce both the number of vectors in the cache and the size
2452      of each vector.  Instead we just avoid the cache entirely unless the
2453      average number of instructions in a basic block is very high.  See
2454      the comment before the declaration of true_dependency_cache for
2455      what we consider "very high".  */
2456   if (insns_in_block > 100 * 5)
2457     {
2458       cache_size = 0;
2459       extend_dependency_caches (luid, true);
2460     }
2461
2462   dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
2463                                /* Allocate lists for one block at a time.  */
2464                                insns_in_block);
2465
2466   dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
2467                                /* Allocate nodes for one block at a time.
2468                                   We assume that average insn has
2469                                   5 producers.  */
2470                                5 * insns_in_block);
2471 }
2472
2473 /* Create or extend (depending on CREATE_P) dependency caches to
2474    size N.  */
2475 void
2476 extend_dependency_caches (int n, bool create_p)
2477 {
2478   if (create_p || true_dependency_cache)
2479     {
2480       int i, luid = cache_size + n;
2481
2482       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
2483                                           luid);
2484       output_dependency_cache = XRESIZEVEC (bitmap_head,
2485                                             output_dependency_cache, luid);
2486       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
2487                                           luid);
2488
2489       if (current_sched_info->flags & DO_SPECULATION)
2490         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
2491                                             luid);
2492
2493       for (i = cache_size; i < luid; i++)
2494         {
2495           bitmap_initialize (&true_dependency_cache[i], 0);
2496           bitmap_initialize (&output_dependency_cache[i], 0);
2497           bitmap_initialize (&anti_dependency_cache[i], 0);
2498
2499           if (current_sched_info->flags & DO_SPECULATION)
2500             bitmap_initialize (&spec_dependency_cache[i], 0);
2501         }
2502       cache_size = luid;
2503     }
2504 }
2505
2506 /* Free the caches allocated in init_dependency_caches.  */
2507
2508 void
2509 free_dependency_caches (void)
2510 {
2511   gcc_assert (deps_pools_are_empty_p ());
2512   free_alloc_pool_if_empty (&dn_pool);
2513   free_alloc_pool_if_empty (&dl_pool);
2514   gcc_assert (dn_pool == NULL && dl_pool == NULL);
2515
2516   if (true_dependency_cache)
2517     {
2518       int i;
2519
2520       for (i = 0; i < cache_size; i++)
2521         {
2522           bitmap_clear (&true_dependency_cache[i]);
2523           bitmap_clear (&output_dependency_cache[i]);
2524           bitmap_clear (&anti_dependency_cache[i]);
2525
2526           if (current_sched_info->flags & DO_SPECULATION)
2527             bitmap_clear (&spec_dependency_cache[i]);
2528         }
2529       free (true_dependency_cache);
2530       true_dependency_cache = NULL;
2531       free (output_dependency_cache);
2532       output_dependency_cache = NULL;
2533       free (anti_dependency_cache);
2534       anti_dependency_cache = NULL;
2535
2536       if (current_sched_info->flags & DO_SPECULATION)
2537         {
2538           free (spec_dependency_cache);
2539           spec_dependency_cache = NULL;
2540         }
2541     }
2542 }
2543
2544 /* Initialize some global variables needed by the dependency analysis
2545    code.  */
2546
2547 void
2548 init_deps_global (void)
2549 {
2550   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
2551   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
2552   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
2553   reg_pending_barrier = NOT_A_BARRIER;
2554 }
2555
2556 /* Free everything used by the dependency analysis code.  */
2557
2558 void
2559 finish_deps_global (void)
2560 {
2561   FREE_REG_SET (reg_pending_sets);
2562   FREE_REG_SET (reg_pending_clobbers);
2563   FREE_REG_SET (reg_pending_uses);
2564 }
2565
2566 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
2567 static dw_t
2568 estimate_dep_weak (rtx mem1, rtx mem2)
2569 {
2570   rtx r1, r2;
2571
2572   if (mem1 == mem2)
2573     /* MEMs are the same - don't speculate.  */
2574     return MIN_DEP_WEAK;
2575
2576   r1 = XEXP (mem1, 0);
2577   r2 = XEXP (mem2, 0);
2578
2579   if (r1 == r2
2580       || (REG_P (r1) && REG_P (r2)
2581           && REGNO (r1) == REGNO (r2)))
2582     /* Again, MEMs are the same.  */
2583     return MIN_DEP_WEAK;
2584   else if ((REG_P (r1) && !REG_P (r2))
2585            || (!REG_P (r1) && REG_P (r2)))
2586     /* Different addressing modes - reason to be more speculative,
2587        than usual.  */
2588     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
2589   else
2590     /* We can't say anything about the dependence.  */
2591     return UNCERTAIN_DEP_WEAK;
2592 }
2593
2594 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
2595    This function can handle same INSN and ELEM (INSN == ELEM).
2596    It is a convenience wrapper.  */
2597 void
2598 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
2599 {
2600   dep_def _dep, *dep = &_dep;
2601
2602   init_dep (dep, elem, insn, dep_type);
2603   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
2604 }
2605
2606 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2607 static dw_t
2608 get_dep_weak_1 (ds_t ds, ds_t type)
2609 {
2610   ds = ds & type;
2611   switch (type)
2612     {
2613     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2614     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2615     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2616     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2617     default: gcc_unreachable ();
2618     }
2619
2620   return (dw_t) ds;
2621 }
2622
2623 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2624 dw_t
2625 get_dep_weak (ds_t ds, ds_t type)
2626 {
2627   dw_t dw = get_dep_weak_1 (ds, type);
2628
2629   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2630
2631   return dw;
2632 }
2633
2634 /* Return the dep_status, which has the same parameters as DS, except for
2635    speculative type TYPE, that will have weakness DW.  */
2636 ds_t
2637 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2638 {
2639   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2640
2641   ds &= ~type;
2642   switch (type)
2643     {
2644     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2645     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2646     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2647     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2648     default: gcc_unreachable ();
2649     }
2650   return ds;
2651 }
2652
2653 /* Return the join of two dep_statuses DS1 and DS2.  */
2654 ds_t
2655 ds_merge (ds_t ds1, ds_t ds2)
2656 {
2657   ds_t ds, t;
2658
2659   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2660
2661   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2662
2663   t = FIRST_SPEC_TYPE;
2664   do
2665     {
2666       if ((ds1 & t) && !(ds2 & t))
2667         ds |= ds1 & t;
2668       else if (!(ds1 & t) && (ds2 & t))
2669         ds |= ds2 & t;
2670       else if ((ds1 & t) && (ds2 & t))
2671         {
2672           ds_t dw;
2673
2674           dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2675           dw /= MAX_DEP_WEAK;
2676           if (dw < MIN_DEP_WEAK)
2677             dw = MIN_DEP_WEAK;
2678
2679           ds = set_dep_weak (ds, t, (dw_t) dw);
2680         }
2681
2682       if (t == LAST_SPEC_TYPE)
2683         break;
2684       t <<= SPEC_TYPE_SHIFT;
2685     }
2686   while (1);
2687
2688   return ds;
2689 }
2690
2691 /* Dump information about the dependence status S.  */
2692 static void
2693 dump_ds (FILE *f, ds_t s)
2694 {
2695   fprintf (f, "{");
2696
2697   if (s & BEGIN_DATA)
2698     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
2699   if (s & BE_IN_DATA)
2700     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
2701   if (s & BEGIN_CONTROL)
2702     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
2703   if (s & BE_IN_CONTROL)
2704     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
2705
2706   if (s & HARD_DEP)
2707     fprintf (f, "HARD_DEP; ");
2708
2709   if (s & DEP_TRUE)
2710     fprintf (f, "DEP_TRUE; ");
2711   if (s & DEP_ANTI)
2712     fprintf (f, "DEP_ANTI; ");
2713   if (s & DEP_OUTPUT)
2714     fprintf (f, "DEP_OUTPUT; ");
2715
2716   fprintf (f, "}");
2717 }
2718
2719 void
2720 debug_ds (ds_t s)
2721 {
2722   dump_ds (stderr, s);
2723   fprintf (stderr, "\n");
2724 }
2725
2726 #ifdef ENABLE_CHECKING
2727 /* Verify that dependence type and status are consistent.
2728    If RELAXED_P is true, then skip dep_weakness checks.  */
2729 static void
2730 check_dep (dep_t dep, bool relaxed_p)
2731 {
2732   enum reg_note dt = DEP_TYPE (dep);
2733   ds_t ds = DEP_STATUS (dep);
2734
2735   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
2736
2737   if (!(current_sched_info->flags & USE_DEPS_LIST))
2738     {
2739       gcc_assert (ds == -1);
2740       return;
2741     }
2742
2743   /* Check that dependence type contains the same bits as the status.  */
2744   if (dt == REG_DEP_TRUE)
2745     gcc_assert (ds & DEP_TRUE);
2746   else if (dt == REG_DEP_OUTPUT)
2747     gcc_assert ((ds & DEP_OUTPUT)
2748                 && !(ds & DEP_TRUE));    
2749   else 
2750     gcc_assert ((dt == REG_DEP_ANTI)
2751                 && (ds & DEP_ANTI)
2752                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2753
2754   /* HARD_DEP can not appear in dep_status of a link.  */
2755   gcc_assert (!(ds & HARD_DEP));          
2756
2757   /* Check that dependence status is set correctly when speculation is not
2758      supported.  */
2759   if (!(current_sched_info->flags & DO_SPECULATION))
2760     gcc_assert (!(ds & SPECULATIVE));
2761   else if (ds & SPECULATIVE)
2762     {
2763       if (!relaxed_p)
2764         {
2765           ds_t type = FIRST_SPEC_TYPE;
2766
2767           /* Check that dependence weakness is in proper range.  */
2768           do
2769             {
2770               if (ds & type)
2771                 get_dep_weak (ds, type);
2772
2773               if (type == LAST_SPEC_TYPE)
2774                 break;
2775               type <<= SPEC_TYPE_SHIFT;
2776             }
2777           while (1);
2778         }
2779
2780       if (ds & BEGIN_SPEC)
2781         {
2782           /* Only true dependence can be data speculative.  */
2783           if (ds & BEGIN_DATA)
2784             gcc_assert (ds & DEP_TRUE);
2785
2786           /* Control dependencies in the insn scheduler are represented by
2787              anti-dependencies, therefore only anti dependence can be
2788              control speculative.  */
2789           if (ds & BEGIN_CONTROL)
2790             gcc_assert (ds & DEP_ANTI);
2791         }
2792       else
2793         {
2794           /* Subsequent speculations should resolve true dependencies.  */
2795           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2796         }
2797           
2798       /* Check that true and anti dependencies can't have other speculative 
2799          statuses.  */
2800       if (ds & DEP_TRUE)
2801         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2802       /* An output dependence can't be speculative at all.  */
2803       gcc_assert (!(ds & DEP_OUTPUT));
2804       if (ds & DEP_ANTI)
2805         gcc_assert (ds & BEGIN_CONTROL);
2806     }
2807 }
2808 #endif /* ENABLE_CHECKING */
2809
2810 #endif /* INSN_SCHEDULING */