OSDN Git Service

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