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