OSDN Git Service

b62797f6a563fda554ab7f9864e5d6e93364f37f
[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 we are currently in a libcall scheduling group, then mark the
2125      current insn as being in a scheduling group and that it can not
2126      be moved into a different basic block.  */
2127
2128   if (deps->libcall_block_tail_insn)
2129     {
2130       SCHED_GROUP_P (insn) = 1;
2131       CANT_MOVE (insn) = 1;
2132     }
2133
2134   /* If a post-call group is still open, see if it should remain so.
2135      This insn must be a simple move of a hard reg to a pseudo or
2136      vice-versa.
2137
2138      We must avoid moving these insns for correctness on
2139      SMALL_REGISTER_CLASS machines, and for special registers like
2140      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
2141      hard regs for all targets.  */
2142
2143   if (deps->in_post_call_group_p)
2144     {
2145       rtx tmp, set = single_set (insn);
2146       int src_regno, dest_regno;
2147
2148       if (set == NULL)
2149         goto end_call_group;
2150
2151       tmp = SET_DEST (set);
2152       if (GET_CODE (tmp) == SUBREG)
2153         tmp = SUBREG_REG (tmp);
2154       if (REG_P (tmp))
2155         dest_regno = REGNO (tmp);
2156       else
2157         goto end_call_group;
2158
2159       tmp = SET_SRC (set);
2160       if (GET_CODE (tmp) == SUBREG)
2161         tmp = SUBREG_REG (tmp);
2162       if ((GET_CODE (tmp) == PLUS
2163            || GET_CODE (tmp) == MINUS)
2164           && REG_P (XEXP (tmp, 0))
2165           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
2166           && dest_regno == STACK_POINTER_REGNUM)
2167         src_regno = STACK_POINTER_REGNUM;
2168       else if (REG_P (tmp))
2169         src_regno = REGNO (tmp);
2170       else
2171         goto end_call_group;
2172
2173       if (src_regno < FIRST_PSEUDO_REGISTER
2174           || dest_regno < FIRST_PSEUDO_REGISTER)
2175         {
2176           if (deps->in_post_call_group_p == post_call_initial)
2177             deps->in_post_call_group_p = post_call;
2178
2179           SCHED_GROUP_P (insn) = 1;
2180           CANT_MOVE (insn) = 1;
2181         }
2182       else
2183         {
2184         end_call_group:
2185           deps->in_post_call_group_p = not_post_call;
2186         }
2187     }
2188
2189   /* Fixup the dependencies in the sched group.  */
2190   if (SCHED_GROUP_P (insn))
2191     fixup_sched_groups (insn);
2192
2193   if ((current_sched_info->flags & DO_SPECULATION)
2194       && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
2195     /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
2196        be speculated.  */
2197     {
2198       sd_iterator_def sd_it;
2199       dep_t dep;
2200
2201       for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
2202            sd_iterator_cond (&sd_it, &dep);)
2203         change_spec_dep_to_hard (sd_it);
2204     }
2205 }
2206
2207 /* Analyze every insn between HEAD and TAIL inclusive, creating backward
2208    dependencies for each insn.  */
2209
2210 void
2211 sched_analyze (struct deps *deps, rtx head, rtx tail)
2212 {
2213   rtx insn;
2214
2215   if (current_sched_info->use_cselib)
2216     cselib_init (true);
2217
2218   /* Before reload, if the previous block ended in a call, show that
2219      we are inside a post-call group, so as to keep the lifetimes of
2220      hard registers correct.  */
2221   if (! reload_completed && !LABEL_P (head))
2222     {
2223       insn = prev_nonnote_insn (head);
2224       if (insn && CALL_P (insn))
2225         deps->in_post_call_group_p = post_call_initial;
2226     }
2227   for (insn = head;; insn = NEXT_INSN (insn))
2228     {
2229       rtx link, end_seq, r0, set;
2230
2231       if (INSN_P (insn))
2232         {
2233           /* And initialize deps_lists.  */
2234           sd_init_insn (insn);
2235         }
2236
2237       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
2238         {
2239           /* Make each JUMP_INSN a scheduling barrier for memory
2240              references.  */
2241           if (JUMP_P (insn))
2242             {
2243               /* Keep the list a reasonable size.  */
2244               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
2245                 flush_pending_lists (deps, insn, true, true);
2246               else
2247                 deps->last_pending_memory_flush
2248                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
2249             }
2250           sched_analyze_insn (deps, PATTERN (insn), insn);
2251         }
2252       else if (CALL_P (insn))
2253         {
2254           int i;
2255
2256           CANT_MOVE (insn) = 1;
2257
2258           if (find_reg_note (insn, REG_SETJMP, NULL))
2259             {
2260               /* This is setjmp.  Assume that all registers, not just
2261                  hard registers, may be clobbered by this call.  */
2262               reg_pending_barrier = MOVE_BARRIER;
2263             }
2264           else
2265             {
2266               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2267                 /* A call may read and modify global register variables.  */
2268                 if (global_regs[i])
2269                   {
2270                     SET_REGNO_REG_SET (reg_pending_sets, i);
2271                     SET_REGNO_REG_SET (reg_pending_uses, i);
2272                   }
2273                 /* Other call-clobbered hard regs may be clobbered.
2274                    Since we only have a choice between 'might be clobbered'
2275                    and 'definitely not clobbered', we must include all
2276                    partly call-clobbered registers here.  */
2277                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
2278                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2279                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
2280                 /* We don't know what set of fixed registers might be used
2281                    by the function, but it is certain that the stack pointer
2282                    is among them, but be conservative.  */
2283                 else if (fixed_regs[i])
2284                   SET_REGNO_REG_SET (reg_pending_uses, i);
2285                 /* The frame pointer is normally not used by the function
2286                    itself, but by the debugger.  */
2287                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
2288                    in the macro expansion of jal but does not represent this
2289                    fact in the call_insn rtl.  */
2290                 else if (i == FRAME_POINTER_REGNUM
2291                          || (i == HARD_FRAME_POINTER_REGNUM
2292                              && (! reload_completed || frame_pointer_needed)))
2293                   SET_REGNO_REG_SET (reg_pending_uses, i);
2294             }
2295
2296           /* For each insn which shouldn't cross a call, add a dependence
2297              between that insn and this call insn.  */
2298           add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
2299                                         REG_DEP_ANTI);
2300
2301           sched_analyze_insn (deps, PATTERN (insn), insn);
2302
2303           /* In the absence of interprocedural alias analysis, we must flush
2304              all pending reads and writes, and start new dependencies starting
2305              from here.  But only flush writes for constant calls (which may
2306              be passed a pointer to something we haven't written yet).  */
2307           flush_pending_lists (deps, insn, true, 
2308                                ! RTL_CONST_OR_PURE_CALL_P (insn));
2309
2310           /* Remember the last function call for limiting lifetimes.  */
2311           free_INSN_LIST_list (&deps->last_function_call);
2312           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
2313
2314           /* Before reload, begin a post-call group, so as to keep the
2315              lifetimes of hard registers correct.  */
2316           if (! reload_completed)
2317             deps->in_post_call_group_p = post_call;
2318         }
2319
2320       /* EH_REGION insn notes can not appear until well after we complete
2321          scheduling.  */
2322       if (NOTE_P (insn))
2323         gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
2324                     && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
2325
2326       if (current_sched_info->use_cselib)
2327         cselib_process_insn (insn);
2328
2329       /* Now that we have completed handling INSN, check and see if it is
2330          a CLOBBER beginning a libcall block.   If it is, record the
2331          end of the libcall sequence.
2332
2333          We want to schedule libcall blocks as a unit before reload.  While
2334          this restricts scheduling, it preserves the meaning of a libcall
2335          block.
2336
2337          As a side effect, we may get better code due to decreased register
2338          pressure as well as less chance of a foreign insn appearing in
2339          a libcall block.  */
2340       if (!reload_completed
2341           /* Note we may have nested libcall sequences.  We only care about
2342              the outermost libcall sequence.  */
2343           && deps->libcall_block_tail_insn == 0
2344           /* The sequence must start with a clobber of a register.  */
2345           && NONJUMP_INSN_P (insn)
2346           && GET_CODE (PATTERN (insn)) == CLOBBER
2347           && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
2348           && REG_P (XEXP (PATTERN (insn), 0))
2349           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
2350           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
2351           && (end_seq = XEXP (link, 0)) != 0
2352           /* The insn referenced by the REG_LIBCALL note must be a
2353              simple nop copy with the same destination as the register
2354              mentioned in the clobber.  */
2355           && (set = single_set (end_seq)) != 0
2356           && SET_DEST (set) == r0 && SET_SRC (set) == r0
2357           /* And finally the insn referenced by the REG_LIBCALL must
2358              also contain a REG_EQUAL note and a REG_RETVAL note.  */
2359           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
2360           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
2361         deps->libcall_block_tail_insn = XEXP (link, 0);
2362
2363       /* If we have reached the end of a libcall block, then close the
2364          block.  */
2365       if (deps->libcall_block_tail_insn == insn)
2366         deps->libcall_block_tail_insn = 0;
2367
2368       if (insn == tail)
2369         {
2370           if (current_sched_info->use_cselib)
2371             cselib_finish ();
2372           return;
2373         }
2374     }
2375   gcc_unreachable ();
2376 }
2377
2378 /* Helper for sched_free_deps ().
2379    Delete INSN's (RESOLVED_P) backward dependencies.  */
2380 static void
2381 delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
2382 {
2383   sd_iterator_def sd_it;
2384   dep_t dep;
2385   sd_list_types_def types;
2386
2387   if (resolved_p)
2388     types = SD_LIST_RES_BACK;
2389   else
2390     types = SD_LIST_BACK;
2391
2392   for (sd_it = sd_iterator_start (insn, types);
2393        sd_iterator_cond (&sd_it, &dep);)
2394     {
2395       dep_link_t link = *sd_it.linkp;
2396       dep_node_t node = DEP_LINK_NODE (link);
2397       deps_list_t back_list;
2398       deps_list_t forw_list;
2399
2400       get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
2401       remove_from_deps_list (link, back_list);
2402       delete_dep_node (node);
2403     }
2404 }
2405
2406 /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
2407    deps_lists.  */
2408 void
2409 sched_free_deps (rtx head, rtx tail, bool resolved_p)
2410 {
2411   rtx insn;
2412   rtx next_tail = NEXT_INSN (tail);
2413
2414   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2415     if (INSN_P (insn) && INSN_LUID (insn) > 0)
2416       {
2417         /* Clear resolved back deps together with its dep_nodes.  */
2418         delete_dep_nodes_in_back_deps (insn, resolved_p);
2419
2420         /* Clear forward deps and leave the dep_nodes to the
2421            corresponding back_deps list.  */
2422         if (resolved_p)
2423           clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
2424         else
2425           clear_deps_list (INSN_FORW_DEPS (insn));
2426
2427         sd_finish_insn (insn);
2428       }
2429 }
2430 \f
2431 /* Initialize variables for region data dependence analysis.
2432    n_bbs is the number of region blocks.  */
2433
2434 void
2435 init_deps (struct deps *deps)
2436 {
2437   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
2438
2439   deps->max_reg = max_reg;
2440   deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
2441   INIT_REG_SET (&deps->reg_last_in_use);
2442   INIT_REG_SET (&deps->reg_conditional_sets);
2443
2444   deps->pending_read_insns = 0;
2445   deps->pending_read_mems = 0;
2446   deps->pending_write_insns = 0;
2447   deps->pending_write_mems = 0;
2448   deps->pending_read_list_length = 0;
2449   deps->pending_write_list_length = 0;
2450   deps->pending_flush_length = 0;
2451   deps->last_pending_memory_flush = 0;
2452   deps->last_function_call = 0;
2453   deps->sched_before_next_call = 0;
2454   deps->in_post_call_group_p = not_post_call;
2455   deps->libcall_block_tail_insn = 0;
2456 }
2457
2458 /* Free insn lists found in DEPS.  */
2459
2460 void
2461 free_deps (struct deps *deps)
2462 {
2463   unsigned i;
2464   reg_set_iterator rsi;
2465
2466   free_INSN_LIST_list (&deps->pending_read_insns);
2467   free_EXPR_LIST_list (&deps->pending_read_mems);
2468   free_INSN_LIST_list (&deps->pending_write_insns);
2469   free_EXPR_LIST_list (&deps->pending_write_mems);
2470   free_INSN_LIST_list (&deps->last_pending_memory_flush);
2471
2472   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
2473      times.  For a testcase with 42000 regs and 8000 small basic blocks,
2474      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
2475   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
2476     {
2477       struct deps_reg *reg_last = &deps->reg_last[i];
2478       if (reg_last->uses)
2479         free_INSN_LIST_list (&reg_last->uses);
2480       if (reg_last->sets)
2481         free_INSN_LIST_list (&reg_last->sets);
2482       if (reg_last->clobbers)
2483         free_INSN_LIST_list (&reg_last->clobbers);
2484     }
2485   CLEAR_REG_SET (&deps->reg_last_in_use);
2486   CLEAR_REG_SET (&deps->reg_conditional_sets);
2487
2488   free (deps->reg_last);
2489 }
2490
2491 /* If it is profitable to use them, initialize caches for tracking
2492    dependency information.  LUID is the number of insns to be scheduled,
2493    it is used in the estimate of profitability.  */
2494
2495 void
2496 init_dependency_caches (int luid)
2497 {
2498   /* Average number of insns in the basic block.
2499      '+ 1' is used to make it nonzero.  */
2500   int insns_in_block = luid / n_basic_blocks + 1;
2501
2502   /* ?!? We could save some memory by computing a per-region luid mapping
2503      which could reduce both the number of vectors in the cache and the size
2504      of each vector.  Instead we just avoid the cache entirely unless the
2505      average number of instructions in a basic block is very high.  See
2506      the comment before the declaration of true_dependency_cache for
2507      what we consider "very high".  */
2508   if (insns_in_block > 100 * 5)
2509     {
2510       cache_size = 0;
2511       extend_dependency_caches (luid, true);
2512     }
2513
2514   dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
2515                                /* Allocate lists for one block at a time.  */
2516                                insns_in_block);
2517
2518   dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
2519                                /* Allocate nodes for one block at a time.
2520                                   We assume that average insn has
2521                                   5 producers.  */
2522                                5 * insns_in_block);
2523 }
2524
2525 /* Create or extend (depending on CREATE_P) dependency caches to
2526    size N.  */
2527 void
2528 extend_dependency_caches (int n, bool create_p)
2529 {
2530   if (create_p || true_dependency_cache)
2531     {
2532       int i, luid = cache_size + n;
2533
2534       true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
2535                                           luid);
2536       output_dependency_cache = XRESIZEVEC (bitmap_head,
2537                                             output_dependency_cache, luid);
2538       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
2539                                           luid);
2540
2541       if (current_sched_info->flags & DO_SPECULATION)
2542         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
2543                                             luid);
2544
2545       for (i = cache_size; i < luid; i++)
2546         {
2547           bitmap_initialize (&true_dependency_cache[i], 0);
2548           bitmap_initialize (&output_dependency_cache[i], 0);
2549           bitmap_initialize (&anti_dependency_cache[i], 0);
2550
2551           if (current_sched_info->flags & DO_SPECULATION)
2552             bitmap_initialize (&spec_dependency_cache[i], 0);
2553         }
2554       cache_size = luid;
2555     }
2556 }
2557
2558 /* Free the caches allocated in init_dependency_caches.  */
2559
2560 void
2561 free_dependency_caches (void)
2562 {
2563   gcc_assert (deps_pools_are_empty_p ());
2564   free_alloc_pool_if_empty (&dn_pool);
2565   free_alloc_pool_if_empty (&dl_pool);
2566   gcc_assert (dn_pool == NULL && dl_pool == NULL);
2567
2568   if (true_dependency_cache)
2569     {
2570       int i;
2571
2572       for (i = 0; i < cache_size; i++)
2573         {
2574           bitmap_clear (&true_dependency_cache[i]);
2575           bitmap_clear (&output_dependency_cache[i]);
2576           bitmap_clear (&anti_dependency_cache[i]);
2577
2578           if (current_sched_info->flags & DO_SPECULATION)
2579             bitmap_clear (&spec_dependency_cache[i]);
2580         }
2581       free (true_dependency_cache);
2582       true_dependency_cache = NULL;
2583       free (output_dependency_cache);
2584       output_dependency_cache = NULL;
2585       free (anti_dependency_cache);
2586       anti_dependency_cache = NULL;
2587
2588       if (current_sched_info->flags & DO_SPECULATION)
2589         {
2590           free (spec_dependency_cache);
2591           spec_dependency_cache = NULL;
2592         }
2593     }
2594 }
2595
2596 /* Initialize some global variables needed by the dependency analysis
2597    code.  */
2598
2599 void
2600 init_deps_global (void)
2601 {
2602   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
2603   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
2604   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
2605   reg_pending_barrier = NOT_A_BARRIER;
2606 }
2607
2608 /* Free everything used by the dependency analysis code.  */
2609
2610 void
2611 finish_deps_global (void)
2612 {
2613   FREE_REG_SET (reg_pending_sets);
2614   FREE_REG_SET (reg_pending_clobbers);
2615   FREE_REG_SET (reg_pending_uses);
2616 }
2617
2618 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
2619 static dw_t
2620 estimate_dep_weak (rtx mem1, rtx mem2)
2621 {
2622   rtx r1, r2;
2623
2624   if (mem1 == mem2)
2625     /* MEMs are the same - don't speculate.  */
2626     return MIN_DEP_WEAK;
2627
2628   r1 = XEXP (mem1, 0);
2629   r2 = XEXP (mem2, 0);
2630
2631   if (r1 == r2
2632       || (REG_P (r1) && REG_P (r2)
2633           && REGNO (r1) == REGNO (r2)))
2634     /* Again, MEMs are the same.  */
2635     return MIN_DEP_WEAK;
2636   else if ((REG_P (r1) && !REG_P (r2))
2637            || (!REG_P (r1) && REG_P (r2)))
2638     /* Different addressing modes - reason to be more speculative,
2639        than usual.  */
2640     return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
2641   else
2642     /* We can't say anything about the dependence.  */
2643     return UNCERTAIN_DEP_WEAK;
2644 }
2645
2646 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
2647    This function can handle same INSN and ELEM (INSN == ELEM).
2648    It is a convenience wrapper.  */
2649 void
2650 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
2651 {
2652   dep_def _dep, *dep = &_dep;
2653
2654   init_dep (dep, elem, insn, dep_type);
2655   maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
2656 }
2657
2658 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2659 static dw_t
2660 get_dep_weak_1 (ds_t ds, ds_t type)
2661 {
2662   ds = ds & type;
2663   switch (type)
2664     {
2665     case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2666     case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2667     case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2668     case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2669     default: gcc_unreachable ();
2670     }
2671
2672   return (dw_t) ds;
2673 }
2674
2675 /* Return weakness of speculative type TYPE in the dep_status DS.  */
2676 dw_t
2677 get_dep_weak (ds_t ds, ds_t type)
2678 {
2679   dw_t dw = get_dep_weak_1 (ds, type);
2680
2681   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2682
2683   return dw;
2684 }
2685
2686 /* Return the dep_status, which has the same parameters as DS, except for
2687    speculative type TYPE, that will have weakness DW.  */
2688 ds_t
2689 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2690 {
2691   gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2692
2693   ds &= ~type;
2694   switch (type)
2695     {
2696     case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2697     case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2698     case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2699     case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2700     default: gcc_unreachable ();
2701     }
2702   return ds;
2703 }
2704
2705 /* Return the join of two dep_statuses DS1 and DS2.  */
2706 ds_t
2707 ds_merge (ds_t ds1, ds_t ds2)
2708 {
2709   ds_t ds, t;
2710
2711   gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2712
2713   ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2714
2715   t = FIRST_SPEC_TYPE;
2716   do
2717     {
2718       if ((ds1 & t) && !(ds2 & t))
2719         ds |= ds1 & t;
2720       else if (!(ds1 & t) && (ds2 & t))
2721         ds |= ds2 & t;
2722       else if ((ds1 & t) && (ds2 & t))
2723         {
2724           ds_t dw;
2725
2726           dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2727           dw /= MAX_DEP_WEAK;
2728           if (dw < MIN_DEP_WEAK)
2729             dw = MIN_DEP_WEAK;
2730
2731           ds = set_dep_weak (ds, t, (dw_t) dw);
2732         }
2733
2734       if (t == LAST_SPEC_TYPE)
2735         break;
2736       t <<= SPEC_TYPE_SHIFT;
2737     }
2738   while (1);
2739
2740   return ds;
2741 }
2742
2743 /* Dump information about the dependence status S.  */
2744 static void
2745 dump_ds (FILE *f, ds_t s)
2746 {
2747   fprintf (f, "{");
2748
2749   if (s & BEGIN_DATA)
2750     fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
2751   if (s & BE_IN_DATA)
2752     fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
2753   if (s & BEGIN_CONTROL)
2754     fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
2755   if (s & BE_IN_CONTROL)
2756     fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
2757
2758   if (s & HARD_DEP)
2759     fprintf (f, "HARD_DEP; ");
2760
2761   if (s & DEP_TRUE)
2762     fprintf (f, "DEP_TRUE; ");
2763   if (s & DEP_ANTI)
2764     fprintf (f, "DEP_ANTI; ");
2765   if (s & DEP_OUTPUT)
2766     fprintf (f, "DEP_OUTPUT; ");
2767
2768   fprintf (f, "}");
2769 }
2770
2771 void
2772 debug_ds (ds_t s)
2773 {
2774   dump_ds (stderr, s);
2775   fprintf (stderr, "\n");
2776 }
2777
2778 #ifdef ENABLE_CHECKING
2779 /* Verify that dependence type and status are consistent.
2780    If RELAXED_P is true, then skip dep_weakness checks.  */
2781 static void
2782 check_dep (dep_t dep, bool relaxed_p)
2783 {
2784   enum reg_note dt = DEP_TYPE (dep);
2785   ds_t ds = DEP_STATUS (dep);
2786
2787   gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
2788
2789   if (!(current_sched_info->flags & USE_DEPS_LIST))
2790     {
2791       gcc_assert (ds == -1);
2792       return;
2793     }
2794
2795   /* Check that dependence type contains the same bits as the status.  */
2796   if (dt == REG_DEP_TRUE)
2797     gcc_assert (ds & DEP_TRUE);
2798   else if (dt == REG_DEP_OUTPUT)
2799     gcc_assert ((ds & DEP_OUTPUT)
2800                 && !(ds & DEP_TRUE));    
2801   else 
2802     gcc_assert ((dt == REG_DEP_ANTI)
2803                 && (ds & DEP_ANTI)
2804                 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2805
2806   /* HARD_DEP can not appear in dep_status of a link.  */
2807   gcc_assert (!(ds & HARD_DEP));          
2808
2809   /* Check that dependence status is set correctly when speculation is not
2810      supported.  */
2811   if (!(current_sched_info->flags & DO_SPECULATION))
2812     gcc_assert (!(ds & SPECULATIVE));
2813   else if (ds & SPECULATIVE)
2814     {
2815       if (!relaxed_p)
2816         {
2817           ds_t type = FIRST_SPEC_TYPE;
2818
2819           /* Check that dependence weakness is in proper range.  */
2820           do
2821             {
2822               if (ds & type)
2823                 get_dep_weak (ds, type);
2824
2825               if (type == LAST_SPEC_TYPE)
2826                 break;
2827               type <<= SPEC_TYPE_SHIFT;
2828             }
2829           while (1);
2830         }
2831
2832       if (ds & BEGIN_SPEC)
2833         {
2834           /* Only true dependence can be data speculative.  */
2835           if (ds & BEGIN_DATA)
2836             gcc_assert (ds & DEP_TRUE);
2837
2838           /* Control dependencies in the insn scheduler are represented by
2839              anti-dependencies, therefore only anti dependence can be
2840              control speculative.  */
2841           if (ds & BEGIN_CONTROL)
2842             gcc_assert (ds & DEP_ANTI);
2843         }
2844       else
2845         {
2846           /* Subsequent speculations should resolve true dependencies.  */
2847           gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2848         }
2849           
2850       /* Check that true and anti dependencies can't have other speculative 
2851          statuses.  */
2852       if (ds & DEP_TRUE)
2853         gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2854       /* An output dependence can't be speculative at all.  */
2855       gcc_assert (!(ds & DEP_OUTPUT));
2856       if (ds & DEP_ANTI)
2857         gcc_assert (ds & BEGIN_CONTROL);
2858     }
2859 }
2860 #endif /* ENABLE_CHECKING */
2861
2862 #endif /* INSN_SCHEDULING */