OSDN Git Service

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