1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000 Free Software Foundation, Inc.
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
13 GNU CC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to the Free
20 the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* Forward declaration. */
26 /* Describe state of dependencies used during sched_analyze phase. */
29 /* The *_insns and *_mems are paired lists. Each pending memory operation
30 will have a pointer to the MEM rtx on one list and a pointer to the
31 containing insn on the other list in the same place in the list. */
33 /* We can't use add_dependence like the old code did, because a single insn
34 may have multiple memory accesses, and hence needs to be on the list
35 once for each memory access. Add_dependence won't let you add an insn
36 to a list more than once. */
38 /* An INSN_LIST containing all insns with pending read operations. */
39 rtx pending_read_insns
;
41 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
42 rtx pending_read_mems
;
44 /* An INSN_LIST containing all insns with pending write operations. */
45 rtx pending_write_insns
;
47 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
48 rtx pending_write_mems
;
50 /* Indicates the combined length of the two pending lists. We must prevent
51 these lists from ever growing too large since the number of dependencies
52 produced is at least O(N*N), and execution time is at least O(4*N*N), as
53 a function of the length of these pending lists. */
54 int pending_lists_length
;
56 /* The last insn upon which all memory references must depend.
57 This is an insn which flushed the pending lists, creating a dependency
58 between it and all previously pending memory references. This creates
59 a barrier (or a checkpoint) which no memory reference is allowed to cross.
61 This includes all non constant CALL_INSNs. When we do interprocedural
62 alias analysis, this restriction can be relaxed.
63 This may also be an INSN that writes memory if the pending lists grow
65 rtx last_pending_memory_flush
;
67 /* The last function call we have seen. All hard regs, and, of course,
68 the last function call, must depend on this. */
69 rtx last_function_call
;
71 /* Used to keep post-call psuedo/hard reg movements together with
73 int in_post_call_group_p
;
75 /* The LOG_LINKS field of this is a list of insns which use a pseudo
76 register that does not already cross a call. We create
77 dependencies between each of those insn and the next call insn,
78 to ensure that they won't cross a call after scheduling is done. */
79 rtx sched_before_next_call
;
81 /* The maximum register number for the following arrays. Before reload
82 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
85 /* Element N is the next insn that sets (hard or pseudo) register
86 N within the current basic block; or zero, if there is no
87 such insn. Needed for new registers which may be introduced
88 by splitting insns. */
96 /* Element N is set for each register that has any non-zero element
97 in reg_last[N].{uses,sets,clobbers}. */
98 regset_head reg_last_in_use
;
101 /* This structure holds some state of the current scheduling pass, and
102 contains some function pointers that abstract out some of the non-generic
103 functionality from functions such as schedule_block or schedule_insn.
104 There is one global variable, current_sched_info, which points to the
105 sched_info structure currently in use. */
108 /* Add all insns that are initially ready to the ready list. Called once
109 before scheduling a set of insns. */
110 void (*init_ready_list
) PARAMS ((struct ready_list
*));
111 /* Called after taking an insn from the ready list. Returns nonzero if
112 this insn can be scheduled, nonzero if we should silently discard it. */
113 int (*can_schedule_ready_p
) PARAMS ((rtx
));
114 /* Return nonzero if there are more insns that should be scheduled. */
115 int (*schedule_more_p
) PARAMS ((void));
116 /* Called after an insn has all its dependencies resolved. Return nonzero
117 if it should be moved to the ready list or the queue, or zero if we
118 should silently discard it. */
119 int (*new_ready
) PARAMS ((rtx
));
120 /* Compare priority of two insns. Return a positive number if the second
121 insn is to be preferred for scheduling, and a negative one if the first
122 is to be preferred. Zero if they are equally good. */
123 int (*rank
) PARAMS ((rtx
, rtx
));
124 /* Return a string that contains the insn uid and optionally anything else
125 necessary to identify this insn in an output. It's valid to use a
126 static buffer for this. The ALIGNED parameter should cause the string
127 to be formatted so that multiple output lines will line up nicely. */
128 const char *(*print_insn
) PARAMS ((rtx
, int));
129 /* Return nonzero if an insn should be included in priority
131 int (*contributes_to_priority
) PARAMS ((rtx
, rtx
));
132 /* Called when computing dependencies for a JUMP_INSN. This function
133 should store the set of registers that must be considered as set by
134 the jump in the regset. */
135 void (*compute_jump_reg_dependencies
) PARAMS ((rtx
, regset
));
137 /* The boundaries of the set of insns to be scheduled. */
138 rtx prev_head
, next_tail
;
140 /* Filled in after the schedule is finished; the first and last scheduled
144 /* If nonzero, enables an additional sanity check in schedule_block. */
145 int queue_must_finish_empty
;
148 extern struct sched_info
*current_sched_info
;
150 /* Indexed by INSN_UID, the collection of all data associated with
151 a single instruction. */
153 struct haifa_insn_data
155 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
156 it represents forward dependancies. */
159 /* The line number note in effect for each insn. For line number
160 notes, this indicates whether the note may be reused. */
163 /* Logical uid gives the original ordering of the insns. */
166 /* A priority for each insn. */
169 /* The number of incoming edges in the forward dependency graph.
170 As scheduling proceds, counts are decreased. An insn moves to
171 the ready queue when its counter reaches zero. */
174 /* An encoding of the blockage range function. Both unit and range
176 unsigned int blockage
;
178 /* Number of instructions referring to this insn. */
181 /* The minimum clock tick at which the insn becomes ready. This is
182 used to note timing constraints for the insns in the pending list. */
187 /* An encoding of the function units used. */
190 /* This weight is an estimation of the insn's contribution to
191 register pressure. */
194 /* Some insns (e.g. call) are not allowed to move across blocks. */
195 unsigned int cant_move
: 1;
197 /* Set if there's DEF-USE dependance between some speculatively
198 moved load insn and this one. */
199 unsigned int fed_by_spec_load
: 1;
200 unsigned int is_load_insn
: 1;
203 extern struct haifa_insn_data
*h_i_d
;
205 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
207 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
208 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
209 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
210 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
211 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
212 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
213 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
214 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
216 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
218 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
219 #define ENCODE_BLOCKAGE(U, R) \
220 (((U) << BLOCKAGE_BITS \
221 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
222 | MAX_BLOCKAGE_COST (R))
223 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
224 #define BLOCKAGE_RANGE(B) \
225 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
226 | ((B) & BLOCKAGE_MASK))
228 /* Encodings of the `<name>_unit_blockage_range' function. */
229 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
230 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
232 extern FILE *sched_dump
;
233 extern int sched_verbose
;
240 #define HAIFA_INLINE __inline
243 /* Functions in sched-vis.c. */
244 extern void init_target_units
PARAMS ((void));
245 extern void insn_print_units
PARAMS ((rtx
));
246 extern void init_block_visualization
PARAMS ((void));
247 extern void print_block_visualization
PARAMS ((const char *));
248 extern void visualize_scheduled_insns
PARAMS ((int));
249 extern void visualize_no_unit
PARAMS ((rtx
));
250 extern void visualize_stall_cycles
PARAMS ((int));
251 extern void visualize_alloc
PARAMS ((void));
252 extern void visualize_free
PARAMS ((void));
254 /* Functions in sched-deps.c. */
255 extern void add_dependence
PARAMS ((rtx
, rtx
, enum reg_note
));
256 extern void add_insn_mem_dependence
PARAMS ((struct deps
*, rtx
*, rtx
*, rtx
,
258 extern void sched_analyze
PARAMS ((struct deps
*, rtx
, rtx
));
259 extern void init_deps
PARAMS ((struct deps
*));
260 extern void free_deps
PARAMS ((struct deps
*));
261 extern void init_deps_global
PARAMS ((void));
262 extern void finish_deps_global
PARAMS ((void));
263 extern void compute_forward_dependences
PARAMS ((rtx
, rtx
));
264 extern int find_insn_mem_list
PARAMS ((rtx
, rtx
, rtx
, rtx
));
265 extern rtx find_insn_list
PARAMS ((rtx
, rtx
));
266 extern void init_dependency_caches
PARAMS ((int));
267 extern void free_dependency_caches
PARAMS ((void));
269 /* Functions in haifa-sched.c. */
270 extern void get_block_head_tail
PARAMS ((int, rtx
*, rtx
*));
271 extern int no_real_insns_p
PARAMS ((rtx
, rtx
));
273 extern void rm_line_notes
PARAMS ((rtx
, rtx
));
274 extern void save_line_notes
PARAMS ((int, rtx
, rtx
));
275 extern void restore_line_notes
PARAMS ((int, rtx
, rtx
));
276 extern void rm_redundant_line_notes
PARAMS ((void));
277 extern void rm_other_notes
PARAMS ((rtx
, rtx
));
279 extern int insn_issue_delay
PARAMS ((rtx
));
280 extern int set_priorities
PARAMS ((rtx
, rtx
));
282 extern void schedule_block
PARAMS ((int, int));
283 extern void sched_init
PARAMS ((FILE *));
284 extern void sched_finish
PARAMS ((void));
286 extern void ready_add
PARAMS ((struct ready_list
*, rtx
));
288 /* The following are exported for the benefit of debugging functions. It
289 would be nicer to keep them private to haifa-sched.c. */
290 extern int insn_unit
PARAMS ((rtx
));
291 extern int insn_cost
PARAMS ((rtx
, rtx
, rtx
));
292 extern rtx get_unit_last_insn
PARAMS ((int));
293 extern int actual_hazard_this_instance
PARAMS ((int, int, rtx
, int, int));