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