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