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));
157 /* The previous code here was completely invalid and could never extract
158 the condition from a jump. This code does the correct thing, but that
159 triggers latent bugs later in the scheduler on ports with conditional
160 execution. So this is disabled for now. */
161 if (XEXP (src, 2) == pc_rtx)
162 return XEXP (src, 0);
163 else if (XEXP (src, 1) == pc_rtx)
165 rtx cond = XEXP (src, 0);
166 enum rtx_code revcode = reversed_comparison_code (cond, insn);
168 if (revcode == UNKNOWN)
170 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
178 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
181 conditions_mutex_p (rtx cond1, rtx cond2)
183 if (COMPARISON_P (cond1)
184 && COMPARISON_P (cond2)
185 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
186 && XEXP (cond1, 0) == XEXP (cond2, 0)
187 && XEXP (cond1, 1) == XEXP (cond2, 1))
192 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
193 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
194 type of dependence that this link represents. The function returns
195 nonzero if a new entry has been added to insn's LOG_LINK. */
198 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
204 /* Don't depend an insn on itself. */
208 /* We can get a dependency on deleted insns due to optimizations in
209 the register allocation and reloading or due to splitting. Any
210 such dependency is useless and can be ignored. */
214 /* flow.c doesn't handle conditional lifetimes entirely correctly;
215 calls mess up the conditional lifetimes. */
216 /* ??? add_dependence is the wrong place to be eliding dependencies,
217 as that forgets that the condition expressions themselves may
219 if (!CALL_P (insn) && !CALL_P (elem))
221 cond1 = get_condition (insn);
222 cond2 = get_condition (elem);
224 && conditions_mutex_p (cond1, cond2)
225 /* Make sure first instruction doesn't affect condition of second
226 instruction if switched. */
227 && !modified_in_p (cond1, elem)
228 /* Make sure second instruction doesn't affect condition of first
229 instruction if switched. */
230 && !modified_in_p (cond2, insn))
235 #ifdef INSN_SCHEDULING
236 /* ??? No good way to tell from here whether we're doing interblock
237 scheduling. Possibly add another callback. */
239 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
240 No need for interblock dependences with calls, since
241 calls are not moved between blocks. Note: the edge where
242 elem is a CALL is still required. */
244 && (INSN_BB (elem) != INSN_BB (insn)))
248 /* If we already have a dependency for ELEM, then we do not need to
249 do anything. Avoiding the list walk below can cut compile times
250 dramatically for some code. */
251 if (true_dependency_cache != NULL)
253 enum reg_note present_dep_type = 0;
255 if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
257 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
259 /* Do nothing (present_set_type is already 0). */
261 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
263 present_dep_type = REG_DEP_ANTI;
264 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
266 present_dep_type = REG_DEP_OUTPUT;
269 if (present_p && (int) dep_type >= (int) present_dep_type)
274 /* Check that we don't already have this dependence. */
276 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
277 if (XEXP (link, 0) == elem)
279 #ifdef INSN_SCHEDULING
280 /* Clear corresponding cache entry because type of the link
282 if (true_dependency_cache != NULL)
284 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
285 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
287 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
288 && output_dependency_cache)
289 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
296 /* If this is a more restrictive type of dependence than the existing
297 one, then change the existing dependence to this type. */
298 if ((int) dep_type < (int) REG_NOTE_KIND (link))
299 PUT_REG_NOTE_KIND (link, dep_type);
301 #ifdef INSN_SCHEDULING
302 /* If we are adding a dependency to INSN's LOG_LINKs, then
303 note that in the bitmap caches of dependency information. */
304 if (true_dependency_cache != NULL)
306 if ((int) REG_NOTE_KIND (link) == 0)
307 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
309 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
310 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
312 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
313 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
319 /* Might want to check one level of transitivity to save conses. */
321 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
322 LOG_LINKS (insn) = link;
324 /* Insn dependency, not data dependency. */
325 PUT_REG_NOTE_KIND (link, dep_type);
327 #ifdef INSN_SCHEDULING
328 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
329 in the bitmap caches of dependency information. */
330 if (true_dependency_cache != NULL)
332 if ((int) dep_type == 0)
333 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
334 else if (dep_type == REG_DEP_ANTI)
335 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
336 else if (dep_type == REG_DEP_OUTPUT)
337 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
343 /* A convenience wrapper to operate on an entire list. */
346 add_dependence_list (rtx insn, rtx list, enum reg_note dep_type)
348 for (; list; list = XEXP (list, 1))
349 add_dependence (insn, XEXP (list, 0), dep_type);
352 /* Similar, but free *LISTP at the same time. */
355 add_dependence_list_and_free (rtx insn, rtx *listp, enum reg_note dep_type)
358 for (list = *listp, *listp = NULL; list ; list = next)
360 next = XEXP (list, 1);
361 add_dependence (insn, XEXP (list, 0), dep_type);
362 free_INSN_LIST_node (list);
366 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
367 goes along with that. */
370 set_sched_group_p (rtx insn)
374 SCHED_GROUP_P (insn) = 1;
376 prev = prev_nonnote_insn (insn);
377 add_dependence (insn, prev, REG_DEP_ANTI);
380 /* Process an insn's memory dependencies. There are four kinds of
383 (0) read dependence: read follows read
384 (1) true dependence: read follows write
385 (2) anti dependence: write follows read
386 (3) output dependence: write follows write
388 We are careful to build only dependencies which actually exist, and
389 use transitivity to avoid building too many links. */
391 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
392 The MEM is a memory reference contained within INSN, which we are saving
393 so that we can do memory aliasing on it. */
396 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
401 link = alloc_INSN_LIST (insn, *insn_list);
404 if (current_sched_info->use_cselib)
406 mem = shallow_copy_rtx (mem);
407 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
409 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
412 deps->pending_lists_length++;
415 /* Make a dependency between every memory reference on the pending lists
416 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
417 dependencies for a read operation, similarly with FOR_WRITE. */
420 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
425 add_dependence_list_and_free (insn, &deps->pending_read_insns,
427 free_EXPR_LIST_list (&deps->pending_read_mems);
430 add_dependence_list_and_free (insn, &deps->pending_write_insns,
431 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
432 free_EXPR_LIST_list (&deps->pending_write_mems);
433 deps->pending_lists_length = 0;
435 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
436 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
437 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
438 deps->pending_flush_length = 1;
441 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
442 rtx, X, creating all dependencies generated by the write to the
443 destination of X, and reads of everything mentioned. */
446 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
449 rtx dest = XEXP (x, 0);
450 enum rtx_code code = GET_CODE (x);
455 if (GET_CODE (dest) == PARALLEL)
459 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
460 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
461 sched_analyze_1 (deps,
462 gen_rtx_CLOBBER (VOIDmode,
463 XEXP (XVECEXP (dest, 0, i), 0)),
466 if (GET_CODE (x) == SET)
467 sched_analyze_2 (deps, SET_SRC (x), insn);
471 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
472 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
474 if (GET_CODE (dest) == STRICT_LOW_PART
475 || GET_CODE (dest) == ZERO_EXTRACT
476 || GET_CODE (dest) == SIGN_EXTRACT
477 || read_modify_subreg_p (dest))
479 /* These both read and modify the result. We must handle
480 them as writes to get proper dependencies for following
481 instructions. We must handle them as reads to get proper
482 dependencies from this to previous instructions.
483 Thus we need to call sched_analyze_2. */
485 sched_analyze_2 (deps, XEXP (dest, 0), insn);
487 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
489 /* The second and third arguments are values read by this insn. */
490 sched_analyze_2 (deps, XEXP (dest, 1), insn);
491 sched_analyze_2 (deps, XEXP (dest, 2), insn);
493 dest = XEXP (dest, 0);
498 regno = REGNO (dest);
500 /* A hard reg in a wide mode may really be multiple registers.
501 If so, mark all of them just like the first. */
502 if (regno < FIRST_PSEUDO_REGISTER)
504 int i = hard_regno_nregs[regno][GET_MODE (dest)];
508 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
513 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
516 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
517 it does not reload. Ignore these as they have served their
519 else if (regno >= deps->max_reg)
521 if (GET_CODE (PATTERN (insn)) != USE
522 && GET_CODE (PATTERN (insn)) != CLOBBER)
528 SET_REGNO_REG_SET (reg_pending_sets, regno);
530 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
532 /* Pseudos that are REG_EQUIV to something may be replaced
533 by that during reloading. We need only add dependencies for
534 the address in the REG_EQUIV note. */
535 if (!reload_completed && get_reg_known_equiv_p (regno))
537 rtx t = get_reg_known_value (regno);
539 sched_analyze_2 (deps, XEXP (t, 0), insn);
542 /* Don't let it cross a call after scheduling if it doesn't
543 already cross one. */
544 if (REG_N_CALLS_CROSSED (regno) == 0)
545 add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
548 else if (MEM_P (dest))
550 /* Writing memory. */
553 if (current_sched_info->use_cselib)
555 t = shallow_copy_rtx (dest);
556 cselib_lookup (XEXP (t, 0), Pmode, 1);
557 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
561 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
563 /* Flush all pending reads and writes to prevent the pending lists
564 from getting any larger. Insn scheduling runs too slowly when
565 these lists get long. When compiling GCC with itself,
566 this flush occurs 8 times for sparc, and 10 times for m88k using
567 the default value of 32. */
568 flush_pending_lists (deps, insn, false, true);
572 rtx pending, pending_mem;
574 pending = deps->pending_read_insns;
575 pending_mem = deps->pending_read_mems;
578 if (anti_dependence (XEXP (pending_mem, 0), t))
579 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
581 pending = XEXP (pending, 1);
582 pending_mem = XEXP (pending_mem, 1);
585 pending = deps->pending_write_insns;
586 pending_mem = deps->pending_write_mems;
589 if (output_dependence (XEXP (pending_mem, 0), t))
590 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
592 pending = XEXP (pending, 1);
593 pending_mem = XEXP (pending_mem, 1);
596 add_dependence_list (insn, deps->last_pending_memory_flush,
599 add_insn_mem_dependence (deps, &deps->pending_write_insns,
600 &deps->pending_write_mems, insn, dest);
602 sched_analyze_2 (deps, XEXP (dest, 0), insn);
606 if (GET_CODE (x) == SET)
607 sched_analyze_2 (deps, SET_SRC (x), insn);
610 /* Analyze the uses of memory and registers in rtx X in INSN. */
613 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
633 /* Ignore constants. Note that we must handle CONST_DOUBLE here
634 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
635 this does not mean that this insn is using cc0. */
640 /* User of CC0 depends on immediately preceding insn. */
641 set_sched_group_p (insn);
642 /* Don't move CC0 setter to another block (it can set up the
643 same flag for previous CC0 users which is safe). */
644 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
650 int regno = REGNO (x);
651 if (regno < FIRST_PSEUDO_REGISTER)
653 int i = hard_regno_nregs[regno][GET_MODE (x)];
655 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
657 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
658 it does not reload. Ignore these as they have served their
660 else if (regno >= deps->max_reg)
662 if (GET_CODE (PATTERN (insn)) != USE
663 && GET_CODE (PATTERN (insn)) != CLOBBER)
668 SET_REGNO_REG_SET (reg_pending_uses, regno);
670 /* Pseudos that are REG_EQUIV to something may be replaced
671 by that during reloading. We need only add dependencies for
672 the address in the REG_EQUIV note. */
673 if (!reload_completed && get_reg_known_equiv_p (regno))
675 rtx t = get_reg_known_value (regno);
677 sched_analyze_2 (deps, XEXP (t, 0), insn);
680 /* If the register does not already cross any calls, then add this
681 insn to the sched_before_next_call list so that it will still
682 not cross calls after scheduling. */
683 if (REG_N_CALLS_CROSSED (regno) == 0)
684 deps->sched_before_next_call
685 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
692 /* Reading memory. */
694 rtx pending, pending_mem;
697 if (current_sched_info->use_cselib)
699 t = shallow_copy_rtx (t);
700 cselib_lookup (XEXP (t, 0), Pmode, 1);
701 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
704 pending = deps->pending_read_insns;
705 pending_mem = deps->pending_read_mems;
708 if (read_dependence (XEXP (pending_mem, 0), t))
709 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
711 pending = XEXP (pending, 1);
712 pending_mem = XEXP (pending_mem, 1);
715 pending = deps->pending_write_insns;
716 pending_mem = deps->pending_write_mems;
719 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
721 add_dependence (insn, XEXP (pending, 0), 0);
723 pending = XEXP (pending, 1);
724 pending_mem = XEXP (pending_mem, 1);
727 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
728 if (!JUMP_P (XEXP (u, 0))
729 || deps_may_trap_p (x))
730 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
732 /* Always add these dependencies to pending_reads, since
733 this insn may be followed by a write. */
734 add_insn_mem_dependence (deps, &deps->pending_read_insns,
735 &deps->pending_read_mems, insn, x);
737 /* Take advantage of tail recursion here. */
738 sched_analyze_2 (deps, XEXP (x, 0), insn);
742 /* Force pending stores to memory in case a trap handler needs them. */
744 flush_pending_lists (deps, insn, true, false);
749 case UNSPEC_VOLATILE:
751 /* Traditional and volatile asm instructions must be considered to use
752 and clobber all hard registers, all pseudo-registers and all of
753 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
755 Consider for instance a volatile asm that changes the fpu rounding
756 mode. An insn should not be moved across this even if it only uses
757 pseudo-regs because it might give an incorrectly rounded result. */
758 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
759 reg_pending_barrier = TRUE_BARRIER;
761 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
762 We can not just fall through here since then we would be confused
763 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
764 traditional asms unlike their normal usage. */
766 if (code == ASM_OPERANDS)
768 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
769 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
779 /* These both read and modify the result. We must handle them as writes
780 to get proper dependencies for following instructions. We must handle
781 them as reads to get proper dependencies from this to previous
782 instructions. Thus we need to pass them to both sched_analyze_1
783 and sched_analyze_2. We must call sched_analyze_2 first in order
784 to get the proper antecedent for the read. */
785 sched_analyze_2 (deps, XEXP (x, 0), insn);
786 sched_analyze_1 (deps, x, insn);
791 /* op0 = op0 + op1 */
792 sched_analyze_2 (deps, XEXP (x, 0), insn);
793 sched_analyze_2 (deps, XEXP (x, 1), insn);
794 sched_analyze_1 (deps, x, insn);
801 /* Other cases: walk the insn. */
802 fmt = GET_RTX_FORMAT (code);
803 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
806 sched_analyze_2 (deps, XEXP (x, i), insn);
807 else if (fmt[i] == 'E')
808 for (j = 0; j < XVECLEN (x, i); j++)
809 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
813 /* Analyze an INSN with pattern X to find all dependencies. */
816 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
818 RTX_CODE code = GET_CODE (x);
822 if (code == COND_EXEC)
824 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
826 /* ??? Should be recording conditions so we reduce the number of
827 false dependencies. */
828 x = COND_EXEC_CODE (x);
831 if (code == SET || code == CLOBBER)
833 sched_analyze_1 (deps, x, insn);
835 /* Bare clobber insns are used for letting life analysis, reg-stack
836 and others know that a value is dead. Depend on the last call
837 instruction so that reg-stack won't get confused. */
839 add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
841 else if (code == PARALLEL)
844 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
846 rtx sub = XVECEXP (x, 0, i);
847 code = GET_CODE (sub);
849 if (code == COND_EXEC)
851 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
852 sub = COND_EXEC_CODE (sub);
853 code = GET_CODE (sub);
855 if (code == SET || code == CLOBBER)
856 sched_analyze_1 (deps, sub, insn);
858 sched_analyze_2 (deps, sub, insn);
862 sched_analyze_2 (deps, x, insn);
864 /* Mark registers CLOBBERED or used by called function. */
867 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
869 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
870 sched_analyze_1 (deps, XEXP (link, 0), insn);
872 sched_analyze_2 (deps, XEXP (link, 0), insn);
874 if (find_reg_note (insn, REG_SETJMP, NULL))
875 reg_pending_barrier = MOVE_BARRIER;
881 next = next_nonnote_insn (insn);
882 if (next && BARRIER_P (next))
883 reg_pending_barrier = TRUE_BARRIER;
886 rtx pending, pending_mem;
887 regset_head tmp_uses, tmp_sets;
888 INIT_REG_SET (&tmp_uses);
889 INIT_REG_SET (&tmp_sets);
891 (*current_sched_info->compute_jump_reg_dependencies)
892 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
893 /* Make latency of jump equal to 0 by using anti-dependence. */
894 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i,
896 struct deps_reg *reg_last = &deps->reg_last[i];
897 add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
898 add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
899 reg_last->uses_length++;
900 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
902 IOR_REG_SET (reg_pending_sets, &tmp_sets);
904 CLEAR_REG_SET (&tmp_uses);
905 CLEAR_REG_SET (&tmp_sets);
907 /* All memory writes and volatile reads must happen before the
908 jump. Non-volatile reads must happen before the jump iff
909 the result is needed by the above register used mask. */
911 pending = deps->pending_write_insns;
912 pending_mem = deps->pending_write_mems;
915 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
916 pending = XEXP (pending, 1);
917 pending_mem = XEXP (pending_mem, 1);
920 pending = deps->pending_read_insns;
921 pending_mem = deps->pending_read_mems;
924 if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
925 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
926 pending = XEXP (pending, 1);
927 pending_mem = XEXP (pending_mem, 1);
930 add_dependence_list (insn, deps->last_pending_memory_flush,
935 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
936 block, then we must be sure that no instructions are scheduled across it.
937 Otherwise, the reg_n_refs info (which depends on loop_depth) would
943 /* Update loop_notes with any notes from this insn. Also determine
944 if any of the notes on the list correspond to instruction scheduling
945 barriers (loop, eh & setjmp notes, but not range notes). */
947 while (XEXP (link, 1))
949 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
950 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
951 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
952 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
953 reg_pending_barrier = MOVE_BARRIER;
955 link = XEXP (link, 1);
957 XEXP (link, 1) = REG_NOTES (insn);
958 REG_NOTES (insn) = loop_notes;
961 /* If this instruction can throw an exception, then moving it changes
962 where block boundaries fall. This is mighty confusing elsewhere.
963 Therefore, prevent such an instruction from being moved. */
964 if (can_throw_internal (insn))
965 reg_pending_barrier = MOVE_BARRIER;
967 /* Add dependencies if a scheduling barrier was found. */
968 if (reg_pending_barrier)
970 /* In the case of barrier the most added dependencies are not
971 real, so we use anti-dependence here. */
972 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
974 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
976 struct deps_reg *reg_last = &deps->reg_last[i];
977 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
979 (insn, reg_last->sets,
980 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
982 (insn, reg_last->clobbers,
983 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
988 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
990 struct deps_reg *reg_last = &deps->reg_last[i];
991 add_dependence_list_and_free (insn, ®_last->uses,
993 add_dependence_list_and_free
994 (insn, ®_last->sets,
995 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
996 add_dependence_list_and_free
997 (insn, ®_last->clobbers,
998 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
999 reg_last->uses_length = 0;
1000 reg_last->clobbers_length = 0;
1004 for (i = 0; i < deps->max_reg; i++)
1006 struct deps_reg *reg_last = &deps->reg_last[i];
1007 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1008 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1011 flush_pending_lists (deps, insn, true, true);
1012 CLEAR_REG_SET (&deps->reg_conditional_sets);
1013 reg_pending_barrier = NOT_A_BARRIER;
1017 /* If the current insn is conditional, we can't free any
1019 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1021 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1023 struct deps_reg *reg_last = &deps->reg_last[i];
1024 add_dependence_list (insn, reg_last->sets, 0);
1025 add_dependence_list (insn, reg_last->clobbers, 0);
1026 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1027 reg_last->uses_length++;
1029 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1031 struct deps_reg *reg_last = &deps->reg_last[i];
1032 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1033 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1034 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1035 reg_last->clobbers_length++;
1037 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1039 struct deps_reg *reg_last = &deps->reg_last[i];
1040 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1041 add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1042 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1043 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1044 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1049 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1051 struct deps_reg *reg_last = &deps->reg_last[i];
1052 add_dependence_list (insn, reg_last->sets, 0);
1053 add_dependence_list (insn, reg_last->clobbers, 0);
1054 reg_last->uses_length++;
1055 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1057 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1059 struct deps_reg *reg_last = &deps->reg_last[i];
1060 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1061 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1063 add_dependence_list_and_free (insn, ®_last->sets,
1065 add_dependence_list_and_free (insn, ®_last->uses,
1067 add_dependence_list_and_free (insn, ®_last->clobbers,
1069 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1070 reg_last->clobbers_length = 0;
1071 reg_last->uses_length = 0;
1075 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1076 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1078 reg_last->clobbers_length++;
1079 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1081 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1083 struct deps_reg *reg_last = &deps->reg_last[i];
1084 add_dependence_list_and_free (insn, ®_last->sets,
1086 add_dependence_list_and_free (insn, ®_last->clobbers,
1088 add_dependence_list_and_free (insn, ®_last->uses,
1090 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1091 reg_last->uses_length = 0;
1092 reg_last->clobbers_length = 0;
1093 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1097 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1098 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1099 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1101 CLEAR_REG_SET (reg_pending_uses);
1102 CLEAR_REG_SET (reg_pending_clobbers);
1103 CLEAR_REG_SET (reg_pending_sets);
1105 /* If we are currently in a libcall scheduling group, then mark the
1106 current insn as being in a scheduling group and that it can not
1107 be moved into a different basic block. */
1109 if (deps->libcall_block_tail_insn)
1111 set_sched_group_p (insn);
1112 CANT_MOVE (insn) = 1;
1115 /* If a post-call group is still open, see if it should remain so.
1116 This insn must be a simple move of a hard reg to a pseudo or
1119 We must avoid moving these insns for correctness on
1120 SMALL_REGISTER_CLASS machines, and for special registers like
1121 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1122 hard regs for all targets. */
1124 if (deps->in_post_call_group_p)
1126 rtx tmp, set = single_set (insn);
1127 int src_regno, dest_regno;
1130 goto end_call_group;
1132 tmp = SET_DEST (set);
1133 if (GET_CODE (tmp) == SUBREG)
1134 tmp = SUBREG_REG (tmp);
1136 dest_regno = REGNO (tmp);
1138 goto end_call_group;
1140 tmp = SET_SRC (set);
1141 if (GET_CODE (tmp) == SUBREG)
1142 tmp = SUBREG_REG (tmp);
1143 if ((GET_CODE (tmp) == PLUS
1144 || GET_CODE (tmp) == MINUS)
1145 && REG_P (XEXP (tmp, 0))
1146 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1147 && dest_regno == STACK_POINTER_REGNUM)
1148 src_regno = STACK_POINTER_REGNUM;
1149 else if (REG_P (tmp))
1150 src_regno = REGNO (tmp);
1152 goto end_call_group;
1154 if (src_regno < FIRST_PSEUDO_REGISTER
1155 || dest_regno < FIRST_PSEUDO_REGISTER)
1157 /* If we are inside a post-call group right at the start of the
1158 scheduling region, we must not add a dependency. */
1159 if (deps->in_post_call_group_p == post_call_initial)
1161 SCHED_GROUP_P (insn) = 1;
1162 deps->in_post_call_group_p = post_call;
1165 set_sched_group_p (insn);
1166 CANT_MOVE (insn) = 1;
1171 deps->in_post_call_group_p = not_post_call;
1176 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1177 for every dependency. */
1180 sched_analyze (struct deps *deps, rtx head, rtx tail)
1185 if (current_sched_info->use_cselib)
1188 /* Before reload, if the previous block ended in a call, show that
1189 we are inside a post-call group, so as to keep the lifetimes of
1190 hard registers correct. */
1191 if (! reload_completed && !LABEL_P (head))
1193 insn = prev_nonnote_insn (head);
1194 if (insn && CALL_P (insn))
1195 deps->in_post_call_group_p = post_call_initial;
1197 for (insn = head;; insn = NEXT_INSN (insn))
1199 rtx link, end_seq, r0, set;
1201 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1203 /* Clear out the stale LOG_LINKS from flow. */
1204 free_INSN_LIST_list (&LOG_LINKS (insn));
1206 /* Make each JUMP_INSN a scheduling barrier for memory
1210 /* Keep the list a reasonable size. */
1211 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1212 flush_pending_lists (deps, insn, true, true);
1214 deps->last_pending_memory_flush
1215 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1217 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1220 else if (CALL_P (insn))
1224 CANT_MOVE (insn) = 1;
1226 /* Clear out the stale LOG_LINKS from flow. */
1227 free_INSN_LIST_list (&LOG_LINKS (insn));
1229 if (find_reg_note (insn, REG_SETJMP, NULL))
1231 /* This is setjmp. Assume that all registers, not just
1232 hard registers, may be clobbered by this call. */
1233 reg_pending_barrier = MOVE_BARRIER;
1237 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1238 /* A call may read and modify global register variables. */
1241 SET_REGNO_REG_SET (reg_pending_sets, i);
1242 SET_REGNO_REG_SET (reg_pending_uses, i);
1244 /* Other call-clobbered hard regs may be clobbered.
1245 Since we only have a choice between 'might be clobbered'
1246 and 'definitely not clobbered', we must include all
1247 partly call-clobbered registers here. */
1248 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1249 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1250 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1251 /* We don't know what set of fixed registers might be used
1252 by the function, but it is certain that the stack pointer
1253 is among them, but be conservative. */
1254 else if (fixed_regs[i])
1255 SET_REGNO_REG_SET (reg_pending_uses, i);
1256 /* The frame pointer is normally not used by the function
1257 itself, but by the debugger. */
1258 /* ??? MIPS o32 is an exception. It uses the frame pointer
1259 in the macro expansion of jal but does not represent this
1260 fact in the call_insn rtl. */
1261 else if (i == FRAME_POINTER_REGNUM
1262 || (i == HARD_FRAME_POINTER_REGNUM
1263 && (! reload_completed || frame_pointer_needed)))
1264 SET_REGNO_REG_SET (reg_pending_uses, i);
1267 /* For each insn which shouldn't cross a call, add a dependence
1268 between that insn and this call insn. */
1269 add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1272 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1275 /* In the absence of interprocedural alias analysis, we must flush
1276 all pending reads and writes, and start new dependencies starting
1277 from here. But only flush writes for constant calls (which may
1278 be passed a pointer to something we haven't written yet). */
1279 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1281 /* Remember the last function call for limiting lifetimes. */
1282 free_INSN_LIST_list (&deps->last_function_call);
1283 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1285 /* Before reload, begin a post-call group, so as to keep the
1286 lifetimes of hard registers correct. */
1287 if (! reload_completed)
1288 deps->in_post_call_group_p = post_call;
1291 /* See comments on reemit_notes as to why we do this.
1292 ??? Actually, the reemit_notes just say what is done, not why. */
1295 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1296 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1297 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1298 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1302 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1303 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1304 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1306 rtx_region = const0_rtx;
1308 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1311 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1312 GEN_INT (NOTE_LINE_NUMBER (insn)),
1314 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1317 if (current_sched_info->use_cselib)
1318 cselib_process_insn (insn);
1320 /* Now that we have completed handling INSN, check and see if it is
1321 a CLOBBER beginning a libcall block. If it is, record the
1322 end of the libcall sequence.
1324 We want to schedule libcall blocks as a unit before reload. While
1325 this restricts scheduling, it preserves the meaning of a libcall
1328 As a side effect, we may get better code due to decreased register
1329 pressure as well as less chance of a foreign insn appearing in
1331 if (!reload_completed
1332 /* Note we may have nested libcall sequences. We only care about
1333 the outermost libcall sequence. */
1334 && deps->libcall_block_tail_insn == 0
1335 /* The sequence must start with a clobber of a register. */
1336 && NONJUMP_INSN_P (insn)
1337 && GET_CODE (PATTERN (insn)) == CLOBBER
1338 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1339 && REG_P (XEXP (PATTERN (insn), 0))
1340 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1341 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1342 && (end_seq = XEXP (link, 0)) != 0
1343 /* The insn referenced by the REG_LIBCALL note must be a
1344 simple nop copy with the same destination as the register
1345 mentioned in the clobber. */
1346 && (set = single_set (end_seq)) != 0
1347 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1348 /* And finally the insn referenced by the REG_LIBCALL must
1349 also contain a REG_EQUAL note and a REG_RETVAL note. */
1350 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1351 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1352 deps->libcall_block_tail_insn = XEXP (link, 0);
1354 /* If we have reached the end of a libcall block, then close the
1356 if (deps->libcall_block_tail_insn == insn)
1357 deps->libcall_block_tail_insn = 0;
1361 if (current_sched_info->use_cselib)
1370 /* The following function adds forward dependence (FROM, TO) with
1371 given DEP_TYPE. The forward dependence should be not exist before. */
1374 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1378 #ifdef ENABLE_CHECKING
1379 /* If add_dependence is working properly there should never
1380 be notes, deleted insns or duplicates in the backward
1381 links. Thus we need not check for them here.
1383 However, if we have enabled checking we might as well go
1384 ahead and verify that add_dependence worked properly. */
1386 || INSN_DELETED_P (from)
1387 || (forward_dependency_cache != NULL
1388 && bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1390 || (forward_dependency_cache == NULL
1391 && find_insn_list (to, INSN_DEPEND (from))))
1393 if (forward_dependency_cache != NULL)
1394 bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1398 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1400 PUT_REG_NOTE_KIND (new_link, dep_type);
1402 INSN_DEPEND (from) = new_link;
1403 INSN_DEP_COUNT (to) += 1;
1406 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1407 dependences from LOG_LINKS to build forward dependences in
1411 compute_forward_dependences (rtx head, rtx tail)
1416 next_tail = NEXT_INSN (tail);
1417 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1419 if (! INSN_P (insn))
1422 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1423 add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1427 /* Initialize variables for region data dependence analysis.
1428 n_bbs is the number of region blocks. */
1431 init_deps (struct deps *deps)
1433 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1435 deps->max_reg = max_reg;
1436 deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1437 INIT_REG_SET (&deps->reg_last_in_use);
1438 INIT_REG_SET (&deps->reg_conditional_sets);
1440 deps->pending_read_insns = 0;
1441 deps->pending_read_mems = 0;
1442 deps->pending_write_insns = 0;
1443 deps->pending_write_mems = 0;
1444 deps->pending_lists_length = 0;
1445 deps->pending_flush_length = 0;
1446 deps->last_pending_memory_flush = 0;
1447 deps->last_function_call = 0;
1448 deps->sched_before_next_call = 0;
1449 deps->in_post_call_group_p = not_post_call;
1450 deps->libcall_block_tail_insn = 0;
1453 /* Free insn lists found in DEPS. */
1456 free_deps (struct deps *deps)
1460 free_INSN_LIST_list (&deps->pending_read_insns);
1461 free_EXPR_LIST_list (&deps->pending_read_mems);
1462 free_INSN_LIST_list (&deps->pending_write_insns);
1463 free_EXPR_LIST_list (&deps->pending_write_mems);
1464 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1466 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1467 times. For a testcase with 42000 regs and 8000 small basic blocks,
1468 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1469 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1471 struct deps_reg *reg_last = &deps->reg_last[i];
1473 free_INSN_LIST_list (®_last->uses);
1475 free_INSN_LIST_list (®_last->sets);
1476 if (reg_last->clobbers)
1477 free_INSN_LIST_list (®_last->clobbers);
1479 CLEAR_REG_SET (&deps->reg_last_in_use);
1480 CLEAR_REG_SET (&deps->reg_conditional_sets);
1482 free (deps->reg_last);
1485 /* If it is profitable to use them, initialize caches for tracking
1486 dependency information. LUID is the number of insns to be scheduled,
1487 it is used in the estimate of profitability. */
1490 init_dependency_caches (int luid)
1492 /* ?!? We could save some memory by computing a per-region luid mapping
1493 which could reduce both the number of vectors in the cache and the size
1494 of each vector. Instead we just avoid the cache entirely unless the
1495 average number of instructions in a basic block is very high. See
1496 the comment before the declaration of true_dependency_cache for
1497 what we consider "very high". */
1498 if (luid / n_basic_blocks > 100 * 5)
1501 true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1502 anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1503 output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1504 #ifdef ENABLE_CHECKING
1505 forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1507 for (i = 0; i < luid; i++)
1509 bitmap_initialize (&true_dependency_cache[i], 0);
1510 bitmap_initialize (&anti_dependency_cache[i], 0);
1511 bitmap_initialize (&output_dependency_cache[i], 0);
1512 #ifdef ENABLE_CHECKING
1513 bitmap_initialize (&forward_dependency_cache[i], 0);
1520 /* Free the caches allocated in init_dependency_caches. */
1523 free_dependency_caches (void)
1525 if (true_dependency_cache)
1529 for (i = 0; i < cache_size; i++)
1531 bitmap_clear (&true_dependency_cache[i]);
1532 bitmap_clear (&anti_dependency_cache[i]);
1533 bitmap_clear (&output_dependency_cache[i]);
1534 #ifdef ENABLE_CHECKING
1535 bitmap_clear (&forward_dependency_cache[i]);
1538 free (true_dependency_cache);
1539 true_dependency_cache = NULL;
1540 free (anti_dependency_cache);
1541 anti_dependency_cache = NULL;
1542 free (output_dependency_cache);
1543 output_dependency_cache = NULL;
1544 #ifdef ENABLE_CHECKING
1545 free (forward_dependency_cache);
1546 forward_dependency_cache = NULL;
1551 /* Initialize some global variables needed by the dependency analysis
1555 init_deps_global (void)
1557 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1558 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1559 reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1560 reg_pending_barrier = NOT_A_BARRIER;
1563 /* Free everything used by the dependency analysis code. */
1566 finish_deps_global (void)
1568 FREE_REG_SET (reg_pending_sets);
1569 FREE_REG_SET (reg_pending_clobbers);
1570 FREE_REG_SET (reg_pending_uses);