* pa-protos.h (get_deferred_plabel): New prototype.
[official-gcc.git] / gcc / sched-deps.c
blob25dccb76dcd2f4d270b93f389fa187e7c5d81b26
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, 2005 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 02110-1301, USA. */
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 "regs.h"
34 #include "function.h"
35 #include "flags.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
38 #include "except.h"
39 #include "toplev.h"
40 #include "recog.h"
41 #include "sched-int.h"
42 #include "params.h"
43 #include "cselib.h"
44 #include "df.h"
47 static regset reg_pending_sets;
48 static regset reg_pending_clobbers;
49 static regset reg_pending_uses;
51 /* The following enumeration values tell us what dependencies we
52 should use to implement the barrier. We use true-dependencies for
53 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
54 enum reg_pending_barrier_mode
56 NOT_A_BARRIER = 0,
57 MOVE_BARRIER,
58 TRUE_BARRIER
61 static enum reg_pending_barrier_mode reg_pending_barrier;
63 /* To speed up the test for duplicate dependency links we keep a
64 record of dependencies created by add_dependence when the average
65 number of instructions in a basic block is very large.
67 Studies have shown that there is typically around 5 instructions between
68 branches for typical C code. So we can make a guess that the average
69 basic block is approximately 5 instructions long; we will choose 100X
70 the average size as a very large basic block.
72 Each insn has associated bitmaps for its dependencies. Each bitmap
73 has enough entries to represent a dependency on any other insn in
74 the insn chain. All bitmap for true dependencies cache is
75 allocated then the rest two ones are also allocated. */
76 static bitmap_head *true_dependency_cache;
77 static bitmap_head *anti_dependency_cache;
78 static bitmap_head *output_dependency_cache;
79 static int cache_size;
81 /* To speed up checking consistency of formed forward insn
82 dependencies we use the following cache. Another possible solution
83 could be switching off checking duplication of insns in forward
84 dependencies. */
85 #ifdef ENABLE_CHECKING
86 static bitmap_head *forward_dependency_cache;
87 #endif
89 static int deps_may_trap_p (rtx);
90 static void add_dependence_list (rtx, rtx, int, enum reg_note);
91 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
92 static void delete_all_dependences (rtx);
93 static void fixup_sched_groups (rtx);
95 static void flush_pending_lists (struct deps *, rtx, int, int);
96 static void sched_analyze_1 (struct deps *, rtx, rtx);
97 static void sched_analyze_2 (struct deps *, rtx, rtx);
98 static void sched_analyze_insn (struct deps *, rtx, rtx, rtx);
100 static rtx sched_get_condition (rtx);
101 static int conditions_mutex_p (rtx, rtx);
103 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
105 static int
106 deps_may_trap_p (rtx mem)
108 rtx addr = XEXP (mem, 0);
110 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
112 rtx t = get_reg_known_value (REGNO (addr));
113 if (t)
114 addr = t;
116 return rtx_addr_can_trap_p (addr);
119 /* Return the INSN_LIST containing INSN in LIST, or NULL
120 if LIST does not contain INSN. */
123 find_insn_list (rtx insn, rtx list)
125 while (list)
127 if (XEXP (list, 0) == insn)
128 return list;
129 list = XEXP (list, 1);
131 return 0;
134 /* Find the condition under which INSN is executed. */
136 static rtx
137 sched_get_condition (rtx insn)
139 rtx pat = PATTERN (insn);
140 rtx src;
142 if (pat == 0)
143 return 0;
145 if (GET_CODE (pat) == COND_EXEC)
146 return COND_EXEC_TEST (pat);
148 if (!any_condjump_p (insn) || !onlyjump_p (insn))
149 return 0;
151 src = SET_SRC (pc_set (insn));
153 if (XEXP (src, 2) == pc_rtx)
154 return XEXP (src, 0);
155 else if (XEXP (src, 1) == pc_rtx)
157 rtx cond = XEXP (src, 0);
158 enum rtx_code revcode = reversed_comparison_code (cond, insn);
160 if (revcode == UNKNOWN)
161 return 0;
162 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
163 XEXP (cond, 1));
166 return 0;
170 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
172 static int
173 conditions_mutex_p (rtx cond1, rtx cond2)
175 if (COMPARISON_P (cond1)
176 && COMPARISON_P (cond2)
177 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
178 && XEXP (cond1, 0) == XEXP (cond2, 0)
179 && XEXP (cond1, 1) == XEXP (cond2, 1))
180 return 1;
181 return 0;
184 /* Return true if insn1 and insn2 can never depend on one another because
185 the conditions under which they are executed are mutually exclusive. */
186 bool
187 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
189 rtx cond1, cond2;
191 /* flow.c doesn't handle conditional lifetimes entirely correctly;
192 calls mess up the conditional lifetimes. */
193 if (!CALL_P (insn1) && !CALL_P (insn2))
195 cond1 = sched_get_condition (insn1);
196 cond2 = sched_get_condition (insn2);
197 if (cond1 && cond2
198 && conditions_mutex_p (cond1, cond2)
199 /* Make sure first instruction doesn't affect condition of second
200 instruction if switched. */
201 && !modified_in_p (cond1, insn2)
202 /* Make sure second instruction doesn't affect condition of first
203 instruction if switched. */
204 && !modified_in_p (cond2, insn1))
205 return true;
207 return false;
210 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
211 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
212 type of dependence that this link represents. The function returns
213 nonzero if a new entry has been added to insn's LOG_LINK. */
216 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
218 rtx link;
219 int present_p;
221 /* Don't depend an insn on itself. */
222 if (insn == elem)
223 return 0;
225 /* We can get a dependency on deleted insns due to optimizations in
226 the register allocation and reloading or due to splitting. Any
227 such dependency is useless and can be ignored. */
228 if (NOTE_P (elem))
229 return 0;
231 present_p = 1;
232 #ifdef INSN_SCHEDULING
233 /* ??? No good way to tell from here whether we're doing interblock
234 scheduling. Possibly add another callback. */
235 #if 0
236 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
237 No need for interblock dependences with calls, since
238 calls are not moved between blocks. Note: the edge where
239 elem is a CALL is still required. */
240 if (CALL_P (insn)
241 && (INSN_BB (elem) != INSN_BB (insn)))
242 return 0;
243 #endif
245 /* If we already have a dependency for ELEM, then we do not need to
246 do anything. Avoiding the list walk below can cut compile times
247 dramatically for some code. */
248 if (true_dependency_cache != NULL)
250 enum reg_note present_dep_type = 0;
252 gcc_assert (anti_dependency_cache);
253 gcc_assert (output_dependency_cache);
254 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
255 INSN_LUID (elem)))
256 /* Do nothing (present_set_type is already 0). */
258 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
259 INSN_LUID (elem)))
260 present_dep_type = REG_DEP_ANTI;
261 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
262 INSN_LUID (elem)))
263 present_dep_type = REG_DEP_OUTPUT;
264 else
265 present_p = 0;
266 if (present_p && (int) dep_type >= (int) present_dep_type)
267 return 0;
269 #endif
271 /* Check that we don't already have this dependence. */
272 if (present_p)
273 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
274 if (XEXP (link, 0) == elem)
276 #ifdef INSN_SCHEDULING
277 /* Clear corresponding cache entry because type of the link
278 may be changed. */
279 if (true_dependency_cache != NULL)
281 enum reg_note kind = REG_NOTE_KIND (link);
282 switch (kind)
284 case REG_DEP_ANTI:
285 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
286 INSN_LUID (elem));
287 break;
288 case REG_DEP_OUTPUT:
289 gcc_assert (output_dependency_cache);
290 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
291 INSN_LUID (elem));
292 break;
293 default:
294 gcc_unreachable ();
297 #endif
299 /* If this is a more restrictive type of dependence than the existing
300 one, then change the existing dependence to this type. */
301 if ((int) dep_type < (int) REG_NOTE_KIND (link))
302 PUT_REG_NOTE_KIND (link, dep_type);
304 #ifdef INSN_SCHEDULING
305 /* If we are adding a dependency to INSN's LOG_LINKs, then
306 note that in the bitmap caches of dependency information. */
307 if (true_dependency_cache != NULL)
309 if ((int) REG_NOTE_KIND (link) == 0)
310 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
311 INSN_LUID (elem));
312 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
313 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
314 INSN_LUID (elem));
315 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
316 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
317 INSN_LUID (elem));
319 #endif
320 return 0;
322 /* Might want to check one level of transitivity to save conses. */
324 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
325 LOG_LINKS (insn) = link;
327 /* Insn dependency, not data dependency. */
328 PUT_REG_NOTE_KIND (link, dep_type);
330 #ifdef INSN_SCHEDULING
331 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
332 in the bitmap caches of dependency information. */
333 if (true_dependency_cache != NULL)
335 if ((int) dep_type == 0)
336 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
337 else if (dep_type == REG_DEP_ANTI)
338 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
339 else if (dep_type == REG_DEP_OUTPUT)
340 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
342 #endif
343 return 1;
346 /* A convenience wrapper to operate on an entire list. */
348 static void
349 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
351 for (; list; list = XEXP (list, 1))
353 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
354 add_dependence (insn, XEXP (list, 0), dep_type);
358 /* Similar, but free *LISTP at the same time. */
360 static void
361 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
362 enum reg_note dep_type)
364 rtx list, next;
365 for (list = *listp, *listp = NULL; list ; list = next)
367 next = XEXP (list, 1);
368 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
369 add_dependence (insn, XEXP (list, 0), dep_type);
370 free_INSN_LIST_node (list);
374 /* Clear all dependencies for an insn. */
376 static void
377 delete_all_dependences (rtx insn)
379 /* Clear caches, if they exist, as well as free the dependence. */
381 #ifdef INSN_SCHEDULING
382 if (true_dependency_cache != NULL)
384 bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
385 bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
386 bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
388 #endif
390 free_INSN_LIST_list (&LOG_LINKS (insn));
393 /* All insns in a scheduling group except the first should only have
394 dependencies on the previous insn in the group. So we find the
395 first instruction in the scheduling group by walking the dependence
396 chains backwards. Then we add the dependencies for the group to
397 the previous nonnote insn. */
399 static void
400 fixup_sched_groups (rtx insn)
402 rtx link, prev_nonnote;
404 for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
406 rtx i = insn;
409 i = prev_nonnote_insn (i);
411 if (XEXP (link, 0) == i)
412 goto next_link;
413 } while (SCHED_GROUP_P (i));
414 if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
415 add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
416 next_link:;
419 delete_all_dependences (insn);
421 prev_nonnote = prev_nonnote_insn (insn);
422 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
423 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
424 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
427 /* Process an insn's memory dependencies. There are four kinds of
428 dependencies:
430 (0) read dependence: read follows read
431 (1) true dependence: read follows write
432 (2) anti dependence: write follows read
433 (3) output dependence: write follows write
435 We are careful to build only dependencies which actually exist, and
436 use transitivity to avoid building too many links. */
438 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
439 The MEM is a memory reference contained within INSN, which we are saving
440 so that we can do memory aliasing on it. */
442 static void
443 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
444 rtx insn, rtx mem)
446 rtx link;
448 link = alloc_INSN_LIST (insn, *insn_list);
449 *insn_list = link;
451 if (current_sched_info->use_cselib)
453 mem = shallow_copy_rtx (mem);
454 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
456 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
457 *mem_list = link;
459 deps->pending_lists_length++;
462 /* Make a dependency between every memory reference on the pending lists
463 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
464 dependencies for a read operation, similarly with FOR_WRITE. */
466 static void
467 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
468 int for_write)
470 if (for_write)
472 add_dependence_list_and_free (insn, &deps->pending_read_insns, 0,
473 REG_DEP_ANTI);
474 free_EXPR_LIST_list (&deps->pending_read_mems);
477 add_dependence_list_and_free (insn, &deps->pending_write_insns, 0,
478 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
479 free_EXPR_LIST_list (&deps->pending_write_mems);
480 deps->pending_lists_length = 0;
482 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
483 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
484 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
485 deps->pending_flush_length = 1;
488 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
489 rtx, X, creating all dependencies generated by the write to the
490 destination of X, and reads of everything mentioned. */
492 static void
493 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
495 int regno;
496 rtx dest = XEXP (x, 0);
497 enum rtx_code code = GET_CODE (x);
499 if (dest == 0)
500 return;
502 if (GET_CODE (dest) == PARALLEL)
504 int i;
506 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
507 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
508 sched_analyze_1 (deps,
509 gen_rtx_CLOBBER (VOIDmode,
510 XEXP (XVECEXP (dest, 0, i), 0)),
511 insn);
513 if (GET_CODE (x) == SET)
514 sched_analyze_2 (deps, SET_SRC (x), insn);
515 return;
518 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
519 || GET_CODE (dest) == ZERO_EXTRACT)
521 if (GET_CODE (dest) == STRICT_LOW_PART
522 || GET_CODE (dest) == ZERO_EXTRACT
523 || read_modify_subreg_p (dest))
525 /* These both read and modify the result. We must handle
526 them as writes to get proper dependencies for following
527 instructions. We must handle them as reads to get proper
528 dependencies from this to previous instructions.
529 Thus we need to call sched_analyze_2. */
531 sched_analyze_2 (deps, XEXP (dest, 0), insn);
533 if (GET_CODE (dest) == ZERO_EXTRACT)
535 /* The second and third arguments are values read by this insn. */
536 sched_analyze_2 (deps, XEXP (dest, 1), insn);
537 sched_analyze_2 (deps, XEXP (dest, 2), insn);
539 dest = XEXP (dest, 0);
542 if (REG_P (dest))
544 regno = REGNO (dest);
546 #ifdef STACK_REGS
547 /* Treat all writes to a stack register as modifying the TOS. */
548 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
550 SET_REGNO_REG_SET (reg_pending_uses, FIRST_STACK_REG);
551 regno = FIRST_STACK_REG;
553 #endif
555 /* A hard reg in a wide mode may really be multiple registers.
556 If so, mark all of them just like the first. */
557 if (regno < FIRST_PSEUDO_REGISTER)
559 int i = hard_regno_nregs[regno][GET_MODE (dest)];
560 if (code == SET)
562 while (--i >= 0)
563 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
565 else
567 while (--i >= 0)
568 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
571 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
572 it does not reload. Ignore these as they have served their
573 purpose already. */
574 else if (regno >= deps->max_reg)
576 gcc_assert (GET_CODE (PATTERN (insn)) == USE
577 || GET_CODE (PATTERN (insn)) == CLOBBER);
579 else
581 if (code == SET)
582 SET_REGNO_REG_SET (reg_pending_sets, regno);
583 else
584 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
586 /* Pseudos that are REG_EQUIV to something may be replaced
587 by that during reloading. We need only add dependencies for
588 the address in the REG_EQUIV note. */
589 if (!reload_completed && get_reg_known_equiv_p (regno))
591 rtx t = get_reg_known_value (regno);
592 if (MEM_P (t))
593 sched_analyze_2 (deps, XEXP (t, 0), insn);
596 /* Don't let it cross a call after scheduling if it doesn't
597 already cross one. */
598 if (REG_N_CALLS_CROSSED (regno) == 0)
599 add_dependence_list (insn, deps->last_function_call, 1,
600 REG_DEP_ANTI);
603 else if (MEM_P (dest))
605 /* Writing memory. */
606 rtx t = dest;
608 if (current_sched_info->use_cselib)
610 t = shallow_copy_rtx (dest);
611 cselib_lookup (XEXP (t, 0), Pmode, 1);
612 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
614 t = canon_rtx (t);
616 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
618 /* Flush all pending reads and writes to prevent the pending lists
619 from getting any larger. Insn scheduling runs too slowly when
620 these lists get long. When compiling GCC with itself,
621 this flush occurs 8 times for sparc, and 10 times for m88k using
622 the default value of 32. */
623 flush_pending_lists (deps, insn, false, true);
625 else
627 rtx pending, pending_mem;
629 pending = deps->pending_read_insns;
630 pending_mem = deps->pending_read_mems;
631 while (pending)
633 if (anti_dependence (XEXP (pending_mem, 0), t)
634 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
635 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
637 pending = XEXP (pending, 1);
638 pending_mem = XEXP (pending_mem, 1);
641 pending = deps->pending_write_insns;
642 pending_mem = deps->pending_write_mems;
643 while (pending)
645 if (output_dependence (XEXP (pending_mem, 0), t)
646 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
647 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
649 pending = XEXP (pending, 1);
650 pending_mem = XEXP (pending_mem, 1);
653 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
654 REG_DEP_ANTI);
656 add_insn_mem_dependence (deps, &deps->pending_write_insns,
657 &deps->pending_write_mems, insn, dest);
659 sched_analyze_2 (deps, XEXP (dest, 0), insn);
662 /* Analyze reads. */
663 if (GET_CODE (x) == SET)
664 sched_analyze_2 (deps, SET_SRC (x), insn);
667 /* Analyze the uses of memory and registers in rtx X in INSN. */
669 static void
670 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
672 int i;
673 int j;
674 enum rtx_code code;
675 const char *fmt;
677 if (x == 0)
678 return;
680 code = GET_CODE (x);
682 switch (code)
684 case CONST_INT:
685 case CONST_DOUBLE:
686 case CONST_VECTOR:
687 case SYMBOL_REF:
688 case CONST:
689 case LABEL_REF:
690 /* Ignore constants. Note that we must handle CONST_DOUBLE here
691 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
692 this does not mean that this insn is using cc0. */
693 return;
695 #ifdef HAVE_cc0
696 case CC0:
697 /* User of CC0 depends on immediately preceding insn. */
698 SCHED_GROUP_P (insn) = 1;
699 /* Don't move CC0 setter to another block (it can set up the
700 same flag for previous CC0 users which is safe). */
701 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
702 return;
703 #endif
705 case REG:
707 int regno = REGNO (x);
709 #ifdef STACK_REGS
710 /* Treat all reads of a stack register as modifying the TOS. */
711 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
713 SET_REGNO_REG_SET (reg_pending_sets, FIRST_STACK_REG);
714 regno = FIRST_STACK_REG;
716 #endif
718 if (regno < FIRST_PSEUDO_REGISTER)
720 int i = hard_regno_nregs[regno][GET_MODE (x)];
721 while (--i >= 0)
722 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
724 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
725 it does not reload. Ignore these as they have served their
726 purpose already. */
727 else if (regno >= deps->max_reg)
729 gcc_assert (GET_CODE (PATTERN (insn)) == USE
730 || GET_CODE (PATTERN (insn)) == CLOBBER);
732 else
734 SET_REGNO_REG_SET (reg_pending_uses, regno);
736 /* Pseudos that are REG_EQUIV to something may be replaced
737 by that during reloading. We need only add dependencies for
738 the address in the REG_EQUIV note. */
739 if (!reload_completed && get_reg_known_equiv_p (regno))
741 rtx t = get_reg_known_value (regno);
742 if (MEM_P (t))
743 sched_analyze_2 (deps, XEXP (t, 0), insn);
746 /* If the register does not already cross any calls, then add this
747 insn to the sched_before_next_call list so that it will still
748 not cross calls after scheduling. */
749 if (REG_N_CALLS_CROSSED (regno) == 0)
750 deps->sched_before_next_call
751 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
753 return;
756 case MEM:
758 /* Reading memory. */
759 rtx u;
760 rtx pending, pending_mem;
761 rtx t = x;
763 if (current_sched_info->use_cselib)
765 t = shallow_copy_rtx (t);
766 cselib_lookup (XEXP (t, 0), Pmode, 1);
767 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
769 t = canon_rtx (t);
770 pending = deps->pending_read_insns;
771 pending_mem = deps->pending_read_mems;
772 while (pending)
774 if (read_dependence (XEXP (pending_mem, 0), t)
775 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
776 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
778 pending = XEXP (pending, 1);
779 pending_mem = XEXP (pending_mem, 1);
782 pending = deps->pending_write_insns;
783 pending_mem = deps->pending_write_mems;
784 while (pending)
786 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
787 t, rtx_varies_p)
788 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
789 add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
791 pending = XEXP (pending, 1);
792 pending_mem = XEXP (pending_mem, 1);
795 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
796 if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
797 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
799 /* Always add these dependencies to pending_reads, since
800 this insn may be followed by a write. */
801 add_insn_mem_dependence (deps, &deps->pending_read_insns,
802 &deps->pending_read_mems, insn, x);
804 /* Take advantage of tail recursion here. */
805 sched_analyze_2 (deps, XEXP (x, 0), insn);
806 return;
809 /* Force pending stores to memory in case a trap handler needs them. */
810 case TRAP_IF:
811 flush_pending_lists (deps, insn, true, false);
812 break;
814 case ASM_OPERANDS:
815 case ASM_INPUT:
816 case UNSPEC_VOLATILE:
818 /* Traditional and volatile asm instructions must be considered to use
819 and clobber all hard registers, all pseudo-registers and all of
820 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
822 Consider for instance a volatile asm that changes the fpu rounding
823 mode. An insn should not be moved across this even if it only uses
824 pseudo-regs because it might give an incorrectly rounded result. */
825 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
826 reg_pending_barrier = TRUE_BARRIER;
828 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
829 We can not just fall through here since then we would be confused
830 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
831 traditional asms unlike their normal usage. */
833 if (code == ASM_OPERANDS)
835 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
836 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
837 return;
839 break;
842 case PRE_DEC:
843 case POST_DEC:
844 case PRE_INC:
845 case POST_INC:
846 /* These both read and modify the result. We must handle them as writes
847 to get proper dependencies for following instructions. We must handle
848 them as reads to get proper dependencies from this to previous
849 instructions. Thus we need to pass them to both sched_analyze_1
850 and sched_analyze_2. We must call sched_analyze_2 first in order
851 to get the proper antecedent for the read. */
852 sched_analyze_2 (deps, XEXP (x, 0), insn);
853 sched_analyze_1 (deps, x, insn);
854 return;
856 case POST_MODIFY:
857 case PRE_MODIFY:
858 /* op0 = op0 + op1 */
859 sched_analyze_2 (deps, XEXP (x, 0), insn);
860 sched_analyze_2 (deps, XEXP (x, 1), insn);
861 sched_analyze_1 (deps, x, insn);
862 return;
864 default:
865 break;
868 /* Other cases: walk the insn. */
869 fmt = GET_RTX_FORMAT (code);
870 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
872 if (fmt[i] == 'e')
873 sched_analyze_2 (deps, XEXP (x, i), insn);
874 else if (fmt[i] == 'E')
875 for (j = 0; j < XVECLEN (x, i); j++)
876 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
880 /* Analyze an INSN with pattern X to find all dependencies. */
882 static void
883 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
885 RTX_CODE code = GET_CODE (x);
886 rtx link;
887 unsigned i;
888 reg_set_iterator rsi;
890 if (code == COND_EXEC)
892 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
894 /* ??? Should be recording conditions so we reduce the number of
895 false dependencies. */
896 x = COND_EXEC_CODE (x);
897 code = GET_CODE (x);
899 if (code == SET || code == CLOBBER)
901 sched_analyze_1 (deps, x, insn);
903 /* Bare clobber insns are used for letting life analysis, reg-stack
904 and others know that a value is dead. Depend on the last call
905 instruction so that reg-stack won't get confused. */
906 if (code == CLOBBER)
907 add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
909 else if (code == PARALLEL)
911 for (i = XVECLEN (x, 0); i--;)
913 rtx sub = XVECEXP (x, 0, i);
914 code = GET_CODE (sub);
916 if (code == COND_EXEC)
918 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
919 sub = COND_EXEC_CODE (sub);
920 code = GET_CODE (sub);
922 if (code == SET || code == CLOBBER)
923 sched_analyze_1 (deps, sub, insn);
924 else
925 sched_analyze_2 (deps, sub, insn);
928 else
929 sched_analyze_2 (deps, x, insn);
931 /* Mark registers CLOBBERED or used by called function. */
932 if (CALL_P (insn))
934 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
936 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
937 sched_analyze_1 (deps, XEXP (link, 0), insn);
938 else
939 sched_analyze_2 (deps, XEXP (link, 0), insn);
941 if (find_reg_note (insn, REG_SETJMP, NULL))
942 reg_pending_barrier = MOVE_BARRIER;
945 if (JUMP_P (insn))
947 rtx next;
948 next = next_nonnote_insn (insn);
949 if (next && BARRIER_P (next))
950 reg_pending_barrier = TRUE_BARRIER;
951 else
953 rtx pending, pending_mem;
954 regset_head tmp_uses, tmp_sets;
955 INIT_REG_SET (&tmp_uses);
956 INIT_REG_SET (&tmp_sets);
958 (*current_sched_info->compute_jump_reg_dependencies)
959 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
960 /* Make latency of jump equal to 0 by using anti-dependence. */
961 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
963 struct deps_reg *reg_last = &deps->reg_last[i];
964 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
965 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
966 reg_last->uses_length++;
967 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
969 IOR_REG_SET (reg_pending_sets, &tmp_sets);
971 CLEAR_REG_SET (&tmp_uses);
972 CLEAR_REG_SET (&tmp_sets);
974 /* All memory writes and volatile reads must happen before the
975 jump. Non-volatile reads must happen before the jump iff
976 the result is needed by the above register used mask. */
978 pending = deps->pending_write_insns;
979 pending_mem = deps->pending_write_mems;
980 while (pending)
982 if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
983 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
984 pending = XEXP (pending, 1);
985 pending_mem = XEXP (pending_mem, 1);
988 pending = deps->pending_read_insns;
989 pending_mem = deps->pending_read_mems;
990 while (pending)
992 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
993 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
994 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
995 pending = XEXP (pending, 1);
996 pending_mem = XEXP (pending_mem, 1);
999 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1000 REG_DEP_ANTI);
1004 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
1005 block, then we must be sure that no instructions are scheduled across it.
1006 Otherwise, the reg_n_refs info (which depends on loop_depth) would
1007 become incorrect. */
1008 if (loop_notes)
1010 rtx link;
1012 /* Update loop_notes with any notes from this insn. */
1013 link = loop_notes;
1014 while (XEXP (link, 1))
1016 gcc_assert (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
1017 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END);
1019 reg_pending_barrier = MOVE_BARRIER;
1020 link = XEXP (link, 1);
1022 XEXP (link, 1) = REG_NOTES (insn);
1023 REG_NOTES (insn) = loop_notes;
1026 /* If this instruction can throw an exception, then moving it changes
1027 where block boundaries fall. This is mighty confusing elsewhere.
1028 Therefore, prevent such an instruction from being moved. */
1029 if (can_throw_internal (insn))
1030 reg_pending_barrier = MOVE_BARRIER;
1032 /* Add dependencies if a scheduling barrier was found. */
1033 if (reg_pending_barrier)
1035 /* In the case of barrier the most added dependencies are not
1036 real, so we use anti-dependence here. */
1037 if (sched_get_condition (insn))
1039 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1041 struct deps_reg *reg_last = &deps->reg_last[i];
1042 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1043 add_dependence_list
1044 (insn, reg_last->sets, 0,
1045 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1046 add_dependence_list
1047 (insn, reg_last->clobbers, 0,
1048 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1051 else
1053 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1055 struct deps_reg *reg_last = &deps->reg_last[i];
1056 add_dependence_list_and_free (insn, &reg_last->uses, 0,
1057 REG_DEP_ANTI);
1058 add_dependence_list_and_free
1059 (insn, &reg_last->sets, 0,
1060 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1061 add_dependence_list_and_free
1062 (insn, &reg_last->clobbers, 0,
1063 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1064 reg_last->uses_length = 0;
1065 reg_last->clobbers_length = 0;
1069 for (i = 0; i < (unsigned)deps->max_reg; i++)
1071 struct deps_reg *reg_last = &deps->reg_last[i];
1072 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1073 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1076 flush_pending_lists (deps, insn, true, true);
1077 CLEAR_REG_SET (&deps->reg_conditional_sets);
1078 reg_pending_barrier = NOT_A_BARRIER;
1080 else
1082 /* If the current insn is conditional, we can't free any
1083 of the lists. */
1084 if (sched_get_condition (insn))
1086 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1088 struct deps_reg *reg_last = &deps->reg_last[i];
1089 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1090 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1091 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1092 reg_last->uses_length++;
1094 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1096 struct deps_reg *reg_last = &deps->reg_last[i];
1097 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1098 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1099 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1100 reg_last->clobbers_length++;
1102 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1104 struct deps_reg *reg_last = &deps->reg_last[i];
1105 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1106 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
1107 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1108 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1109 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1112 else
1114 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1116 struct deps_reg *reg_last = &deps->reg_last[i];
1117 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1118 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1119 reg_last->uses_length++;
1120 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1122 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1124 struct deps_reg *reg_last = &deps->reg_last[i];
1125 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1126 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1128 add_dependence_list_and_free (insn, &reg_last->sets, 0,
1129 REG_DEP_OUTPUT);
1130 add_dependence_list_and_free (insn, &reg_last->uses, 0,
1131 REG_DEP_ANTI);
1132 add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1133 REG_DEP_OUTPUT);
1134 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1135 reg_last->clobbers_length = 0;
1136 reg_last->uses_length = 0;
1138 else
1140 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1141 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1143 reg_last->clobbers_length++;
1144 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1146 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1148 struct deps_reg *reg_last = &deps->reg_last[i];
1149 add_dependence_list_and_free (insn, &reg_last->sets, 0,
1150 REG_DEP_OUTPUT);
1151 add_dependence_list_and_free (insn, &reg_last->clobbers, 0,
1152 REG_DEP_OUTPUT);
1153 add_dependence_list_and_free (insn, &reg_last->uses, 0,
1154 REG_DEP_ANTI);
1155 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1156 reg_last->uses_length = 0;
1157 reg_last->clobbers_length = 0;
1158 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1162 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1163 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1164 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1166 CLEAR_REG_SET (reg_pending_uses);
1167 CLEAR_REG_SET (reg_pending_clobbers);
1168 CLEAR_REG_SET (reg_pending_sets);
1170 /* If we are currently in a libcall scheduling group, then mark the
1171 current insn as being in a scheduling group and that it can not
1172 be moved into a different basic block. */
1174 if (deps->libcall_block_tail_insn)
1176 SCHED_GROUP_P (insn) = 1;
1177 CANT_MOVE (insn) = 1;
1180 /* If a post-call group is still open, see if it should remain so.
1181 This insn must be a simple move of a hard reg to a pseudo or
1182 vice-versa.
1184 We must avoid moving these insns for correctness on
1185 SMALL_REGISTER_CLASS machines, and for special registers like
1186 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1187 hard regs for all targets. */
1189 if (deps->in_post_call_group_p)
1191 rtx tmp, set = single_set (insn);
1192 int src_regno, dest_regno;
1194 if (set == NULL)
1195 goto end_call_group;
1197 tmp = SET_DEST (set);
1198 if (GET_CODE (tmp) == SUBREG)
1199 tmp = SUBREG_REG (tmp);
1200 if (REG_P (tmp))
1201 dest_regno = REGNO (tmp);
1202 else
1203 goto end_call_group;
1205 tmp = SET_SRC (set);
1206 if (GET_CODE (tmp) == SUBREG)
1207 tmp = SUBREG_REG (tmp);
1208 if ((GET_CODE (tmp) == PLUS
1209 || GET_CODE (tmp) == MINUS)
1210 && REG_P (XEXP (tmp, 0))
1211 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1212 && dest_regno == STACK_POINTER_REGNUM)
1213 src_regno = STACK_POINTER_REGNUM;
1214 else if (REG_P (tmp))
1215 src_regno = REGNO (tmp);
1216 else
1217 goto end_call_group;
1219 if (src_regno < FIRST_PSEUDO_REGISTER
1220 || dest_regno < FIRST_PSEUDO_REGISTER)
1222 if (deps->in_post_call_group_p == post_call_initial)
1223 deps->in_post_call_group_p = post_call;
1225 SCHED_GROUP_P (insn) = 1;
1226 CANT_MOVE (insn) = 1;
1228 else
1230 end_call_group:
1231 deps->in_post_call_group_p = not_post_call;
1235 /* Fixup the dependencies in the sched group. */
1236 if (SCHED_GROUP_P (insn))
1237 fixup_sched_groups (insn);
1240 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1241 for every dependency. */
1243 void
1244 sched_analyze (struct deps *deps, rtx head, rtx tail)
1246 rtx insn;
1247 rtx loop_notes = 0;
1249 if (current_sched_info->use_cselib)
1250 cselib_init (true);
1252 /* Before reload, if the previous block ended in a call, show that
1253 we are inside a post-call group, so as to keep the lifetimes of
1254 hard registers correct. */
1255 if (! reload_completed && !LABEL_P (head))
1257 insn = prev_nonnote_insn (head);
1258 if (insn && CALL_P (insn))
1259 deps->in_post_call_group_p = post_call_initial;
1261 for (insn = head;; insn = NEXT_INSN (insn))
1263 rtx link, end_seq, r0, set;
1265 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1267 /* Clear out the stale LOG_LINKS from flow. */
1268 free_INSN_LIST_list (&LOG_LINKS (insn));
1270 /* Make each JUMP_INSN a scheduling barrier for memory
1271 references. */
1272 if (JUMP_P (insn))
1274 /* Keep the list a reasonable size. */
1275 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1276 flush_pending_lists (deps, insn, true, true);
1277 else
1278 deps->last_pending_memory_flush
1279 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1281 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1282 loop_notes = 0;
1284 else if (CALL_P (insn))
1286 int i;
1288 CANT_MOVE (insn) = 1;
1290 /* Clear out the stale LOG_LINKS from flow. */
1291 free_INSN_LIST_list (&LOG_LINKS (insn));
1293 if (find_reg_note (insn, REG_SETJMP, NULL))
1295 /* This is setjmp. Assume that all registers, not just
1296 hard registers, may be clobbered by this call. */
1297 reg_pending_barrier = MOVE_BARRIER;
1299 else
1301 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1302 /* A call may read and modify global register variables. */
1303 if (global_regs[i])
1305 SET_REGNO_REG_SET (reg_pending_sets, i);
1306 SET_REGNO_REG_SET (reg_pending_uses, i);
1308 /* Other call-clobbered hard regs may be clobbered.
1309 Since we only have a choice between 'might be clobbered'
1310 and 'definitely not clobbered', we must include all
1311 partly call-clobbered registers here. */
1312 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1313 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1314 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1315 /* We don't know what set of fixed registers might be used
1316 by the function, but it is certain that the stack pointer
1317 is among them, but be conservative. */
1318 else if (fixed_regs[i])
1319 SET_REGNO_REG_SET (reg_pending_uses, i);
1320 /* The frame pointer is normally not used by the function
1321 itself, but by the debugger. */
1322 /* ??? MIPS o32 is an exception. It uses the frame pointer
1323 in the macro expansion of jal but does not represent this
1324 fact in the call_insn rtl. */
1325 else if (i == FRAME_POINTER_REGNUM
1326 || (i == HARD_FRAME_POINTER_REGNUM
1327 && (! reload_completed || frame_pointer_needed)))
1328 SET_REGNO_REG_SET (reg_pending_uses, i);
1331 /* For each insn which shouldn't cross a call, add a dependence
1332 between that insn and this call insn. */
1333 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
1334 REG_DEP_ANTI);
1336 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1337 loop_notes = 0;
1339 /* In the absence of interprocedural alias analysis, we must flush
1340 all pending reads and writes, and start new dependencies starting
1341 from here. But only flush writes for constant calls (which may
1342 be passed a pointer to something we haven't written yet). */
1343 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1345 /* Remember the last function call for limiting lifetimes. */
1346 free_INSN_LIST_list (&deps->last_function_call);
1347 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1349 /* Before reload, begin a post-call group, so as to keep the
1350 lifetimes of hard registers correct. */
1351 if (! reload_completed)
1352 deps->in_post_call_group_p = post_call;
1355 /* EH_REGION insn notes can not appear until well after we complete
1356 scheduling. */
1357 if (NOTE_P (insn))
1358 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1359 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1361 /* See comments on reemit_notes as to why we do this.
1362 ??? Actually, the reemit_notes just say what is done, not why. */
1364 if (NOTE_P (insn)
1365 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1366 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
1368 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1369 GEN_INT (NOTE_LINE_NUMBER (insn)),
1370 loop_notes);
1371 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1374 if (current_sched_info->use_cselib)
1375 cselib_process_insn (insn);
1377 /* Now that we have completed handling INSN, check and see if it is
1378 a CLOBBER beginning a libcall block. If it is, record the
1379 end of the libcall sequence.
1381 We want to schedule libcall blocks as a unit before reload. While
1382 this restricts scheduling, it preserves the meaning of a libcall
1383 block.
1385 As a side effect, we may get better code due to decreased register
1386 pressure as well as less chance of a foreign insn appearing in
1387 a libcall block. */
1388 if (!reload_completed
1389 /* Note we may have nested libcall sequences. We only care about
1390 the outermost libcall sequence. */
1391 && deps->libcall_block_tail_insn == 0
1392 /* The sequence must start with a clobber of a register. */
1393 && NONJUMP_INSN_P (insn)
1394 && GET_CODE (PATTERN (insn)) == CLOBBER
1395 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1396 && REG_P (XEXP (PATTERN (insn), 0))
1397 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1398 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1399 && (end_seq = XEXP (link, 0)) != 0
1400 /* The insn referenced by the REG_LIBCALL note must be a
1401 simple nop copy with the same destination as the register
1402 mentioned in the clobber. */
1403 && (set = single_set (end_seq)) != 0
1404 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1405 /* And finally the insn referenced by the REG_LIBCALL must
1406 also contain a REG_EQUAL note and a REG_RETVAL note. */
1407 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1408 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1409 deps->libcall_block_tail_insn = XEXP (link, 0);
1411 /* If we have reached the end of a libcall block, then close the
1412 block. */
1413 if (deps->libcall_block_tail_insn == insn)
1414 deps->libcall_block_tail_insn = 0;
1416 if (insn == tail)
1418 if (current_sched_info->use_cselib)
1419 cselib_finish ();
1420 return;
1423 gcc_unreachable ();
1427 /* The following function adds forward dependence (FROM, TO) with
1428 given DEP_TYPE. The forward dependence should be not exist before. */
1430 void
1431 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1433 rtx new_link;
1435 #ifdef ENABLE_CHECKING
1436 /* If add_dependence is working properly there should never
1437 be notes, deleted insns or duplicates in the backward
1438 links. Thus we need not check for them here.
1440 However, if we have enabled checking we might as well go
1441 ahead and verify that add_dependence worked properly. */
1442 gcc_assert (!NOTE_P (from));
1443 gcc_assert (!INSN_DELETED_P (from));
1444 if (forward_dependency_cache)
1445 gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1446 INSN_LUID (to)));
1447 else
1448 gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1450 /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
1451 if (forward_dependency_cache != NULL)
1452 bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1453 INSN_LUID (to));
1454 #endif
1456 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1458 PUT_REG_NOTE_KIND (new_link, dep_type);
1460 INSN_DEPEND (from) = new_link;
1461 INSN_DEP_COUNT (to) += 1;
1464 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1465 dependences from LOG_LINKS to build forward dependences in
1466 INSN_DEPEND. */
1468 void
1469 compute_forward_dependences (rtx head, rtx tail)
1471 rtx insn, link;
1472 rtx next_tail;
1474 next_tail = NEXT_INSN (tail);
1475 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1477 if (! INSN_P (insn))
1478 continue;
1480 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1481 add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1485 /* Initialize variables for region data dependence analysis.
1486 n_bbs is the number of region blocks. */
1488 void
1489 init_deps (struct deps *deps)
1491 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1493 deps->max_reg = max_reg;
1494 deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1495 INIT_REG_SET (&deps->reg_last_in_use);
1496 INIT_REG_SET (&deps->reg_conditional_sets);
1498 deps->pending_read_insns = 0;
1499 deps->pending_read_mems = 0;
1500 deps->pending_write_insns = 0;
1501 deps->pending_write_mems = 0;
1502 deps->pending_lists_length = 0;
1503 deps->pending_flush_length = 0;
1504 deps->last_pending_memory_flush = 0;
1505 deps->last_function_call = 0;
1506 deps->sched_before_next_call = 0;
1507 deps->in_post_call_group_p = not_post_call;
1508 deps->libcall_block_tail_insn = 0;
1511 /* Free insn lists found in DEPS. */
1513 void
1514 free_deps (struct deps *deps)
1516 unsigned i;
1517 reg_set_iterator rsi;
1519 free_INSN_LIST_list (&deps->pending_read_insns);
1520 free_EXPR_LIST_list (&deps->pending_read_mems);
1521 free_INSN_LIST_list (&deps->pending_write_insns);
1522 free_EXPR_LIST_list (&deps->pending_write_mems);
1523 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1525 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1526 times. For a testcase with 42000 regs and 8000 small basic blocks,
1527 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1528 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1530 struct deps_reg *reg_last = &deps->reg_last[i];
1531 if (reg_last->uses)
1532 free_INSN_LIST_list (&reg_last->uses);
1533 if (reg_last->sets)
1534 free_INSN_LIST_list (&reg_last->sets);
1535 if (reg_last->clobbers)
1536 free_INSN_LIST_list (&reg_last->clobbers);
1538 CLEAR_REG_SET (&deps->reg_last_in_use);
1539 CLEAR_REG_SET (&deps->reg_conditional_sets);
1541 free (deps->reg_last);
1544 /* If it is profitable to use them, initialize caches for tracking
1545 dependency information. LUID is the number of insns to be scheduled,
1546 it is used in the estimate of profitability. */
1548 void
1549 init_dependency_caches (int luid)
1551 /* ?!? We could save some memory by computing a per-region luid mapping
1552 which could reduce both the number of vectors in the cache and the size
1553 of each vector. Instead we just avoid the cache entirely unless the
1554 average number of instructions in a basic block is very high. See
1555 the comment before the declaration of true_dependency_cache for
1556 what we consider "very high". */
1557 if (luid / n_basic_blocks > 100 * 5)
1559 int i;
1560 true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1561 anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1562 output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1563 #ifdef ENABLE_CHECKING
1564 forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1565 #endif
1566 for (i = 0; i < luid; i++)
1568 bitmap_initialize (&true_dependency_cache[i], 0);
1569 bitmap_initialize (&anti_dependency_cache[i], 0);
1570 bitmap_initialize (&output_dependency_cache[i], 0);
1571 #ifdef ENABLE_CHECKING
1572 bitmap_initialize (&forward_dependency_cache[i], 0);
1573 #endif
1575 cache_size = luid;
1579 /* Free the caches allocated in init_dependency_caches. */
1581 void
1582 free_dependency_caches (void)
1584 if (true_dependency_cache)
1586 int i;
1588 for (i = 0; i < cache_size; i++)
1590 bitmap_clear (&true_dependency_cache[i]);
1591 bitmap_clear (&anti_dependency_cache[i]);
1592 bitmap_clear (&output_dependency_cache[i]);
1593 #ifdef ENABLE_CHECKING
1594 bitmap_clear (&forward_dependency_cache[i]);
1595 #endif
1597 free (true_dependency_cache);
1598 true_dependency_cache = NULL;
1599 free (anti_dependency_cache);
1600 anti_dependency_cache = NULL;
1601 free (output_dependency_cache);
1602 output_dependency_cache = NULL;
1603 #ifdef ENABLE_CHECKING
1604 free (forward_dependency_cache);
1605 forward_dependency_cache = NULL;
1606 #endif
1610 /* Initialize some global variables needed by the dependency analysis
1611 code. */
1613 void
1614 init_deps_global (void)
1616 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
1617 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
1618 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
1619 reg_pending_barrier = NOT_A_BARRIER;
1622 /* Free everything used by the dependency analysis code. */
1624 void
1625 finish_deps_global (void)
1627 FREE_REG_SET (reg_pending_sets);
1628 FREE_REG_SET (reg_pending_clobbers);
1629 FREE_REG_SET (reg_pending_uses);