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