OSDN Git Service

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