OSDN Git Service

PR rtl-optimization/15521:
[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           /* If we are inside a post-call group right at the start of the
1149              scheduling region, we must not add a dependency.  */
1150           if (deps->in_post_call_group_p == post_call_initial)
1151             {
1152               SCHED_GROUP_P (insn) = 1;
1153               deps->in_post_call_group_p = post_call;
1154             }
1155           else
1156             set_sched_group_p (insn);
1157           CANT_MOVE (insn) = 1;
1158         }
1159       else
1160         {
1161         end_call_group:
1162           deps->in_post_call_group_p = not_post_call;
1163         }
1164     }
1165 }
1166
1167 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1168    for every dependency.  */
1169
1170 void
1171 sched_analyze (struct deps *deps, rtx head, rtx tail)
1172 {
1173   rtx insn;
1174   rtx loop_notes = 0;
1175
1176   if (current_sched_info->use_cselib)
1177     cselib_init (true);
1178
1179   /* Before reload, if the previous block ended in a call, show that
1180      we are inside a post-call group, so as to keep the lifetimes of
1181      hard registers correct.  */
1182   if (! reload_completed && GET_CODE (head) != CODE_LABEL)
1183     {
1184       insn = prev_nonnote_insn (head);
1185       if (insn && GET_CODE (insn) == CALL_INSN)
1186         deps->in_post_call_group_p = post_call_initial;
1187     }
1188   for (insn = head;; insn = NEXT_INSN (insn))
1189     {
1190       rtx link, end_seq, r0, set;
1191
1192       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1193         {
1194           /* Clear out the stale LOG_LINKS from flow.  */
1195           free_INSN_LIST_list (&LOG_LINKS (insn));
1196
1197           /* Make each JUMP_INSN a scheduling barrier for memory
1198              references.  */
1199           if (GET_CODE (insn) == JUMP_INSN)
1200             {
1201               /* Keep the list a reasonable size.  */
1202               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1203                 flush_pending_lists (deps, insn, true, true);
1204               else
1205                 deps->last_pending_memory_flush
1206                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1207             }
1208           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1209           loop_notes = 0;
1210         }
1211       else if (GET_CODE (insn) == CALL_INSN)
1212         {
1213           int i;
1214
1215           CANT_MOVE (insn) = 1;
1216
1217           /* Clear out the stale LOG_LINKS from flow.  */
1218           free_INSN_LIST_list (&LOG_LINKS (insn));
1219
1220           if (find_reg_note (insn, REG_SETJMP, NULL))
1221             {
1222               /* This is setjmp.  Assume that all registers, not just
1223                  hard registers, may be clobbered by this call.  */
1224               reg_pending_barrier = MOVE_BARRIER;
1225             }
1226           else
1227             {
1228               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1229                 /* A call may read and modify global register variables.  */
1230                 if (global_regs[i])
1231                   {
1232                     SET_REGNO_REG_SET (reg_pending_sets, i);
1233                     SET_REGNO_REG_SET (reg_pending_uses, i);
1234                   }
1235                 /* Other call-clobbered hard regs may be clobbered.
1236                    Since we only have a choice between 'might be clobbered'
1237                    and 'definitely not clobbered', we must include all
1238                    partly call-clobbered registers here.  */
1239                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1240                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1241                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1242                 /* We don't know what set of fixed registers might be used
1243                    by the function, but it is certain that the stack pointer
1244                    is among them, but be conservative.  */
1245                 else if (fixed_regs[i])
1246                   SET_REGNO_REG_SET (reg_pending_uses, i);
1247                 /* The frame pointer is normally not used by the function
1248                    itself, but by the debugger.  */
1249                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1250                    in the macro expansion of jal but does not represent this
1251                    fact in the call_insn rtl.  */
1252                 else if (i == FRAME_POINTER_REGNUM
1253                          || (i == HARD_FRAME_POINTER_REGNUM
1254                              && (! reload_completed || frame_pointer_needed)))
1255                   SET_REGNO_REG_SET (reg_pending_uses, i);
1256             }
1257
1258           /* For each insn which shouldn't cross a call, add a dependence
1259              between that insn and this call insn.  */
1260           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1261                                         REG_DEP_ANTI);
1262
1263           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1264           loop_notes = 0;
1265
1266           /* In the absence of interprocedural alias analysis, we must flush
1267              all pending reads and writes, and start new dependencies starting
1268              from here.  But only flush writes for constant calls (which may
1269              be passed a pointer to something we haven't written yet).  */
1270           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1271
1272           /* Remember the last function call for limiting lifetimes.  */
1273           free_INSN_LIST_list (&deps->last_function_call);
1274           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1275
1276           /* Before reload, begin a post-call group, so as to keep the
1277              lifetimes of hard registers correct.  */
1278           if (! reload_completed)
1279             deps->in_post_call_group_p = post_call;
1280         }
1281
1282       /* See comments on reemit_notes as to why we do this.
1283          ??? Actually, the reemit_notes just say what is done, not why.  */
1284
1285       if (GET_CODE (insn) == NOTE
1286                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1287                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1288                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1289                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1290         {
1291           rtx rtx_region;
1292
1293           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1294               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1295             rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1296           else
1297             rtx_region = const0_rtx;
1298
1299           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1300                                         rtx_region,
1301                                         loop_notes);
1302           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1303                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1304                                         loop_notes);
1305           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1306         }
1307
1308       if (current_sched_info->use_cselib)
1309         cselib_process_insn (insn);
1310
1311       /* Now that we have completed handling INSN, check and see if it is
1312          a CLOBBER beginning a libcall block.   If it is, record the
1313          end of the libcall sequence.
1314
1315          We want to schedule libcall blocks as a unit before reload.  While
1316          this restricts scheduling, it preserves the meaning of a libcall
1317          block.
1318
1319          As a side effect, we may get better code due to decreased register
1320          pressure as well as less chance of a foreign insn appearing in
1321          a libcall block.  */
1322       if (!reload_completed
1323           /* Note we may have nested libcall sequences.  We only care about
1324              the outermost libcall sequence.  */
1325           && deps->libcall_block_tail_insn == 0
1326           /* The sequence must start with a clobber of a register.  */
1327           && GET_CODE (insn) == INSN
1328           && GET_CODE (PATTERN (insn)) == CLOBBER
1329           && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG)
1330           && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
1331           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1332           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1333           && (end_seq = XEXP (link, 0)) != 0
1334           /* The insn referenced by the REG_LIBCALL note must be a
1335              simple nop copy with the same destination as the register
1336              mentioned in the clobber.  */
1337           && (set = single_set (end_seq)) != 0
1338           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1339           /* And finally the insn referenced by the REG_LIBCALL must
1340              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1341           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1342           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1343         deps->libcall_block_tail_insn = XEXP (link, 0);
1344
1345       /* If we have reached the end of a libcall block, then close the
1346          block.  */
1347       if (deps->libcall_block_tail_insn == insn)
1348         deps->libcall_block_tail_insn = 0;
1349
1350       if (insn == tail)
1351         {
1352           if (current_sched_info->use_cselib)
1353             cselib_finish ();
1354           return;
1355         }
1356     }
1357   abort ();
1358 }
1359 \f
1360
1361 /* The following function adds forward dependence (FROM, TO) with
1362    given DEP_TYPE.  The forward dependence should be not exist before.  */
1363
1364 void
1365 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1366 {
1367   rtx new_link;
1368
1369 #ifdef ENABLE_CHECKING
1370   /* If add_dependence is working properly there should never
1371      be notes, deleted insns or duplicates in the backward
1372      links.  Thus we need not check for them here.
1373
1374      However, if we have enabled checking we might as well go
1375      ahead and verify that add_dependence worked properly.  */
1376   if (GET_CODE (from) == NOTE
1377       || INSN_DELETED_P (from)
1378       || (forward_dependency_cache != NULL
1379           && bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1380                            INSN_LUID (to)))
1381       || (forward_dependency_cache == NULL
1382           && find_insn_list (to, INSN_DEPEND (from))))
1383     abort ();
1384   if (forward_dependency_cache != NULL)
1385     bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1386                   INSN_LUID (to));
1387 #endif
1388
1389   new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1390
1391   PUT_REG_NOTE_KIND (new_link, dep_type);
1392
1393   INSN_DEPEND (from) = new_link;
1394   INSN_DEP_COUNT (to) += 1;
1395 }
1396
1397 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1398    dependences from LOG_LINKS to build forward dependences in
1399    INSN_DEPEND.  */
1400
1401 void
1402 compute_forward_dependences (rtx head, rtx tail)
1403 {
1404   rtx insn, link;
1405   rtx next_tail;
1406
1407   next_tail = NEXT_INSN (tail);
1408   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1409     {
1410       if (! INSN_P (insn))
1411         continue;
1412
1413       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1414         add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1415     }
1416 }
1417 \f
1418 /* Initialize variables for region data dependence analysis.
1419    n_bbs is the number of region blocks.  */
1420
1421 void
1422 init_deps (struct deps *deps)
1423 {
1424   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1425
1426   deps->max_reg = max_reg;
1427   deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1428   INIT_REG_SET (&deps->reg_last_in_use);
1429   INIT_REG_SET (&deps->reg_conditional_sets);
1430
1431   deps->pending_read_insns = 0;
1432   deps->pending_read_mems = 0;
1433   deps->pending_write_insns = 0;
1434   deps->pending_write_mems = 0;
1435   deps->pending_lists_length = 0;
1436   deps->pending_flush_length = 0;
1437   deps->last_pending_memory_flush = 0;
1438   deps->last_function_call = 0;
1439   deps->sched_before_next_call = 0;
1440   deps->in_post_call_group_p = not_post_call;
1441   deps->libcall_block_tail_insn = 0;
1442 }
1443
1444 /* Free insn lists found in DEPS.  */
1445
1446 void
1447 free_deps (struct deps *deps)
1448 {
1449   int i;
1450
1451   free_INSN_LIST_list (&deps->pending_read_insns);
1452   free_EXPR_LIST_list (&deps->pending_read_mems);
1453   free_INSN_LIST_list (&deps->pending_write_insns);
1454   free_EXPR_LIST_list (&deps->pending_write_mems);
1455   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1456
1457   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1458      times.  For a testcase with 42000 regs and 8000 small basic blocks,
1459      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1460   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1461     {
1462       struct deps_reg *reg_last = &deps->reg_last[i];
1463       if (reg_last->uses)
1464         free_INSN_LIST_list (&reg_last->uses);
1465       if (reg_last->sets)
1466         free_INSN_LIST_list (&reg_last->sets);
1467       if (reg_last->clobbers)
1468         free_INSN_LIST_list (&reg_last->clobbers);
1469     });
1470   CLEAR_REG_SET (&deps->reg_last_in_use);
1471   CLEAR_REG_SET (&deps->reg_conditional_sets);
1472
1473   free (deps->reg_last);
1474 }
1475
1476 /* If it is profitable to use them, initialize caches for tracking
1477    dependency information.  LUID is the number of insns to be scheduled,
1478    it is used in the estimate of profitability.  */
1479
1480 void
1481 init_dependency_caches (int luid)
1482 {
1483   /* ?!? We could save some memory by computing a per-region luid mapping
1484      which could reduce both the number of vectors in the cache and the size
1485      of each vector.  Instead we just avoid the cache entirely unless the
1486      average number of instructions in a basic block is very high.  See
1487      the comment before the declaration of true_dependency_cache for
1488      what we consider "very high".  */
1489   if (luid / n_basic_blocks > 100 * 5)
1490     {
1491       int i;
1492       true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1493       anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1494       output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1495 #ifdef ENABLE_CHECKING
1496       forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1497 #endif
1498       for (i = 0; i < luid; i++)
1499         {
1500           bitmap_initialize (&true_dependency_cache[i], 0);
1501           bitmap_initialize (&anti_dependency_cache[i], 0);
1502           bitmap_initialize (&output_dependency_cache[i], 0);
1503 #ifdef ENABLE_CHECKING
1504           bitmap_initialize (&forward_dependency_cache[i], 0);
1505 #endif
1506         }
1507       cache_size = luid;
1508     }
1509 }
1510
1511 /* Free the caches allocated in init_dependency_caches.  */
1512
1513 void
1514 free_dependency_caches (void)
1515 {
1516   if (true_dependency_cache)
1517     {
1518       int i;
1519
1520       for (i = 0; i < cache_size; i++)
1521         {
1522           bitmap_clear (&true_dependency_cache[i]);
1523           bitmap_clear (&anti_dependency_cache[i]);
1524           bitmap_clear (&output_dependency_cache[i]);
1525 #ifdef ENABLE_CHECKING
1526           bitmap_clear (&forward_dependency_cache[i]);
1527 #endif
1528         }
1529       free (true_dependency_cache);
1530       true_dependency_cache = NULL;
1531       free (anti_dependency_cache);
1532       anti_dependency_cache = NULL;
1533       free (output_dependency_cache);
1534       output_dependency_cache = NULL;
1535 #ifdef ENABLE_CHECKING
1536       free (forward_dependency_cache);
1537       forward_dependency_cache = NULL;
1538 #endif
1539     }
1540 }
1541
1542 /* Initialize some global variables needed by the dependency analysis
1543    code.  */
1544
1545 void
1546 init_deps_global (void)
1547 {
1548   reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1549   reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1550   reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1551   reg_pending_barrier = NOT_A_BARRIER;
1552 }
1553
1554 /* Free everything used by the dependency analysis code.  */
1555
1556 void
1557 finish_deps_global (void)
1558 {
1559   FREE_REG_SET (reg_pending_sets);
1560   FREE_REG_SET (reg_pending_clobbers);
1561   FREE_REG_SET (reg_pending_uses);
1562 }