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 delete_all_dependences (rtx);
98 static void fixup_sched_groups (rtx);
100 static void flush_pending_lists (struct deps *, rtx, int, int);
101 static void sched_analyze_1 (struct deps *, rtx, rtx);
102 static void sched_analyze_2 (struct deps *, rtx, rtx);
103 static void sched_analyze_insn (struct deps *, rtx, rtx, rtx);
105 static rtx sched_get_condition (rtx);
106 static int conditions_mutex_p (rtx, rtx);
108 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
111 deps_may_trap_p (rtx mem)
113 rtx addr = XEXP (mem, 0);
115 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
117 rtx t = get_reg_known_value (REGNO (addr));
121 return rtx_addr_can_trap_p (addr);
124 /* Return the INSN_LIST containing INSN in LIST, or NULL
125 if LIST does not contain INSN. */
128 find_insn_list (rtx insn, rtx list)
132 if (XEXP (list, 0) == insn)
134 list = XEXP (list, 1);
139 /* Find the condition under which INSN is executed. */
142 sched_get_condition (rtx insn)
144 rtx pat = PATTERN (insn);
150 if (GET_CODE (pat) == COND_EXEC)
151 return COND_EXEC_TEST (pat);
153 if (!any_condjump_p (insn) || !onlyjump_p (insn))
156 src = SET_SRC (pc_set (insn));
158 /* The previous code here was completely invalid and could never extract
159 the condition from a jump. This code does the correct thing, but that
160 triggers latent bugs later in the scheduler on ports with conditional
161 execution. So this is disabled for now. */
162 if (XEXP (src, 2) == pc_rtx)
163 return XEXP (src, 0);
164 else if (XEXP (src, 1) == pc_rtx)
166 rtx cond = XEXP (src, 0);
167 enum rtx_code revcode = reversed_comparison_code (cond, insn);
169 if (revcode == UNKNOWN)
171 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
179 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
182 conditions_mutex_p (rtx cond1, rtx cond2)
184 if (COMPARISON_P (cond1)
185 && COMPARISON_P (cond2)
186 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
187 && XEXP (cond1, 0) == XEXP (cond2, 0)
188 && XEXP (cond1, 1) == XEXP (cond2, 1))
193 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
194 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
195 type of dependence that this link represents. The function returns
196 nonzero if a new entry has been added to insn's LOG_LINK. */
199 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
205 /* Don't depend an insn on itself. */
209 /* We can get a dependency on deleted insns due to optimizations in
210 the register allocation and reloading or due to splitting. Any
211 such dependency is useless and can be ignored. */
215 /* flow.c doesn't handle conditional lifetimes entirely correctly;
216 calls mess up the conditional lifetimes. */
217 /* ??? add_dependence is the wrong place to be eliding dependencies,
218 as that forgets that the condition expressions themselves may
220 if (!CALL_P (insn) && !CALL_P (elem))
222 cond1 = sched_get_condition (insn);
223 cond2 = sched_get_condition (elem);
225 && conditions_mutex_p (cond1, cond2)
226 /* Make sure first instruction doesn't affect condition of second
227 instruction if switched. */
228 && !modified_in_p (cond1, elem)
229 /* Make sure second instruction doesn't affect condition of first
230 instruction if switched. */
231 && !modified_in_p (cond2, insn))
236 #ifdef INSN_SCHEDULING
237 /* ??? No good way to tell from here whether we're doing interblock
238 scheduling. Possibly add another callback. */
240 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
241 No need for interblock dependences with calls, since
242 calls are not moved between blocks. Note: the edge where
243 elem is a CALL is still required. */
245 && (INSN_BB (elem) != INSN_BB (insn)))
249 /* If we already have a dependency for ELEM, then we do not need to
250 do anything. Avoiding the list walk below can cut compile times
251 dramatically for some code. */
252 if (true_dependency_cache != NULL)
254 enum reg_note present_dep_type = 0;
256 gcc_assert (anti_dependency_cache);
257 gcc_assert (output_dependency_cache);
258 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
260 /* Do nothing (present_set_type is already 0). */
262 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
264 present_dep_type = REG_DEP_ANTI;
265 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
267 present_dep_type = REG_DEP_OUTPUT;
270 if (present_p && (int) dep_type >= (int) present_dep_type)
275 /* Check that we don't already have this dependence. */
277 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
278 if (XEXP (link, 0) == elem)
280 #ifdef INSN_SCHEDULING
281 /* Clear corresponding cache entry because type of the link
283 if (true_dependency_cache != NULL)
285 enum reg_note kind = REG_NOTE_KIND (link);
289 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
293 gcc_assert (output_dependency_cache);
294 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
303 /* If this is a more restrictive type of dependence than the existing
304 one, then change the existing dependence to this type. */
305 if ((int) dep_type < (int) REG_NOTE_KIND (link))
306 PUT_REG_NOTE_KIND (link, dep_type);
308 #ifdef INSN_SCHEDULING
309 /* If we are adding a dependency to INSN's LOG_LINKs, then
310 note that in the bitmap caches of dependency information. */
311 if (true_dependency_cache != NULL)
313 if ((int) REG_NOTE_KIND (link) == 0)
314 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
316 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
317 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
319 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
320 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
326 /* Might want to check one level of transitivity to save conses. */
328 link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
329 LOG_LINKS (insn) = link;
331 /* Insn dependency, not data dependency. */
332 PUT_REG_NOTE_KIND (link, dep_type);
334 #ifdef INSN_SCHEDULING
335 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
336 in the bitmap caches of dependency information. */
337 if (true_dependency_cache != NULL)
339 if ((int) dep_type == 0)
340 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
341 else if (dep_type == REG_DEP_ANTI)
342 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
343 else if (dep_type == REG_DEP_OUTPUT)
344 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
350 /* A convenience wrapper to operate on an entire list. */
353 add_dependence_list (rtx insn, rtx list, enum reg_note dep_type)
355 for (; list; list = XEXP (list, 1))
356 add_dependence (insn, XEXP (list, 0), dep_type);
359 /* Similar, but free *LISTP at the same time. */
362 add_dependence_list_and_free (rtx insn, rtx *listp, enum reg_note dep_type)
365 for (list = *listp, *listp = NULL; list ; list = next)
367 next = XEXP (list, 1);
368 add_dependence (insn, XEXP (list, 0), dep_type);
369 free_INSN_LIST_node (list);
373 /* Clear all dependencies for an insn. */
376 delete_all_dependences (rtx insn)
378 /* Clear caches, if they exist, as well as free the dependence. */
380 #ifdef INSN_SCHEDULING
381 if (true_dependency_cache != NULL)
383 bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
384 bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
385 bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
389 free_INSN_LIST_list (&LOG_LINKS (insn));
392 /* All insns in a scheduling group except the first should only have
393 dependencies on the previous insn in the group. So we find the
394 first instruction in the scheduling group by walking the dependence
395 chains backwards. Then we add the dependencies for the group to
396 the previous nonnote insn. */
399 fixup_sched_groups (rtx insn)
403 for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
408 i = prev_nonnote_insn (i);
410 if (XEXP (link, 0) == i)
412 } while (SCHED_GROUP_P (i));
413 add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
417 delete_all_dependences (insn);
419 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote_insn (insn)))
420 add_dependence (insn, prev_nonnote_insn (insn), REG_DEP_ANTI);
423 /* Process an insn's memory dependencies. There are four kinds of
426 (0) read dependence: read follows read
427 (1) true dependence: read follows write
428 (2) anti dependence: write follows read
429 (3) output dependence: write follows write
431 We are careful to build only dependencies which actually exist, and
432 use transitivity to avoid building too many links. */
434 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
435 The MEM is a memory reference contained within INSN, which we are saving
436 so that we can do memory aliasing on it. */
439 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
444 link = alloc_INSN_LIST (insn, *insn_list);
447 if (current_sched_info->use_cselib)
449 mem = shallow_copy_rtx (mem);
450 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
452 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
455 deps->pending_lists_length++;
458 /* Make a dependency between every memory reference on the pending lists
459 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
460 dependencies for a read operation, similarly with FOR_WRITE. */
463 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
468 add_dependence_list_and_free (insn, &deps->pending_read_insns,
470 free_EXPR_LIST_list (&deps->pending_read_mems);
473 add_dependence_list_and_free (insn, &deps->pending_write_insns,
474 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
475 free_EXPR_LIST_list (&deps->pending_write_mems);
476 deps->pending_lists_length = 0;
478 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
479 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
480 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
481 deps->pending_flush_length = 1;
484 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
485 rtx, X, creating all dependencies generated by the write to the
486 destination of X, and reads of everything mentioned. */
489 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
492 rtx dest = XEXP (x, 0);
493 enum rtx_code code = GET_CODE (x);
498 if (GET_CODE (dest) == PARALLEL)
502 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
503 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
504 sched_analyze_1 (deps,
505 gen_rtx_CLOBBER (VOIDmode,
506 XEXP (XVECEXP (dest, 0, i), 0)),
509 if (GET_CODE (x) == SET)
510 sched_analyze_2 (deps, SET_SRC (x), insn);
514 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
515 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
517 if (GET_CODE (dest) == STRICT_LOW_PART
518 || GET_CODE (dest) == ZERO_EXTRACT
519 || GET_CODE (dest) == SIGN_EXTRACT
520 || read_modify_subreg_p (dest))
522 /* These both read and modify the result. We must handle
523 them as writes to get proper dependencies for following
524 instructions. We must handle them as reads to get proper
525 dependencies from this to previous instructions.
526 Thus we need to call sched_analyze_2. */
528 sched_analyze_2 (deps, XEXP (dest, 0), insn);
530 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
532 /* The second and third arguments are values read by this insn. */
533 sched_analyze_2 (deps, XEXP (dest, 1), insn);
534 sched_analyze_2 (deps, XEXP (dest, 2), insn);
536 dest = XEXP (dest, 0);
541 regno = REGNO (dest);
543 /* A hard reg in a wide mode may really be multiple registers.
544 If so, mark all of them just like the first. */
545 if (regno < FIRST_PSEUDO_REGISTER)
547 int i = hard_regno_nregs[regno][GET_MODE (dest)];
551 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
556 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
559 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
560 it does not reload. Ignore these as they have served their
562 else if (regno >= deps->max_reg)
564 gcc_assert (GET_CODE (PATTERN (insn)) == USE
565 || GET_CODE (PATTERN (insn)) == CLOBBER);
570 SET_REGNO_REG_SET (reg_pending_sets, regno);
572 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
574 /* Pseudos that are REG_EQUIV to something may be replaced
575 by that during reloading. We need only add dependencies for
576 the address in the REG_EQUIV note. */
577 if (!reload_completed && get_reg_known_equiv_p (regno))
579 rtx t = get_reg_known_value (regno);
581 sched_analyze_2 (deps, XEXP (t, 0), insn);
584 /* Don't let it cross a call after scheduling if it doesn't
585 already cross one. */
586 if (REG_N_CALLS_CROSSED (regno) == 0)
587 add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
590 else if (MEM_P (dest))
592 /* Writing memory. */
595 if (current_sched_info->use_cselib)
597 t = shallow_copy_rtx (dest);
598 cselib_lookup (XEXP (t, 0), Pmode, 1);
599 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
603 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
605 /* Flush all pending reads and writes to prevent the pending lists
606 from getting any larger. Insn scheduling runs too slowly when
607 these lists get long. When compiling GCC with itself,
608 this flush occurs 8 times for sparc, and 10 times for m88k using
609 the default value of 32. */
610 flush_pending_lists (deps, insn, false, true);
614 rtx pending, pending_mem;
616 pending = deps->pending_read_insns;
617 pending_mem = deps->pending_read_mems;
620 if (anti_dependence (XEXP (pending_mem, 0), t))
621 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
623 pending = XEXP (pending, 1);
624 pending_mem = XEXP (pending_mem, 1);
627 pending = deps->pending_write_insns;
628 pending_mem = deps->pending_write_mems;
631 if (output_dependence (XEXP (pending_mem, 0), t))
632 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
634 pending = XEXP (pending, 1);
635 pending_mem = XEXP (pending_mem, 1);
638 add_dependence_list (insn, deps->last_pending_memory_flush,
641 add_insn_mem_dependence (deps, &deps->pending_write_insns,
642 &deps->pending_write_mems, insn, dest);
644 sched_analyze_2 (deps, XEXP (dest, 0), insn);
648 if (GET_CODE (x) == SET)
649 sched_analyze_2 (deps, SET_SRC (x), insn);
652 /* Analyze the uses of memory and registers in rtx X in INSN. */
655 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
675 /* Ignore constants. Note that we must handle CONST_DOUBLE here
676 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
677 this does not mean that this insn is using cc0. */
682 /* User of CC0 depends on immediately preceding insn. */
683 SCHED_GROUP_P (insn) = 1;
684 /* Don't move CC0 setter to another block (it can set up the
685 same flag for previous CC0 users which is safe). */
686 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
692 int regno = REGNO (x);
693 if (regno < FIRST_PSEUDO_REGISTER)
695 int i = hard_regno_nregs[regno][GET_MODE (x)];
697 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
699 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
700 it does not reload. Ignore these as they have served their
702 else if (regno >= deps->max_reg)
704 gcc_assert (GET_CODE (PATTERN (insn)) == USE
705 || GET_CODE (PATTERN (insn)) == CLOBBER);
709 SET_REGNO_REG_SET (reg_pending_uses, regno);
711 /* Pseudos that are REG_EQUIV to something may be replaced
712 by that during reloading. We need only add dependencies for
713 the address in the REG_EQUIV note. */
714 if (!reload_completed && get_reg_known_equiv_p (regno))
716 rtx t = get_reg_known_value (regno);
718 sched_analyze_2 (deps, XEXP (t, 0), insn);
721 /* If the register does not already cross any calls, then add this
722 insn to the sched_before_next_call list so that it will still
723 not cross calls after scheduling. */
724 if (REG_N_CALLS_CROSSED (regno) == 0)
725 deps->sched_before_next_call
726 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
733 /* Reading memory. */
735 rtx pending, pending_mem;
738 if (current_sched_info->use_cselib)
740 t = shallow_copy_rtx (t);
741 cselib_lookup (XEXP (t, 0), Pmode, 1);
742 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
745 pending = deps->pending_read_insns;
746 pending_mem = deps->pending_read_mems;
749 if (read_dependence (XEXP (pending_mem, 0), t))
750 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
752 pending = XEXP (pending, 1);
753 pending_mem = XEXP (pending_mem, 1);
756 pending = deps->pending_write_insns;
757 pending_mem = deps->pending_write_mems;
760 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
762 add_dependence (insn, XEXP (pending, 0), 0);
764 pending = XEXP (pending, 1);
765 pending_mem = XEXP (pending_mem, 1);
768 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
769 if (!JUMP_P (XEXP (u, 0))
770 || deps_may_trap_p (x))
771 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
773 /* Always add these dependencies to pending_reads, since
774 this insn may be followed by a write. */
775 add_insn_mem_dependence (deps, &deps->pending_read_insns,
776 &deps->pending_read_mems, insn, x);
778 /* Take advantage of tail recursion here. */
779 sched_analyze_2 (deps, XEXP (x, 0), insn);
783 /* Force pending stores to memory in case a trap handler needs them. */
785 flush_pending_lists (deps, insn, true, false);
790 case UNSPEC_VOLATILE:
792 /* Traditional and volatile asm instructions must be considered to use
793 and clobber all hard registers, all pseudo-registers and all of
794 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
796 Consider for instance a volatile asm that changes the fpu rounding
797 mode. An insn should not be moved across this even if it only uses
798 pseudo-regs because it might give an incorrectly rounded result. */
799 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
800 reg_pending_barrier = TRUE_BARRIER;
802 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
803 We can not just fall through here since then we would be confused
804 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
805 traditional asms unlike their normal usage. */
807 if (code == ASM_OPERANDS)
809 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
810 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
820 /* These both read and modify the result. We must handle them as writes
821 to get proper dependencies for following instructions. We must handle
822 them as reads to get proper dependencies from this to previous
823 instructions. Thus we need to pass them to both sched_analyze_1
824 and sched_analyze_2. We must call sched_analyze_2 first in order
825 to get the proper antecedent for the read. */
826 sched_analyze_2 (deps, XEXP (x, 0), insn);
827 sched_analyze_1 (deps, x, insn);
832 /* op0 = op0 + op1 */
833 sched_analyze_2 (deps, XEXP (x, 0), insn);
834 sched_analyze_2 (deps, XEXP (x, 1), insn);
835 sched_analyze_1 (deps, x, insn);
842 /* Other cases: walk the insn. */
843 fmt = GET_RTX_FORMAT (code);
844 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
847 sched_analyze_2 (deps, XEXP (x, i), insn);
848 else if (fmt[i] == 'E')
849 for (j = 0; j < XVECLEN (x, i); j++)
850 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
854 /* Analyze an INSN with pattern X to find all dependencies. */
857 sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
859 RTX_CODE code = GET_CODE (x);
862 reg_set_iterator rsi;
864 if (code == COND_EXEC)
866 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
868 /* ??? Should be recording conditions so we reduce the number of
869 false dependencies. */
870 x = COND_EXEC_CODE (x);
873 if (code == SET || code == CLOBBER)
875 sched_analyze_1 (deps, x, insn);
877 /* Bare clobber insns are used for letting life analysis, reg-stack
878 and others know that a value is dead. Depend on the last call
879 instruction so that reg-stack won't get confused. */
881 add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
883 else if (code == PARALLEL)
885 for (i = XVECLEN (x, 0); i--;)
887 rtx sub = XVECEXP (x, 0, i);
888 code = GET_CODE (sub);
890 if (code == COND_EXEC)
892 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
893 sub = COND_EXEC_CODE (sub);
894 code = GET_CODE (sub);
896 if (code == SET || code == CLOBBER)
897 sched_analyze_1 (deps, sub, insn);
899 sched_analyze_2 (deps, sub, insn);
903 sched_analyze_2 (deps, x, insn);
905 /* Mark registers CLOBBERED or used by called function. */
908 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
910 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
911 sched_analyze_1 (deps, XEXP (link, 0), insn);
913 sched_analyze_2 (deps, XEXP (link, 0), insn);
915 if (find_reg_note (insn, REG_SETJMP, NULL))
916 reg_pending_barrier = MOVE_BARRIER;
922 next = next_nonnote_insn (insn);
923 if (next && BARRIER_P (next))
924 reg_pending_barrier = TRUE_BARRIER;
927 rtx pending, pending_mem;
928 regset_head tmp_uses, tmp_sets;
929 INIT_REG_SET (&tmp_uses);
930 INIT_REG_SET (&tmp_sets);
932 (*current_sched_info->compute_jump_reg_dependencies)
933 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
934 /* Make latency of jump equal to 0 by using anti-dependence. */
935 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
937 struct deps_reg *reg_last = &deps->reg_last[i];
938 add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
939 add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
940 reg_last->uses_length++;
941 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
943 IOR_REG_SET (reg_pending_sets, &tmp_sets);
945 CLEAR_REG_SET (&tmp_uses);
946 CLEAR_REG_SET (&tmp_sets);
948 /* All memory writes and volatile reads must happen before the
949 jump. Non-volatile reads must happen before the jump iff
950 the result is needed by the above register used mask. */
952 pending = deps->pending_write_insns;
953 pending_mem = deps->pending_write_mems;
956 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
957 pending = XEXP (pending, 1);
958 pending_mem = XEXP (pending_mem, 1);
961 pending = deps->pending_read_insns;
962 pending_mem = deps->pending_read_mems;
965 if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
966 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
967 pending = XEXP (pending, 1);
968 pending_mem = XEXP (pending_mem, 1);
971 add_dependence_list (insn, deps->last_pending_memory_flush,
976 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
977 block, then we must be sure that no instructions are scheduled across it.
978 Otherwise, the reg_n_refs info (which depends on loop_depth) would
984 /* Update loop_notes with any notes from this insn. Also determine
985 if any of the notes on the list correspond to instruction scheduling
986 barriers (loop, eh & setjmp notes, but not range notes). */
988 while (XEXP (link, 1))
990 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
991 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
992 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
993 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
994 reg_pending_barrier = MOVE_BARRIER;
996 link = XEXP (link, 1);
998 XEXP (link, 1) = REG_NOTES (insn);
999 REG_NOTES (insn) = loop_notes;
1002 /* If this instruction can throw an exception, then moving it changes
1003 where block boundaries fall. This is mighty confusing elsewhere.
1004 Therefore, prevent such an instruction from being moved. */
1005 if (can_throw_internal (insn))
1006 reg_pending_barrier = MOVE_BARRIER;
1008 /* Add dependencies if a scheduling barrier was found. */
1009 if (reg_pending_barrier)
1011 /* In the case of barrier the most added dependencies are not
1012 real, so we use anti-dependence here. */
1013 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1015 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1017 struct deps_reg *reg_last = &deps->reg_last[i];
1018 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1020 (insn, reg_last->sets,
1021 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1023 (insn, reg_last->clobbers,
1024 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1029 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1031 struct deps_reg *reg_last = &deps->reg_last[i];
1032 add_dependence_list_and_free (insn, ®_last->uses,
1034 add_dependence_list_and_free
1035 (insn, ®_last->sets,
1036 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1037 add_dependence_list_and_free
1038 (insn, ®_last->clobbers,
1039 reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
1040 reg_last->uses_length = 0;
1041 reg_last->clobbers_length = 0;
1045 for (i = 0; i < (unsigned)deps->max_reg; i++)
1047 struct deps_reg *reg_last = &deps->reg_last[i];
1048 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1049 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1052 flush_pending_lists (deps, insn, true, true);
1053 CLEAR_REG_SET (&deps->reg_conditional_sets);
1054 reg_pending_barrier = NOT_A_BARRIER;
1058 /* If the current insn is conditional, we can't free any
1060 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1062 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1064 struct deps_reg *reg_last = &deps->reg_last[i];
1065 add_dependence_list (insn, reg_last->sets, 0);
1066 add_dependence_list (insn, reg_last->clobbers, 0);
1067 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1068 reg_last->uses_length++;
1070 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1072 struct deps_reg *reg_last = &deps->reg_last[i];
1073 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1074 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1075 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1076 reg_last->clobbers_length++;
1078 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1080 struct deps_reg *reg_last = &deps->reg_last[i];
1081 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1082 add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1083 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1084 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1085 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1090 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1092 struct deps_reg *reg_last = &deps->reg_last[i];
1093 add_dependence_list (insn, reg_last->sets, 0);
1094 add_dependence_list (insn, reg_last->clobbers, 0);
1095 reg_last->uses_length++;
1096 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1098 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1100 struct deps_reg *reg_last = &deps->reg_last[i];
1101 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1102 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1104 add_dependence_list_and_free (insn, ®_last->sets,
1106 add_dependence_list_and_free (insn, ®_last->uses,
1108 add_dependence_list_and_free (insn, ®_last->clobbers,
1110 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1111 reg_last->clobbers_length = 0;
1112 reg_last->uses_length = 0;
1116 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1117 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1119 reg_last->clobbers_length++;
1120 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1122 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1124 struct deps_reg *reg_last = &deps->reg_last[i];
1125 add_dependence_list_and_free (insn, ®_last->sets,
1127 add_dependence_list_and_free (insn, ®_last->clobbers,
1129 add_dependence_list_and_free (insn, ®_last->uses,
1131 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1132 reg_last->uses_length = 0;
1133 reg_last->clobbers_length = 0;
1134 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1138 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1139 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1140 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1142 CLEAR_REG_SET (reg_pending_uses);
1143 CLEAR_REG_SET (reg_pending_clobbers);
1144 CLEAR_REG_SET (reg_pending_sets);
1146 /* If we are currently in a libcall scheduling group, then mark the
1147 current insn as being in a scheduling group and that it can not
1148 be moved into a different basic block. */
1150 if (deps->libcall_block_tail_insn)
1152 SCHED_GROUP_P (insn) = 1;
1153 CANT_MOVE (insn) = 1;
1156 /* If a post-call group is still open, see if it should remain so.
1157 This insn must be a simple move of a hard reg to a pseudo or
1160 We must avoid moving these insns for correctness on
1161 SMALL_REGISTER_CLASS machines, and for special registers like
1162 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1163 hard regs for all targets. */
1165 if (deps->in_post_call_group_p)
1167 rtx tmp, set = single_set (insn);
1168 int src_regno, dest_regno;
1171 goto end_call_group;
1173 tmp = SET_DEST (set);
1174 if (GET_CODE (tmp) == SUBREG)
1175 tmp = SUBREG_REG (tmp);
1177 dest_regno = REGNO (tmp);
1179 goto end_call_group;
1181 tmp = SET_SRC (set);
1182 if (GET_CODE (tmp) == SUBREG)
1183 tmp = SUBREG_REG (tmp);
1184 if ((GET_CODE (tmp) == PLUS
1185 || GET_CODE (tmp) == MINUS)
1186 && REG_P (XEXP (tmp, 0))
1187 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1188 && dest_regno == STACK_POINTER_REGNUM)
1189 src_regno = STACK_POINTER_REGNUM;
1190 else if (REG_P (tmp))
1191 src_regno = REGNO (tmp);
1193 goto end_call_group;
1195 if (src_regno < FIRST_PSEUDO_REGISTER
1196 || dest_regno < FIRST_PSEUDO_REGISTER)
1198 if (deps->in_post_call_group_p == post_call_initial)
1199 deps->in_post_call_group_p = post_call;
1201 SCHED_GROUP_P (insn) = 1;
1202 CANT_MOVE (insn) = 1;
1207 deps->in_post_call_group_p = not_post_call;
1211 /* Fixup the dependencies in the sched group. */
1212 if (SCHED_GROUP_P (insn))
1213 fixup_sched_groups (insn);
1216 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1217 for every dependency. */
1220 sched_analyze (struct deps *deps, rtx head, rtx tail)
1225 if (current_sched_info->use_cselib)
1228 /* Before reload, if the previous block ended in a call, show that
1229 we are inside a post-call group, so as to keep the lifetimes of
1230 hard registers correct. */
1231 if (! reload_completed && !LABEL_P (head))
1233 insn = prev_nonnote_insn (head);
1234 if (insn && CALL_P (insn))
1235 deps->in_post_call_group_p = post_call_initial;
1237 for (insn = head;; insn = NEXT_INSN (insn))
1239 rtx link, end_seq, r0, set;
1241 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1243 /* Clear out the stale LOG_LINKS from flow. */
1244 free_INSN_LIST_list (&LOG_LINKS (insn));
1246 /* Make each JUMP_INSN a scheduling barrier for memory
1250 /* Keep the list a reasonable size. */
1251 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1252 flush_pending_lists (deps, insn, true, true);
1254 deps->last_pending_memory_flush
1255 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1257 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1260 else if (CALL_P (insn))
1264 CANT_MOVE (insn) = 1;
1266 /* Clear out the stale LOG_LINKS from flow. */
1267 free_INSN_LIST_list (&LOG_LINKS (insn));
1269 if (find_reg_note (insn, REG_SETJMP, NULL))
1271 /* This is setjmp. Assume that all registers, not just
1272 hard registers, may be clobbered by this call. */
1273 reg_pending_barrier = MOVE_BARRIER;
1277 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1278 /* A call may read and modify global register variables. */
1281 SET_REGNO_REG_SET (reg_pending_sets, i);
1282 SET_REGNO_REG_SET (reg_pending_uses, i);
1284 /* Other call-clobbered hard regs may be clobbered.
1285 Since we only have a choice between 'might be clobbered'
1286 and 'definitely not clobbered', we must include all
1287 partly call-clobbered registers here. */
1288 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1289 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1290 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1291 /* We don't know what set of fixed registers might be used
1292 by the function, but it is certain that the stack pointer
1293 is among them, but be conservative. */
1294 else if (fixed_regs[i])
1295 SET_REGNO_REG_SET (reg_pending_uses, i);
1296 /* The frame pointer is normally not used by the function
1297 itself, but by the debugger. */
1298 /* ??? MIPS o32 is an exception. It uses the frame pointer
1299 in the macro expansion of jal but does not represent this
1300 fact in the call_insn rtl. */
1301 else if (i == FRAME_POINTER_REGNUM
1302 || (i == HARD_FRAME_POINTER_REGNUM
1303 && (! reload_completed || frame_pointer_needed)))
1304 SET_REGNO_REG_SET (reg_pending_uses, i);
1307 /* For each insn which shouldn't cross a call, add a dependence
1308 between that insn and this call insn. */
1309 add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1312 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1315 /* In the absence of interprocedural alias analysis, we must flush
1316 all pending reads and writes, and start new dependencies starting
1317 from here. But only flush writes for constant calls (which may
1318 be passed a pointer to something we haven't written yet). */
1319 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1321 /* Remember the last function call for limiting lifetimes. */
1322 free_INSN_LIST_list (&deps->last_function_call);
1323 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1325 /* Before reload, begin a post-call group, so as to keep the
1326 lifetimes of hard registers correct. */
1327 if (! reload_completed)
1328 deps->in_post_call_group_p = post_call;
1331 /* See comments on reemit_notes as to why we do this.
1332 ??? Actually, the reemit_notes just say what is done, not why. */
1335 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1336 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1337 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1338 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1342 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1343 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1344 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1346 rtx_region = const0_rtx;
1348 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1351 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1352 GEN_INT (NOTE_LINE_NUMBER (insn)),
1354 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1357 if (current_sched_info->use_cselib)
1358 cselib_process_insn (insn);
1360 /* Now that we have completed handling INSN, check and see if it is
1361 a CLOBBER beginning a libcall block. If it is, record the
1362 end of the libcall sequence.
1364 We want to schedule libcall blocks as a unit before reload. While
1365 this restricts scheduling, it preserves the meaning of a libcall
1368 As a side effect, we may get better code due to decreased register
1369 pressure as well as less chance of a foreign insn appearing in
1371 if (!reload_completed
1372 /* Note we may have nested libcall sequences. We only care about
1373 the outermost libcall sequence. */
1374 && deps->libcall_block_tail_insn == 0
1375 /* The sequence must start with a clobber of a register. */
1376 && NONJUMP_INSN_P (insn)
1377 && GET_CODE (PATTERN (insn)) == CLOBBER
1378 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1379 && REG_P (XEXP (PATTERN (insn), 0))
1380 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1381 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1382 && (end_seq = XEXP (link, 0)) != 0
1383 /* The insn referenced by the REG_LIBCALL note must be a
1384 simple nop copy with the same destination as the register
1385 mentioned in the clobber. */
1386 && (set = single_set (end_seq)) != 0
1387 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1388 /* And finally the insn referenced by the REG_LIBCALL must
1389 also contain a REG_EQUAL note and a REG_RETVAL note. */
1390 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1391 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1392 deps->libcall_block_tail_insn = XEXP (link, 0);
1394 /* If we have reached the end of a libcall block, then close the
1396 if (deps->libcall_block_tail_insn == insn)
1397 deps->libcall_block_tail_insn = 0;
1401 if (current_sched_info->use_cselib)
1410 /* The following function adds forward dependence (FROM, TO) with
1411 given DEP_TYPE. The forward dependence should be not exist before. */
1414 add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
1418 #ifdef ENABLE_CHECKING
1419 /* If add_dependence is working properly there should never
1420 be notes, deleted insns or duplicates in the backward
1421 links. Thus we need not check for them here.
1423 However, if we have enabled checking we might as well go
1424 ahead and verify that add_dependence worked properly. */
1425 gcc_assert (!NOTE_P (from));
1426 gcc_assert (!INSN_DELETED_P (from));
1427 if (forward_dependency_cache)
1428 gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1431 gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1433 /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
1434 if (forward_dependency_cache != NULL)
1435 bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1439 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1441 PUT_REG_NOTE_KIND (new_link, dep_type);
1443 INSN_DEPEND (from) = new_link;
1444 INSN_DEP_COUNT (to) += 1;
1447 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1448 dependences from LOG_LINKS to build forward dependences in
1452 compute_forward_dependences (rtx head, rtx tail)
1457 next_tail = NEXT_INSN (tail);
1458 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1460 if (! INSN_P (insn))
1463 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1464 add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1468 /* Initialize variables for region data dependence analysis.
1469 n_bbs is the number of region blocks. */
1472 init_deps (struct deps *deps)
1474 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1476 deps->max_reg = max_reg;
1477 deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
1478 INIT_REG_SET (&deps->reg_last_in_use);
1479 INIT_REG_SET (&deps->reg_conditional_sets);
1481 deps->pending_read_insns = 0;
1482 deps->pending_read_mems = 0;
1483 deps->pending_write_insns = 0;
1484 deps->pending_write_mems = 0;
1485 deps->pending_lists_length = 0;
1486 deps->pending_flush_length = 0;
1487 deps->last_pending_memory_flush = 0;
1488 deps->last_function_call = 0;
1489 deps->sched_before_next_call = 0;
1490 deps->in_post_call_group_p = not_post_call;
1491 deps->libcall_block_tail_insn = 0;
1494 /* Free insn lists found in DEPS. */
1497 free_deps (struct deps *deps)
1500 reg_set_iterator rsi;
1502 free_INSN_LIST_list (&deps->pending_read_insns);
1503 free_EXPR_LIST_list (&deps->pending_read_mems);
1504 free_INSN_LIST_list (&deps->pending_write_insns);
1505 free_EXPR_LIST_list (&deps->pending_write_mems);
1506 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1508 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1509 times. For a testcase with 42000 regs and 8000 small basic blocks,
1510 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1511 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1513 struct deps_reg *reg_last = &deps->reg_last[i];
1515 free_INSN_LIST_list (®_last->uses);
1517 free_INSN_LIST_list (®_last->sets);
1518 if (reg_last->clobbers)
1519 free_INSN_LIST_list (®_last->clobbers);
1521 CLEAR_REG_SET (&deps->reg_last_in_use);
1522 CLEAR_REG_SET (&deps->reg_conditional_sets);
1524 free (deps->reg_last);
1527 /* If it is profitable to use them, initialize caches for tracking
1528 dependency information. LUID is the number of insns to be scheduled,
1529 it is used in the estimate of profitability. */
1532 init_dependency_caches (int luid)
1534 /* ?!? We could save some memory by computing a per-region luid mapping
1535 which could reduce both the number of vectors in the cache and the size
1536 of each vector. Instead we just avoid the cache entirely unless the
1537 average number of instructions in a basic block is very high. See
1538 the comment before the declaration of true_dependency_cache for
1539 what we consider "very high". */
1540 if (luid / n_basic_blocks > 100 * 5)
1543 true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1544 anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1545 output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1546 #ifdef ENABLE_CHECKING
1547 forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
1549 for (i = 0; i < luid; i++)
1551 bitmap_initialize (&true_dependency_cache[i], 0);
1552 bitmap_initialize (&anti_dependency_cache[i], 0);
1553 bitmap_initialize (&output_dependency_cache[i], 0);
1554 #ifdef ENABLE_CHECKING
1555 bitmap_initialize (&forward_dependency_cache[i], 0);
1562 /* Free the caches allocated in init_dependency_caches. */
1565 free_dependency_caches (void)
1567 if (true_dependency_cache)
1571 for (i = 0; i < cache_size; i++)
1573 bitmap_clear (&true_dependency_cache[i]);
1574 bitmap_clear (&anti_dependency_cache[i]);
1575 bitmap_clear (&output_dependency_cache[i]);
1576 #ifdef ENABLE_CHECKING
1577 bitmap_clear (&forward_dependency_cache[i]);
1580 free (true_dependency_cache);
1581 true_dependency_cache = NULL;
1582 free (anti_dependency_cache);
1583 anti_dependency_cache = NULL;
1584 free (output_dependency_cache);
1585 output_dependency_cache = NULL;
1586 #ifdef ENABLE_CHECKING
1587 free (forward_dependency_cache);
1588 forward_dependency_cache = NULL;
1593 /* Initialize some global variables needed by the dependency analysis
1597 init_deps_global (void)
1599 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1600 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1601 reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1602 reg_pending_barrier = NOT_A_BARRIER;
1605 /* Free everything used by the dependency analysis code. */
1608 finish_deps_global (void)
1610 FREE_REG_SET (reg_pending_sets);
1611 FREE_REG_SET (reg_pending_clobbers);
1612 FREE_REG_SET (reg_pending_uses);