OSDN Git Service

PR middle-end/28071
[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, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, 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 /* Type to represent status of a dependence.  */
40 typedef int ds_t;
41
42 /* Type to represent weakness of speculative dependence.  */
43 typedef int dw_t;
44
45 extern enum reg_note ds_to_dk (ds_t);
46 extern ds_t dk_to_ds (enum reg_note);
47
48 /* Information about the dependency.  */
49 struct _dep
50 {
51   /* Producer.  */
52   rtx pro;
53
54   /* Consumer.  */
55   rtx con;
56
57   /* Dependency kind (aka dependency major type).  This field is superseded
58      by STATUS below.  Though, it is still in place because all the backends
59      use it.  */
60   enum reg_note kind;
61
62   /* Dependency status.  This field holds all dependency types and additional
63      information for speculative dependencies.  */
64   ds_t status;
65 };
66 typedef struct _dep *dep_t;
67
68 #define DEP_PRO(D) ((D)->pro)
69 #define DEP_CON(D) ((D)->con)
70 #define DEP_KIND(D) ((D)->kind)
71 #define DEP_STATUS(D) ((D)->status)
72
73 /* Functions to work with dep.  */
74
75 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
76
77 /* Definition of this struct resides below.  */
78 struct _dep_node;
79
80 /* A link in the dependency list.  This is essentially an equivalent of a
81    single {INSN, DEPS}_LIST rtx.  */
82 struct _dep_link
83 {
84   /* Dep node with all the data.  */
85   struct _dep_node *node;
86
87   /* Next link in the list. For the last one it is NULL.  */
88   struct _dep_link *next;
89
90   /* Pointer to the next field of the previous link in the list.
91      For the first link this points to the deps_list->first.
92
93      With help of this field it is easy to remove and insert links to the
94      list.  */
95   struct _dep_link **prev_nextp;
96 };
97 typedef struct _dep_link *dep_link_t;
98
99 #define DEP_LINK_NODE(N) ((N)->node)
100 #define DEP_LINK_NEXT(N) ((N)->next)
101 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
102
103 /* Macros to work dep_link.  For most usecases only part of the dependency
104    information is need.  These macros conveniently provide that piece of
105    information.  */
106
107 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
108 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
109 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
110 #define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N)))
111 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
112
113 void debug_dep_links (dep_link_t);
114
115 /* A list of dep_links.  Lists of this type are now used instead of rtx
116    LOG_LINKS and alike lists.  */
117 struct _deps_list
118 {
119   dep_link_t first;
120 };
121 typedef struct _deps_list *deps_list_t;
122
123 #define DEPS_LIST_FIRST(L) ((L)->first)
124
125 /* Macro to walk through deps_list.  */
126 #define FOR_EACH_DEP_LINK(LINK, LIST) \
127   for ((LINK) = DEPS_LIST_FIRST (LIST); \
128        (LINK) != NULL; \
129        (LINK) = DEP_LINK_NEXT (LINK))
130
131 /* Functions to work with deps_list.  */
132
133 deps_list_t create_deps_list (bool);
134 void free_deps_list (deps_list_t);
135 void delete_deps_list (deps_list_t);
136 bool deps_list_empty_p (deps_list_t);
137 void debug_deps_list (deps_list_t);
138 void add_back_dep_to_deps_list (deps_list_t, dep_t);
139 dep_link_t find_link_by_pro_in_deps_list (deps_list_t, rtx);
140 dep_link_t find_link_by_con_in_deps_list (deps_list_t, rtx);
141 void copy_deps_list_change_con (deps_list_t, deps_list_t, rtx);
142
143 void move_dep_link (dep_link_t, deps_list_t);
144
145 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
146    additional dependents con0 and con2, and con1 is dependent on additional
147    insns pro0 and pro1:
148
149    .con0      pro0
150    . ^         |
151    . |         |
152    . |         |
153    . X         A
154    . |         |
155    . |         |
156    . |         V
157    .pro1--Y-->con1
158    . |         ^
159    . |         |
160    . |         |
161    . Z         B
162    . |         |
163    . |         |
164    . V         |
165    .con2      pro2
166
167    This is represented using a "dep_node" for each dependence arc, which are
168    connected as follows (diagram is centered around Y which is fully shown;
169    other dep_nodes shown partially):
170
171    .          +------------+    +--------------+    +------------+
172    .          : dep_node X :    |  dep_node Y  |    : dep_node Z :
173    .          :            :    |              |    :            :
174    .          :            :    |              |    :            :
175    .          : forw       :    |  forw        |    : forw       :
176    .          : +--------+ :    |  +--------+  |    : +--------+ :
177    forw_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
178    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
179    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
180    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
181    . ^  ^     : |     ^  | :    |  |     ^  |  |    : |        | :
182    . |  |     : |     |  | :    |  |     |  |  |    : |        | :
183    . |  +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
184    . |        : |  |     | :    |  |  |     |  |    : |  |     | :
185    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
186    . |        : | |prev| | :    |  | |prev| |  |    : | |prev| | :
187    . |        : | |next| | :    |  | |next| |  |    : | |next| | :
188    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
189    . |        : |        | :<-+ |  |        |  |<-+ : |        | :<-+
190    . |        : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
191    . |        : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
192    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
193    . |        : |        | :    |  |        |  |    : |        | :
194    . |        : +--------+ :    |  +--------+  |    : +--------+ :
195    . |        :            :    |              |    :            :
196    . |        :  SAME pro1 :    |  +--------+  |    :  SAME pro1 :
197    . |        :  DIFF con0 :    |  |dep     |  |    :  DIFF con2 :
198    . |        :            :    |  |        |  |    :            :
199    . |                          |  | +----+ |  |
200    .RTX<------------------------+--+-|pro1| |  |
201    .pro1                        |  | +----+ |  |
202    .                            |  |        |  |
203    .                            |  | +----+ |  |
204    .RTX<------------------------+--+-|con1| |  |
205    .con1                        |  | +----+ |  |
206    . |                          |  |        |  |
207    . |                          |  | +----+ |  |
208    . |                          |  | |kind| |  |
209    . |                          |  | +----+ |  |
210    . |        :            :    |  | |stat| |  |    :            :
211    . |        :  DIFF pro0 :    |  | +----+ |  |    :  DIFF pro2 :
212    . |        :  SAME con1 :    |  |        |  |    :  SAME con1 :
213    . |        :            :    |  +--------+  |    :            :
214    . |        :            :    |              |    :            :
215    . |        : back       :    |  back        |    : back       :
216    . v        : +--------+ :    |  +--------+  |    : +--------+ :
217    back_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
218    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
219    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
220    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
221    .    ^     : |     ^  | :    |  |     ^  |  |    : |        | :
222    .    |     : |     |  | :    |  |     |  |  |    : |        | :
223    .    +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
224    .          : |  |     | :    |  |  |     |  |    : |  |     | :
225    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
226    .          : | |prev| | :    |  | |prev| |  |    : | |prev| | :
227    .          : | |next| | :    |  | |next| |  |    : | |next| | :
228    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
229    .          : |        | :<-+ |  |        |  |<-+ : |        | :<-+
230    .          : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
231    .          : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
232    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
233    .          : |        | :    |  |        |  |    : |        | :
234    .          : +--------+ :    |  +--------+  |    : +--------+ :
235    .          :            :    |              |    :            :
236    .          : dep_node A :    |  dep_node Y  |    : dep_node B :
237    .          +------------+    +--------------+    +------------+
238 */
239
240 struct _dep_node
241 {
242   /* Backward link.  */
243   struct _dep_link back;
244
245   /* The dep.  */
246   struct _dep dep;
247
248   /* Forward link.  */
249   struct _dep_link forw;
250 };
251 typedef struct _dep_node *dep_node_t;
252
253 #define DEP_NODE_BACK(N) (&(N)->back)
254 #define DEP_NODE_DEP(N) (&(N)->dep)
255 #define DEP_NODE_FORW(N) (&(N)->forw)
256
257 /* Describe state of dependencies used during sched_analyze phase.  */
258 struct deps
259 {
260   /* The *_insns and *_mems are paired lists.  Each pending memory operation
261      will have a pointer to the MEM rtx on one list and a pointer to the
262      containing insn on the other list in the same place in the list.  */
263
264   /* We can't use add_dependence like the old code did, because a single insn
265      may have multiple memory accesses, and hence needs to be on the list
266      once for each memory access.  Add_dependence won't let you add an insn
267      to a list more than once.  */
268
269   /* An INSN_LIST containing all insns with pending read operations.  */
270   rtx pending_read_insns;
271
272   /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
273   rtx pending_read_mems;
274
275   /* An INSN_LIST containing all insns with pending write operations.  */
276   rtx pending_write_insns;
277
278   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
279   rtx pending_write_mems;
280
281   /* We must prevent the above lists from ever growing too large since
282      the number of dependencies produced is at least O(N*N),
283      and execution time is at least O(4*N*N), as a function of the
284      length of these pending lists.  */
285
286   /* Indicates the length of the pending_read list.  */
287   int pending_read_list_length;
288
289   /* Indicates the length of the pending_write list.  */
290   int pending_write_list_length;
291
292   /* Length of the pending memory flush list. Large functions with no
293      calls may build up extremely large lists.  */
294   int pending_flush_length;
295
296   /* The last insn upon which all memory references must depend.
297      This is an insn which flushed the pending lists, creating a dependency
298      between it and all previously pending memory references.  This creates
299      a barrier (or a checkpoint) which no memory reference is allowed to cross.
300
301      This includes all non constant CALL_INSNs.  When we do interprocedural
302      alias analysis, this restriction can be relaxed.
303      This may also be an INSN that writes memory if the pending lists grow
304      too large.  */
305   rtx last_pending_memory_flush;
306
307   /* A list of the last function calls we have seen.  We use a list to
308      represent last function calls from multiple predecessor blocks.
309      Used to prevent register lifetimes from expanding unnecessarily.  */
310   rtx last_function_call;
311
312   /* A list of insns which use a pseudo register that does not already
313      cross a call.  We create dependencies between each of those insn
314      and the next call insn, to ensure that they won't cross a call after
315      scheduling is done.  */
316   rtx sched_before_next_call;
317
318   /* Used to keep post-call pseudo/hard reg movements together with
319      the call.  */
320   enum { not_post_call, post_call, post_call_initial } in_post_call_group_p;
321
322   /* Set to the tail insn of the outermost libcall block.
323
324      When nonzero, we will mark each insn processed by sched_analyze_insn
325      with SCHED_GROUP_P to ensure libcalls are scheduled as a unit.  */
326   rtx libcall_block_tail_insn;
327
328   /* The maximum register number for the following arrays.  Before reload
329      this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
330   int max_reg;
331
332   /* Element N is the next insn that sets (hard or pseudo) register
333      N within the current basic block; or zero, if there is no
334      such insn.  Needed for new registers which may be introduced
335      by splitting insns.  */
336   struct deps_reg
337     {
338       rtx uses;
339       rtx sets;
340       rtx clobbers;
341       int uses_length;
342       int clobbers_length;
343     } *reg_last;
344
345   /* Element N is set for each register that has any nonzero element
346      in reg_last[N].{uses,sets,clobbers}.  */
347   regset_head reg_last_in_use;
348
349   /* Element N is set for each register that is conditionally set.  */
350   regset_head reg_conditional_sets;
351 };
352
353 /* This structure holds some state of the current scheduling pass, and
354    contains some function pointers that abstract out some of the non-generic
355    functionality from functions such as schedule_block or schedule_insn.
356    There is one global variable, current_sched_info, which points to the
357    sched_info structure currently in use.  */
358 struct sched_info
359 {
360   /* Add all insns that are initially ready to the ready list.  Called once
361      before scheduling a set of insns.  */
362   void (*init_ready_list) (void);
363   /* Called after taking an insn from the ready list.  Returns nonzero if
364      this insn can be scheduled, nonzero if we should silently discard it.  */
365   int (*can_schedule_ready_p) (rtx);
366   /* Return nonzero if there are more insns that should be scheduled.  */
367   int (*schedule_more_p) (void);
368   /* Called after an insn has all its hard dependencies resolved. 
369      Adjusts status of instruction (which is passed through second parameter)
370      to indicate if instruction should be moved to the ready list or the
371      queue, or if it should silently discard it (until next resolved
372      dependence).  */
373   ds_t (*new_ready) (rtx, ds_t);
374   /* Compare priority of two insns.  Return a positive number if the second
375      insn is to be preferred for scheduling, and a negative one if the first
376      is to be preferred.  Zero if they are equally good.  */
377   int (*rank) (rtx, rtx);
378   /* Return a string that contains the insn uid and optionally anything else
379      necessary to identify this insn in an output.  It's valid to use a
380      static buffer for this.  The ALIGNED parameter should cause the string
381      to be formatted so that multiple output lines will line up nicely.  */
382   const char *(*print_insn) (rtx, int);
383   /* Return nonzero if an insn should be included in priority
384      calculations.  */
385   int (*contributes_to_priority) (rtx, rtx);
386   /* Called when computing dependencies for a JUMP_INSN.  This function
387      should store the set of registers that must be considered as set by
388      the jump in the regset.  */
389   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
390
391   /* The boundaries of the set of insns to be scheduled.  */
392   rtx prev_head, next_tail;
393
394   /* Filled in after the schedule is finished; the first and last scheduled
395      insns.  */
396   rtx head, tail;
397
398   /* If nonzero, enables an additional sanity check in schedule_block.  */
399   unsigned int queue_must_finish_empty:1;
400   /* Nonzero if we should use cselib for better alias analysis.  This
401      must be 0 if the dependency information is used after sched_analyze
402      has completed, e.g. if we're using it to initialize state for successor
403      blocks in region scheduling.  */
404   unsigned int use_cselib:1;
405
406   /* Maximum priority that has been assigned to an insn.  */
407   int sched_max_insns_priority;
408
409   /* Hooks to support speculative scheduling.  */
410
411   /* Called to notify frontend that instruction is being added (second
412      parameter == 0) or removed (second parameter == 1).  */     
413   void (*add_remove_insn) (rtx, int);
414
415   /* Called to notify frontend that instruction is being scheduled.
416      The first parameter - instruction to scheduled, the second parameter -
417      last scheduled instruction.  */
418   void (*begin_schedule_ready) (rtx, rtx);
419
420   /* Called to notify frontend, that new basic block is being added.
421      The first parameter - new basic block.
422      The second parameter - block, after which new basic block is being added,
423      or EXIT_BLOCK_PTR, if recovery block is being added,
424      or NULL, if standalone block is being added.  */
425   void (*add_block) (basic_block, basic_block);
426
427   /* If the second parameter is not NULL, return nonnull value, if the
428      basic block should be advanced.
429      If the second parameter is NULL, return the next basic block in EBB.
430      The first parameter is the current basic block in EBB.  */
431   basic_block (*advance_target_bb) (basic_block, rtx);
432
433   /* Called after blocks were rearranged due to movement of jump instruction.
434      The first parameter - index of basic block, in which jump currently is.
435      The second parameter - index of basic block, in which jump used
436      to be.
437      The third parameter - index of basic block, that follows the second
438      parameter.  */
439   void (*fix_recovery_cfg) (int, int, int);
440
441 #ifdef ENABLE_CHECKING
442   /* If the second parameter is zero, return nonzero, if block is head of the
443      region.
444      If the second parameter is nonzero, return nonzero, if block is leaf of
445      the region.
446      global_live_at_start should not change in region heads and
447      global_live_at_end should not change in region leafs due to scheduling.  */
448   int (*region_head_or_leaf_p) (basic_block, int);
449 #endif
450
451   /* ??? FIXME: should use straight bitfields inside sched_info instead of
452      this flag field.  */
453   unsigned int flags;
454 };
455
456 /* This structure holds description of the properties for speculative
457    scheduling.  */
458 struct spec_info_def
459 {
460   /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
461      BE_IN_{DATA_CONTROL}.  */
462   int mask;
463
464   /* A dump file for additional information on speculative scheduling.  */
465   FILE *dump;
466
467   /* Minimal cumulative weakness of speculative instruction's
468      dependencies, so that insn will be scheduled.  */
469   dw_t weakness_cutoff;
470
471   /* Flags from the enum SPEC_SCHED_FLAGS.  */
472   int flags;
473 };
474 typedef struct spec_info_def *spec_info_t;
475
476 extern struct sched_info *current_sched_info;
477
478 /* Indexed by INSN_UID, the collection of all data associated with
479    a single instruction.  */
480
481 struct haifa_insn_data
482 {
483   /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
484      h_i_d because when h_i_d extends, addresses of the deps_list->first
485      change without updating deps_list->first->next->prev_nextp.  Thus
486      BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
487      list is allocated on the obstack.  */
488
489   /* A list of backward dependencies.  The insn is a consumer of all the
490      deps mentioned here.  */
491   deps_list_t back_deps;
492
493   /* A list of insns which depend on the instruction.  Unlike 'back_deps',
494      it represents forward dependencies.  */
495   deps_list_t forw_deps;
496
497   /* A list of scheduled producers of the instruction.  Links are being moved
498      from 'back_deps' to 'resolved_back_deps' while scheduling.  */
499   deps_list_t resolved_back_deps;
500  
501   /* Logical uid gives the original ordering of the insns.  */
502   int luid;
503
504   /* A priority for each insn.  */
505   int priority;
506
507   /* The number of incoming edges in the forward dependency graph.
508      As scheduling proceeds, counts are decreased.  An insn moves to
509      the ready queue when its counter reaches zero.  */
510   int dep_count;
511
512   /* Number of instructions referring to this insn.  */
513   int ref_count;
514
515   /* The minimum clock tick at which the insn becomes ready.  This is
516      used to note timing constraints for the insns in the pending list.  */
517   int tick;
518
519   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
520      subsequent blocks in a region.  */
521   int inter_tick;
522   
523   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
524   int queue_index;
525
526   short cost;
527
528   /* This weight is an estimation of the insn's contribution to
529      register pressure.  */
530   short reg_weight;
531
532   /* Some insns (e.g. call) are not allowed to move across blocks.  */
533   unsigned int cant_move : 1;
534
535   /* Set if there's DEF-USE dependence between some speculatively
536      moved load insn and this one.  */
537   unsigned int fed_by_spec_load : 1;
538   unsigned int is_load_insn : 1;
539
540   /* Nonzero if priority has been computed already.  */
541   unsigned int priority_known : 1;
542
543   /* Nonzero if instruction has internal dependence
544      (e.g. add_dependence was invoked with (insn == elem)).  */
545   unsigned int has_internal_dep : 1;
546   
547   /* What speculations are necessary to apply to schedule the instruction.  */
548   ds_t todo_spec;
549   /* What speculations were already applied.  */
550   ds_t done_spec; 
551   /* What speculations are checked by this instruction.  */
552   ds_t check_spec;
553
554   /* Recovery block for speculation checks.  */
555   basic_block recovery_block;
556
557   /* Original pattern of the instruction.  */
558   rtx orig_pat;
559 };
560
561 extern struct haifa_insn_data *h_i_d;
562 /* Used only if (current_sched_info->flags & USE_GLAT) != 0.
563    These regsets store global_live_at_{start, end} information
564    for each basic block.  */
565 extern regset *glat_start, *glat_end;
566
567 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
568    sched-rgn.c.  */
569 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
570 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
571 #define INSN_RESOLVED_BACK_DEPS(INSN) \
572   (h_i_d[INSN_UID (INSN)].resolved_back_deps)
573 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
574 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
575 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
576 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
577 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
578 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
579 #define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
580 #define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
581 #define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
582 #define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
583 #define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
584 #define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
585
586 /* INSN is either a simple or a branchy speculation check.  */
587 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
588
589 /* INSN is a speculation check that will simply reexecute the speculatively
590    scheduled instruction if the speculation fails.  */
591 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
592   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
593
594 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
595    speculation fails.  Insns in that block will reexecute the speculatively
596    scheduled code and then will return immediately after INSN thus preserving
597    semantics of the program.  */
598 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
599   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
600
601 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
602    for speculative scheduling.  Namely, it is 4 integers in the range
603    [0, MAX_DEP_WEAK] and 3 bits.
604    The integers correspond to the probability of the dependence to *not*
605    exist, it is the probability, that overcoming of this dependence will
606    not be followed by execution of the recovery code.  Nevertheless,
607    whatever high the probability of success is, recovery code should still
608    be generated to preserve semantics of the program.  To find a way to
609    get/set these integers, please refer to the {get, set}_dep_weak ()
610    functions in sched-deps.c .
611    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
612    output- and anti- dependence.  It is not enough for speculative scheduling
613    to know just the major type of all the dependence between two instructions,
614    as only true dependence can be overcome.
615    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
616    for using to describe instruction's status.  It is set whenever instruction
617    has at least one dependence, that cannot be overcame.
618    See also: check_dep_status () in sched-deps.c .  */
619
620 /* We exclude sign bit.  */
621 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
622
623 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
624    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
625    dep weakness.  */
626 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
627
628 /* Mask of speculative weakness in dep_status.  */
629 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
630
631 /* This constant means that dependence is fake with 99.999...% probability.
632    This is the maximum value, that can appear in dep_status.
633    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
634    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
635    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
636 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
637
638 /* This constant means that dependence is 99.999...% real and it is a really
639    bad idea to overcome it (though this can be done, preserving program
640    semantics).  */
641 #define MIN_DEP_WEAK 1
642
643 /* This constant represents 100% probability.
644    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
645 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
646
647 /* Default weakness of speculative dependence.  Used when we can't say
648    neither bad nor good about the dependence.  */
649 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
650
651 /* Offset for speculative weaknesses in dep_status.  */
652 enum SPEC_TYPES_OFFSETS {
653   BEGIN_DATA_BITS_OFFSET = 0,
654   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
655   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
656   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
657 };
658
659 /* The following defines provide numerous constants used to distinguish between
660    different types of speculative dependencies.  */
661
662 /* Dependence can be overcome with generation of new data speculative
663    instruction.  */
664 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
665
666 /* This dependence is to the instruction in the recovery block, that was
667    formed to recover after data-speculation failure.
668    Thus, this dependence can overcome with generating of the copy of
669    this instruction in the recovery block.  */
670 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
671
672 /* Dependence can be overcome with generation of new control speculative
673    instruction.  */
674 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
675
676 /* This dependence is to the instruction in the recovery block, that was
677    formed to recover after control-speculation failure.
678    Thus, this dependence can be overcome with generating of the copy of
679    this instruction in the recovery block.  */
680 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
681
682 /* A few convenient combinations.  */
683 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
684 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
685 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
686 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
687 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
688
689 /* Constants, that are helpful in iterating through dep_status.  */
690 #define FIRST_SPEC_TYPE BEGIN_DATA
691 #define LAST_SPEC_TYPE BE_IN_CONTROL
692 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
693
694 /* Dependence on instruction can be of multiple types
695    (e.g. true and output). This fields enhance REG_NOTE_KIND information
696    of the dependence.  */
697 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
698 #define DEP_OUTPUT (DEP_TRUE << 1)
699 #define DEP_ANTI (DEP_OUTPUT << 1)
700
701 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
702
703 /* Instruction has non-speculative dependence.  This bit represents the
704    property of an instruction - not the one of a dependence.
705    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
706 #define HARD_DEP (DEP_ANTI << 1)
707
708 /* This represents the results of calling sched-deps.c functions, 
709    which modify dependencies.  Possible choices are: a dependence
710    is already present and nothing has been changed; a dependence type
711    has been changed; brand new dependence has been created.  */
712 enum DEPS_ADJUST_RESULT {
713   DEP_PRESENT = 1,
714   DEP_CHANGED = 2,
715   DEP_CREATED = 3
716 };
717
718 /* Represents the bits that can be set in the flags field of the 
719    sched_info structure.  */
720 enum SCHED_FLAGS {
721   /* If set, generate links between instruction as DEPS_LIST.
722      Otherwise, generate usual INSN_LIST links.  */
723   USE_DEPS_LIST = 1,
724   /* Perform data or control (or both) speculation.
725      Results in generation of data and control speculative dependencies.
726      Requires USE_DEPS_LIST set.  */
727   DO_SPECULATION = USE_DEPS_LIST << 1,
728   SCHED_RGN = DO_SPECULATION << 1,
729   SCHED_EBB = SCHED_RGN << 1,
730   /* Detach register live information from basic block headers.
731      This is necessary to invoke functions, that change CFG (e.g. split_edge).
732      Requires USE_GLAT.  */
733   DETACH_LIFE_INFO = SCHED_EBB << 1,
734   /* Save register live information from basic block headers to
735      glat_{start, end} arrays.  */
736   USE_GLAT = DETACH_LIFE_INFO << 1
737 };
738
739 enum SPEC_SCHED_FLAGS {
740   COUNT_SPEC_IN_CRITICAL_PATH = 1,
741   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
742   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
743 };
744
745 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE)  \
746                                                != NOTE_INSN_BASIC_BLOCK))
747
748 extern FILE *sched_dump;
749 extern int sched_verbose;
750
751 /* Exception Free Loads:
752
753    We define five classes of speculative loads: IFREE, IRISKY,
754    PFREE, PRISKY, and MFREE.
755
756    IFREE loads are loads that are proved to be exception-free, just
757    by examining the load insn.  Examples for such loads are loads
758    from TOC and loads of global data.
759
760    IRISKY loads are loads that are proved to be exception-risky,
761    just by examining the load insn.  Examples for such loads are
762    volatile loads and loads from shared memory.
763
764    PFREE loads are loads for which we can prove, by examining other
765    insns, that they are exception-free.  Currently, this class consists
766    of loads for which we are able to find a "similar load", either in
767    the target block, or, if only one split-block exists, in that split
768    block.  Load2 is similar to load1 if both have same single base
769    register.  We identify only part of the similar loads, by finding
770    an insn upon which both load1 and load2 have a DEF-USE dependence.
771
772    PRISKY loads are loads for which we can prove, by examining other
773    insns, that they are exception-risky.  Currently we have two proofs for
774    such loads.  The first proof detects loads that are probably guarded by a
775    test on the memory address.  This proof is based on the
776    backward and forward data dependence information for the region.
777    Let load-insn be the examined load.
778    Load-insn is PRISKY iff ALL the following hold:
779
780    - insn1 is not in the same block as load-insn
781    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
782    - test-insn is either a compare or a branch, not in the same block
783      as load-insn
784    - load-insn is reachable from test-insn
785    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
786
787    This proof might fail when the compare and the load are fed
788    by an insn not in the region.  To solve this, we will add to this
789    group all loads that have no input DEF-USE dependence.
790
791    The second proof detects loads that are directly or indirectly
792    fed by a speculative load.  This proof is affected by the
793    scheduling process.  We will use the flag  fed_by_spec_load.
794    Initially, all insns have this flag reset.  After a speculative
795    motion of an insn, if insn is either a load, or marked as
796    fed_by_spec_load, we will also mark as fed_by_spec_load every
797    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
798    load which is fed_by_spec_load is also PRISKY.
799
800    MFREE (maybe-free) loads are all the remaining loads. They may be
801    exception-free, but we cannot prove it.
802
803    Now, all loads in IFREE and PFREE classes are considered
804    exception-free, while all loads in IRISKY and PRISKY classes are
805    considered exception-risky.  As for loads in the MFREE class,
806    these are considered either exception-free or exception-risky,
807    depending on whether we are pessimistic or optimistic.  We have
808    to take the pessimistic approach to assure the safety of
809    speculative scheduling, but we can take the optimistic approach
810    by invoking the -fsched_spec_load_dangerous option.  */
811
812 enum INSN_TRAP_CLASS
813 {
814   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
815   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
816 };
817
818 #define WORST_CLASS(class1, class2) \
819 ((class1 > class2) ? class1 : class2)
820
821 #ifndef __GNUC__
822 #define __inline
823 #endif
824
825 #ifndef HAIFA_INLINE
826 #define HAIFA_INLINE __inline
827 #endif
828
829 /* Functions in sched-vis.c.  */
830 extern void print_insn (char *, rtx, int);
831
832 /* Functions in sched-deps.c.  */
833 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
834 extern void add_dependence (rtx, rtx, enum reg_note);
835 extern void sched_analyze (struct deps *, rtx, rtx);
836 extern void init_deps (struct deps *);
837 extern void free_deps (struct deps *);
838 extern void init_deps_global (void);
839 extern void finish_deps_global (void);
840 extern void add_forw_dep (dep_link_t);
841 extern void compute_forward_dependences (rtx, rtx);
842 extern void init_dependency_caches (int);
843 extern void free_dependency_caches (void);
844 extern void extend_dependency_caches (int, bool);
845 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx, 
846                                                        enum reg_note, ds_t);
847 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
848 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
849 extern void delete_back_forw_dep (dep_link_t);
850 extern dw_t get_dep_weak (ds_t, ds_t);
851 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
852 extern ds_t ds_merge (ds_t, ds_t);
853
854 /* Functions in haifa-sched.c.  */
855 extern int haifa_classify_insn (rtx);
856 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
857 extern int no_real_insns_p (rtx, rtx);
858
859 extern void rm_other_notes (rtx, rtx);
860
861 extern int insn_cost (rtx);
862 extern int dep_cost (dep_t);
863 extern int set_priorities (rtx, rtx);
864
865 extern void schedule_block (basic_block *, int);
866 extern void sched_init (void);
867 extern void sched_finish (void);
868
869 extern int try_ready (rtx);
870 extern void * xrecalloc (void *, size_t, size_t, size_t);
871 extern void unlink_bb_notes (basic_block, basic_block);
872 extern void add_block (basic_block, basic_block);
873 extern void attach_life_info (void);
874 extern rtx bb_note (basic_block);
875
876 #ifdef ENABLE_CHECKING
877 extern void check_reg_live (bool);
878 #endif
879
880 #endif /* GCC_SCHED_INT_H */