sched-int.h revision 117395
190075Sobrien/* Instruction scheduling pass. This file contains definitions used 290075Sobrien internally in the scheduler. 390075Sobrien Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 490075Sobrien 1999, 2000, 2001 Free Software Foundation, Inc. 590075Sobrien 690075SobrienThis file is part of GCC. 790075Sobrien 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1290075Sobrien 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1790075Sobrien 1890075SobrienYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 2090075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2190075Sobrien02111-1307, USA. */ 2290075Sobrien 23117395Skan/* Pointer to data describing the current DFA state. */ 24117395Skanextern state_t curr_state; 25117395Skan 2690075Sobrien/* Forward declaration. */ 2790075Sobrienstruct ready_list; 2890075Sobrien 2990075Sobrien/* Describe state of dependencies used during sched_analyze phase. */ 3090075Sobrienstruct deps 3190075Sobrien{ 3290075Sobrien /* The *_insns and *_mems are paired lists. Each pending memory operation 3390075Sobrien will have a pointer to the MEM rtx on one list and a pointer to the 3490075Sobrien containing insn on the other list in the same place in the list. */ 3590075Sobrien 3690075Sobrien /* We can't use add_dependence like the old code did, because a single insn 3790075Sobrien may have multiple memory accesses, and hence needs to be on the list 3890075Sobrien once for each memory access. Add_dependence won't let you add an insn 3990075Sobrien to a list more than once. */ 4090075Sobrien 4190075Sobrien /* An INSN_LIST containing all insns with pending read operations. */ 4290075Sobrien rtx pending_read_insns; 4390075Sobrien 4490075Sobrien /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 4590075Sobrien rtx pending_read_mems; 4690075Sobrien 4790075Sobrien /* An INSN_LIST containing all insns with pending write operations. */ 4890075Sobrien rtx pending_write_insns; 4990075Sobrien 5090075Sobrien /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 5190075Sobrien rtx pending_write_mems; 5290075Sobrien 5390075Sobrien /* Indicates the combined length of the two pending lists. We must prevent 5490075Sobrien these lists from ever growing too large since the number of dependencies 5590075Sobrien produced is at least O(N*N), and execution time is at least O(4*N*N), as 5690075Sobrien a function of the length of these pending lists. */ 5790075Sobrien int pending_lists_length; 5890075Sobrien 5990075Sobrien /* Length of the pending memory flush list. Large functions with no 6090075Sobrien calls may build up extremely large lists. */ 6190075Sobrien int pending_flush_length; 6290075Sobrien 6390075Sobrien /* The last insn upon which all memory references must depend. 6490075Sobrien This is an insn which flushed the pending lists, creating a dependency 6590075Sobrien between it and all previously pending memory references. This creates 6690075Sobrien a barrier (or a checkpoint) which no memory reference is allowed to cross. 6790075Sobrien 6890075Sobrien This includes all non constant CALL_INSNs. When we do interprocedural 6990075Sobrien alias analysis, this restriction can be relaxed. 7090075Sobrien This may also be an INSN that writes memory if the pending lists grow 7190075Sobrien too large. */ 7290075Sobrien rtx last_pending_memory_flush; 7390075Sobrien 7490075Sobrien /* A list of the last function calls we have seen. We use a list to 7590075Sobrien represent last function calls from multiple predecessor blocks. 7690075Sobrien Used to prevent register lifetimes from expanding unnecessarily. */ 7790075Sobrien rtx last_function_call; 7890075Sobrien 7990075Sobrien /* A list of insns which use a pseudo register that does not already 8090075Sobrien cross a call. We create dependencies between each of those insn 8190075Sobrien and the next call insn, to ensure that they won't cross a call after 8290075Sobrien scheduling is done. */ 8390075Sobrien rtx sched_before_next_call; 8490075Sobrien 8590075Sobrien /* Used to keep post-call psuedo/hard reg movements together with 8690075Sobrien the call. */ 8790075Sobrien bool in_post_call_group_p; 8890075Sobrien 89102780Skan /* Set to the tail insn of the outermost libcall block. 90102780Skan 91102780Skan When nonzero, we will mark each insn processed by sched_analyze_insn 92102780Skan with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */ 93102780Skan rtx libcall_block_tail_insn; 94102780Skan 9590075Sobrien /* The maximum register number for the following arrays. Before reload 9690075Sobrien this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 9790075Sobrien int max_reg; 9890075Sobrien 9990075Sobrien /* Element N is the next insn that sets (hard or pseudo) register 10090075Sobrien N within the current basic block; or zero, if there is no 10190075Sobrien such insn. Needed for new registers which may be introduced 10290075Sobrien by splitting insns. */ 10390075Sobrien struct deps_reg 10490075Sobrien { 10590075Sobrien rtx uses; 10690075Sobrien rtx sets; 10790075Sobrien rtx clobbers; 10890075Sobrien int uses_length; 10990075Sobrien int clobbers_length; 11090075Sobrien } *reg_last; 11190075Sobrien 112117395Skan /* Element N is set for each register that has any nonzero element 11390075Sobrien in reg_last[N].{uses,sets,clobbers}. */ 11490075Sobrien regset_head reg_last_in_use; 11590075Sobrien}; 11690075Sobrien 11790075Sobrien/* This structure holds some state of the current scheduling pass, and 11890075Sobrien contains some function pointers that abstract out some of the non-generic 11990075Sobrien functionality from functions such as schedule_block or schedule_insn. 12090075Sobrien There is one global variable, current_sched_info, which points to the 12190075Sobrien sched_info structure currently in use. */ 12290075Sobrienstruct sched_info 12390075Sobrien{ 12490075Sobrien /* Add all insns that are initially ready to the ready list. Called once 12590075Sobrien before scheduling a set of insns. */ 12690075Sobrien void (*init_ready_list) PARAMS ((struct ready_list *)); 12790075Sobrien /* Called after taking an insn from the ready list. Returns nonzero if 12890075Sobrien this insn can be scheduled, nonzero if we should silently discard it. */ 12990075Sobrien int (*can_schedule_ready_p) PARAMS ((rtx)); 13090075Sobrien /* Return nonzero if there are more insns that should be scheduled. */ 13190075Sobrien int (*schedule_more_p) PARAMS ((void)); 13290075Sobrien /* Called after an insn has all its dependencies resolved. Return nonzero 13390075Sobrien if it should be moved to the ready list or the queue, or zero if we 13490075Sobrien should silently discard it. */ 13590075Sobrien int (*new_ready) PARAMS ((rtx)); 13690075Sobrien /* Compare priority of two insns. Return a positive number if the second 13790075Sobrien insn is to be preferred for scheduling, and a negative one if the first 13890075Sobrien is to be preferred. Zero if they are equally good. */ 13990075Sobrien int (*rank) PARAMS ((rtx, rtx)); 14090075Sobrien /* Return a string that contains the insn uid and optionally anything else 14190075Sobrien necessary to identify this insn in an output. It's valid to use a 14290075Sobrien static buffer for this. The ALIGNED parameter should cause the string 14390075Sobrien to be formatted so that multiple output lines will line up nicely. */ 14490075Sobrien const char *(*print_insn) PARAMS ((rtx, int)); 14590075Sobrien /* Return nonzero if an insn should be included in priority 14690075Sobrien calculations. */ 14790075Sobrien int (*contributes_to_priority) PARAMS ((rtx, rtx)); 14890075Sobrien /* Called when computing dependencies for a JUMP_INSN. This function 14990075Sobrien should store the set of registers that must be considered as set by 15090075Sobrien the jump in the regset. */ 15190075Sobrien void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset)); 15290075Sobrien 15390075Sobrien /* The boundaries of the set of insns to be scheduled. */ 15490075Sobrien rtx prev_head, next_tail; 15590075Sobrien 15690075Sobrien /* Filled in after the schedule is finished; the first and last scheduled 15790075Sobrien insns. */ 15890075Sobrien rtx head, tail; 15990075Sobrien 16090075Sobrien /* If nonzero, enables an additional sanity check in schedule_block. */ 16190075Sobrien unsigned int queue_must_finish_empty:1; 16290075Sobrien /* Nonzero if we should use cselib for better alias analysis. This 16390075Sobrien must be 0 if the dependency information is used after sched_analyze 16490075Sobrien has completed, e.g. if we're using it to initialize state for successor 16590075Sobrien blocks in region scheduling. */ 16690075Sobrien unsigned int use_cselib:1; 16790075Sobrien}; 16890075Sobrien 16990075Sobrienextern struct sched_info *current_sched_info; 17090075Sobrien 17190075Sobrien/* Indexed by INSN_UID, the collection of all data associated with 17290075Sobrien a single instruction. */ 17390075Sobrien 17490075Sobrienstruct haifa_insn_data 17590075Sobrien{ 17690075Sobrien /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 17790075Sobrien it represents forward dependencies. */ 17890075Sobrien rtx depend; 17990075Sobrien 18090075Sobrien /* The line number note in effect for each insn. For line number 18190075Sobrien notes, this indicates whether the note may be reused. */ 18290075Sobrien rtx line_note; 18390075Sobrien 18490075Sobrien /* Logical uid gives the original ordering of the insns. */ 18590075Sobrien int luid; 18690075Sobrien 18790075Sobrien /* A priority for each insn. */ 18890075Sobrien int priority; 18990075Sobrien 19090075Sobrien /* The number of incoming edges in the forward dependency graph. 19190075Sobrien As scheduling proceds, counts are decreased. An insn moves to 19290075Sobrien the ready queue when its counter reaches zero. */ 19390075Sobrien int dep_count; 19490075Sobrien 19590075Sobrien /* An encoding of the blockage range function. Both unit and range 196117395Skan are coded. This member is used only for old pipeline interface. */ 19790075Sobrien unsigned int blockage; 19890075Sobrien 19990075Sobrien /* Number of instructions referring to this insn. */ 20090075Sobrien int ref_count; 20190075Sobrien 20290075Sobrien /* The minimum clock tick at which the insn becomes ready. This is 20390075Sobrien used to note timing constraints for the insns in the pending list. */ 20490075Sobrien int tick; 20590075Sobrien 20690075Sobrien short cost; 20790075Sobrien 208117395Skan /* An encoding of the function units used. This member is used only 209117395Skan for old pipeline interface. */ 21090075Sobrien short units; 21190075Sobrien 21290075Sobrien /* This weight is an estimation of the insn's contribution to 21390075Sobrien register pressure. */ 21490075Sobrien short reg_weight; 21590075Sobrien 21690075Sobrien /* Some insns (e.g. call) are not allowed to move across blocks. */ 21790075Sobrien unsigned int cant_move : 1; 21890075Sobrien 21990075Sobrien /* Set if there's DEF-USE dependence between some speculatively 22090075Sobrien moved load insn and this one. */ 22190075Sobrien unsigned int fed_by_spec_load : 1; 22290075Sobrien unsigned int is_load_insn : 1; 22390075Sobrien 22490075Sobrien /* Nonzero if priority has been computed already. */ 22590075Sobrien unsigned int priority_known : 1; 22690075Sobrien}; 22790075Sobrien 22890075Sobrienextern struct haifa_insn_data *h_i_d; 22990075Sobrien 23090075Sobrien/* Accessor macros for h_i_d. There are more in haifa-sched.c and 23190075Sobrien sched-rgn.c. */ 23290075Sobrien#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 23390075Sobrien#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 23490075Sobrien#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 23590075Sobrien#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 23690075Sobrien#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 23790075Sobrien#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 23890075Sobrien#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 23990075Sobrien#define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) 24090075Sobrien#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 24190075Sobrien 24290075Sobrien#define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) 24390075Sobrien#define UNIT_BITS 5 24490075Sobrien#define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) 24590075Sobrien#define ENCODE_BLOCKAGE(U, R) \ 24690075Sobrien (((U) << BLOCKAGE_BITS \ 24790075Sobrien | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ 24890075Sobrien | MAX_BLOCKAGE_COST (R)) 24990075Sobrien#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) 25090075Sobrien#define BLOCKAGE_RANGE(B) \ 25190075Sobrien (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ 25290075Sobrien | ((B) & BLOCKAGE_MASK)) 25390075Sobrien 25490075Sobrien/* Encodings of the `<name>_unit_blockage_range' function. */ 25590075Sobrien#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) 25690075Sobrien#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) 25790075Sobrien 25890075Sobrienextern FILE *sched_dump; 25990075Sobrienextern int sched_verbose; 26090075Sobrien 26190075Sobrien#ifndef __GNUC__ 26290075Sobrien#define __inline 26390075Sobrien#endif 26490075Sobrien 26590075Sobrien#ifndef HAIFA_INLINE 26690075Sobrien#define HAIFA_INLINE __inline 26790075Sobrien#endif 26890075Sobrien 26990075Sobrien/* Functions in sched-vis.c. */ 27090075Sobrienextern void init_target_units PARAMS ((void)); 27190075Sobrienextern void insn_print_units PARAMS ((rtx)); 27290075Sobrienextern void init_block_visualization PARAMS ((void)); 27390075Sobrienextern void print_block_visualization PARAMS ((const char *)); 27490075Sobrienextern void visualize_scheduled_insns PARAMS ((int)); 27590075Sobrienextern void visualize_no_unit PARAMS ((rtx)); 27690075Sobrienextern void visualize_stall_cycles PARAMS ((int)); 27790075Sobrienextern void visualize_alloc PARAMS ((void)); 27890075Sobrienextern void visualize_free PARAMS ((void)); 27990075Sobrien 28090075Sobrien/* Functions in sched-deps.c. */ 28190075Sobrienextern void add_dependence PARAMS ((rtx, rtx, enum reg_note)); 28290075Sobrienextern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, 28390075Sobrien rtx)); 28490075Sobrienextern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); 28590075Sobrienextern void init_deps PARAMS ((struct deps *)); 28690075Sobrienextern void free_deps PARAMS ((struct deps *)); 28790075Sobrienextern void init_deps_global PARAMS ((void)); 28890075Sobrienextern void finish_deps_global PARAMS ((void)); 28990075Sobrienextern void compute_forward_dependences PARAMS ((rtx, rtx)); 29090075Sobrienextern rtx find_insn_list PARAMS ((rtx, rtx)); 29190075Sobrienextern void init_dependency_caches PARAMS ((int)); 29290075Sobrienextern void free_dependency_caches PARAMS ((void)); 29390075Sobrien 29490075Sobrien/* Functions in haifa-sched.c. */ 29590075Sobrienextern void get_block_head_tail PARAMS ((int, rtx *, rtx *)); 29690075Sobrienextern int no_real_insns_p PARAMS ((rtx, rtx)); 29790075Sobrien 29890075Sobrienextern void rm_line_notes PARAMS ((rtx, rtx)); 29990075Sobrienextern void save_line_notes PARAMS ((int, rtx, rtx)); 30090075Sobrienextern void restore_line_notes PARAMS ((rtx, rtx)); 30190075Sobrienextern void rm_redundant_line_notes PARAMS ((void)); 30290075Sobrienextern void rm_other_notes PARAMS ((rtx, rtx)); 30390075Sobrien 30490075Sobrienextern int insn_issue_delay PARAMS ((rtx)); 30590075Sobrienextern int set_priorities PARAMS ((rtx, rtx)); 30690075Sobrien 30796263Sobrienextern rtx sched_emit_insn PARAMS ((rtx)); 30890075Sobrienextern void schedule_block PARAMS ((int, int)); 30990075Sobrienextern void sched_init PARAMS ((FILE *)); 31090075Sobrienextern void sched_finish PARAMS ((void)); 31190075Sobrien 31290075Sobrienextern void ready_add PARAMS ((struct ready_list *, rtx)); 31390075Sobrien 31490075Sobrien/* The following are exported for the benefit of debugging functions. It 31590075Sobrien would be nicer to keep them private to haifa-sched.c. */ 31690075Sobrienextern int insn_unit PARAMS ((rtx)); 31790075Sobrienextern int insn_cost PARAMS ((rtx, rtx, rtx)); 31890075Sobrienextern rtx get_unit_last_insn PARAMS ((int)); 31990075Sobrienextern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); 320117395Skanextern void print_insn PARAMS ((char *, rtx, int)); 321