1 /* Instruction scheduling pass. This file computes dependencies between
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)
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
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
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
27 #include "coretypes.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
42 #include "sched-int.h"
48 static regset_head reg_pending_sets_head;
49 static regset_head reg_pending_clobbers_head;
50 static regset_head reg_pending_uses_head;
52 static regset reg_pending_sets;
53 static regset reg_pending_clobbers;
54 static regset reg_pending_uses;
56 /* The following enumeration values tell us what dependencies we
57 should use to implement the barrier. We use true-dependencies for
58 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
59 enum reg_pending_barrier_mode
66 static enum reg_pending_barrier_mode reg_pending_barrier;
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.
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.
77 Each insn has associated bitmaps for its dependencies. Each bitmap
78 has enough entries to represent a dependency on any other insn in
79 the insn chain. All bitmap for true dependencies cache is
80 allocated then the rest two ones are also allocated. */
81 static bitmap_head *true_dependency_cache;
82 static bitmap_head *anti_dependency_cache;
83 static bitmap_head *output_dependency_cache;
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
90 #ifdef ENABLE_CHECKING
91 static bitmap_head *forward_dependency_cache;
94 static int deps_may_trap_p (rtx);
95 static void add_dependence_list (rtx, rtx, enum reg_note);
96 static void add_dependence_list_and_free (rtx, rtx *, enum reg_note);
97 static void set_sched_group_p (rtx);
99 static void flush_pending_lists (struct deps *, rtx, int, int);
100 static void sched_analyze_1 (struct deps *, rtx, rtx);
101 static void sched_analyze_2 (struct deps *, rtx, rtx);
102 static void sched_analyze_insn (struct deps *, rtx, rtx, rtx);
104 static rtx get_condition (rtx);
105 static int conditions_mutex_p (rtx, rtx);
107 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
110 deps_may_trap_p (rtx mem)
112 rtx addr = XEXP (mem, 0);
114 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
116 rtx t = get_reg_known_value (REGNO (addr));
120 return rtx_addr_can_trap_p (addr);
123 /* Return the INSN_LIST containing INSN in LIST, or NULL
124 if LIST does not contain INSN. */
127 find_insn_list (rtx insn, rtx list)
131 if (XEXP (list, 0) == insn)
133 list = XEXP (list, 1);
138 /* Find the condition under which INSN is executed. */
141 get_condition (rtx insn)
143 rtx pat = PATTERN (insn);
149 if (GET_CODE (pat) == COND_EXEC)
150 return COND_EXEC_TEST (pat);
152 if (!any_condjump_p (insn) || !onlyjump_p (insn))
155 src = SET_SRC (pc_set (insn));
156 if (XEXP (src, 2) == pc_rtx)
157 return XEXP (src, 0);
158 else if (XEXP (src, 1) == pc_rtx)
160 rtx cond = XEXP (src, 0);
161 enum rtx_code revcode = reversed_comparison_code (cond, insn);
163 if (revcode == UNKNOWN)
165 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
172 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
175 conditions_mutex_p (rtx cond1, rtx cond2)
177 if (COMPARISON_P (cond1)
178 && COMPARISON_P (cond2)
179 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
180 && XEXP (cond1, 0) == XEXP (cond2, 0)
181 && XEXP (cond1, 1) == XEXP (cond2, 1))
186 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
187 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
188 type of dependence that this link represents. The function returns
189 nonzero if a new entry has been added to insn's LOG_LINK. */
192 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
198 /* Don't depend an insn on itself. */
202 /* We can get a dependency on deleted insns due to optimizations in
203 the register allocation and reloading or due to splitting. Any
204 such dependency is useless and can be ignored. */
208 /* flow.c doesn't handle conditional lifetimes entirely correctly;
209 calls mess up the conditional lifetimes. */
210 /* ??? add_dependence is the wrong place to be eliding dependencies,
211 as that forgets that the condition expressions themselves may
213 if (!CALL_P (insn) && !CALL_P (elem))
215 cond1 = get_condition (insn);
216 cond2 = get_condition (elem);
218 && conditions_mutex_p (cond1, cond2)
219 /* Make sure first instruction doesn't affect condition of second
220 instruction if switched. */
221 && !modified_in_p (cond1, elem)
222 /* Make sure second instruction doesn't affect condition of first
223 instruction if switched. */
224 && !modified_in_p (cond2, insn))
229 #ifdef INSN_SCHEDULING
230 /* ??? No good way to tell from here whether we're doing interblock
231 scheduling. Possibly add another callback. */
233 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
234 No need for interblock dependences with calls, since
235 calls are not moved between blocks. Note: the edge where
236 elem is a CALL is still required. */
238 && (INSN_BB (elem) != INSN_BB (insn)))
242 /* If we already have a dependency for ELEM, then we do not need to
243 do anything. Avoiding the list walk below can cut compile times
244 dramatically for some code. */
245 if (true_dependency_cache != NULL)
247 enum reg_note present_dep_type = 0;
249 if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
251 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
253 /* Do nothing (present_set_type is already 0). */
255 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
257 present_dep_type = REG_DEP_ANTI;
258 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
260 present_dep_type = REG_DEP_OUTPUT;
263 if (present_p && (int) dep_type >= (int) present_dep_type)
268 /* Check that we don't already have this dependence. */
270 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
271 if (XEXP (link, 0) == elem)
273 #ifdef INSN_SCHEDULING
274 /* Clear corresponding cache entry because type of the link
276 if (true_dependency_cache != NULL)
278 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
279 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
281 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
282 && output_dependency_cache)
283 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
290 /* If this is a more restrictive type of dependence than the existing
291 one, then change the existing dependence to this type. */
292 if ((int) dep_type < (int) REG_NOTE_KIND (link))
293 PUT_REG_NOTE_KIND (link, dep_type);
295 #ifdef INSN_SCHEDULING
296 /* If we are adding a dependency to INSN's LOG_LINKs, then
297 note that in the bitmap caches of dependency information. */
298 if (true_dependency_cache != NULL)
300 if ((int) REG_NOTE_KIND (link) == 0)
301 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
303 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
304 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
306 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
307 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
313 /* Might want to check one level of transitivity to save conses. */
315 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
316 LOG_LINKS (insn) = link;
318 /* Insn dependency, not data dependency. */
319 PUT_REG_NOTE_KIND (link, dep_type);
321 #ifdef INSN_SCHEDULING
322 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
323 in the bitmap caches of dependency information. */
324 if (true_dependency_cache != NULL)
326 if ((int) dep_type == 0)
327 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
328 else if (dep_type == REG_DEP_ANTI)
329 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
330 else if (dep_type == REG_DEP_OUTPUT)
331 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
337 /* A convenience wrapper to operate on an entire list. */
340 add_dependence_list (rtx insn, rtx list, enum reg_note dep_type)
342 for (; list; list = XEXP (list, 1))
343 add_dependence (insn, XEXP (list, 0), dep_type);
346 /* Similar, but free *LISTP at the same time. */
349 add_dependence_list_and_free (rtx insn, rtx *listp, enum reg_note dep_type)
352 for (list = *listp, *listp = NULL; list ; list = next)
354 next = XEXP (list, 1);
355 add_dependence (insn, XEXP (list, 0), dep_type);
356 free_INSN_LIST_node (list);
360 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
361 goes along with that. */
364 set_sched_group_p (rtx insn)
368 SCHED_GROUP_P (insn) = 1;
370 prev = prev_nonnote_insn (insn);
371 add_dependence (insn, prev, REG_DEP_ANTI);
374 /* Process an insn's memory dependencies. There are four kinds of
377 (0) read dependence: read follows read
378 (1) true dependence: read follows write
379 (2) anti dependence: write follows read
380 (3) output dependence: write follows write
382 We are careful to build only dependencies which actually exist, and
383 use transitivity to avoid building too many links. */
385 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
386 The MEM is a memory reference contained within INSN, which we are saving
387 so that we can do memory aliasing on it. */
390 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
395 link = alloc_INSN_LIST (insn, *insn_list);
398 if (current_sched_info->use_cselib)
400 mem = shallow_copy_rtx (mem);
401 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
403 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
406 deps->pending_lists_length++;
409 /* Make a dependency between every memory reference on the pending lists
410 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
411 dependencies for a read operation, similarly with FOR_WRITE. */
414 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
419 add_dependence_list_and_free (insn, &deps->pending_read_insns,
421 free_EXPR_LIST_list (&deps->pending_read_mems);
424 add_dependence_list_and_free (insn, &deps->pending_write_insns,
425 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
426 free_EXPR_LIST_list (&deps->pending_write_mems);
427 deps->pending_lists_length = 0;
429 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
430 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
431 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
432 deps->pending_flush_length = 1;
435 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
436 rtx, X, creating all dependencies generated by the write to the
437 destination of X, and reads of everything mentioned. */
440 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
443 rtx dest = XEXP (x, 0);
444 enum rtx_code code = GET_CODE (x);
449 if (GET_CODE (dest) == PARALLEL)
453 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
454 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
455 sched_analyze_1 (deps,
456 gen_rtx_CLOBBER (VOIDmode,
457 XEXP (XVECEXP (dest, 0, i), 0)),
460 if (GET_CODE (x) == SET)
461 sched_analyze_2 (deps, SET_SRC (x), insn);
465 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
466 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
468 if (GET_CODE (dest) == STRICT_LOW_PART
469 || GET_CODE (dest) == ZERO_EXTRACT
470 || GET_CODE (dest) == SIGN_EXTRACT
471 || read_modify_subreg_p (dest))
473 /* These both read and modify the result. We must handle
474 them as writes to get proper dependencies for following
475 instructions. We must handle them as reads to get proper
476 dependencies from this to previous instructions.
477 Thus we need to call sched_analyze_2. */
479 sched_analyze_2 (deps, XEXP (dest, 0), insn);
481 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
483 /* The second and third arguments are values read by this insn. */
484 sched_analyze_2 (deps, XEXP (dest, 1), insn);
485 sched_analyze_2 (deps, XEXP (dest, 2), insn);
487 dest = XEXP (dest, 0);
492 regno = REGNO (dest);
494 /* A hard reg in a wide mode may really be multiple registers.
495 If so, mark all of them just like the first. */
496 if (regno < FIRST_PSEUDO_REGISTER)
498 int i = hard_regno_nregs[regno][GET_MODE (dest)];
502 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
507 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
510 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
511 it does not reload. Ignore these as they have served their
513 else if (regno >= deps->max_reg)
515 if (GET_CODE (PATTERN (insn)) != USE
516 && GET_CODE (PATTERN (insn)) != CLOBBER)
522 SET_REGNO_REG_SET (reg_pending_sets, regno);
524 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
526 /* Pseudos that are REG_EQUIV to something may be replaced
527 by that during reloading. We need only add dependencies for
528 the address in the REG_EQUIV note. */
529 if (!reload_completed && get_reg_known_equiv_p (regno))
531 rtx t = get_reg_known_value (regno);
533 sched_analyze_2 (deps, XEXP (t, 0), insn);
536 /* Don't let it cross a call after scheduling if it doesn't
537 already cross one. */
538 if (REG_N_CALLS_CROSSED (regno) == 0)
539 add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
542 else if (MEM_P (dest))
544 /* Writing memory. */
547 if (current_sched_info->use_cselib)
549 t = shallow_copy_rtx (dest);
550 cselib_lookup (XEXP (t, 0), Pmode, 1);
551 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
555 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
557 /* Flush all pending reads and writes to prevent the pending lists
558 from getting any larger. Insn scheduling runs too slowly when
559 these lists get long. When compiling GCC with itself,
560 this flush occurs 8 times for sparc, and 10 times for m88k using
561 the default value of 32. */
562 flush_pending_lists (deps, insn, false, true);
566 rtx pending, pending_mem;
568 pending = deps->pending_read_insns;
569 pending_mem = deps->pending_read_mems;
572 if (anti_dependence (XEXP (pending_mem, 0), t))
573 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
575 pending = XEXP (pending, 1);
576 pending_mem = XEXP (pending_mem, 1);
579 pending = deps->pending_write_insns;
580 pending_mem = deps->pending_write_mems;
583 if (output_dependence (XEXP (pending_mem, 0), t))
584 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
586 pending = XEXP (pending, 1);
587 pending_mem = XEXP (pending_mem, 1);
590 add_dependence_list (insn, deps->last_pending_memory_flush,
593 add_insn_mem_dependence (deps, &deps->pending_write_insns,
594 &deps->pending_write_mems, insn, dest);
596 sched_analyze_2 (deps, XEXP (dest, 0), insn);
600 if (GET_CODE (x) == SET)
601 sched_analyze_2 (deps, SET_SRC (x), insn);
604 /* Analyze the uses of memory and registers in rtx X in INSN. */
607 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
627 /* Ignore constants. Note that we must handle CONST_DOUBLE here
628 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
629 this does not mean that this insn is using cc0. */
634 /* User of CC0 depends on immediately preceding insn. */
635 set_sched_group_p (insn);
636 /* Don't move CC0 setter to another block (it can set up the
637 same flag for previous CC0 users which is safe). */
638 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
644 int regno = REGNO (x);
645 if (regno < FIRST_PSEUDO_REGISTER)
647 int i = hard_regno_nregs[regno][GET_MODE (x)];
649 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
651 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
652 it does not reload. Ignore these as they have served their
654 else if (regno >= deps->max_reg)
656 if (GET_CODE (PATTERN (insn)) != USE
657 && GET_CODE (PATTERN (insn)) != CLOBBER)
662 SET_REGNO_REG_SET (reg_pending_uses, regno);
664 /* Pseudos that are REG_EQUIV to something may be replaced
665 by that during reloading. We need only add dependencies for
666 the address in the REG_EQUIV note. */
667 if (!reload_completed && get_reg_known_equiv_p (regno))
669 rtx t = get_reg_known_value (regno);
671 sched_analyze_2 (deps, XEXP (t, 0), insn);
674 /* If the register does not already cross any calls, then add this
675 insn to the sched_before_next_call list so that it will still
676 not cross calls after scheduling. */
677 if (REG_N_CALLS_CROSSED (regno) == 0)
678 deps->sched_before_next_call
679 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
686 /* Reading memory. */
688 rtx pending, pending_mem;
691 if (current_sched_info->use_cselib)
693 t = shallow_copy_rtx (t);
694 cselib_lookup (XEXP (t, 0), Pmode, 1);
695 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
698 pending = deps->pending_read_insns;
699 pending_mem = deps->pending_read_mems;
702 if (read_dependence (XEXP (pending_mem, 0), t))
703 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
705 pending = XEXP (pending, 1);
706 pending_mem = XEXP (pending_mem, 1);
709 pending = deps->pending_write_insns;
710 pending_mem = deps->pending_write_mems;
713 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
715 add_dependence (insn, XEXP (pending, 0), 0);
717 pending = XEXP (pending, 1);
718 pending_mem = XEXP (pending_mem, 1);
721 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
722 if (!JUMP_P (XEXP (u, 0))
723 || deps_may_trap_p (x))
724 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
726 /* Always add these dependencies to pending_reads, since
727 this insn may be followed by a write. */
728 add_insn_mem_dependence (deps, &deps->pending_read_insns,
729 &deps->pending_read_mems, insn, x);
731 /* Take advantage of tail recursion here. */
732 sched_analyze_2 (deps, XEXP (x, 0), insn);
736 /* Force pending stores to memory in case a trap handler needs them. */
738 flush_pending_lists (deps, insn, true, false);
743 case UNSPEC_VOLATILE:
745 /* Traditional and volatile asm instructions must be considered to use
746 and clobber all hard registers, all pseudo-registers and all of
747 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
749 Consider for instance a volatile asm that changes the fpu rounding
750 mode. An insn should not be moved across this even if it only uses
751 pseudo-regs because it might give an incorrectly rounded result. */
752 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
753 reg_pending_barrier = TRUE_BARRIER;
755 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
756 We can not just fall through here since then we would be confused
757 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
758 traditional asms unlike their normal usage. */
760 if (code == ASM_OPERANDS)
762 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
763 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
773 /* These both read and modify the result. We must handle them as writes
774 to get proper dependencies for following instructions. We must handle
775 them as reads to get proper dependencies from this to previous
776 instructions. Thus we need to pass them to both sched_analyze_1
777 and sched_analyze_2. We must call sched_analyze_2 first in order
778 to get the proper antecedent for the read. */
779 sched_analyze_2 (deps, XEXP (x, 0), insn);
780 sched_analyze_1 (deps, x, insn);
785 /* op0 = op0 + op1 */
786 sched_analyze_2 (deps, XEXP (x, 0), insn);
787 sched_analyze_2 (deps, XEXP (x, 1), insn);
788 sched_analyze_1 (deps, x, insn);
795 /* Other cases: walk the insn. */
796 fmt = GET_RTX_FORMAT (code);
797 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
800 sched_analyze_2 (deps, XEXP (x, i), insn);
801 else if (fmt[i] == 'E')
802 for (j = 0; j < XVECLEN (x, i); j++)
803 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
807 /* Analyze an INSN with pattern X to find all dependencies. */
810 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
812 RTX_CODE code = GET_CODE (x);
816 if (code == COND_EXEC)
818 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
820 /* ??? Should be recording conditions so we reduce the number of
821 false dependencies. */
822 x = COND_EXEC_CODE (x);
825 if (code == SET || code == CLOBBER)
827 sched_analyze_1 (deps, x, insn);
829 /* Bare clobber insns are used for letting life analysis, reg-stack
830 and others know that a value is dead. Depend on the last call
831 instruction so that reg-stack won't get confused. */
833 add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
835 else if (code == PARALLEL)
838 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
840 rtx sub = XVECEXP (x, 0, i);
841 code = GET_CODE (sub);
843 if (code == COND_EXEC)
845 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
846 sub = COND_EXEC_CODE (sub);
847 code = GET_CODE (sub);
849 if (code == SET || code == CLOBBER)
850 sched_analyze_1 (deps, sub, insn);
852 sched_analyze_2 (deps, sub, insn);
856 sched_analyze_2 (deps, x, insn);
858 /* Mark registers CLOBBERED or used by called function. */
861 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
863 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
864 sched_analyze_1 (deps, XEXP (link, 0), insn);
866 sched_analyze_2 (deps, XEXP (link, 0), insn);
868 if (find_reg_note (insn, REG_SETJMP, NULL))
869 reg_pending_barrier = MOVE_BARRIER;
875 next = next_nonnote_insn (insn);
876 if (next && BARRIER_P (next))
877 reg_pending_barrier = TRUE_BARRIER;
880 rtx pending, pending_mem;
881 regset_head tmp_uses, tmp_sets;
882 INIT_REG_SET (&tmp_uses);
883 INIT_REG_SET (&tmp_sets);
885 (*current_sched_info->compute_jump_reg_dependencies)
886 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
887 /* Make latency of jump equal to 0 by using anti-dependence. */
888 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i,
890 struct deps_reg *reg_last = &deps->reg_last[i];
891 add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
892 add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
893 reg_last->uses_length++;
894 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
896 IOR_REG_SET (reg_pending_sets, &tmp_sets);
898 CLEAR_REG_SET (&tmp_uses);
899 CLEAR_REG_SET (&tmp_sets);
901 /* All memory writes and volatile reads must happen before the
902 jump. Non-volatile reads must happen before the jump iff
903 the result is needed by the above register used mask. */
905 pending = deps->pending_write_insns;
906 pending_mem = deps->pending_write_mems;
909 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
910 pending = XEXP (pending, 1);
911 pending_mem = XEXP (pending_mem, 1);
914 pending = deps->pending_read_insns;
915 pending_mem = deps->pending_read_mems;
918 if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
919 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
920 pending = XEXP (pending, 1);
921 pending_mem = XEXP (pending_mem, 1);
924 add_dependence_list (insn, deps->last_pending_memory_flush,
929 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
930 block, then we must be sure that no instructions are scheduled across it.
931 Otherwise, the reg_n_refs info (which depends on loop_depth) would
937 /* Update loop_notes with any notes from this insn. Also determine
938 if any of the notes on the list correspond to instruction scheduling
939 barriers (loop, eh & setjmp notes, but not range notes). */
941 while (XEXP (link, 1))
943 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
944 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
945 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
946 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
947 reg_pending_barrier = MOVE_BARRIER;
949 link = XEXP (link, 1);
951 XEXP (link, 1) = REG_NOTES (insn);
952 REG_NOTES (insn) = loop_notes;
955 /* If this instruction can throw an exception, then moving it changes
956 where block boundaries fall. This is mighty confusing elsewhere.
957 Therefore, prevent such an instruction from being moved. */
958 if (can_throw_internal (insn))
959 reg_pending_barrier = MOVE_BARRIER;
961 /* Add dependencies if a scheduling barrier was found. */
962 if (reg_pending_barrier)
964 /* In the case of barrier the most added dependencies are not
965 real, so we use anti-dependence here. */
966 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
968 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
970 struct deps_reg *reg_last = &deps->reg_last[i];
971 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
973 (insn, reg_last->sets,
974 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
976 (insn, reg_last->clobbers,
977 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
982 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
984 struct deps_reg *reg_last = &deps->reg_last[i];
985 add_dependence_list_and_free (insn, ®_last->uses,
987 add_dependence_list_and_free
988 (insn, ®_last->sets,
989 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
990 add_dependence_list_and_free
991 (insn, ®_last->clobbers,
992 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
993 reg_last->uses_length = 0;
994 reg_last->clobbers_length = 0;
998 for (i = 0; i < deps->max_reg; i++)
1000 struct deps_reg *reg_last = &deps->reg_last[i];
1001 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1002 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1005 flush_pending_lists (deps, insn, true, true);
1006 CLEAR_REG_SET (&deps->reg_conditional_sets);
1007 reg_pending_barrier = NOT_A_BARRIER;
1011 /* If the current insn is conditional, we can't free any
1013 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1015 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1017 struct deps_reg *reg_last = &deps->reg_last[i];
1018 add_dependence_list (insn, reg_last->sets, 0);
1019 add_dependence_list (insn, reg_last->clobbers, 0);
1020 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1021 reg_last->uses_length++;
1023 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1025 struct deps_reg *reg_last = &deps->reg_last[i];
1026 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1027 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1028 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1029 reg_last->clobbers_length++;
1031 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1033 struct deps_reg *reg_last = &deps->reg_last[i];
1034 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1035 add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1036 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1037 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1038 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1043 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1045 struct deps_reg *reg_last = &deps->reg_last[i];
1046 add_dependence_list (insn, reg_last->sets, 0);
1047 add_dependence_list (insn, reg_last->clobbers, 0);
1048 reg_last->uses_length++;
1049 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1051 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1053 struct deps_reg *reg_last = &deps->reg_last[i];
1054 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1055 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1057 add_dependence_list_and_free (insn, ®_last->sets,
1059 add_dependence_list_and_free (insn, ®_last->uses,
1061 add_dependence_list_and_free (insn, ®_last->clobbers,
1063 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1064 reg_last->clobbers_length = 0;
1065 reg_last->uses_length = 0;
1069 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1070 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1072 reg_last->clobbers_length++;
1073 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1075 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1077 struct deps_reg *reg_last = &deps->reg_last[i];
1078 add_dependence_list_and_free (insn, ®_last->sets,
1080 add_dependence_list_and_free (insn, ®_last->clobbers,
1082 add_dependence_list_and_free (insn, ®_last->uses,
1084 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1085 reg_last->uses_length = 0;
1086 reg_last->clobbers_length = 0;
1087 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1091 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1092 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1093 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1095 CLEAR_REG_SET (reg_pending_uses);
1096 CLEAR_REG_SET (reg_pending_clobbers);
1097 CLEAR_REG_SET (reg_pending_sets);
1099 /* If we are currently in a libcall scheduling group, then mark the
1100 current insn as being in a scheduling group and that it can not
1101 be moved into a different basic block. */
1103 if (deps->libcall_block_tail_insn)
1105 set_sched_group_p (insn);
1106 CANT_MOVE (insn) = 1;
1109 /* If a post-call group is still open, see if it should remain so.
1110 This insn must be a simple move of a hard reg to a pseudo or
1113 We must avoid moving these insns for correctness on
1114 SMALL_REGISTER_CLASS machines, and for special registers like
1115 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1116 hard regs for all targets. */
1118 if (deps->in_post_call_group_p)
1120 rtx tmp, set = single_set (insn);
1121 int src_regno, dest_regno;
1124 goto end_call_group;
1126 tmp = SET_DEST (set);
1127 if (GET_CODE (tmp) == SUBREG)
1128 tmp = SUBREG_REG (tmp);
1130 dest_regno = REGNO (tmp);
1132 goto end_call_group;
1134 tmp = SET_SRC (set);
1135 if (GET_CODE (tmp) == SUBREG)
1136 tmp = SUBREG_REG (tmp);
1137 if ((GET_CODE (tmp) == PLUS
1138 || GET_CODE (tmp) == MINUS)
1139 && REG_P (XEXP (tmp, 0))
1140 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1141 && dest_regno == STACK_POINTER_REGNUM)
1142 src_regno = STACK_POINTER_REGNUM;
1143 else if (REG_P (tmp))
1144 src_regno = REGNO (tmp);
1146 goto end_call_group;
1148 if (src_regno < FIRST_PSEUDO_REGISTER
1149 || dest_regno < FIRST_PSEUDO_REGISTER)
1151 /* If we are inside a post-call group right at the start of the
1152 scheduling region, we must not add a dependency. */
1153 if (deps->in_post_call_group_p == post_call_initial)
1155 SCHED_GROUP_P (insn) = 1;
1156 deps->in_post_call_group_p = post_call;
1159 set_sched_group_p (insn);
1160 CANT_MOVE (insn) = 1;
1165 deps->in_post_call_group_p = not_post_call;
1170 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1171 for every dependency. */
1174 sched_analyze (struct deps *deps, rtx head, rtx tail)
1179 if (current_sched_info->use_cselib)
1182 /* Before reload, if the previous block ended in a call, show that
1183 we are inside a post-call group, so as to keep the lifetimes of
1184 hard registers correct. */
1185 if (! reload_completed && !LABEL_P (head))
1187 insn = prev_nonnote_insn (head);
1188 if (insn && CALL_P (insn))
1189 deps->in_post_call_group_p = post_call_initial;
1191 for (insn = head;; insn = NEXT_INSN (insn))
1193 rtx link, end_seq, r0, set;
1195 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1197 /* Clear out the stale LOG_LINKS from flow. */
1198 free_INSN_LIST_list (&LOG_LINKS (insn));
1200 /* Make each JUMP_INSN a scheduling barrier for memory
1204 /* Keep the list a reasonable size. */
1205 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1206 flush_pending_lists (deps, insn, true, true);
1208 deps->last_pending_memory_flush
1209 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1211 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1214 else if (CALL_P (insn))
1218 CANT_MOVE (insn) = 1;
1220 /* Clear out the stale LOG_LINKS from flow. */
1221 free_INSN_LIST_list (&LOG_LINKS (insn));
1223 if (find_reg_note (insn, REG_SETJMP, NULL))
1225 /* This is setjmp. Assume that all registers, not just
1226 hard registers, may be clobbered by this call. */
1227 reg_pending_barrier = MOVE_BARRIER;
1231 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1232 /* A call may read and modify global register variables. */
1235 SET_REGNO_REG_SET (reg_pending_sets, i);
1236 SET_REGNO_REG_SET (reg_pending_uses, i);
1238 /* Other call-clobbered hard regs may be clobbered.
1239 Since we only have a choice between 'might be clobbered'
1240 and 'definitely not clobbered', we must include all
1241 partly call-clobbered registers here. */
1242 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1243 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1244 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1245 /* We don't know what set of fixed registers might be used
1246 by the function, but it is certain that the stack pointer
1247 is among them, but be conservative. */
1248 else if (fixed_regs[i])
1249 SET_REGNO_REG_SET (reg_pending_uses, i);
1250 /* The frame pointer is normally not used by the function
1251 itself, but by the debugger. */
1252 /* ??? MIPS o32 is an exception. It uses the frame pointer
1253 in the macro expansion of jal but does not represent this
1254 fact in the call_insn rtl. */
1255 else if (i == FRAME_POINTER_REGNUM
1256 || (i == HARD_FRAME_POINTER_REGNUM
1257 && (! reload_completed || frame_pointer_needed)))
1258 SET_REGNO_REG_SET (reg_pending_uses, i);
1261 /* For each insn which shouldn't cross a call, add a dependence
1262 between that insn and this call insn. */
1263 add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1266 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1269 /* In the absence of interprocedural alias analysis, we must flush
1270 all pending reads and writes, and start new dependencies starting
1271 from here. But only flush writes for constant calls (which may
1272 be passed a pointer to something we haven't written yet). */
1273 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1275 /* Remember the last function call for limiting lifetimes. */
1276 free_INSN_LIST_list (&deps->last_function_call);
1277 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1279 /* Before reload, begin a post-call group, so as to keep the
1280 lifetimes of hard registers correct. */
1281 if (! reload_completed)
1282 deps->in_post_call_group_p = post_call;
1285 /* See comments on reemit_notes as to why we do this.
1286 ??? Actually, the reemit_notes just say what is done, not why. */
1289 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1290 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1291 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1292 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1296 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1297 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1298 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1300 rtx_region = const0_rtx;
1302 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1305 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1306 GEN_INT (NOTE_LINE_NUMBER (insn)),
1308 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1311 if (current_sched_info->use_cselib)
1312 cselib_process_insn (insn);
1314 /* Now that we have completed handling INSN, check and see if it is
1315 a CLOBBER beginning a libcall block. If it is, record the
1316 end of the libcall sequence.
1318 We want to schedule libcall blocks as a unit before reload. While
1319 this restricts scheduling, it preserves the meaning of a libcall
1322 As a side effect, we may get better code due to decreased register
1323 pressure as well as less chance of a foreign insn appearing in
1325 if (!reload_completed
1326 /* Note we may have nested libcall sequences. We only care about
1327 the outermost libcall sequence. */
1328 && deps->libcall_block_tail_insn == 0
1329 /* The sequence must start with a clobber of a register. */
1330 && NONJUMP_INSN_P (insn)
1331 && GET_CODE (PATTERN (insn)) == CLOBBER
1332 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1333 && REG_P (XEXP (PATTERN (insn), 0))
1334 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1335 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1336 && (end_seq = XEXP (link, 0)) != 0
1337 /* The insn referenced by the REG_LIBCALL note must be a
1338 simple nop copy with the same destination as the register
1339 mentioned in the clobber. */
1340 && (set = single_set (end_seq)) != 0
1341 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1342 /* And finally the insn referenced by the REG_LIBCALL must
1343 also contain a REG_EQUAL note and a REG_RETVAL note. */
1344 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1345 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1346 deps->libcall_block_tail_insn = XEXP (link, 0);
1348 /* If we have reached the end of a libcall block, then close the
1350 if (deps->libcall_block_tail_insn == insn)
1351 deps->libcall_block_tail_insn = 0;
1355 if (current_sched_info->use_cselib)
1364 /* The following function adds forward dependence (FROM, TO) with
1365 given DEP_TYPE. The forward dependence should be not exist before. */
1368 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1372 #ifdef ENABLE_CHECKING
1373 /* If add_dependence is working properly there should never
1374 be notes, deleted insns or duplicates in the backward
1375 links. Thus we need not check for them here.
1377 However, if we have enabled checking we might as well go
1378 ahead and verify that add_dependence worked properly. */
1380 || INSN_DELETED_P (from)
1381 || (forward_dependency_cache != NULL
1382 && bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1384 || (forward_dependency_cache == NULL
1385 && find_insn_list (to, INSN_DEPEND (from))))
1387 if (forward_dependency_cache != NULL)
1388 bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1392 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1394 PUT_REG_NOTE_KIND (new_link, dep_type);
1396 INSN_DEPEND (from) = new_link;
1397 INSN_DEP_COUNT (to) += 1;
1400 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1401 dependences from LOG_LINKS to build forward dependences in
1405 compute_forward_dependences (rtx head, rtx tail)
1410 next_tail = NEXT_INSN (tail);
1411 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1413 if (! INSN_P (insn))
1416 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1417 add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1421 /* Initialize variables for region data dependence analysis.
1422 n_bbs is the number of region blocks. */
1425 init_deps (struct deps *deps)
1427 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1429 deps->max_reg = max_reg;
1430 deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1431 INIT_REG_SET (&deps->reg_last_in_use);
1432 INIT_REG_SET (&deps->reg_conditional_sets);
1434 deps->pending_read_insns = 0;
1435 deps->pending_read_mems = 0;
1436 deps->pending_write_insns = 0;
1437 deps->pending_write_mems = 0;
1438 deps->pending_lists_length = 0;
1439 deps->pending_flush_length = 0;
1440 deps->last_pending_memory_flush = 0;
1441 deps->last_function_call = 0;
1442 deps->sched_before_next_call = 0;
1443 deps->in_post_call_group_p = not_post_call;
1444 deps->libcall_block_tail_insn = 0;
1447 /* Free insn lists found in DEPS. */
1450 free_deps (struct deps *deps)
1454 free_INSN_LIST_list (&deps->pending_read_insns);
1455 free_EXPR_LIST_list (&deps->pending_read_mems);
1456 free_INSN_LIST_list (&deps->pending_write_insns);
1457 free_EXPR_LIST_list (&deps->pending_write_mems);
1458 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1460 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1461 times. For a testcase with 42000 regs and 8000 small basic blocks,
1462 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1463 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1465 struct deps_reg *reg_last = &deps->reg_last[i];
1467 free_INSN_LIST_list (®_last->uses);
1469 free_INSN_LIST_list (®_last->sets);
1470 if (reg_last->clobbers)
1471 free_INSN_LIST_list (®_last->clobbers);
1473 CLEAR_REG_SET (&deps->reg_last_in_use);
1474 CLEAR_REG_SET (&deps->reg_conditional_sets);
1476 free (deps->reg_last);
1479 /* If it is profitable to use them, initialize caches for tracking
1480 dependency information. LUID is the number of insns to be scheduled,
1481 it is used in the estimate of profitability. */
1484 init_dependency_caches (int luid)
1486 /* ?!? We could save some memory by computing a per-region luid mapping
1487 which could reduce both the number of vectors in the cache and the size
1488 of each vector. Instead we just avoid the cache entirely unless the
1489 average number of instructions in a basic block is very high. See
1490 the comment before the declaration of true_dependency_cache for
1491 what we consider "very high". */
1492 if (luid / n_basic_blocks > 100 * 5)
1495 true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1496 anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1497 output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1498 #ifdef ENABLE_CHECKING
1499 forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1501 for (i = 0; i < luid; i++)
1503 bitmap_initialize (&true_dependency_cache[i], 0);
1504 bitmap_initialize (&anti_dependency_cache[i], 0);
1505 bitmap_initialize (&output_dependency_cache[i], 0);
1506 #ifdef ENABLE_CHECKING
1507 bitmap_initialize (&forward_dependency_cache[i], 0);
1514 /* Free the caches allocated in init_dependency_caches. */
1517 free_dependency_caches (void)
1519 if (true_dependency_cache)
1523 for (i = 0; i < cache_size; i++)
1525 bitmap_clear (&true_dependency_cache[i]);
1526 bitmap_clear (&anti_dependency_cache[i]);
1527 bitmap_clear (&output_dependency_cache[i]);
1528 #ifdef ENABLE_CHECKING
1529 bitmap_clear (&forward_dependency_cache[i]);
1532 free (true_dependency_cache);
1533 true_dependency_cache = NULL;
1534 free (anti_dependency_cache);
1535 anti_dependency_cache = NULL;
1536 free (output_dependency_cache);
1537 output_dependency_cache = NULL;
1538 #ifdef ENABLE_CHECKING
1539 free (forward_dependency_cache);
1540 forward_dependency_cache = NULL;
1545 /* Initialize some global variables needed by the dependency analysis
1549 init_deps_global (void)
1551 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1552 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1553 reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1554 reg_pending_barrier = NOT_A_BARRIER;
1557 /* Free everything used by the dependency analysis code. */
1560 finish_deps_global (void)
1562 FREE_REG_SET (reg_pending_sets);
1563 FREE_REG_SET (reg_pending_clobbers);
1564 FREE_REG_SET (reg_pending_uses);