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