OSDN Git Service

* sched-int.h (struct _haifa_deps_insn_data): New members cond
[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, 2008, 2009, 2010
5    Free Software Foundation, Inc.
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23 #ifndef GCC_SCHED_INT_H
24 #define GCC_SCHED_INT_H
25
26 #ifdef INSN_SCHEDULING
27
28 /* For state_t.  */
29 #include "insn-attr.h"
30 #include "df.h"
31 #include "basic-block.h"
32
33 /* For VEC (int, heap).  */
34 #include "vecprim.h"
35
36 /* Identificator of a scheduler pass.  */
37 enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,
38                        SCHED_SMS_PASS, SCHED_SEL_PASS };
39
40 typedef VEC (basic_block, heap) *bb_vec_t;
41 typedef VEC (rtx, heap) *insn_vec_t;
42 typedef VEC (rtx, heap) *rtx_vec_t;
43
44 extern void sched_init_bbs (void);
45
46 extern void sched_extend_luids (void);
47 extern void sched_init_insn_luid (rtx);
48 extern void sched_init_luids (bb_vec_t);
49 extern void sched_finish_luids (void);
50
51 extern void sched_extend_target (void);
52
53 extern void haifa_init_h_i_d (bb_vec_t);
54 extern void haifa_finish_h_i_d (void);
55
56 /* Hooks that are common to all the schedulers.  */
57 struct common_sched_info_def
58 {
59   /* Called after blocks were rearranged due to movement of jump instruction.
60      The first parameter - index of basic block, in which jump currently is.
61      The second parameter - index of basic block, in which jump used
62      to be.
63      The third parameter - index of basic block, that follows the second
64      parameter.  */
65   void (*fix_recovery_cfg) (int, int, int);
66
67   /* Called to notify frontend, that new basic block is being added.
68      The first parameter - new basic block.
69      The second parameter - block, after which new basic block is being added,
70      or EXIT_BLOCK_PTR, if recovery block is being added,
71      or NULL, if standalone block is being added.  */
72   void (*add_block) (basic_block, basic_block);
73
74   /* Estimate number of insns in the basic block.  */
75   int (*estimate_number_of_insns) (basic_block);
76
77   /* Given a non-insn (!INSN_P (x)) return
78      -1 - if this rtx don't need a luid.
79      0 - if it should have the same luid as the previous insn.
80      1 - if it needs a separate luid.  */
81   int (*luid_for_non_insn) (rtx);
82
83   /* Scheduler pass identifier.  It is preferably used in assertions.  */
84   enum sched_pass_id_t sched_pass_id;
85 };
86
87 extern struct common_sched_info_def *common_sched_info;
88
89 extern const struct common_sched_info_def haifa_common_sched_info;
90
91 /* Return true if selective scheduling pass is working.  */
92 static inline bool
93 sel_sched_p (void)
94 {
95   return common_sched_info->sched_pass_id == SCHED_SEL_PASS;
96 }
97
98 /* Returns maximum priority that an insn was assigned to.  */
99 extern int get_rgn_sched_max_insns_priority (void);
100
101 /* Increases effective priority for INSN by AMOUNT.  */
102 extern void sel_add_to_insn_priority (rtx, int);
103
104 /* True if during selective scheduling we need to emulate some of haifa
105    scheduler behaviour.  */
106 extern int sched_emulate_haifa_p;
107
108 /* Mapping from INSN_UID to INSN_LUID.  In the end all other per insn data
109    structures should be indexed by luid.  */
110 extern VEC (int, heap) *sched_luids;
111 #define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
112 #define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
113
114 #define SET_INSN_LUID(INSN, LUID) \
115 (VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
116
117 /* The highest INSN_LUID.  */
118 extern int sched_max_luid;
119
120 extern int insn_luid (rtx);
121
122 /* This list holds ripped off notes from the current block.  These notes will
123    be attached to the beginning of the block when its scheduling is
124    finished.  */
125 extern rtx note_list;
126
127 extern void remove_notes (rtx, rtx);
128 extern rtx restore_other_notes (rtx, basic_block);
129 extern void sched_insns_init (rtx);
130 extern void sched_insns_finish (void);
131
132 extern void *xrecalloc (void *, size_t, size_t, size_t);
133 extern rtx bb_note (basic_block);
134
135 extern void reemit_notes (rtx);
136
137 /* Functions in haifa-sched.c.  */
138 extern int haifa_classify_insn (const_rtx);
139
140 /* Functions in sel-sched-ir.c.  */
141 extern void sel_find_rgns (void);
142 extern void sel_mark_hard_insn (rtx);
143
144 extern size_t dfa_state_size;
145
146 extern void advance_state (state_t);
147
148 extern void setup_sched_dump (void);
149 extern void sched_init (void);
150 extern void sched_finish (void);
151
152 extern bool sel_insn_is_speculation_check (rtx);
153
154 /* Describe the ready list of the scheduler.
155    VEC holds space enough for all insns in the current region.  VECLEN
156    says how many exactly.
157    FIRST is the index of the element with the highest priority; i.e. the
158    last one in the ready list, since elements are ordered by ascending
159    priority.
160    N_READY determines how many insns are on the ready list.
161    N_DEBUG determines how many debug insns are on the ready list.  */
162 struct ready_list
163 {
164   rtx *vec;
165   int veclen;
166   int first;
167   int n_ready;
168   int n_debug;
169 };
170
171 extern char *ready_try;
172 extern struct ready_list ready;
173
174 extern int max_issue (struct ready_list *, int, state_t, bool, int *);
175
176 extern void ebb_compute_jump_reg_dependencies (rtx, regset, regset, regset);
177
178 extern edge find_fallthru_edge_from (basic_block);
179
180 extern void (* sched_init_only_bb) (basic_block, basic_block);
181 extern basic_block (* sched_split_block) (basic_block, rtx);
182 extern basic_block sched_split_block_1 (basic_block, rtx);
183 extern basic_block (* sched_create_empty_bb) (basic_block);
184 extern basic_block sched_create_empty_bb_1 (basic_block);
185
186 extern basic_block sched_create_recovery_block (basic_block *);
187 extern void sched_create_recovery_edges (basic_block, basic_block,
188                                          basic_block);
189
190 /* Pointer to data describing the current DFA state.  */
191 extern state_t curr_state;
192
193 /* Type to represent status of a dependence.  */
194 typedef int ds_t;
195
196 /* Type to represent weakness of speculative dependence.  */
197 typedef int dw_t;
198
199 extern enum reg_note ds_to_dk (ds_t);
200 extern ds_t dk_to_ds (enum reg_note);
201
202 /* Information about the dependency.  */
203 struct _dep
204 {
205   /* Producer.  */
206   rtx pro;
207
208   /* Consumer.  */
209   rtx con;
210
211   /* Dependency major type.  This field is superseded by STATUS below.
212      Though, it is still in place because some targets use it.  */
213   enum reg_note type;
214
215   /* Dependency status.  This field holds all dependency types and additional
216      information for speculative dependencies.  */
217   ds_t status;
218 };
219
220 typedef struct _dep dep_def;
221 typedef dep_def *dep_t;
222
223 #define DEP_PRO(D) ((D)->pro)
224 #define DEP_CON(D) ((D)->con)
225 #define DEP_TYPE(D) ((D)->type)
226 #define DEP_STATUS(D) ((D)->status)
227
228 /* Functions to work with dep.  */
229
230 extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t);
231 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
232
233 extern void sd_debug_dep (dep_t);
234
235 /* Definition of this struct resides below.  */
236 struct _dep_node;
237 typedef struct _dep_node *dep_node_t;
238
239 /* A link in the dependency list.  This is essentially an equivalent of a
240    single {INSN, DEPS}_LIST rtx.  */
241 struct _dep_link
242 {
243   /* Dep node with all the data.  */
244   dep_node_t node;
245
246   /* Next link in the list. For the last one it is NULL.  */
247   struct _dep_link *next;
248
249   /* Pointer to the next field of the previous link in the list.
250      For the first link this points to the deps_list->first.
251
252      With help of this field it is easy to remove and insert links to the
253      list.  */
254   struct _dep_link **prev_nextp;
255 };
256 typedef struct _dep_link *dep_link_t;
257
258 #define DEP_LINK_NODE(N) ((N)->node)
259 #define DEP_LINK_NEXT(N) ((N)->next)
260 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
261
262 /* Macros to work dep_link.  For most usecases only part of the dependency
263    information is need.  These macros conveniently provide that piece of
264    information.  */
265
266 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
267 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
268 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
269 #define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
270 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
271
272 /* A list of dep_links.  */
273 struct _deps_list
274 {
275   /* First element.  */
276   dep_link_t first;
277
278   /* Total number of elements in the list.  */
279   int n_links;
280 };
281 typedef struct _deps_list *deps_list_t;
282
283 #define DEPS_LIST_FIRST(L) ((L)->first)
284 #define DEPS_LIST_N_LINKS(L) ((L)->n_links)
285
286 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
287    additional dependents con0 and con2, and con1 is dependent on additional
288    insns pro0 and pro1:
289
290    .con0      pro0
291    . ^         |
292    . |         |
293    . |         |
294    . X         A
295    . |         |
296    . |         |
297    . |         V
298    .pro1--Y-->con1
299    . |         ^
300    . |         |
301    . |         |
302    . Z         B
303    . |         |
304    . |         |
305    . V         |
306    .con2      pro2
307
308    This is represented using a "dep_node" for each dependence arc, which are
309    connected as follows (diagram is centered around Y which is fully shown;
310    other dep_nodes shown partially):
311
312    .          +------------+    +--------------+    +------------+
313    .          : dep_node X :    |  dep_node Y  |    : dep_node Z :
314    .          :            :    |              |    :            :
315    .          :            :    |              |    :            :
316    .          : forw       :    |  forw        |    : forw       :
317    .          : +--------+ :    |  +--------+  |    : +--------+ :
318    forw_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
319    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
320    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
321    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
322    . ^  ^     : |     ^  | :    |  |     ^  |  |    : |        | :
323    . |  |     : |     |  | :    |  |     |  |  |    : |        | :
324    . |  +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
325    . |        : |  |     | :    |  |  |     |  |    : |  |     | :
326    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
327    . |        : | |prev| | :    |  | |prev| |  |    : | |prev| | :
328    . |        : | |next| | :    |  | |next| |  |    : | |next| | :
329    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
330    . |        : |        | :<-+ |  |        |  |<-+ : |        | :<-+
331    . |        : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
332    . |        : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
333    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
334    . |        : |        | :    |  |        |  |    : |        | :
335    . |        : +--------+ :    |  +--------+  |    : +--------+ :
336    . |        :            :    |              |    :            :
337    . |        :  SAME pro1 :    |  +--------+  |    :  SAME pro1 :
338    . |        :  DIFF con0 :    |  |dep     |  |    :  DIFF con2 :
339    . |        :            :    |  |        |  |    :            :
340    . |                          |  | +----+ |  |
341    .RTX<------------------------+--+-|pro1| |  |
342    .pro1                        |  | +----+ |  |
343    .                            |  |        |  |
344    .                            |  | +----+ |  |
345    .RTX<------------------------+--+-|con1| |  |
346    .con1                        |  | +----+ |  |
347    . |                          |  |        |  |
348    . |                          |  | +----+ |  |
349    . |                          |  | |kind| |  |
350    . |                          |  | +----+ |  |
351    . |        :            :    |  | |stat| |  |    :            :
352    . |        :  DIFF pro0 :    |  | +----+ |  |    :  DIFF pro2 :
353    . |        :  SAME con1 :    |  |        |  |    :  SAME con1 :
354    . |        :            :    |  +--------+  |    :            :
355    . |        :            :    |              |    :            :
356    . |        : back       :    |  back        |    : back       :
357    . v        : +--------+ :    |  +--------+  |    : +--------+ :
358    back_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
359    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
360    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
361    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
362    .    ^     : |     ^  | :    |  |     ^  |  |    : |        | :
363    .    |     : |     |  | :    |  |     |  |  |    : |        | :
364    .    +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
365    .          : |  |     | :    |  |  |     |  |    : |  |     | :
366    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
367    .          : | |prev| | :    |  | |prev| |  |    : | |prev| | :
368    .          : | |next| | :    |  | |next| |  |    : | |next| | :
369    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
370    .          : |        | :<-+ |  |        |  |<-+ : |        | :<-+
371    .          : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
372    .          : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
373    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
374    .          : |        | :    |  |        |  |    : |        | :
375    .          : +--------+ :    |  +--------+  |    : +--------+ :
376    .          :            :    |              |    :            :
377    .          : dep_node A :    |  dep_node Y  |    : dep_node B :
378    .          +------------+    +--------------+    +------------+
379 */
380
381 struct _dep_node
382 {
383   /* Backward link.  */
384   struct _dep_link back;
385
386   /* The dep.  */
387   struct _dep dep;
388
389   /* Forward link.  */
390   struct _dep_link forw;
391 };
392
393 #define DEP_NODE_BACK(N) (&(N)->back)
394 #define DEP_NODE_DEP(N) (&(N)->dep)
395 #define DEP_NODE_FORW(N) (&(N)->forw)
396
397 /* The following enumeration values tell us what dependencies we
398    should use to implement the barrier.  We use true-dependencies for
399    TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
400 enum reg_pending_barrier_mode
401 {
402   NOT_A_BARRIER = 0,
403   MOVE_BARRIER,
404   TRUE_BARRIER
405 };
406
407 /* Whether a register movement is associated with a call.  */
408 enum post_call_group
409 {
410   not_post_call,
411   post_call,
412   post_call_initial
413 };
414
415 /* Insns which affect pseudo-registers.  */
416 struct deps_reg
417 {
418   rtx uses;
419   rtx sets;
420   rtx implicit_sets;
421   rtx clobbers;
422   int uses_length;
423   int clobbers_length;
424 };
425
426 /* Describe state of dependencies used during sched_analyze phase.  */
427 struct deps_desc
428 {
429   /* The *_insns and *_mems are paired lists.  Each pending memory operation
430      will have a pointer to the MEM rtx on one list and a pointer to the
431      containing insn on the other list in the same place in the list.  */
432
433   /* We can't use add_dependence like the old code did, because a single insn
434      may have multiple memory accesses, and hence needs to be on the list
435      once for each memory access.  Add_dependence won't let you add an insn
436      to a list more than once.  */
437
438   /* An INSN_LIST containing all insns with pending read operations.  */
439   rtx pending_read_insns;
440
441   /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
442   rtx pending_read_mems;
443
444   /* An INSN_LIST containing all insns with pending write operations.  */
445   rtx pending_write_insns;
446
447   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
448   rtx pending_write_mems;
449
450   /* We must prevent the above lists from ever growing too large since
451      the number of dependencies produced is at least O(N*N),
452      and execution time is at least O(4*N*N), as a function of the
453      length of these pending lists.  */
454
455   /* Indicates the length of the pending_read list.  */
456   int pending_read_list_length;
457
458   /* Indicates the length of the pending_write list.  */
459   int pending_write_list_length;
460
461   /* Length of the pending memory flush list. Large functions with no
462      calls may build up extremely large lists.  */
463   int pending_flush_length;
464
465   /* The last insn upon which all memory references must depend.
466      This is an insn which flushed the pending lists, creating a dependency
467      between it and all previously pending memory references.  This creates
468      a barrier (or a checkpoint) which no memory reference is allowed to cross.
469
470      This includes all non constant CALL_INSNs.  When we do interprocedural
471      alias analysis, this restriction can be relaxed.
472      This may also be an INSN that writes memory if the pending lists grow
473      too large.  */
474   rtx last_pending_memory_flush;
475
476   /* A list of the last function calls we have seen.  We use a list to
477      represent last function calls from multiple predecessor blocks.
478      Used to prevent register lifetimes from expanding unnecessarily.  */
479   rtx last_function_call;
480
481   /* A list of the last function calls that may not return normally
482      we have seen.  We use a list to represent last function calls from
483      multiple predecessor blocks.  Used to prevent moving trapping insns
484      across such calls.  */
485   rtx last_function_call_may_noreturn;
486
487   /* A list of insns which use a pseudo register that does not already
488      cross a call.  We create dependencies between each of those insn
489      and the next call insn, to ensure that they won't cross a call after
490      scheduling is done.  */
491   rtx sched_before_next_call;
492
493   /* Used to keep post-call pseudo/hard reg movements together with
494      the call.  */
495   enum post_call_group in_post_call_group_p;
496
497   /* The last debug insn we've seen.  */
498   rtx last_debug_insn;
499
500   /* The maximum register number for the following arrays.  Before reload
501      this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
502   int max_reg;
503
504   /* Element N is the next insn that sets (hard or pseudo) register
505      N within the current basic block; or zero, if there is no
506      such insn.  Needed for new registers which may be introduced
507      by splitting insns.  */
508   struct deps_reg *reg_last;
509
510   /* Element N is set for each register that has any nonzero element
511      in reg_last[N].{uses,sets,clobbers}.  */
512   regset_head reg_last_in_use;
513
514   /* Element N is set for each register that is conditionally set.  */
515   regset_head reg_conditional_sets;
516
517   /* Shows the last value of reg_pending_barrier associated with the insn.  */
518   enum reg_pending_barrier_mode last_reg_pending_barrier;
519
520   /* True when this context should be treated as a readonly by
521      the analysis.  */
522   BOOL_BITFIELD readonly : 1;
523 };
524
525 typedef struct deps_desc *deps_t;
526
527 /* This structure holds some state of the current scheduling pass, and
528    contains some function pointers that abstract out some of the non-generic
529    functionality from functions such as schedule_block or schedule_insn.
530    There is one global variable, current_sched_info, which points to the
531    sched_info structure currently in use.  */
532 struct haifa_sched_info
533 {
534   /* Add all insns that are initially ready to the ready list.  Called once
535      before scheduling a set of insns.  */
536   void (*init_ready_list) (void);
537   /* Called after taking an insn from the ready list.  Returns nonzero if
538      this insn can be scheduled, nonzero if we should silently discard it.  */
539   int (*can_schedule_ready_p) (rtx);
540   /* Return nonzero if there are more insns that should be scheduled.  */
541   int (*schedule_more_p) (void);
542   /* Called after an insn has all its hard dependencies resolved.
543      Adjusts status of instruction (which is passed through second parameter)
544      to indicate if instruction should be moved to the ready list or the
545      queue, or if it should silently discard it (until next resolved
546      dependence).  */
547   ds_t (*new_ready) (rtx, ds_t);
548   /* Compare priority of two insns.  Return a positive number if the second
549      insn is to be preferred for scheduling, and a negative one if the first
550      is to be preferred.  Zero if they are equally good.  */
551   int (*rank) (rtx, rtx);
552   /* Return a string that contains the insn uid and optionally anything else
553      necessary to identify this insn in an output.  It's valid to use a
554      static buffer for this.  The ALIGNED parameter should cause the string
555      to be formatted so that multiple output lines will line up nicely.  */
556   const char *(*print_insn) (const_rtx, int);
557   /* Return nonzero if an insn should be included in priority
558      calculations.  */
559   int (*contributes_to_priority) (rtx, rtx);
560
561   /* Return true if scheduling insn (passed as the parameter) will trigger
562      finish of scheduling current block.  */
563   bool (*insn_finishes_block_p) (rtx);
564
565   /* The boundaries of the set of insns to be scheduled.  */
566   rtx prev_head, next_tail;
567
568   /* Filled in after the schedule is finished; the first and last scheduled
569      insns.  */
570   rtx head, tail;
571
572   /* If nonzero, enables an additional sanity check in schedule_block.  */
573   unsigned int queue_must_finish_empty:1;
574
575   /* Maximum priority that has been assigned to an insn.  */
576   int sched_max_insns_priority;
577
578   /* Hooks to support speculative scheduling.  */
579
580   /* Called to notify frontend that instruction is being added (second
581      parameter == 0) or removed (second parameter == 1).  */
582   void (*add_remove_insn) (rtx, int);
583
584   /* Called to notify the frontend that instruction INSN is being
585      scheduled.  */
586   void (*begin_schedule_ready) (rtx insn);
587
588   /* Called to notify the frontend that an instruction INSN is about to be
589      moved to its correct place in the final schedule.  This is done for all
590      insns in order of the schedule.  LAST indicates the last scheduled
591      instruction.  */
592   void (*begin_move_insn) (rtx insn, rtx last);
593
594   /* If the second parameter is not NULL, return nonnull value, if the
595      basic block should be advanced.
596      If the second parameter is NULL, return the next basic block in EBB.
597      The first parameter is the current basic block in EBB.  */
598   basic_block (*advance_target_bb) (basic_block, rtx);
599
600   /* ??? FIXME: should use straight bitfields inside sched_info instead of
601      this flag field.  */
602   unsigned int flags;
603 };
604
605 /* This structure holds description of the properties for speculative
606    scheduling.  */
607 struct spec_info_def
608 {
609   /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
610      BE_IN_{DATA_CONTROL}.  */
611   int mask;
612
613   /* A dump file for additional information on speculative scheduling.  */
614   FILE *dump;
615
616   /* Minimal cumulative weakness of speculative instruction's
617      dependencies, so that insn will be scheduled.  */
618   dw_t data_weakness_cutoff;
619
620   /* Minimal usefulness of speculative instruction to be considered for
621      scheduling.  */
622   int control_weakness_cutoff;
623
624   /* Flags from the enum SPEC_SCHED_FLAGS.  */
625   int flags;
626 };
627 typedef struct spec_info_def *spec_info_t;
628
629 extern spec_info_t spec_info;
630
631 extern struct haifa_sched_info *current_sched_info;
632
633 /* Do register pressure sensitive insn scheduling if the flag is set
634    up.  */
635 extern bool sched_pressure_p;
636
637 /* Map regno -> its pressure class.  The map defined only when
638    SCHED_PRESSURE_P is true.  */
639 extern enum reg_class *sched_regno_pressure_class;
640
641 /* Indexed by INSN_UID, the collection of all data associated with
642    a single instruction.  */
643
644 struct _haifa_deps_insn_data
645 {
646   /* The number of incoming edges in the forward dependency graph.
647      As scheduling proceeds, counts are decreased.  An insn moves to
648      the ready queue when its counter reaches zero.  */
649   int dep_count;
650
651   /* Nonzero if instruction has internal dependence
652      (e.g. add_dependence was invoked with (insn == elem)).  */
653   unsigned int has_internal_dep;
654
655   /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
656      h_i_d because when h_i_d extends, addresses of the deps_list->first
657      change without updating deps_list->first->next->prev_nextp.  Thus
658      BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
659      list is allocated on the obstack.  */
660
661   /* A list of hard backward dependencies.  The insn is a consumer of all the
662      deps mentioned here.  */
663   deps_list_t hard_back_deps;
664
665   /* A list of speculative (weak) dependencies.  The insn is a consumer of all
666      the deps mentioned here.  */
667   deps_list_t spec_back_deps;
668
669   /* A list of insns which depend on the instruction.  Unlike 'back_deps',
670      it represents forward dependencies.  */
671   deps_list_t forw_deps;
672
673   /* A list of scheduled producers of the instruction.  Links are being moved
674      from 'back_deps' to 'resolved_back_deps' while scheduling.  */
675   deps_list_t resolved_back_deps;
676
677   /* A list of scheduled consumers of the instruction.  Links are being moved
678      from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
679      search in 'forw_deps'.  */
680   deps_list_t resolved_forw_deps;
681
682   /* If the insn is conditional (either through COND_EXEC, or because
683      it is a conditional branch), this records the condition.  NULL
684      for insns that haven't been seen yet or don't have a condition;
685      const_true_rtx to mark an insn without a condition, or with a
686      condition that has been clobbered by a subsequent insn.  */
687   rtx cond;
688
689   /* True if the condition in 'cond' should be reversed to get the actual
690      condition.  */
691   unsigned int reverse_cond : 1;
692
693   /* Some insns (e.g. call) are not allowed to move across blocks.  */
694   unsigned int cant_move : 1;
695 };
696
697 /* Bits used for storing values of the fields in the following
698    structure.  */
699 #define INCREASE_BITS 8
700
701 /* The structure describes how the corresponding insn increases the
702    register pressure for each pressure class.  */
703 struct reg_pressure_data
704 {
705   /* Pressure increase for given class because of clobber.  */
706   unsigned int clobber_increase : INCREASE_BITS;
707   /* Increase in register pressure for given class because of register
708      sets. */
709   unsigned int set_increase : INCREASE_BITS;
710   /* Pressure increase for given class because of unused register
711      set.  */
712   unsigned int unused_set_increase : INCREASE_BITS;
713   /* Pressure change: #sets - #deaths.  */
714   int change : INCREASE_BITS;
715 };
716
717 /* The following structure describes usage of registers by insns.  */
718 struct reg_use_data
719 {
720   /* Regno used in the insn.  */
721   int regno;
722   /* Insn using the regno.  */
723   rtx insn;
724   /* Cyclic list of elements with the same regno.  */
725   struct reg_use_data *next_regno_use;
726   /* List of elements with the same insn.  */
727   struct reg_use_data *next_insn_use;
728 };
729
730 /* The following structure describes used sets of registers by insns.
731    Registers are pseudos whose pressure class is not NO_REGS or hard
732    registers available for allocations.  */
733 struct reg_set_data
734 {
735   /* Regno used in the insn.  */
736   int regno;
737   /* Insn setting the regno.  */
738   rtx insn;
739   /* List of elements with the same insn.  */
740   struct reg_set_data *next_insn_set;
741 };
742
743 struct _haifa_insn_data
744 {
745   /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
746      because when h_i_d extends, addresses of the deps_list->first
747      change without updating deps_list->first->next->prev_nextp.  */
748
749   /* Logical uid gives the original ordering of the insns.  */
750   int luid;
751
752   /* A priority for each insn.  */
753   int priority;
754
755   /* The minimum clock tick at which the insn becomes ready.  This is
756      used to note timing constraints for the insns in the pending list.  */
757   int tick;
758
759   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
760      subsequent blocks in a region.  */
761   int inter_tick;
762
763   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
764   int queue_index;
765
766   short cost;
767
768   /* Set if there's DEF-USE dependence between some speculatively
769      moved load insn and this one.  */
770   unsigned int fed_by_spec_load : 1;
771   unsigned int is_load_insn : 1;
772
773   /* '> 0' if priority is valid,
774      '== 0' if priority was not yet computed,
775      '< 0' if priority in invalid and should be recomputed.  */
776   signed char priority_status;
777
778   /* What speculations are necessary to apply to schedule the instruction.  */
779   ds_t todo_spec;
780
781   /* What speculations were already applied.  */
782   ds_t done_spec;
783
784   /* What speculations are checked by this instruction.  */
785   ds_t check_spec;
786
787   /* Recovery block for speculation checks.  */
788   basic_block recovery_block;
789
790   /* Original pattern of the instruction.  */
791   rtx orig_pat;
792
793   /* The following array contains info how the insn increases register
794      pressure.  There is an element for each cover class of pseudos
795      referenced in insns.  */
796   struct reg_pressure_data *reg_pressure;
797   /* The following array contains maximal reg pressure between last
798      scheduled insn and given insn.  There is an element for each
799      pressure class of pseudos referenced in insns.  This info updated
800      after scheduling each insn for each insn between the two
801      mentioned insns.  */
802   int *max_reg_pressure;
803   /* The following list contains info about used pseudos and hard
804      registers available for allocation.  */
805   struct reg_use_data *reg_use_list;
806   /* The following list contains info about set pseudos and hard
807      registers available for allocation.  */
808   struct reg_set_data *reg_set_list;
809   /* Info about how scheduling the insn changes cost of register
810      pressure excess (between source and target).  */
811   int reg_pressure_excess_cost_change;
812 };
813
814 typedef struct _haifa_insn_data haifa_insn_data_def;
815 typedef haifa_insn_data_def *haifa_insn_data_t;
816
817 DEF_VEC_O (haifa_insn_data_def);
818 DEF_VEC_ALLOC_O (haifa_insn_data_def, heap);
819
820 extern VEC(haifa_insn_data_def, heap) *h_i_d;
821
822 #define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN)))
823
824 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
825    sched-rgn.c.  */
826 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
827 #define INSN_REG_PRESSURE(INSN) (HID (INSN)->reg_pressure)
828 #define INSN_MAX_REG_PRESSURE(INSN) (HID (INSN)->max_reg_pressure)
829 #define INSN_REG_USE_LIST(INSN) (HID (INSN)->reg_use_list)
830 #define INSN_REG_SET_LIST(INSN) (HID (INSN)->reg_set_list)
831 #define INSN_REG_PRESSURE_EXCESS_COST_CHANGE(INSN) \
832   (HID (INSN)->reg_pressure_excess_cost_change)
833 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
834
835 typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def;
836 typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t;
837
838 DEF_VEC_O (haifa_deps_insn_data_def);
839 DEF_VEC_ALLOC_O (haifa_deps_insn_data_def, heap);
840
841 extern VEC(haifa_deps_insn_data_def, heap) *h_d_i_d;
842
843 #define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d,       \
844                                INSN_LUID (INSN)))
845 #define INSN_DEP_COUNT(INSN)    (HDID (INSN)->dep_count)
846 #define HAS_INTERNAL_DEP(INSN)  (HDID (INSN)->has_internal_dep)
847 #define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
848 #define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
849 #define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
850 #define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
851 #define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
852 #define INSN_COND(INSN) (HDID (INSN)->cond)
853 #define INSN_REVERSE_COND(INSN) (HDID (INSN)->reverse_cond)
854 #define CANT_MOVE(INSN) (HDID (INSN)->cant_move)
855 #define CANT_MOVE_BY_LUID(LUID) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
856                                             LUID)->cant_move)
857
858
859 #define INSN_PRIORITY(INSN)     (HID (INSN)->priority)
860 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
861 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
862 #define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
863 #define DONE_SPEC(INSN) (HID (INSN)->done_spec)
864 #define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
865 #define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
866 #define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
867
868 /* INSN is either a simple or a branchy speculation check.  */
869 #define IS_SPECULATION_CHECK_P(INSN) \
870   (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
871
872 /* INSN is a speculation check that will simply reexecute the speculatively
873    scheduled instruction if the speculation fails.  */
874 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
875   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
876
877 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
878    speculation fails.  Insns in that block will reexecute the speculatively
879    scheduled code and then will return immediately after INSN thus preserving
880    semantics of the program.  */
881 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
882   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
883
884 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
885    for speculative scheduling.  Namely, it is 4 integers in the range
886    [0, MAX_DEP_WEAK] and 3 bits.
887    The integers correspond to the probability of the dependence to *not*
888    exist, it is the probability, that overcoming of this dependence will
889    not be followed by execution of the recovery code.  Nevertheless,
890    whatever high the probability of success is, recovery code should still
891    be generated to preserve semantics of the program.  To find a way to
892    get/set these integers, please refer to the {get, set}_dep_weak ()
893    functions in sched-deps.c .
894    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
895    output- and anti- dependence.  It is not enough for speculative scheduling
896    to know just the major type of all the dependence between two instructions,
897    as only true dependence can be overcome.
898    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
899    for using to describe instruction's status.  It is set whenever instruction
900    has at least one dependence, that cannot be overcame.
901    See also: check_dep_status () in sched-deps.c .  */
902
903 /* We exclude sign bit.  */
904 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
905
906 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
907    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
908    dep weakness.  */
909 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
910
911 /* Mask of speculative weakness in dep_status.  */
912 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
913
914 /* This constant means that dependence is fake with 99.999...% probability.
915    This is the maximum value, that can appear in dep_status.
916    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
917    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
918    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
919 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
920
921 /* This constant means that dependence is 99.999...% real and it is a really
922    bad idea to overcome it (though this can be done, preserving program
923    semantics).  */
924 #define MIN_DEP_WEAK 1
925
926 /* This constant represents 100% probability.
927    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
928 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
929
930 /* Default weakness of speculative dependence.  Used when we can't say
931    neither bad nor good about the dependence.  */
932 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
933
934 /* Offset for speculative weaknesses in dep_status.  */
935 enum SPEC_TYPES_OFFSETS {
936   BEGIN_DATA_BITS_OFFSET = 0,
937   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
938   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
939   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
940 };
941
942 /* The following defines provide numerous constants used to distinguish between
943    different types of speculative dependencies.  */
944
945 /* Dependence can be overcome with generation of new data speculative
946    instruction.  */
947 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
948
949 /* This dependence is to the instruction in the recovery block, that was
950    formed to recover after data-speculation failure.
951    Thus, this dependence can overcome with generating of the copy of
952    this instruction in the recovery block.  */
953 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
954
955 /* Dependence can be overcome with generation of new control speculative
956    instruction.  */
957 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
958
959 /* This dependence is to the instruction in the recovery block, that was
960    formed to recover after control-speculation failure.
961    Thus, this dependence can be overcome with generating of the copy of
962    this instruction in the recovery block.  */
963 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
964
965 /* A few convenient combinations.  */
966 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
967 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
968 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
969 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
970 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
971
972 /* Constants, that are helpful in iterating through dep_status.  */
973 #define FIRST_SPEC_TYPE BEGIN_DATA
974 #define LAST_SPEC_TYPE BE_IN_CONTROL
975 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
976
977 /* Dependence on instruction can be of multiple types
978    (e.g. true and output). This fields enhance REG_NOTE_KIND information
979    of the dependence.  */
980 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
981 #define DEP_OUTPUT (DEP_TRUE << 1)
982 #define DEP_ANTI (DEP_OUTPUT << 1)
983
984 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
985
986 /* Instruction has non-speculative dependence.  This bit represents the
987    property of an instruction - not the one of a dependence.
988    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
989 #define HARD_DEP (DEP_ANTI << 1)
990
991 /* This represents the results of calling sched-deps.c functions,
992    which modify dependencies.  */
993 enum DEPS_ADJUST_RESULT {
994   /* No dependence needed (e.g. producer == consumer).  */
995   DEP_NODEP,
996   /* Dependence is already present and wasn't modified.  */
997   DEP_PRESENT,
998   /* Existing dependence was modified to include additional information.  */
999   DEP_CHANGED,
1000   /* New dependence has been created.  */
1001   DEP_CREATED
1002 };
1003
1004 /* Represents the bits that can be set in the flags field of the
1005    sched_info structure.  */
1006 enum SCHED_FLAGS {
1007   /* If set, generate links between instruction as DEPS_LIST.
1008      Otherwise, generate usual INSN_LIST links.  */
1009   USE_DEPS_LIST = 1,
1010   /* Perform data or control (or both) speculation.
1011      Results in generation of data and control speculative dependencies.
1012      Requires USE_DEPS_LIST set.  */
1013   DO_SPECULATION = USE_DEPS_LIST << 1,
1014   SCHED_RGN = DO_SPECULATION << 1,
1015   SCHED_EBB = SCHED_RGN << 1,
1016   /* Scheduler can possibly create new basic blocks.  Used for assertions.  */
1017   NEW_BBS = SCHED_EBB << 1,
1018   SEL_SCHED = NEW_BBS << 1
1019 };
1020
1021 enum SPEC_SCHED_FLAGS {
1022   COUNT_SPEC_IN_CRITICAL_PATH = 1,
1023   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
1024   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1,
1025   SEL_SCHED_SPEC_DONT_CHECK_CONTROL = PREFER_NON_CONTROL_SPEC << 1
1026 };
1027
1028 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
1029                                                != NOTE_INSN_BASIC_BLOCK))
1030
1031 extern FILE *sched_dump;
1032 extern int sched_verbose;
1033
1034 extern spec_info_t spec_info;
1035 extern bool haifa_recovery_bb_ever_added_p;
1036
1037 /* Exception Free Loads:
1038
1039    We define five classes of speculative loads: IFREE, IRISKY,
1040    PFREE, PRISKY, and MFREE.
1041
1042    IFREE loads are loads that are proved to be exception-free, just
1043    by examining the load insn.  Examples for such loads are loads
1044    from TOC and loads of global data.
1045
1046    IRISKY loads are loads that are proved to be exception-risky,
1047    just by examining the load insn.  Examples for such loads are
1048    volatile loads and loads from shared memory.
1049
1050    PFREE loads are loads for which we can prove, by examining other
1051    insns, that they are exception-free.  Currently, this class consists
1052    of loads for which we are able to find a "similar load", either in
1053    the target block, or, if only one split-block exists, in that split
1054    block.  Load2 is similar to load1 if both have same single base
1055    register.  We identify only part of the similar loads, by finding
1056    an insn upon which both load1 and load2 have a DEF-USE dependence.
1057
1058    PRISKY loads are loads for which we can prove, by examining other
1059    insns, that they are exception-risky.  Currently we have two proofs for
1060    such loads.  The first proof detects loads that are probably guarded by a
1061    test on the memory address.  This proof is based on the
1062    backward and forward data dependence information for the region.
1063    Let load-insn be the examined load.
1064    Load-insn is PRISKY iff ALL the following hold:
1065
1066    - insn1 is not in the same block as load-insn
1067    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1068    - test-insn is either a compare or a branch, not in the same block
1069      as load-insn
1070    - load-insn is reachable from test-insn
1071    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1072
1073    This proof might fail when the compare and the load are fed
1074    by an insn not in the region.  To solve this, we will add to this
1075    group all loads that have no input DEF-USE dependence.
1076
1077    The second proof detects loads that are directly or indirectly
1078    fed by a speculative load.  This proof is affected by the
1079    scheduling process.  We will use the flag  fed_by_spec_load.
1080    Initially, all insns have this flag reset.  After a speculative
1081    motion of an insn, if insn is either a load, or marked as
1082    fed_by_spec_load, we will also mark as fed_by_spec_load every
1083    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
1084    load which is fed_by_spec_load is also PRISKY.
1085
1086    MFREE (maybe-free) loads are all the remaining loads. They may be
1087    exception-free, but we cannot prove it.
1088
1089    Now, all loads in IFREE and PFREE classes are considered
1090    exception-free, while all loads in IRISKY and PRISKY classes are
1091    considered exception-risky.  As for loads in the MFREE class,
1092    these are considered either exception-free or exception-risky,
1093    depending on whether we are pessimistic or optimistic.  We have
1094    to take the pessimistic approach to assure the safety of
1095    speculative scheduling, but we can take the optimistic approach
1096    by invoking the -fsched_spec_load_dangerous option.  */
1097
1098 enum INSN_TRAP_CLASS
1099 {
1100   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1101   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1102 };
1103
1104 #define WORST_CLASS(class1, class2) \
1105 ((class1 > class2) ? class1 : class2)
1106
1107 #ifndef __GNUC__
1108 #define __inline
1109 #endif
1110
1111 #ifndef HAIFA_INLINE
1112 #define HAIFA_INLINE __inline
1113 #endif
1114
1115 struct sched_deps_info_def
1116 {
1117   /* Called when computing dependencies for a JUMP_INSN.  This function
1118      should store the set of registers that must be considered as set by
1119      the jump in the regset.  */
1120   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
1121
1122   /* Start analyzing insn.  */
1123   void (*start_insn) (rtx);
1124
1125   /* Finish analyzing insn.  */
1126   void (*finish_insn) (void);
1127
1128   /* Start analyzing insn LHS (Left Hand Side).  */
1129   void (*start_lhs) (rtx);
1130
1131   /* Finish analyzing insn LHS.  */
1132   void (*finish_lhs) (void);
1133
1134   /* Start analyzing insn RHS (Right Hand Side).  */
1135   void (*start_rhs) (rtx);
1136
1137   /* Finish analyzing insn RHS.  */
1138   void (*finish_rhs) (void);
1139
1140   /* Note set of the register.  */
1141   void (*note_reg_set) (int);
1142
1143   /* Note clobber of the register.  */
1144   void (*note_reg_clobber) (int);
1145
1146   /* Note use of the register.  */
1147   void (*note_reg_use) (int);
1148
1149   /* Note memory dependence of type DS between MEM1 and MEM2 (which is
1150      in the INSN2).  */
1151   void (*note_mem_dep) (rtx mem1, rtx mem2, rtx insn2, ds_t ds);
1152
1153   /* Note a dependence of type DS from the INSN.  */
1154   void (*note_dep) (rtx insn, ds_t ds);
1155
1156   /* Nonzero if we should use cselib for better alias analysis.  This
1157      must be 0 if the dependency information is used after sched_analyze
1158      has completed, e.g. if we're using it to initialize state for successor
1159      blocks in region scheduling.  */
1160   unsigned int use_cselib : 1;
1161
1162   /* If set, generate links between instruction as DEPS_LIST.
1163      Otherwise, generate usual INSN_LIST links.  */
1164   unsigned int use_deps_list : 1;
1165
1166   /* Generate data and control speculative dependencies.
1167      Requires USE_DEPS_LIST set.  */
1168   unsigned int generate_spec_deps : 1;
1169 };
1170
1171 extern struct sched_deps_info_def *sched_deps_info;
1172
1173
1174 /* Functions in sched-deps.c.  */
1175 extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
1176 extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t);
1177 extern void add_dependence (rtx, rtx, enum reg_note);
1178 extern void sched_analyze (struct deps_desc *, rtx, rtx);
1179 extern void init_deps (struct deps_desc *, bool);
1180 extern void init_deps_reg_last (struct deps_desc *);
1181 extern void free_deps (struct deps_desc *);
1182 extern void init_deps_global (void);
1183 extern void finish_deps_global (void);
1184 extern void deps_analyze_insn (struct deps_desc *, rtx);
1185 extern void remove_from_deps (struct deps_desc *, rtx);
1186 extern void init_insn_reg_pressure_info (rtx);
1187
1188 extern dw_t get_dep_weak_1 (ds_t, ds_t);
1189 extern dw_t get_dep_weak (ds_t, ds_t);
1190 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
1191 extern dw_t estimate_dep_weak (rtx, rtx);
1192 extern ds_t ds_merge (ds_t, ds_t);
1193 extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx);
1194 extern ds_t ds_max_merge (ds_t, ds_t);
1195 extern dw_t ds_weak (ds_t);
1196 extern ds_t ds_get_speculation_types (ds_t);
1197 extern ds_t ds_get_max_dep_weak (ds_t);
1198
1199 extern void sched_deps_init (bool);
1200 extern void sched_deps_finish (void);
1201
1202 extern void haifa_note_reg_set (int);
1203 extern void haifa_note_reg_clobber (int);
1204 extern void haifa_note_reg_use (int);
1205
1206 extern void maybe_extend_reg_info_p (void);
1207
1208 extern void deps_start_bb (struct deps_desc *, rtx);
1209 extern enum reg_note ds_to_dt (ds_t);
1210
1211 extern bool deps_pools_are_empty_p (void);
1212 extern void sched_free_deps (rtx, rtx, bool);
1213 extern void extend_dependency_caches (int, bool);
1214
1215 extern void debug_ds (ds_t);
1216
1217
1218 /* Functions in haifa-sched.c.  */
1219 extern void sched_init_region_reg_pressure_info (void);
1220 extern int haifa_classify_insn (const_rtx);
1221 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
1222 extern int no_real_insns_p (const_rtx, const_rtx);
1223
1224 extern int insn_cost (rtx);
1225 extern int dep_cost_1 (dep_t, dw_t);
1226 extern int dep_cost (dep_t);
1227 extern int set_priorities (rtx, rtx);
1228
1229 extern void sched_setup_bb_reg_pressure_info (basic_block, rtx);
1230 extern void schedule_block (basic_block *);
1231
1232 extern int cycle_issued_insns;
1233 extern int issue_rate;
1234 extern int dfa_lookahead;
1235
1236 extern void ready_sort (struct ready_list *);
1237 extern rtx ready_element (struct ready_list *, int);
1238 extern rtx *ready_lastpos (struct ready_list *);
1239
1240 extern int try_ready (rtx);
1241 extern void sched_extend_ready_list (int);
1242 extern void sched_finish_ready_list (void);
1243 extern void sched_change_pattern (rtx, rtx);
1244 extern int sched_speculate_insn (rtx, ds_t, rtx *);
1245 extern void unlink_bb_notes (basic_block, basic_block);
1246 extern void add_block (basic_block, basic_block);
1247 extern rtx bb_note (basic_block);
1248 extern void concat_note_lists (rtx, rtx *);
1249 extern rtx sched_emit_insn (rtx);
1250 extern rtx get_ready_element (int);
1251 extern int number_in_ready (void);
1252 \f
1253
1254 /* Types and functions in sched-rgn.c.  */
1255
1256 /* A region is the main entity for interblock scheduling: insns
1257    are allowed to move between blocks in the same region, along
1258    control flow graph edges, in the 'up' direction.  */
1259 typedef struct
1260 {
1261   /* Number of extended basic blocks in region.  */
1262   int rgn_nr_blocks;
1263   /* cblocks in the region (actually index in rgn_bb_table).  */
1264   int rgn_blocks;
1265   /* Dependencies for this region are already computed.  Basically, indicates,
1266      that this is a recovery block.  */
1267   unsigned int dont_calc_deps : 1;
1268   /* This region has at least one non-trivial ebb.  */
1269   unsigned int has_real_ebb : 1;
1270 }
1271 region;
1272
1273 extern int nr_regions;
1274 extern region *rgn_table;
1275 extern int *rgn_bb_table;
1276 extern int *block_to_bb;
1277 extern int *containing_rgn;
1278
1279 /* Often used short-hand in the scheduler.  The rest of the compiler uses
1280    BLOCK_FOR_INSN(INSN) and an indirect reference to get the basic block
1281    number ("index").  For historical reasons, the scheduler does not.  */
1282 #define BLOCK_NUM(INSN)       (BLOCK_FOR_INSN (INSN)->index + 0)
1283
1284 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
1285 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
1286 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
1287 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
1288 #define BLOCK_TO_BB(block) (block_to_bb[block])
1289 #define CONTAINING_RGN(block) (containing_rgn[block])
1290
1291 /* The mapping from ebb to block.  */
1292 extern int *ebb_head;
1293 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
1294 #define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
1295 #define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
1296 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
1297
1298 extern int current_nr_blocks;
1299 extern int current_blocks;
1300 extern int target_bb;
1301
1302 extern bool sched_is_disabled_for_current_region_p (void);
1303 extern void sched_rgn_init (bool);
1304 extern void sched_rgn_finish (void);
1305 extern void rgn_setup_region (int);
1306 extern void sched_rgn_compute_dependencies (int);
1307 extern void sched_rgn_local_init (int);
1308 extern void sched_rgn_local_finish (void);
1309 extern void sched_rgn_local_free (void);
1310 extern void extend_regions (void);
1311 extern void rgn_make_new_region_out_of_new_block (basic_block);
1312
1313 extern void compute_priorities (void);
1314 extern void increase_insn_priority (rtx, int);
1315 extern void debug_rgn_dependencies (int);
1316 extern void debug_dependencies (rtx, rtx);
1317 extern void free_rgn_deps (void);
1318 extern int contributes_to_priority (rtx, rtx);
1319 extern void extend_rgns (int *, int *, sbitmap, int *);
1320 extern void deps_join (struct deps_desc *, struct deps_desc *);
1321
1322 extern void rgn_setup_common_sched_info (void);
1323 extern void rgn_setup_sched_infos (void);
1324
1325 extern void debug_regions (void);
1326 extern void debug_region (int);
1327 extern void dump_region_dot (FILE *, int);
1328 extern void dump_region_dot_file (const char *, int);
1329
1330 extern void haifa_sched_init (void);
1331 extern void haifa_sched_finish (void);
1332
1333 /* sched-deps.c interface to walk, add, search, update, resolve, delete
1334    and debug instruction dependencies.  */
1335
1336 /* Constants defining dependences lists.  */
1337
1338 /* No list.  */
1339 #define SD_LIST_NONE (0)
1340
1341 /* hard_back_deps.  */
1342 #define SD_LIST_HARD_BACK (1)
1343
1344 /* spec_back_deps.  */
1345 #define SD_LIST_SPEC_BACK (2)
1346
1347 /* forw_deps.  */
1348 #define SD_LIST_FORW (4)
1349
1350 /* resolved_back_deps.  */
1351 #define SD_LIST_RES_BACK (8)
1352
1353 /* resolved_forw_deps.  */
1354 #define SD_LIST_RES_FORW (16)
1355
1356 #define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
1357
1358 /* A type to hold above flags.  */
1359 typedef int sd_list_types_def;
1360
1361 extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *);
1362
1363 /* Iterator to walk through, resolve and delete dependencies.  */
1364 struct _sd_iterator
1365 {
1366   /* What lists to walk.  Can be any combination of SD_LIST_* flags.  */
1367   sd_list_types_def types;
1368
1369   /* Instruction dependencies lists of which will be walked.  */
1370   rtx insn;
1371
1372   /* Pointer to the next field of the previous element.  This is not
1373      simply a pointer to the next element to allow easy deletion from the
1374      list.  When a dep is being removed from the list the iterator
1375      will automatically advance because the value in *linkp will start
1376      referring to the next element.  */
1377   dep_link_t *linkp;
1378
1379   /* True if the current list is a resolved one.  */
1380   bool resolved_p;
1381 };
1382
1383 typedef struct _sd_iterator sd_iterator_def;
1384
1385 /* ??? We can move some definitions that are used in below inline functions
1386    out of sched-int.h to sched-deps.c provided that the below functions will
1387    become global externals.
1388    These definitions include:
1389    * struct _deps_list: opaque pointer is needed at global scope.
1390    * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
1391    * struct _dep_node: opaque pointer is needed at scope of
1392    struct _deps_link.  */
1393
1394 /* Return initialized iterator.  */
1395 static inline sd_iterator_def
1396 sd_iterator_start (rtx insn, sd_list_types_def types)
1397 {
1398   /* Some dep_link a pointer to which will return NULL.  */
1399   static dep_link_t null_link = NULL;
1400
1401   sd_iterator_def i;
1402
1403   i.types = types;
1404   i.insn = insn;
1405   i.linkp = &null_link;
1406
1407   /* Avoid 'uninitialized warning'.  */
1408   i.resolved_p = false;
1409
1410   return i;
1411 }
1412
1413 /* Return the current element.  */
1414 static inline bool
1415 sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr)
1416 {
1417   dep_link_t link = *it_ptr->linkp;
1418
1419   if (link != NULL)
1420     {
1421       *dep_ptr = DEP_LINK_DEP (link);
1422       return true;
1423     }
1424   else
1425     {
1426       sd_list_types_def types = it_ptr->types;
1427
1428       if (types != SD_LIST_NONE)
1429         /* Switch to next list.  */
1430         {
1431           deps_list_t list;
1432
1433           sd_next_list (it_ptr->insn,
1434                         &it_ptr->types, &list, &it_ptr->resolved_p);
1435
1436           it_ptr->linkp = &DEPS_LIST_FIRST (list);
1437
1438           if (list)
1439             return sd_iterator_cond (it_ptr, dep_ptr);
1440         }
1441
1442       *dep_ptr = NULL;
1443       return false;
1444     }
1445 }
1446
1447 /* Advance iterator.  */
1448 static inline void
1449 sd_iterator_next (sd_iterator_def *it_ptr)
1450 {
1451   it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp);
1452 }
1453
1454 /* A cycle wrapper.  */
1455 #define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP)               \
1456   for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES));       \
1457        sd_iterator_cond (&(ITER), &(DEP));                      \
1458        sd_iterator_next (&(ITER)))
1459
1460 #define IS_DISPATCH_ON 1
1461 #define IS_CMP 2
1462 #define DISPATCH_VIOLATION 3
1463 #define FITS_DISPATCH_WINDOW 4
1464 #define DISPATCH_INIT 5
1465 #define ADD_TO_DISPATCH_WINDOW 6
1466
1467 extern int sd_lists_size (const_rtx, sd_list_types_def);
1468 extern bool sd_lists_empty_p (const_rtx, sd_list_types_def);
1469 extern void sd_init_insn (rtx);
1470 extern void sd_finish_insn (rtx);
1471 extern dep_t sd_find_dep_between (rtx, rtx, bool);
1472 extern void sd_add_dep (dep_t, bool);
1473 extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
1474 extern void sd_resolve_dep (sd_iterator_def);
1475 extern void sd_copy_back_deps (rtx, rtx, bool);
1476 extern void sd_delete_dep (sd_iterator_def);
1477 extern void sd_debug_lists (rtx, sd_list_types_def);
1478
1479 #endif /* INSN_SCHEDULING */
1480
1481 /* Functions in sched-vis.c.  These must be outside INSN_SCHEDULING as
1482    sched-vis.c is compiled always.  */
1483 extern void print_insn (char *, const_rtx, int);
1484 extern void print_pattern (char *, const_rtx, int);
1485 extern void print_value (char *, const_rtx, int);
1486
1487 #endif /* GCC_SCHED_INT_H */