OSDN Git Service

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