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