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, 2001 Free Software Foundation, Inc.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 2, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING.  If not, write to the Free
20Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2102111-1307, USA.  */
22
23/* Pointer to data describing the current DFA state.  */
24extern state_t curr_state;
25
26/* Forward declaration.  */
27struct ready_list;
28
29/* Describe state of dependencies used during sched_analyze phase.  */
30struct deps
31{
32  /* The *_insns and *_mems are paired lists.  Each pending memory operation
33     will have a pointer to the MEM rtx on one list and a pointer to the
34     containing insn on the other list in the same place in the list.  */
35
36  /* We can't use add_dependence like the old code did, because a single insn
37     may have multiple memory accesses, and hence needs to be on the list
38     once for each memory access.  Add_dependence won't let you add an insn
39     to a list more than once.  */
40
41  /* An INSN_LIST containing all insns with pending read operations.  */
42  rtx pending_read_insns;
43
44  /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
45  rtx pending_read_mems;
46
47  /* An INSN_LIST containing all insns with pending write operations.  */
48  rtx pending_write_insns;
49
50  /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
51  rtx pending_write_mems;
52
53  /* Indicates the combined length of the two pending lists.  We must prevent
54     these lists from ever growing too large since the number of dependencies
55     produced is at least O(N*N), and execution time is at least O(4*N*N), as
56     a function of the length of these pending lists.  */
57  int pending_lists_length;
58
59  /* Length of the pending memory flush list. Large functions with no
60     calls may build up extremely large lists.  */
61  int pending_flush_length;
62
63  /* The last insn upon which all memory references must depend.
64     This is an insn which flushed the pending lists, creating a dependency
65     between it and all previously pending memory references.  This creates
66     a barrier (or a checkpoint) which no memory reference is allowed to cross.
67
68     This includes all non constant CALL_INSNs.  When we do interprocedural
69     alias analysis, this restriction can be relaxed.
70     This may also be an INSN that writes memory if the pending lists grow
71     too large.  */
72  rtx last_pending_memory_flush;
73
74  /* A list of the last function calls we have seen.  We use a list to
75     represent last function calls from multiple predecessor blocks.
76     Used to prevent register lifetimes from expanding unnecessarily.  */
77  rtx last_function_call;
78
79  /* A list of insns which use a pseudo register that does not already
80     cross a call.  We create dependencies between each of those insn
81     and the next call insn, to ensure that they won't cross a call after
82     scheduling is done.  */
83  rtx sched_before_next_call;
84
85  /* Used to keep post-call psuedo/hard reg movements together with
86     the call.  */
87  bool in_post_call_group_p;
88
89  /* Set to the tail insn of the outermost libcall block.
90
91     When nonzero, we will mark each insn processed by sched_analyze_insn
92     with SCHED_GROUP_P to ensure libcalls are scheduled as a unit.  */
93  rtx libcall_block_tail_insn;
94
95  /* The maximum register number for the following arrays.  Before reload
96     this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
97  int max_reg;
98
99  /* Element N is the next insn that sets (hard or pseudo) register
100     N within the current basic block; or zero, if there is no
101     such insn.  Needed for new registers which may be introduced
102     by splitting insns.  */
103  struct deps_reg
104    {
105      rtx uses;
106      rtx sets;
107      rtx clobbers;
108      int uses_length;
109      int clobbers_length;
110    } *reg_last;
111
112  /* Element N is set for each register that has any nonzero element
113     in reg_last[N].{uses,sets,clobbers}.  */
114  regset_head reg_last_in_use;
115
116  /* Element N is set for each register that is conditionally set.  */
117  regset_head reg_conditional_sets;
118};
119
120/* This structure holds some state of the current scheduling pass, and
121   contains some function pointers that abstract out some of the non-generic
122   functionality from functions such as schedule_block or schedule_insn.
123   There is one global variable, current_sched_info, which points to the
124   sched_info structure currently in use.  */
125struct sched_info
126{
127  /* Add all insns that are initially ready to the ready list.  Called once
128     before scheduling a set of insns.  */
129  void (*init_ready_list) PARAMS ((struct ready_list *));
130  /* Called after taking an insn from the ready list.  Returns nonzero if
131     this insn can be scheduled, nonzero if we should silently discard it.  */
132  int (*can_schedule_ready_p) PARAMS ((rtx));
133  /* Return nonzero if there are more insns that should be scheduled.  */
134  int (*schedule_more_p) PARAMS ((void));
135  /* Called after an insn has all its dependencies resolved.  Return nonzero
136     if it should be moved to the ready list or the queue, or zero if we
137     should silently discard it.  */
138  int (*new_ready) PARAMS ((rtx));
139  /* Compare priority of two insns.  Return a positive number if the second
140     insn is to be preferred for scheduling, and a negative one if the first
141     is to be preferred.  Zero if they are equally good.  */
142  int (*rank) PARAMS ((rtx, rtx));
143  /* Return a string that contains the insn uid and optionally anything else
144     necessary to identify this insn in an output.  It's valid to use a
145     static buffer for this.  The ALIGNED parameter should cause the string
146     to be formatted so that multiple output lines will line up nicely.  */
147  const char *(*print_insn) PARAMS ((rtx, int));
148  /* Return nonzero if an insn should be included in priority
149     calculations.  */
150  int (*contributes_to_priority) PARAMS ((rtx, rtx));
151  /* Called when computing dependencies for a JUMP_INSN.  This function
152     should store the set of registers that must be considered as used
153     and the set of registers that must be considered as set by the jump.  */
154  void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset, regset, regset));
155
156  /* The boundaries of the set of insns to be scheduled.  */
157  rtx prev_head, next_tail;
158
159  /* Filled in after the schedule is finished; the first and last scheduled
160     insns.  */
161  rtx head, tail;
162
163  /* If nonzero, enables an additional sanity check in schedule_block.  */
164  unsigned int queue_must_finish_empty:1;
165  /* Nonzero if we should use cselib for better alias analysis.  This
166     must be 0 if the dependency information is used after sched_analyze
167     has completed, e.g. if we're using it to initialize state for successor
168     blocks in region scheduling.  */
169  unsigned int use_cselib:1;
170};
171
172extern struct sched_info *current_sched_info;
173
174/* Indexed by INSN_UID, the collection of all data associated with
175   a single instruction.  */
176
177struct haifa_insn_data
178{
179  /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
180     it represents forward dependencies.  */
181  rtx depend;
182
183  /* The line number note in effect for each insn.  For line number
184     notes, this indicates whether the note may be reused.  */
185  rtx line_note;
186
187  /* Logical uid gives the original ordering of the insns.  */
188  int luid;
189
190  /* A priority for each insn.  */
191  int priority;
192
193  /* The number of incoming edges in the forward dependency graph.
194     As scheduling proceds, counts are decreased.  An insn moves to
195     the ready queue when its counter reaches zero.  */
196  int dep_count;
197
198  /* An encoding of the blockage range function.  Both unit and range
199     are coded.  This member is used only for old pipeline interface.  */
200  unsigned int blockage;
201
202  /* Number of instructions referring to this insn.  */
203  int ref_count;
204
205  /* The minimum clock tick at which the insn becomes ready.  This is
206     used to note timing constraints for the insns in the pending list.  */
207  int tick;
208
209  short cost;
210
211  /* An encoding of the function units used.  This member is used only
212     for old pipeline interface.  */
213  short units;
214
215  /* This weight is an estimation of the insn's contribution to
216     register pressure.  */
217  short reg_weight;
218
219  /* Some insns (e.g. call) are not allowed to move across blocks.  */
220  unsigned int cant_move : 1;
221
222  /* Set if there's DEF-USE dependence between some speculatively
223     moved load insn and this one.  */
224  unsigned int fed_by_spec_load : 1;
225  unsigned int is_load_insn : 1;
226
227  /* Nonzero if priority has been computed already.  */
228  unsigned int priority_known : 1;
229};
230
231extern struct haifa_insn_data *h_i_d;
232
233/* Accessor macros for h_i_d.  There are more in haifa-sched.c and
234   sched-rgn.c.  */
235#define INSN_DEPEND(INSN)	(h_i_d[INSN_UID (INSN)].depend)
236#define INSN_LUID(INSN)		(h_i_d[INSN_UID (INSN)].luid)
237#define CANT_MOVE(insn)		(h_i_d[INSN_UID (insn)].cant_move)
238#define INSN_DEP_COUNT(INSN)	(h_i_d[INSN_UID (INSN)].dep_count)
239#define INSN_PRIORITY(INSN)	(h_i_d[INSN_UID (INSN)].priority)
240#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
241#define INSN_COST(INSN)		(h_i_d[INSN_UID (INSN)].cost)
242#define INSN_UNIT(INSN)		(h_i_d[INSN_UID (INSN)].units)
243#define INSN_REG_WEIGHT(INSN)	(h_i_d[INSN_UID (INSN)].reg_weight)
244
245#define INSN_BLOCKAGE(INSN)	(h_i_d[INSN_UID (INSN)].blockage)
246#define UNIT_BITS		5
247#define BLOCKAGE_MASK		((1 << BLOCKAGE_BITS) - 1)
248#define ENCODE_BLOCKAGE(U, R)			\
249  (((U) << BLOCKAGE_BITS			\
250    | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS	\
251   | MAX_BLOCKAGE_COST (R))
252#define UNIT_BLOCKED(B)		((B) >> (2 * BLOCKAGE_BITS))
253#define BLOCKAGE_RANGE(B)                                                \
254  (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
255   | ((B) & BLOCKAGE_MASK))
256
257/* Encodings of the `<name>_unit_blockage_range' function.  */
258#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
259#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
260
261extern FILE *sched_dump;
262extern int sched_verbose;
263
264#ifndef __GNUC__
265#define __inline
266#endif
267
268#ifndef HAIFA_INLINE
269#define HAIFA_INLINE __inline
270#endif
271
272/* Functions in sched-vis.c.  */
273extern void init_target_units PARAMS ((void));
274extern void insn_print_units PARAMS ((rtx));
275extern void init_block_visualization PARAMS ((void));
276extern void print_block_visualization PARAMS ((const char *));
277extern void visualize_scheduled_insns PARAMS ((int));
278extern void visualize_no_unit PARAMS ((rtx));
279extern void visualize_stall_cycles PARAMS ((int));
280extern void visualize_alloc PARAMS ((void));
281extern void visualize_free PARAMS ((void));
282
283/* Functions in sched-deps.c.  */
284extern void add_dependence PARAMS ((rtx, rtx, enum reg_note));
285extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
286					     rtx));
287extern void sched_analyze PARAMS ((struct deps *, rtx, rtx));
288extern void init_deps PARAMS ((struct deps *));
289extern void free_deps PARAMS ((struct deps *));
290extern void init_deps_global PARAMS ((void));
291extern void finish_deps_global PARAMS ((void));
292extern void compute_forward_dependences PARAMS ((rtx, rtx));
293extern rtx find_insn_list PARAMS ((rtx, rtx));
294extern void init_dependency_caches PARAMS ((int));
295extern void free_dependency_caches PARAMS ((void));
296
297/* Functions in haifa-sched.c.  */
298extern void get_block_head_tail PARAMS ((int, rtx *, rtx *));
299extern int no_real_insns_p PARAMS ((rtx, rtx));
300
301extern void rm_line_notes PARAMS ((rtx, rtx));
302extern void save_line_notes PARAMS ((int, rtx, rtx));
303extern void restore_line_notes PARAMS ((rtx, rtx));
304extern void rm_redundant_line_notes PARAMS ((void));
305extern void rm_other_notes PARAMS ((rtx, rtx));
306
307extern int insn_issue_delay PARAMS ((rtx));
308extern int set_priorities PARAMS ((rtx, rtx));
309
310extern rtx sched_emit_insn PARAMS ((rtx));
311extern void schedule_block PARAMS ((int, int));
312extern void sched_init PARAMS ((FILE *));
313extern void sched_finish PARAMS ((void));
314
315extern void ready_add PARAMS ((struct ready_list *, rtx));
316
317/* The following are exported for the benefit of debugging functions.  It
318   would be nicer to keep them private to haifa-sched.c.  */
319extern int insn_unit PARAMS ((rtx));
320extern int insn_cost PARAMS ((rtx, rtx, rtx));
321extern rtx get_unit_last_insn PARAMS ((int));
322extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
323extern void print_insn PARAMS ((char *, rtx, int));
324