OSDN Git Service

PR debug/25023
[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 Free Software Foundation, Inc.
5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING.  If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 02110-1301, USA.  */
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 #include "df.h"
45
46
47 static regset reg_pending_sets;
48 static regset reg_pending_clobbers;
49 static regset reg_pending_uses;
50
51 /* The following enumeration values tell us what dependencies we
52    should use to implement the barrier.  We use true-dependencies for
53    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
54 enum reg_pending_barrier_mode
55 {
56   NOT_A_BARRIER = 0,
57   MOVE_BARRIER,
58   TRUE_BARRIER
59 };
60
61 static enum reg_pending_barrier_mode reg_pending_barrier;
62
63 /* To speed up the test for duplicate dependency links we keep a
64    record of dependencies created by add_dependence when the average
65    number of instructions in a basic block is very large.
66
67    Studies have shown that there is typically around 5 instructions between
68    branches for typical C code.  So we can make a guess that the average
69    basic block is approximately 5 instructions long; we will choose 100X
70    the average size as a very large basic block.
71
72    Each insn has associated bitmaps for its dependencies.  Each bitmap
73    has enough entries to represent a dependency on any other insn in
74    the insn chain.  All bitmap for true dependencies cache is
75    allocated then the rest two ones are also allocated.  */
76 static bitmap_head *true_dependency_cache;
77 static bitmap_head *anti_dependency_cache;
78 static bitmap_head *output_dependency_cache;
79 static int cache_size;
80
81 /* To speed up checking consistency of formed forward insn
82    dependencies we use the following cache.  Another possible solution
83    could be switching off checking duplication of insns in forward
84    dependencies.  */
85 #ifdef ENABLE_CHECKING
86 static bitmap_head *forward_dependency_cache;
87 #endif
88
89 static int deps_may_trap_p (rtx);
90 static void add_dependence_list (rtx, rtx, int, enum reg_note);
91 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
92 static void delete_all_dependences (rtx);
93 static void fixup_sched_groups (rtx);
94
95 static void flush_pending_lists (struct deps *, rtx, int, int);
96 static void sched_analyze_1 (struct deps *, rtx, rtx);
97 static void sched_analyze_2 (struct deps *, rtx, rtx);
98 static void sched_analyze_insn (struct deps *, rtx, rtx, rtx);
99
100 static rtx sched_get_condition (rtx);
101 static int conditions_mutex_p (rtx, rtx);
102 \f
103 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
104
105 static int
106 deps_may_trap_p (rtx mem)
107 {
108   rtx addr = XEXP (mem, 0);
109
110   if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
111     {
112       rtx t = get_reg_known_value (REGNO (addr));
113       if (t)
114         addr = t;
115     }
116   return rtx_addr_can_trap_p (addr);
117 }
118 \f
119 /* Return the INSN_LIST containing INSN in LIST, or NULL
120    if LIST does not contain INSN.  */
121
122 rtx
123 find_insn_list (rtx insn, rtx list)
124 {
125   while (list)
126     {
127       if (XEXP (list, 0) == insn)
128         return list;
129       list = XEXP (list, 1);
130     }
131   return 0;
132 }
133 \f
134 /* Find the condition under which INSN is executed.  */
135
136 static rtx
137 sched_get_condition (rtx insn)
138 {
139   rtx pat = PATTERN (insn);
140   rtx src;
141
142   if (pat == 0)
143     return 0;
144
145   if (GET_CODE (pat) == COND_EXEC)
146     return COND_EXEC_TEST (pat);
147
148   if (!any_condjump_p (insn) || !onlyjump_p (insn))
149     return 0;
150
151   src = SET_SRC (pc_set (insn));
152
153   if (XEXP (src, 2) == pc_rtx)
154     return XEXP (src, 0);
155   else if (XEXP (src, 1) == pc_rtx)
156     {
157       rtx cond = XEXP (src, 0);
158       enum rtx_code revcode = reversed_comparison_code (cond, insn);
159
160       if (revcode == UNKNOWN)
161         return 0;
162       return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
163                              XEXP (cond, 1));
164     }
165
166   return 0;
167 }
168
169 \f
170 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
171
172 static int
173 conditions_mutex_p (rtx cond1, rtx cond2)
174 {
175   if (COMPARISON_P (cond1)
176       && COMPARISON_P (cond2)
177       && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
178       && XEXP (cond1, 0) == XEXP (cond2, 0)
179       && XEXP (cond1, 1) == XEXP (cond2, 1))
180     return 1;
181   return 0;
182 }
183
184 /* Return true if insn1 and insn2 can never depend on one another because
185    the conditions under which they are executed are mutually exclusive.  */
186 bool
187 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
188 {
189   rtx cond1, cond2;
190
191   /* flow.c doesn't handle conditional lifetimes entirely correctly;
192      calls mess up the conditional lifetimes.  */
193   if (!CALL_P (insn1) && !CALL_P (insn2))
194     {
195       cond1 = sched_get_condition (insn1);
196       cond2 = sched_get_condition (insn2);
197       if (cond1 && cond2
198           && conditions_mutex_p (cond1, cond2)
199           /* Make sure first instruction doesn't affect condition of second
200              instruction if switched.  */
201           && !modified_in_p (cond1, insn2)
202           /* Make sure second instruction doesn't affect condition of first
203              instruction if switched.  */
204           && !modified_in_p (cond2, insn1))
205         return true;
206     }
207   return false;
208 }
209 \f
210 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
211    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the
212    type of dependence that this link represents.  The function returns
213    nonzero if a new entry has been added to insn's LOG_LINK.  */
214
215 int
216 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
217 {
218   rtx link;
219   int present_p;
220
221   /* Don't depend an insn on itself.  */
222   if (insn == elem)
223     return 0;
224
225   /* We can get a dependency on deleted insns due to optimizations in
226      the register allocation and reloading or due to splitting.  Any
227      such dependency is useless and can be ignored.  */
228   if (NOTE_P (elem))
229     return 0;
230
231   present_p = 1;
232 #ifdef INSN_SCHEDULING
233   /* ??? No good way to tell from here whether we're doing interblock
234      scheduling.  Possibly add another callback.  */
235 #if 0
236   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
237      No need for interblock dependences with calls, since
238      calls are not moved between blocks.   Note: the edge where
239      elem is a CALL is still required.  */
240   if (CALL_P (insn)
241       && (INSN_BB (elem) != INSN_BB (insn)))
242     return 0;
243 #endif
244
245   /* If we already have a dependency for ELEM, then we do not need to
246      do anything.  Avoiding the list walk below can cut compile times
247      dramatically for some code.  */
248   if (true_dependency_cache != NULL)
249     {
250       enum reg_note present_dep_type = 0;
251
252       gcc_assert (anti_dependency_cache);
253       gcc_assert (output_dependency_cache);
254       if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
255                         INSN_LUID (elem)))
256         /* Do nothing (present_set_type is already 0).  */
257         ;
258       else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
259                          INSN_LUID (elem)))
260         present_dep_type = REG_DEP_ANTI;
261       else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
262                          INSN_LUID (elem)))
263         present_dep_type = REG_DEP_OUTPUT;
264       else
265         present_p = 0;
266       if (present_p && (int) dep_type >= (int) present_dep_type)
267         return 0;
268     }
269 #endif
270
271   /* Check that we don't already have this dependence.  */
272   if (present_p)
273     for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
274       if (XEXP (link, 0) == elem)
275         {
276 #ifdef INSN_SCHEDULING
277           /* Clear corresponding cache entry because type of the link
278              may be changed.  */
279           if (true_dependency_cache != NULL)
280             {
281               enum reg_note kind = REG_NOTE_KIND (link);
282               switch (kind)
283                 {
284                 case REG_DEP_ANTI:
285                   bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
286                                     INSN_LUID (elem));
287                   break;
288                 case REG_DEP_OUTPUT:
289                   gcc_assert (output_dependency_cache);
290                   bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
291                                     INSN_LUID (elem));
292                   break;
293                 default:
294                   gcc_unreachable ();
295                 }
296             }
297 #endif
298
299           /* If this is a more restrictive type of dependence than the existing
300              one, then change the existing dependence to this type.  */
301           if ((int) dep_type < (int) REG_NOTE_KIND (link))
302             PUT_REG_NOTE_KIND (link, dep_type);
303
304 #ifdef INSN_SCHEDULING
305           /* If we are adding a dependency to INSN's LOG_LINKs, then
306              note that in the bitmap caches of dependency information.  */
307           if (true_dependency_cache != NULL)
308             {
309               if ((int) REG_NOTE_KIND (link) == 0)
310                 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
311                                 INSN_LUID (elem));
312               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
313                 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
314                                 INSN_LUID (elem));
315               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
316                 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
317                                 INSN_LUID (elem));
318             }
319 #endif
320           return 0;
321         }
322   /* Might want to check one level of transitivity to save conses.  */
323
324   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
325   LOG_LINKS (insn) = link;
326
327   /* Insn dependency, not data dependency.  */
328   PUT_REG_NOTE_KIND (link, dep_type);
329
330 #ifdef INSN_SCHEDULING
331   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
332      in the bitmap caches of dependency information.  */
333   if (true_dependency_cache != NULL)
334     {
335       if ((int) dep_type == 0)
336         bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
337       else if (dep_type == REG_DEP_ANTI)
338         bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
339       else if (dep_type == REG_DEP_OUTPUT)
340         bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
341     }
342 #endif
343   return 1;
344 }
345
346 /* A convenience wrapper to operate on an entire list.  */
347
348 static void
349 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
350 {
351   for (; list; list = XEXP (list, 1))
352     {
353       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
354         add_dependence (insn, XEXP (list, 0), dep_type);
355     }
356 }
357
358 /* Similar, but free *LISTP at the same time.  */
359
360 static void
361 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
362                               enum reg_note dep_type)
363 {
364   rtx list, next;
365   for (list = *listp, *listp = NULL; list ; list = next)
366     {
367       next = XEXP (list, 1);
368       if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
369         add_dependence (insn, XEXP (list, 0), dep_type);
370       free_INSN_LIST_node (list);
371     }
372 }
373
374 /* Clear all dependencies for an insn.  */
375
376 static void
377 delete_all_dependences (rtx insn)
378 {
379   /* Clear caches, if they exist, as well as free the dependence.  */
380
381 #ifdef INSN_SCHEDULING
382   if (true_dependency_cache != NULL)
383     {
384       bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
385       bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
386       bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
387     }
388 #endif
389
390   free_INSN_LIST_list (&LOG_LINKS (insn));
391 }
392
393 /* All insns in a scheduling group except the first should only have
394    dependencies on the previous insn in the group.  So we find the
395    first instruction in the scheduling group by walking the dependence
396    chains backwards. Then we add the dependencies for the group to
397    the previous nonnote insn.  */
398
399 static void
400 fixup_sched_groups (rtx insn)
401 {
402   rtx link, prev_nonnote;
403
404   for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
405     {
406       rtx i = insn;
407       do
408         {
409           i = prev_nonnote_insn (i);
410
411           if (XEXP (link, 0) == i)
412             goto next_link;
413         } while (SCHED_GROUP_P (i));
414       if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
415         add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
416     next_link:;
417     }
418
419   delete_all_dependences (insn);
420
421   prev_nonnote = prev_nonnote_insn (insn);
422   if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
423       && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
424     add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
425 }
426 \f
427 /* Process an insn's memory dependencies.  There are four kinds of
428    dependencies:
429
430    (0) read dependence: read follows read
431    (1) true dependence: read follows write
432    (2) anti dependence: write follows read
433    (3) output dependence: write follows write
434
435    We are careful to build only dependencies which actually exist, and
436    use transitivity to avoid building too many links.  */
437
438 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
439    The MEM is a memory reference contained within INSN, which we are saving
440    so that we can do memory aliasing on it.  */
441
442 static void
443 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
444                          rtx insn, rtx mem)
445 {
446   rtx link;
447
448   link = alloc_INSN_LIST (insn, *insn_list);
449   *insn_list = link;
450
451   if (current_sched_info->use_cselib)
452     {
453       mem = shallow_copy_rtx (mem);
454       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
455     }
456   link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
457   *mem_list = link;
458
459   deps->pending_lists_length++;
460 }
461
462 /* Make a dependency between every memory reference on the pending lists
463    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
464    dependencies for a read operation, similarly with FOR_WRITE.  */
465
466 static void
467 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
468                      int for_write)
469 {
470   if (for_write)
471     {
472       add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
473                                     REG_DEP_ANTI);
474       free_EXPR_LIST_list (&deps->pending_read_mems);
475     }
476
477   add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
478                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
479   free_EXPR_LIST_list (&deps->pending_write_mems);
480   deps->pending_lists_length = 0;
481
482   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
483                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
484   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
485   deps->pending_flush_length = 1;
486 }
487 \f
488 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
489    rtx, X, creating all dependencies generated by the write to the
490    destination of X, and reads of everything mentioned.  */
491
492 static void
493 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
494 {
495   int regno;
496   rtx dest = XEXP (x, 0);
497   enum rtx_code code = GET_CODE (x);
498
499   if (dest == 0)
500     return;
501
502   if (GET_CODE (dest) == PARALLEL)
503     {
504       int i;
505
506       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
507         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
508           sched_analyze_1 (deps,
509                            gen_rtx_CLOBBER (VOIDmode,
510                                             XEXP (XVECEXP (dest, 0, i), 0)),
511                            insn);
512
513       if (GET_CODE (x) == SET)
514         sched_analyze_2 (deps, SET_SRC (x), insn);
515       return;
516     }
517
518   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
519          || GET_CODE (dest) == ZERO_EXTRACT)
520     {
521       if (GET_CODE (dest) == STRICT_LOW_PART
522          || GET_CODE (dest) == ZERO_EXTRACT
523          || read_modify_subreg_p (dest))
524         {
525           /* These both read and modify the result.  We must handle
526              them as writes to get proper dependencies for following
527              instructions.  We must handle them as reads to get proper
528              dependencies from this to previous instructions.
529              Thus we need to call sched_analyze_2.  */
530
531           sched_analyze_2 (deps, XEXP (dest, 0), insn);
532         }
533       if (GET_CODE (dest) == ZERO_EXTRACT)
534         {
535           /* The second and third arguments are values read by this insn.  */
536           sched_analyze_2 (deps, XEXP (dest, 1), insn);
537           sched_analyze_2 (deps, XEXP (dest, 2), insn);
538         }
539       dest = XEXP (dest, 0);
540     }
541
542   if (REG_P (dest))
543     {
544       regno = REGNO (dest);
545
546 #ifdef STACK_REGS
547       /* Treat all writes to a stack register as modifying the TOS.  */
548       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
549         {
550           SET_REGNO_REG_SET (reg_pending_uses, FIRST_STACK_REG);
551           regno = FIRST_STACK_REG;
552         }
553 #endif
554
555       /* A hard reg in a wide mode may really be multiple registers.
556          If so, mark all of them just like the first.  */
557       if (regno < FIRST_PSEUDO_REGISTER)
558         {
559           int i = hard_regno_nregs[regno][GET_MODE (dest)];
560           if (code == SET)
561             {
562               while (--i >= 0)
563                 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
564             }
565           else
566             {
567               while (--i >= 0)
568                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
569             }
570         }
571       /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
572          it does not reload.  Ignore these as they have served their
573          purpose already.  */
574       else if (regno >= deps->max_reg)
575         {
576           gcc_assert (GET_CODE (PATTERN (insn)) == USE
577                       || GET_CODE (PATTERN (insn)) == CLOBBER);
578         }
579       else
580         {
581           if (code == SET)
582             SET_REGNO_REG_SET (reg_pending_sets, regno);
583           else
584             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
585
586           /* Pseudos that are REG_EQUIV to something may be replaced
587              by that during reloading.  We need only add dependencies for
588              the address in the REG_EQUIV note.  */
589           if (!reload_completed && get_reg_known_equiv_p (regno))
590             {
591               rtx t = get_reg_known_value (regno);
592               if (MEM_P (t))
593                 sched_analyze_2 (deps, XEXP (t, 0), insn);
594             }
595
596           /* Don't let it cross a call after scheduling if it doesn't
597              already cross one.  */
598           if (REG_N_CALLS_CROSSED (regno) == 0)
599             add_dependence_list (insn, deps->last_function_call, 1,
600                                  REG_DEP_ANTI);
601         }
602     }
603   else if (MEM_P (dest))
604     {
605       /* Writing memory.  */
606       rtx t = dest;
607
608       if (current_sched_info->use_cselib)
609         {
610           t = shallow_copy_rtx (dest);
611           cselib_lookup (XEXP (t, 0), Pmode, 1);
612           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
613         }
614       t = canon_rtx (t);
615
616       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
617         {
618           /* Flush all pending reads and writes to prevent the pending lists
619              from getting any larger.  Insn scheduling runs too slowly when
620              these lists get long.  When compiling GCC with itself,
621              this flush occurs 8 times for sparc, and 10 times for m88k using
622              the default value of 32.  */
623           flush_pending_lists (deps, insn, false, true);
624         }
625       else
626         {
627           rtx pending, pending_mem;
628
629           pending = deps->pending_read_insns;
630           pending_mem = deps->pending_read_mems;
631           while (pending)
632             {
633               if (anti_dependence (XEXP (pending_mem, 0), t)
634                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
635                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
636
637               pending = XEXP (pending, 1);
638               pending_mem = XEXP (pending_mem, 1);
639             }
640
641           pending = deps->pending_write_insns;
642           pending_mem = deps->pending_write_mems;
643           while (pending)
644             {
645               if (output_dependence (XEXP (pending_mem, 0), t)
646                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
647                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
648
649               pending = XEXP (pending, 1);
650               pending_mem = XEXP (pending_mem, 1);
651             }
652
653           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
654                                REG_DEP_ANTI);
655
656           add_insn_mem_dependence (deps, &deps->pending_write_insns,
657                                    &deps->pending_write_mems, insn, dest);
658         }
659       sched_analyze_2 (deps, XEXP (dest, 0), insn);
660     }
661
662   /* Analyze reads.  */
663   if (GET_CODE (x) == SET)
664     sched_analyze_2 (deps, SET_SRC (x), insn);
665 }
666
667 /* Analyze the uses of memory and registers in rtx X in INSN.  */
668
669 static void
670 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
671 {
672   int i;
673   int j;
674   enum rtx_code code;
675   const char *fmt;
676
677   if (x == 0)
678     return;
679
680   code = GET_CODE (x);
681
682   switch (code)
683     {
684     case CONST_INT:
685     case CONST_DOUBLE:
686     case CONST_VECTOR:
687     case SYMBOL_REF:
688     case CONST:
689     case LABEL_REF:
690       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
691          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
692          this does not mean that this insn is using cc0.  */
693       return;
694
695 #ifdef HAVE_cc0
696     case CC0:
697       /* User of CC0 depends on immediately preceding insn.  */
698       SCHED_GROUP_P (insn) = 1;
699        /* Don't move CC0 setter to another block (it can set up the
700         same flag for previous CC0 users which is safe).  */
701       CANT_MOVE (prev_nonnote_insn (insn)) = 1;
702       return;
703 #endif
704
705     case REG:
706       {
707         int regno = REGNO (x);
708
709 #ifdef STACK_REGS
710       /* Treat all reads of a stack register as modifying the TOS.  */
711       if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
712         {
713           SET_REGNO_REG_SET (reg_pending_sets, FIRST_STACK_REG);
714           regno = FIRST_STACK_REG;
715         }
716 #endif
717
718         if (regno < FIRST_PSEUDO_REGISTER)
719           {
720             int i = hard_regno_nregs[regno][GET_MODE (x)];
721             while (--i >= 0)
722               SET_REGNO_REG_SET (reg_pending_uses, regno + i);
723           }
724         /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
725            it does not reload.  Ignore these as they have served their
726            purpose already.  */
727         else if (regno >= deps->max_reg)
728           {
729             gcc_assert (GET_CODE (PATTERN (insn)) == USE
730                         || GET_CODE (PATTERN (insn)) == CLOBBER);
731           }
732         else
733           {
734             SET_REGNO_REG_SET (reg_pending_uses, regno);
735
736             /* Pseudos that are REG_EQUIV to something may be replaced
737                by that during reloading.  We need only add dependencies for
738                the address in the REG_EQUIV note.  */
739             if (!reload_completed && get_reg_known_equiv_p (regno))
740               {
741                 rtx t = get_reg_known_value (regno);
742                 if (MEM_P (t))
743                   sched_analyze_2 (deps, XEXP (t, 0), insn);
744               }
745
746             /* If the register does not already cross any calls, then add this
747                insn to the sched_before_next_call list so that it will still
748                not cross calls after scheduling.  */
749             if (REG_N_CALLS_CROSSED (regno) == 0)
750               deps->sched_before_next_call
751                 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
752           }
753         return;
754       }
755
756     case MEM:
757       {
758         /* Reading memory.  */
759         rtx u;
760         rtx pending, pending_mem;
761         rtx t = x;
762
763         if (current_sched_info->use_cselib)
764           {
765             t = shallow_copy_rtx (t);
766             cselib_lookup (XEXP (t, 0), Pmode, 1);
767             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
768           }
769         t = canon_rtx (t);
770         pending = deps->pending_read_insns;
771         pending_mem = deps->pending_read_mems;
772         while (pending)
773           {
774             if (read_dependence (XEXP (pending_mem, 0), t)
775                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
776               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
777
778             pending = XEXP (pending, 1);
779             pending_mem = XEXP (pending_mem, 1);
780           }
781
782         pending = deps->pending_write_insns;
783         pending_mem = deps->pending_write_mems;
784         while (pending)
785           {
786             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
787                                  t, rtx_varies_p)
788                 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
789               add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
790
791             pending = XEXP (pending, 1);
792             pending_mem = XEXP (pending_mem, 1);
793           }
794
795         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
796           if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
797             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
798
799         /* Always add these dependencies to pending_reads, since
800            this insn may be followed by a write.  */
801         add_insn_mem_dependence (deps, &deps->pending_read_insns,
802                                  &deps->pending_read_mems, insn, x);
803
804         /* Take advantage of tail recursion here.  */
805         sched_analyze_2 (deps, XEXP (x, 0), insn);
806         return;
807       }
808
809     /* Force pending stores to memory in case a trap handler needs them.  */
810     case TRAP_IF:
811       flush_pending_lists (deps, insn, true, false);
812       break;
813
814     case ASM_OPERANDS:
815     case ASM_INPUT:
816     case UNSPEC_VOLATILE:
817       {
818         /* Traditional and volatile asm instructions must be considered to use
819            and clobber all hard registers, all pseudo-registers and all of
820            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
821
822            Consider for instance a volatile asm that changes the fpu rounding
823            mode.  An insn should not be moved across this even if it only uses
824            pseudo-regs because it might give an incorrectly rounded result.  */
825         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
826           reg_pending_barrier = TRUE_BARRIER;
827
828         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
829            We can not just fall through here since then we would be confused
830            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
831            traditional asms unlike their normal usage.  */
832
833         if (code == ASM_OPERANDS)
834           {
835             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
836               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
837             return;
838           }
839         break;
840       }
841
842     case PRE_DEC:
843     case POST_DEC:
844     case PRE_INC:
845     case POST_INC:
846       /* These both read and modify the result.  We must handle them as writes
847          to get proper dependencies for following instructions.  We must handle
848          them as reads to get proper dependencies from this to previous
849          instructions.  Thus we need to pass them to both sched_analyze_1
850          and sched_analyze_2.  We must call sched_analyze_2 first in order
851          to get the proper antecedent for the read.  */
852       sched_analyze_2 (deps, XEXP (x, 0), insn);
853       sched_analyze_1 (deps, x, insn);
854       return;
855
856     case POST_MODIFY:
857     case PRE_MODIFY:
858       /* op0 = op0 + op1 */
859       sched_analyze_2 (deps, XEXP (x, 0), insn);
860       sched_analyze_2 (deps, XEXP (x, 1), insn);
861       sched_analyze_1 (deps, x, insn);
862       return;
863
864     default:
865       break;
866     }
867
868   /* Other cases: walk the insn.  */
869   fmt = GET_RTX_FORMAT (code);
870   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
871     {
872       if (fmt[i] == 'e')
873         sched_analyze_2 (deps, XEXP (x, i), insn);
874       else if (fmt[i] == 'E')
875         for (j = 0; j < XVECLEN (x, i); j++)
876           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
877     }
878 }
879
880 /* Analyze an INSN with pattern X to find all dependencies.  */
881
882 static void
883 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
884 {
885   RTX_CODE code = GET_CODE (x);
886   rtx link;
887   unsigned i;
888   reg_set_iterator rsi;
889
890   if (code == COND_EXEC)
891     {
892       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
893
894       /* ??? Should be recording conditions so we reduce the number of
895          false dependencies.  */
896       x = COND_EXEC_CODE (x);
897       code = GET_CODE (x);
898     }
899   if (code == SET || code == CLOBBER)
900     {
901       sched_analyze_1 (deps, x, insn);
902
903       /* Bare clobber insns are used for letting life analysis, reg-stack
904          and others know that a value is dead.  Depend on the last call
905          instruction so that reg-stack won't get confused.  */
906       if (code == CLOBBER)
907         add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
908     }
909   else if (code == PARALLEL)
910     {
911       for (i = XVECLEN (x, 0); i--;)
912         {
913           rtx sub = XVECEXP (x, 0, i);
914           code = GET_CODE (sub);
915
916           if (code == COND_EXEC)
917             {
918               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
919               sub = COND_EXEC_CODE (sub);
920               code = GET_CODE (sub);
921             }
922           if (code == SET || code == CLOBBER)
923             sched_analyze_1 (deps, sub, insn);
924           else
925             sched_analyze_2 (deps, sub, insn);
926         }
927     }
928   else
929     sched_analyze_2 (deps, x, insn);
930
931   /* Mark registers CLOBBERED or used by called function.  */
932   if (CALL_P (insn))
933     {
934       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
935         {
936           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
937             sched_analyze_1 (deps, XEXP (link, 0), insn);
938           else
939             sched_analyze_2 (deps, XEXP (link, 0), insn);
940         }
941       if (find_reg_note (insn, REG_SETJMP, NULL))
942         reg_pending_barrier = MOVE_BARRIER;
943     }
944
945   if (JUMP_P (insn))
946     {
947       rtx next;
948       next = next_nonnote_insn (insn);
949       if (next && BARRIER_P (next))
950         reg_pending_barrier = TRUE_BARRIER;
951       else
952         {
953           rtx pending, pending_mem;
954           regset_head tmp_uses, tmp_sets;
955           INIT_REG_SET (&tmp_uses);
956           INIT_REG_SET (&tmp_sets);
957
958           (*current_sched_info->compute_jump_reg_dependencies)
959             (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
960           /* Make latency of jump equal to 0 by using anti-dependence.  */
961           EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
962             {
963               struct deps_reg *reg_last = &deps->reg_last[i];
964               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
965               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
966               reg_last->uses_length++;
967               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
968             }
969           IOR_REG_SET (reg_pending_sets, &tmp_sets);
970
971           CLEAR_REG_SET (&tmp_uses);
972           CLEAR_REG_SET (&tmp_sets);
973
974           /* All memory writes and volatile reads must happen before the
975              jump.  Non-volatile reads must happen before the jump iff
976              the result is needed by the above register used mask.  */
977
978           pending = deps->pending_write_insns;
979           pending_mem = deps->pending_write_mems;
980           while (pending)
981             {
982               if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
983                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
984               pending = XEXP (pending, 1);
985               pending_mem = XEXP (pending_mem, 1);
986             }
987
988           pending = deps->pending_read_insns;
989           pending_mem = deps->pending_read_mems;
990           while (pending)
991             {
992               if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
993                   && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
994                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
995               pending = XEXP (pending, 1);
996               pending_mem = XEXP (pending_mem, 1);
997             }
998
999           add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1000                                REG_DEP_ANTI);
1001         }
1002     }
1003
1004   /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1005      block, then we must be sure that no instructions are scheduled across it.
1006      Otherwise, the reg_n_refs info (which depends on loop_depth) would
1007      become incorrect.  */
1008   if (loop_notes)
1009     {
1010       rtx link;
1011
1012       /* Update loop_notes with any notes from this insn.  */
1013       link = loop_notes;
1014       while (XEXP (link, 1))
1015         {
1016           gcc_assert (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
1017                       || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END);
1018
1019           reg_pending_barrier = MOVE_BARRIER;
1020           link = XEXP (link, 1);
1021         }
1022       XEXP (link, 1) = REG_NOTES (insn);
1023       REG_NOTES (insn) = loop_notes;
1024     }
1025
1026   /* If this instruction can throw an exception, then moving it changes
1027      where block boundaries fall.  This is mighty confusing elsewhere.
1028      Therefore, prevent such an instruction from being moved.  */
1029   if (can_throw_internal (insn))
1030     reg_pending_barrier = MOVE_BARRIER;
1031
1032   /* Add dependencies if a scheduling barrier was found.  */
1033   if (reg_pending_barrier)
1034     {
1035       /* In the case of barrier the most added dependencies are not
1036          real, so we use anti-dependence here.  */
1037       if (sched_get_condition (insn))
1038         {
1039           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1040             {
1041               struct deps_reg *reg_last = &deps->reg_last[i];
1042               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1043               add_dependence_list
1044                 (insn, reg_last->sets, 0,
1045                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1046               add_dependence_list
1047                 (insn, reg_last->clobbers, 0,
1048                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1049             }
1050         }
1051       else
1052         {
1053           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1054             {
1055               struct deps_reg *reg_last = &deps->reg_last[i];
1056               add_dependence_list_and_free (insn, &reg_last->uses, 0,
1057                                             REG_DEP_ANTI);
1058               add_dependence_list_and_free
1059                 (insn, &reg_last->sets, 0,
1060                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1061               add_dependence_list_and_free
1062                 (insn, &reg_last->clobbers, 0,
1063                  reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1064               reg_last->uses_length = 0;
1065               reg_last->clobbers_length = 0;
1066             }
1067         }
1068
1069       for (i = 0; i < (unsigned)deps->max_reg; i++)
1070         {
1071           struct deps_reg *reg_last = &deps->reg_last[i];
1072           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1073           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1074         }
1075
1076       flush_pending_lists (deps, insn, true, true);
1077       CLEAR_REG_SET (&deps->reg_conditional_sets);
1078       reg_pending_barrier = NOT_A_BARRIER;
1079     }
1080   else
1081     {
1082       /* If the current insn is conditional, we can't free any
1083          of the lists.  */
1084       if (sched_get_condition (insn))
1085         {
1086           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1087             {
1088               struct deps_reg *reg_last = &deps->reg_last[i];
1089               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1090               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1091               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1092               reg_last->uses_length++;
1093             }
1094           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1095             {
1096               struct deps_reg *reg_last = &deps->reg_last[i];
1097               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1098               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1099               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1100               reg_last->clobbers_length++;
1101             }
1102           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1103             {
1104               struct deps_reg *reg_last = &deps->reg_last[i];
1105               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1106               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
1107               add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1108               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1109               SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1110             }
1111         }
1112       else
1113         {
1114           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1115             {
1116               struct deps_reg *reg_last = &deps->reg_last[i];
1117               add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1118               add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1119               reg_last->uses_length++;
1120               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1121             }
1122           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1123             {
1124               struct deps_reg *reg_last = &deps->reg_last[i];
1125               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1126                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1127                 {
1128                   add_dependence_list_and_free (insn, &reg_last->sets, 0,
1129                                                 REG_DEP_OUTPUT);
1130                   add_dependence_list_and_free (insn, &reg_last->uses, 0,
1131                                                 REG_DEP_ANTI);
1132                   add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1133                                                 REG_DEP_OUTPUT);
1134                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1135                   reg_last->clobbers_length = 0;
1136                   reg_last->uses_length = 0;
1137                 }
1138               else
1139                 {
1140                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1141                   add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1142                 }
1143               reg_last->clobbers_length++;
1144               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1145             }
1146           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1147             {
1148               struct deps_reg *reg_last = &deps->reg_last[i];
1149               add_dependence_list_and_free (insn, &reg_last->sets, 0,
1150                                             REG_DEP_OUTPUT);
1151               add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1152                                             REG_DEP_OUTPUT);
1153               add_dependence_list_and_free (insn, &reg_last->uses, 0,
1154                                             REG_DEP_ANTI);
1155               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1156               reg_last->uses_length = 0;
1157               reg_last->clobbers_length = 0;
1158               CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1159             }
1160         }
1161
1162       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1163       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1164       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1165     }
1166   CLEAR_REG_SET (reg_pending_uses);
1167   CLEAR_REG_SET (reg_pending_clobbers);
1168   CLEAR_REG_SET (reg_pending_sets);
1169
1170   /* If we are currently in a libcall scheduling group, then mark the
1171      current insn as being in a scheduling group and that it can not
1172      be moved into a different basic block.  */
1173
1174   if (deps->libcall_block_tail_insn)
1175     {
1176       SCHED_GROUP_P (insn) = 1;
1177       CANT_MOVE (insn) = 1;
1178     }
1179
1180   /* If a post-call group is still open, see if it should remain so.
1181      This insn must be a simple move of a hard reg to a pseudo or
1182      vice-versa.
1183
1184      We must avoid moving these insns for correctness on
1185      SMALL_REGISTER_CLASS machines, and for special registers like
1186      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1187      hard regs for all targets.  */
1188
1189   if (deps->in_post_call_group_p)
1190     {
1191       rtx tmp, set = single_set (insn);
1192       int src_regno, dest_regno;
1193
1194       if (set == NULL)
1195         goto end_call_group;
1196
1197       tmp = SET_DEST (set);
1198       if (GET_CODE (tmp) == SUBREG)
1199         tmp = SUBREG_REG (tmp);
1200       if (REG_P (tmp))
1201         dest_regno = REGNO (tmp);
1202       else
1203         goto end_call_group;
1204
1205       tmp = SET_SRC (set);
1206       if (GET_CODE (tmp) == SUBREG)
1207         tmp = SUBREG_REG (tmp);
1208       if ((GET_CODE (tmp) == PLUS
1209            || GET_CODE (tmp) == MINUS)
1210           && REG_P (XEXP (tmp, 0))
1211           && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1212           && dest_regno == STACK_POINTER_REGNUM)
1213         src_regno = STACK_POINTER_REGNUM;
1214       else if (REG_P (tmp))
1215         src_regno = REGNO (tmp);
1216       else
1217         goto end_call_group;
1218
1219       if (src_regno < FIRST_PSEUDO_REGISTER
1220           || dest_regno < FIRST_PSEUDO_REGISTER)
1221         {
1222           if (deps->in_post_call_group_p == post_call_initial)
1223             deps->in_post_call_group_p = post_call;
1224
1225           SCHED_GROUP_P (insn) = 1;
1226           CANT_MOVE (insn) = 1;
1227         }
1228       else
1229         {
1230         end_call_group:
1231           deps->in_post_call_group_p = not_post_call;
1232         }
1233     }
1234
1235   /* Fixup the dependencies in the sched group.  */
1236   if (SCHED_GROUP_P (insn))
1237     fixup_sched_groups (insn);
1238 }
1239
1240 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1241    for every dependency.  */
1242
1243 void
1244 sched_analyze (struct deps *deps, rtx head, rtx tail)
1245 {
1246   rtx insn;
1247   rtx loop_notes = 0;
1248
1249   if (current_sched_info->use_cselib)
1250     cselib_init (true);
1251
1252   /* Before reload, if the previous block ended in a call, show that
1253      we are inside a post-call group, so as to keep the lifetimes of
1254      hard registers correct.  */
1255   if (! reload_completed && !LABEL_P (head))
1256     {
1257       insn = prev_nonnote_insn (head);
1258       if (insn && CALL_P (insn))
1259         deps->in_post_call_group_p = post_call_initial;
1260     }
1261   for (insn = head;; insn = NEXT_INSN (insn))
1262     {
1263       rtx link, end_seq, r0, set;
1264
1265       if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1266         {
1267           /* Clear out the stale LOG_LINKS from flow.  */
1268           free_INSN_LIST_list (&LOG_LINKS (insn));
1269
1270           /* Make each JUMP_INSN a scheduling barrier for memory
1271              references.  */
1272           if (JUMP_P (insn))
1273             {
1274               /* Keep the list a reasonable size.  */
1275               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1276                 flush_pending_lists (deps, insn, true, true);
1277               else
1278                 deps->last_pending_memory_flush
1279                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1280             }
1281           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1282           loop_notes = 0;
1283         }
1284       else if (CALL_P (insn))
1285         {
1286           int i;
1287
1288           CANT_MOVE (insn) = 1;
1289
1290           /* Clear out the stale LOG_LINKS from flow.  */
1291           free_INSN_LIST_list (&LOG_LINKS (insn));
1292
1293           if (find_reg_note (insn, REG_SETJMP, NULL))
1294             {
1295               /* This is setjmp.  Assume that all registers, not just
1296                  hard registers, may be clobbered by this call.  */
1297               reg_pending_barrier = MOVE_BARRIER;
1298             }
1299           else
1300             {
1301               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1302                 /* A call may read and modify global register variables.  */
1303                 if (global_regs[i])
1304                   {
1305                     SET_REGNO_REG_SET (reg_pending_sets, i);
1306                     SET_REGNO_REG_SET (reg_pending_uses, i);
1307                   }
1308                 /* Other call-clobbered hard regs may be clobbered.
1309                    Since we only have a choice between 'might be clobbered'
1310                    and 'definitely not clobbered', we must include all
1311                    partly call-clobbered registers here.  */
1312                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1313                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1314                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1315                 /* We don't know what set of fixed registers might be used
1316                    by the function, but it is certain that the stack pointer
1317                    is among them, but be conservative.  */
1318                 else if (fixed_regs[i])
1319                   SET_REGNO_REG_SET (reg_pending_uses, i);
1320                 /* The frame pointer is normally not used by the function
1321                    itself, but by the debugger.  */
1322                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1323                    in the macro expansion of jal but does not represent this
1324                    fact in the call_insn rtl.  */
1325                 else if (i == FRAME_POINTER_REGNUM
1326                          || (i == HARD_FRAME_POINTER_REGNUM
1327                              && (! reload_completed || frame_pointer_needed)))
1328                   SET_REGNO_REG_SET (reg_pending_uses, i);
1329             }
1330
1331           /* For each insn which shouldn't cross a call, add a dependence
1332              between that insn and this call insn.  */
1333           add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
1334                                         REG_DEP_ANTI);
1335
1336           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1337           loop_notes = 0;
1338
1339           /* In the absence of interprocedural alias analysis, we must flush
1340              all pending reads and writes, and start new dependencies starting
1341              from here.  But only flush writes for constant calls (which may
1342              be passed a pointer to something we haven't written yet).  */
1343           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1344
1345           /* Remember the last function call for limiting lifetimes.  */
1346           free_INSN_LIST_list (&deps->last_function_call);
1347           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1348
1349           /* Before reload, begin a post-call group, so as to keep the
1350              lifetimes of hard registers correct.  */
1351           if (! reload_completed)
1352             deps->in_post_call_group_p = post_call;
1353         }
1354
1355       /* EH_REGION insn notes can not appear until well after we complete
1356          scheduling.  */
1357       if (NOTE_P (insn))
1358         gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1359                     && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1360
1361       /* See comments on reemit_notes as to why we do this.
1362          ??? Actually, the reemit_notes just say what is done, not why.  */
1363
1364       if (NOTE_P (insn)
1365           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1366               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
1367         {
1368           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1369                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1370                                         loop_notes);
1371           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1372         }
1373
1374       if (current_sched_info->use_cselib)
1375         cselib_process_insn (insn);
1376
1377       /* Now that we have completed handling INSN, check and see if it is
1378          a CLOBBER beginning a libcall block.   If it is, record the
1379          end of the libcall sequence.
1380
1381          We want to schedule libcall blocks as a unit before reload.  While
1382          this restricts scheduling, it preserves the meaning of a libcall
1383          block.
1384
1385          As a side effect, we may get better code due to decreased register
1386          pressure as well as less chance of a foreign insn appearing in
1387          a libcall block.  */
1388       if (!reload_completed
1389           /* Note we may have nested libcall sequences.  We only care about
1390              the outermost libcall sequence.  */
1391           && deps->libcall_block_tail_insn == 0
1392           /* The sequence must start with a clobber of a register.  */
1393           && NONJUMP_INSN_P (insn)
1394           && GET_CODE (PATTERN (insn)) == CLOBBER
1395           && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1396           && REG_P (XEXP (PATTERN (insn), 0))
1397           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1398           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1399           && (end_seq = XEXP (link, 0)) != 0
1400           /* The insn referenced by the REG_LIBCALL note must be a
1401              simple nop copy with the same destination as the register
1402              mentioned in the clobber.  */
1403           && (set = single_set (end_seq)) != 0
1404           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1405           /* And finally the insn referenced by the REG_LIBCALL must
1406              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1407           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1408           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1409         deps->libcall_block_tail_insn = XEXP (link, 0);
1410
1411       /* If we have reached the end of a libcall block, then close the
1412          block.  */
1413       if (deps->libcall_block_tail_insn == insn)
1414         deps->libcall_block_tail_insn = 0;
1415
1416       if (insn == tail)
1417         {
1418           if (current_sched_info->use_cselib)
1419             cselib_finish ();
1420           return;
1421         }
1422     }
1423   gcc_unreachable ();
1424 }
1425 \f
1426
1427 /* The following function adds forward dependence (FROM, TO) with
1428    given DEP_TYPE.  The forward dependence should be not exist before.  */
1429
1430 void
1431 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1432 {
1433   rtx new_link;
1434
1435 #ifdef ENABLE_CHECKING
1436   /* If add_dependence is working properly there should never
1437      be notes, deleted insns or duplicates in the backward
1438      links.  Thus we need not check for them here.
1439
1440      However, if we have enabled checking we might as well go
1441      ahead and verify that add_dependence worked properly.  */
1442   gcc_assert (!NOTE_P (from));
1443   gcc_assert (!INSN_DELETED_P (from));
1444   if (forward_dependency_cache)
1445     gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1446                                INSN_LUID (to)));
1447   else
1448     gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1449
1450   /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
1451   if (forward_dependency_cache != NULL)
1452     bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1453                   INSN_LUID (to));
1454 #endif
1455
1456   new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1457
1458   PUT_REG_NOTE_KIND (new_link, dep_type);
1459
1460   INSN_DEPEND (from) = new_link;
1461   INSN_DEP_COUNT (to) += 1;
1462 }
1463
1464 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1465    dependences from LOG_LINKS to build forward dependences in
1466    INSN_DEPEND.  */
1467
1468 void
1469 compute_forward_dependences (rtx head, rtx tail)
1470 {
1471   rtx insn, link;
1472   rtx next_tail;
1473
1474   next_tail = NEXT_INSN (tail);
1475   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1476     {
1477       if (! INSN_P (insn))
1478         continue;
1479
1480       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1481         add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1482     }
1483 }
1484 \f
1485 /* Initialize variables for region data dependence analysis.
1486    n_bbs is the number of region blocks.  */
1487
1488 void
1489 init_deps (struct deps *deps)
1490 {
1491   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1492
1493   deps->max_reg = max_reg;
1494   deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1495   INIT_REG_SET (&deps->reg_last_in_use);
1496   INIT_REG_SET (&deps->reg_conditional_sets);
1497
1498   deps->pending_read_insns = 0;
1499   deps->pending_read_mems = 0;
1500   deps->pending_write_insns = 0;
1501   deps->pending_write_mems = 0;
1502   deps->pending_lists_length = 0;
1503   deps->pending_flush_length = 0;
1504   deps->last_pending_memory_flush = 0;
1505   deps->last_function_call = 0;
1506   deps->sched_before_next_call = 0;
1507   deps->in_post_call_group_p = not_post_call;
1508   deps->libcall_block_tail_insn = 0;
1509 }
1510
1511 /* Free insn lists found in DEPS.  */
1512
1513 void
1514 free_deps (struct deps *deps)
1515 {
1516   unsigned i;
1517   reg_set_iterator rsi;
1518
1519   free_INSN_LIST_list (&deps->pending_read_insns);
1520   free_EXPR_LIST_list (&deps->pending_read_mems);
1521   free_INSN_LIST_list (&deps->pending_write_insns);
1522   free_EXPR_LIST_list (&deps->pending_write_mems);
1523   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1524
1525   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1526      times.  For a testcase with 42000 regs and 8000 small basic blocks,
1527      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1528   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1529     {
1530       struct deps_reg *reg_last = &deps->reg_last[i];
1531       if (reg_last->uses)
1532         free_INSN_LIST_list (&reg_last->uses);
1533       if (reg_last->sets)
1534         free_INSN_LIST_list (&reg_last->sets);
1535       if (reg_last->clobbers)
1536         free_INSN_LIST_list (&reg_last->clobbers);
1537     }
1538   CLEAR_REG_SET (&deps->reg_last_in_use);
1539   CLEAR_REG_SET (&deps->reg_conditional_sets);
1540
1541   free (deps->reg_last);
1542 }
1543
1544 /* If it is profitable to use them, initialize caches for tracking
1545    dependency information.  LUID is the number of insns to be scheduled,
1546    it is used in the estimate of profitability.  */
1547
1548 void
1549 init_dependency_caches (int luid)
1550 {
1551   /* ?!? We could save some memory by computing a per-region luid mapping
1552      which could reduce both the number of vectors in the cache and the size
1553      of each vector.  Instead we just avoid the cache entirely unless the
1554      average number of instructions in a basic block is very high.  See
1555      the comment before the declaration of true_dependency_cache for
1556      what we consider "very high".  */
1557   if (luid / n_basic_blocks > 100 * 5)
1558     {
1559       int i;
1560       true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1561       anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1562       output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1563 #ifdef ENABLE_CHECKING
1564       forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1565 #endif
1566       for (i = 0; i < luid; i++)
1567         {
1568           bitmap_initialize (&true_dependency_cache[i], 0);
1569           bitmap_initialize (&anti_dependency_cache[i], 0);
1570           bitmap_initialize (&output_dependency_cache[i], 0);
1571 #ifdef ENABLE_CHECKING
1572           bitmap_initialize (&forward_dependency_cache[i], 0);
1573 #endif
1574         }
1575       cache_size = luid;
1576     }
1577 }
1578
1579 /* Free the caches allocated in init_dependency_caches.  */
1580
1581 void
1582 free_dependency_caches (void)
1583 {
1584   if (true_dependency_cache)
1585     {
1586       int i;
1587
1588       for (i = 0; i < cache_size; i++)
1589         {
1590           bitmap_clear (&true_dependency_cache[i]);
1591           bitmap_clear (&anti_dependency_cache[i]);
1592           bitmap_clear (&output_dependency_cache[i]);
1593 #ifdef ENABLE_CHECKING
1594           bitmap_clear (&forward_dependency_cache[i]);
1595 #endif
1596         }
1597       free (true_dependency_cache);
1598       true_dependency_cache = NULL;
1599       free (anti_dependency_cache);
1600       anti_dependency_cache = NULL;
1601       free (output_dependency_cache);
1602       output_dependency_cache = NULL;
1603 #ifdef ENABLE_CHECKING
1604       free (forward_dependency_cache);
1605       forward_dependency_cache = NULL;
1606 #endif
1607     }
1608 }
1609
1610 /* Initialize some global variables needed by the dependency analysis
1611    code.  */
1612
1613 void
1614 init_deps_global (void)
1615 {
1616   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
1617   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
1618   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
1619   reg_pending_barrier = NOT_A_BARRIER;
1620 }
1621
1622 /* Free everything used by the dependency analysis code.  */
1623
1624 void
1625 finish_deps_global (void)
1626 {
1627   FREE_REG_SET (reg_pending_sets);
1628   FREE_REG_SET (reg_pending_clobbers);
1629   FREE_REG_SET (reg_pending_uses);
1630 }