diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 32 | ||||
| -rw-r--r-- | gcc/Makefile.in | 5 | ||||
| -rw-r--r-- | gcc/haifa-sched.c | 1473 | ||||
| -rw-r--r-- | gcc/sched-deps.c | 1399 | ||||
| -rw-r--r-- | gcc/sched-int.h | 161 |
5 files changed, 1599 insertions, 1471 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index efabdb459f5..d38b6e8bf03 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,32 @@ 2000-12-03 Bernd Schmidt <bernds@redhat.co.uk> + * Makefile.in (OBJS): Add sched-deps.o. + (sched-deps.o): New rule. + * haifa-sched.c (struct deps, struct haifa_insn_data): Moved to + sched-int.h. + (INSN_DEPEND, INSN_LUID, CANT_MOVE, INSN_DEP_COUNT): Macros moved to + sched-int.h. + (SIZE_FOR_MODE): Delete unused macro. + (reg_known_equiv_p, reg_known_value, reg_pending_clobbers, + reg_pending_sets, reg_pending_sets_all, true_dependency_cache, + anti_dependency_cache, output_dependency_cache, + forward_dependency_cache): Variables moved to sched-deps.c. + (add_dependence, remove_dependence, find_insn_list, + find_insn_mem_list, add_insn_mem_dependence, flush_pending_lists, + sched_analyze_insn, sched_analyze_1, sched_analyze_2, + sched_analyze, group_leader, compute_forward_dependences, + init_deps, free_deps, init_dependency_caches, free_dependency_caches): + Functions moved to sched-deps.c. + (schedule_region): Call init_deps_global and finish_deps_global + instead of directly manipulating dependency data structures. + * sched-deps.c: New file. + (init_deps_global, finish_deps_global): New functions. + * sched-int.h (struct haifa_insn_data, struct deps): Moved here from + haifa-sched.c. + (h_i_d): Declare. + (INSN_DEPEND, INSN_LUID, CANT_MOVE, INSN_DEP_COUNT): Macros moved here + from haifa-sched.c. + * Makefile.in (OBJS): Add sched-vis.o. (sched-vis.o): New rule. * haifa-sched.c (get_unit_last_insn): New function. @@ -20,6 +47,11 @@ print_block_visualization): Lose basic block argument. All callers changed. (visualize_scheduled_insns): Use new function get_unit_last_insn. + * sched-int.h (current_sched_info, sched_dump): Declare. + (init_target_units, insn_print_units, init_block_visualization, + print_block_visualization, visualize_scheduled_inns, + visualize_no_unit, visualize_stall_cycles, visualize_alloc, + visualize_free): Declare functions. * sched-int.h: New file. * Makefile.in (haifa-sched.o): Depend on it. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 6cb0d77a0c7..62f5ae07ede 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -737,7 +737,7 @@ OBJS = diagnostic.o version.o tree.o print-tree.o stor-layout.o fold-const.o \ mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o \ lists.o ggc-common.o $(GGC) stringpool.o simplify-rtx.o ssa.o bb-reorder.o \ sibcall.o conflict.o timevar.o ifcvt.o dominance.o dependence.o dce.o \ - sched-vis.o hashtab.o + sched-vis.o sched-deps.o hashtab.o BACKEND = toplev.o libbackend.a @@ -1455,6 +1455,9 @@ regmove.o : regmove.c $(CONFIG_H) system.h $(RTL_H) insn-config.h \ haifa-sched.o : haifa-sched.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \ $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \ $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h +sched-deps.o : haifa-sched.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \ + $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \ + $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h sched-vis.o : sched-vis.c $(CONFIG_H) system.h $(RTL_H) sched-int.h \ $(INSN_ATTR_H) $(REGS_H) final.o : final.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h intl.h \ diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index f89f2a1dd77..d768d85e963 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -172,9 +172,6 @@ the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "recog.h" #include "sched-int.h" -extern char *reg_known_equiv_p; -extern rtx *reg_known_value; - #ifdef INSN_SCHEDULING /* issue_rate is the number of insns that can be scheduled in the same @@ -225,158 +222,9 @@ fix_sched_param (param, val) warning ("fix_sched_param: unknown param: %s", param); } -/* Describe state of dependencies used during sched_analyze phase. */ -struct deps -{ - /* The *_insns and *_mems are paired lists. Each pending memory operation - will have a pointer to the MEM rtx on one list and a pointer to the - containing insn on the other list in the same place in the list. */ - - /* We can't use add_dependence like the old code did, because a single insn - may have multiple memory accesses, and hence needs to be on the list - once for each memory access. Add_dependence won't let you add an insn - to a list more than once. */ - - /* An INSN_LIST containing all insns with pending read operations. */ - rtx pending_read_insns; - - /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ - rtx pending_read_mems; - - /* An INSN_LIST containing all insns with pending write operations. */ - rtx pending_write_insns; - - /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ - rtx pending_write_mems; - - /* Indicates the combined length of the two pending lists. We must prevent - these lists from ever growing too large since the number of dependencies - produced is at least O(N*N), and execution time is at least O(4*N*N), as - a function of the length of these pending lists. */ - int pending_lists_length; - - /* The last insn upon which all memory references must depend. - This is an insn which flushed the pending lists, creating a dependency - between it and all previously pending memory references. This creates - a barrier (or a checkpoint) which no memory reference is allowed to cross. - - This includes all non constant CALL_INSNs. When we do interprocedural - alias analysis, this restriction can be relaxed. - This may also be an INSN that writes memory if the pending lists grow - too large. */ - rtx last_pending_memory_flush; - - /* The last function call we have seen. All hard regs, and, of course, - the last function call, must depend on this. */ - rtx last_function_call; - - /* Used to keep post-call psuedo/hard reg movements together with - the call. */ - int in_post_call_group_p; - - /* The LOG_LINKS field of this is a list of insns which use a pseudo - register that does not already cross a call. We create - dependencies between each of those insn and the next call insn, - to ensure that they won't cross a call after scheduling is done. */ - rtx sched_before_next_call; - - /* Element N is the next insn that sets (hard or pseudo) register - N within the current basic block; or zero, if there is no - such insn. Needed for new registers which may be introduced - by splitting insns. */ - rtx *reg_last_uses; - rtx *reg_last_sets; - rtx *reg_last_clobbers; -}; - -static regset reg_pending_sets; -static regset reg_pending_clobbers; -static int reg_pending_sets_all; - -/* To speed up the test for duplicate dependency links we keep a - record of dependencies created by add_dependence when the average - number of instructions in a basic block is very large. - - Studies have shown that there is typically around 5 instructions between - branches for typical C code. So we can make a guess that the average - basic block is approximately 5 instructions long; we will choose 100X - the average size as a very large basic block. - - Each insn has associated bitmaps for its dependencies. Each bitmap - has enough entries to represent a dependency on any other insn in - the insn chain. All bitmap for true dependencies cache is - allocated then the rest two ones are also allocated. */ -static sbitmap *true_dependency_cache; -static sbitmap *anti_dependency_cache; -static sbitmap *output_dependency_cache; - -/* To speed up checking consistency of formed forward insn - dependencies we use the following cache. Another possible solution - could be switching off checking duplication of insns in forward - dependencies. */ -#ifdef ENABLE_CHECKING -static sbitmap *forward_dependency_cache; -#endif - -/* Indexed by INSN_UID, the collection of all data associated with - a single instruction. */ - -struct haifa_insn_data -{ - /* A list of insns which depend on the instruction. Unlike LOG_LINKS, - it represents forward dependancies. */ - rtx depend; - - /* The line number note in effect for each insn. For line number - notes, this indicates whether the note may be reused. */ - rtx line_note; - - /* Logical uid gives the original ordering of the insns. */ - int luid; - - /* A priority for each insn. */ - int priority; - - /* The number of incoming edges in the forward dependency graph. - As scheduling proceds, counts are decreased. An insn moves to - the ready queue when its counter reaches zero. */ - int dep_count; - - /* An encoding of the blockage range function. Both unit and range - are coded. */ - unsigned int blockage; - - /* Number of instructions referring to this insn. */ - int ref_count; - - /* The minimum clock tick at which the insn becomes ready. This is - used to note timing constraints for the insns in the pending list. */ - int tick; +struct haifa_insn_data *h_i_d; - short cost; - - /* An encoding of the function units used. */ - short units; - - /* This weight is an estimation of the insn's contribution to - register pressure. */ - short reg_weight; - - /* Some insns (e.g. call) are not allowed to move across blocks. */ - unsigned int cant_move : 1; - - /* Set if there's DEF-USE dependance between some speculatively - moved load insn and this one. */ - unsigned int fed_by_spec_load : 1; - unsigned int is_load_insn : 1; -}; - -static struct haifa_insn_data *h_i_d; - -#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) -#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) -#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) @@ -407,7 +255,6 @@ static struct haifa_insn_data *h_i_d; #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count) #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note) #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) -#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load) #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn) @@ -489,10 +336,6 @@ struct ready_list }; /* Forward declarations. */ -static void add_dependence PARAMS ((rtx, rtx, enum reg_note)); -static void remove_dependence PARAMS ((rtx, rtx)); -static rtx find_insn_list PARAMS ((rtx, rtx)); -static void set_sched_group_p PARAMS ((rtx)); static unsigned int blockage_range PARAMS ((int, rtx)); static void clear_units PARAMS ((void)); static void schedule_unit PARAMS ((int, rtx, int)); @@ -501,13 +344,6 @@ static int potential_hazard PARAMS ((int, rtx, int)); static int insn_cost PARAMS ((rtx, rtx, rtx)); static int priority PARAMS ((rtx)); static void free_pending_lists PARAMS ((void)); -static void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, - rtx)); -static void flush_pending_lists PARAMS ((struct deps *, rtx, int)); -static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx)); -static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx)); -static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx)); -static void sched_analyze PARAMS ((struct deps *, rtx, rtx)); static int rank_for_schedule PARAMS ((const PTR, const PTR)); static void swap_sort PARAMS ((rtx *, int)); static void queue_insn PARAMS ((rtx, int)); @@ -740,8 +576,6 @@ static int haifa_classify_insn PARAMS ((rtx)); static int is_prisky PARAMS ((rtx, int, int)); static int is_exception_free PARAMS ((rtx, int, int)); -static char find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx)); -static void compute_forward_dependences PARAMS ((rtx, rtx)); static void add_branch_dependences PARAMS ((rtx, rtx)); static void compute_block_backward_dependences PARAMS ((int)); void debug_dependencies PARAMS ((void)); @@ -794,12 +628,7 @@ void debug_reg_vector PARAMS ((regset)); static rtx move_insn1 PARAMS ((rtx, rtx)); static rtx move_insn PARAMS ((rtx, rtx)); -static rtx group_leader PARAMS ((rtx)); static int set_priorities PARAMS ((int)); -static void init_deps PARAMS ((struct deps *)); -static void free_deps PARAMS ((struct deps *)); -static void init_dependency_caches PARAMS ((int)); -static void free_dependency_caches PARAMS ((void)); static void init_regions PARAMS ((void)); static void sched_init PARAMS ((FILE *)); static void schedule_region PARAMS ((int)); @@ -809,307 +638,6 @@ static void propagate_deps PARAMS ((int, struct deps *, int)); /* Point to state used for the current scheduling pass. */ struct sched_info *current_sched_info; - -#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) - -/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the - LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type - of dependence that this link represents. */ - -static void -add_dependence (insn, elem, dep_type) - rtx insn; - rtx elem; - enum reg_note dep_type; -{ - rtx link, next; - int present_p; - enum reg_note present_dep_type; - - /* Don't depend an insn on itself. */ - if (insn == elem) - return; - - /* We can get a dependency on deleted insns due to optimizations in - the register allocation and reloading or due to splitting. Any - such dependency is useless and can be ignored. */ - if (GET_CODE (elem) == NOTE) - return; - - /* If elem is part of a sequence that must be scheduled together, then - make the dependence point to the last insn of the sequence. - When HAVE_cc0, it is possible for NOTEs to exist between users and - setters of the condition codes, so we must skip past notes here. - Otherwise, NOTEs are impossible here. */ - next = next_nonnote_insn (elem); - if (next && SCHED_GROUP_P (next) - && GET_CODE (next) != CODE_LABEL) - { - /* Notes will never intervene here though, so don't bother checking - for them. */ - /* Hah! Wrong. */ - /* We must reject CODE_LABELs, so that we don't get confused by one - that has LABEL_PRESERVE_P set, which is represented by the same - bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be - SCHED_GROUP_P. */ - - rtx nnext; - while ((nnext = next_nonnote_insn (next)) != NULL - && SCHED_GROUP_P (nnext) - && GET_CODE (nnext) != CODE_LABEL) - next = nnext; - - /* Again, don't depend an insn on itself. */ - if (insn == next) - return; - - /* Make the dependence to NEXT, the last insn of the group, instead - of the original ELEM. */ - elem = next; - } - - present_p = 1; -#ifdef INSN_SCHEDULING - /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.) - No need for interblock dependences with calls, since - calls are not moved between blocks. Note: the edge where - elem is a CALL is still required. */ - if (GET_CODE (insn) == CALL_INSN - && (INSN_BB (elem) != INSN_BB (insn))) - return; - - /* If we already have a dependency for ELEM, then we do not need to - do anything. Avoiding the list walk below can cut compile times - dramatically for some code. */ - if (true_dependency_cache != NULL) - { - if (anti_dependency_cache == NULL || output_dependency_cache == NULL) - abort (); - if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem))) - present_dep_type = 0; - else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem))) - present_dep_type = REG_DEP_ANTI; - else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem))) - present_dep_type = REG_DEP_OUTPUT; - else - present_p = 0; - if (present_p && (int) dep_type >= (int) present_dep_type) - return; - } -#endif - - /* Check that we don't already have this dependence. */ - if (present_p) - for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) - if (XEXP (link, 0) == elem) - { -#ifdef INSN_SCHEDULING - /* Clear corresponding cache entry because type of the link - may be changed. */ - if (true_dependency_cache != NULL) - { - if (REG_NOTE_KIND (link) == REG_DEP_ANTI) - RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT - && output_dependency_cache) - RESET_BIT (output_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else - abort (); - } -#endif - - /* If this is a more restrictive type of dependence than the existing - one, then change the existing dependence to this type. */ - if ((int) dep_type < (int) REG_NOTE_KIND (link)) - PUT_REG_NOTE_KIND (link, dep_type); - -#ifdef INSN_SCHEDULING - /* If we are adding a dependency to INSN's LOG_LINKs, then - note that in the bitmap caches of dependency information. */ - if (true_dependency_cache != NULL) - { - if ((int)REG_NOTE_KIND (link) == 0) - SET_BIT (true_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) - SET_BIT (anti_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) - SET_BIT (output_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - } -#endif - return; - } - /* Might want to check one level of transitivity to save conses. */ - - link = alloc_INSN_LIST (elem, LOG_LINKS (insn)); - LOG_LINKS (insn) = link; - - /* Insn dependency, not data dependency. */ - PUT_REG_NOTE_KIND (link, dep_type); - -#ifdef INSN_SCHEDULING - /* If we are adding a dependency to INSN's LOG_LINKs, then note that - in the bitmap caches of dependency information. */ - if (true_dependency_cache != NULL) - { - if ((int)dep_type == 0) - SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); - else if (dep_type == REG_DEP_ANTI) - SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); - else if (dep_type == REG_DEP_OUTPUT) - SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); - } -#endif -} - -/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS - of INSN. Abort if not found. */ - -static void -remove_dependence (insn, elem) - rtx insn; - rtx elem; -{ - rtx prev, link, next; - int found = 0; - - for (prev = 0, link = LOG_LINKS (insn); link; link = next) - { - next = XEXP (link, 1); - if (XEXP (link, 0) == elem) - { - if (prev) - XEXP (prev, 1) = next; - else - LOG_LINKS (insn) = next; - -#ifdef INSN_SCHEDULING - /* If we are removing a dependency from the LOG_LINKS list, - make sure to remove it from the cache too. */ - if (true_dependency_cache != NULL) - { - if (REG_NOTE_KIND (link) == 0) - RESET_BIT (true_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) - RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) - RESET_BIT (output_dependency_cache[INSN_LUID (insn)], - INSN_LUID (elem)); - } -#endif - - free_INSN_LIST_node (link); - - found = 1; - } - else - prev = link; - } - - if (!found) - abort (); - return; -} - -/* Return the INSN_LIST containing INSN in LIST, or NULL - if LIST does not contain INSN. */ - -static inline rtx -find_insn_list (insn, list) - rtx insn; - rtx list; -{ - while (list) - { - if (XEXP (list, 0) == insn) - return list; - list = XEXP (list, 1); - } - return 0; -} - -/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that - goes along with that. */ - -static void -set_sched_group_p (insn) - rtx insn; -{ - rtx link, prev; - - SCHED_GROUP_P (insn) = 1; - - /* There may be a note before this insn now, but all notes will - be removed before we actually try to schedule the insns, so - it won't cause a problem later. We must avoid it here though. */ - prev = prev_nonnote_insn (insn); - - /* Make a copy of all dependencies on the immediately previous insn, - and add to this insn. This is so that all the dependencies will - apply to the group. Remove an explicit dependence on this insn - as SCHED_GROUP_P now represents it. */ - - if (find_insn_list (prev, LOG_LINKS (insn))) - remove_dependence (insn, prev); - - for (link = LOG_LINKS (prev); link; link = XEXP (link, 1)) - add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link)); -} - -/* If it is profitable to use them, initialize caches for tracking - dependency informatino. LUID is the number of insns to be scheduled, - it is used in the estimate of profitability. */ -static void -init_dependency_caches (luid) - int luid; -{ - /* ?!? We could save some memory by computing a per-region luid mapping - which could reduce both the number of vectors in the cache and the size - of each vector. Instead we just avoid the cache entirely unless the - average number of instructions in a basic block is very high. See - the comment before the declaration of true_dependency_cache for - what we consider "very high". */ - if (luid / n_basic_blocks > 100 * 5) - { - true_dependency_cache = sbitmap_vector_alloc (luid, luid); - sbitmap_vector_zero (true_dependency_cache, luid); - anti_dependency_cache = sbitmap_vector_alloc (luid, luid); - sbitmap_vector_zero (anti_dependency_cache, luid); - output_dependency_cache = sbitmap_vector_alloc (luid, luid); - sbitmap_vector_zero (output_dependency_cache, luid); -#ifdef ENABLE_CHECKING - forward_dependency_cache = sbitmap_vector_alloc (luid, luid); - sbitmap_vector_zero (forward_dependency_cache, luid); -#endif - } -} - -/* Free the caches allocated in init_dependency_caches. */ -static void -free_dependency_caches () -{ - if (true_dependency_cache) - { - free (true_dependency_cache); - true_dependency_cache = NULL; - free (anti_dependency_cache); - anti_dependency_cache = NULL; - free (output_dependency_cache); - output_dependency_cache = NULL; -#ifdef ENABLE_CHECKING - free (forward_dependency_cache); - forward_dependency_cache = NULL; -#endif - } -} #ifndef INSN_SCHEDULING void @@ -2853,37 +2381,7 @@ is_exception_free (insn, bb_src, bb_trg) return flag_schedule_speculative_load_dangerous; } - -/* Process an insn's memory dependencies. There are four kinds of - dependencies: - - (0) read dependence: read follows read - (1) true dependence: read follows write - (2) anti dependence: write follows read - (3) output dependence: write follows write - - We are careful to build only dependencies which actually exist, and - use transitivity to avoid building too many links. */ -/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 - otherwise. */ - -HAIFA_INLINE static char -find_insn_mem_list (insn, x, list, list1) - rtx insn, x; - rtx list, list1; -{ - while (list) - { - if (XEXP (list, 0) == insn - && XEXP (list1, 0) == x) - return 1; - list = XEXP (list, 1); - list1 = XEXP (list1, 1); - } - return 0; -} - /* Compute the function units used by INSN. This caches the value returned by function_units_used. A function unit is encoded as the unit number if the value is non-negative and the compliment of a @@ -3299,836 +2797,6 @@ free_pending_lists () free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems); } } - -/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. - The MEM is a memory reference contained within INSN, which we are saving - so that we can do memory aliasing on it. */ - -static void -add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem) - struct deps *deps; - rtx *insn_list, *mem_list, insn, mem; -{ - register rtx link; - - link = alloc_INSN_LIST (insn, *insn_list); - *insn_list = link; - - link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list); - *mem_list = link; - - deps->pending_lists_length++; -} - -/* Make a dependency between every memory reference on the pending lists - and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush - the read list. */ - -static void -flush_pending_lists (deps, insn, only_write) - struct deps *deps; - rtx insn; - int only_write; -{ - rtx u; - rtx link; - - while (deps->pending_read_insns && ! only_write) - { - add_dependence (insn, XEXP (deps->pending_read_insns, 0), - REG_DEP_ANTI); - - link = deps->pending_read_insns; - deps->pending_read_insns = XEXP (deps->pending_read_insns, 1); - free_INSN_LIST_node (link); - - link = deps->pending_read_mems; - deps->pending_read_mems = XEXP (deps->pending_read_mems, 1); - free_EXPR_LIST_node (link); - } - while (deps->pending_write_insns) - { - add_dependence (insn, XEXP (deps->pending_write_insns, 0), - REG_DEP_ANTI); - - link = deps->pending_write_insns; - deps->pending_write_insns = XEXP (deps->pending_write_insns, 1); - free_INSN_LIST_node (link); - - link = deps->pending_write_mems; - deps->pending_write_mems = XEXP (deps->pending_write_mems, 1); - free_EXPR_LIST_node (link); - } - deps->pending_lists_length = 0; - - /* last_pending_memory_flush is now a list of insns. */ - for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - free_INSN_LIST_list (&deps->last_pending_memory_flush); - deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); -} - -/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC - rtx, X, creating all dependencies generated by the write to the - destination of X, and reads of everything mentioned. */ - -static void -sched_analyze_1 (deps, x, insn) - struct deps *deps; - rtx x; - rtx insn; -{ - register int regno; - register rtx dest = XEXP (x, 0); - enum rtx_code code = GET_CODE (x); - - if (dest == 0) - return; - - if (GET_CODE (dest) == PARALLEL - && GET_MODE (dest) == BLKmode) - { - register int i; - for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) - sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn); - if (GET_CODE (x) == SET) - sched_analyze_2 (deps, SET_SRC (x), insn); - return; - } - - while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG - || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) - { - if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) - { - /* The second and third arguments are values read by this insn. */ - sched_analyze_2 (deps, XEXP (dest, 1), insn); - sched_analyze_2 (deps, XEXP (dest, 2), insn); - } - dest = XEXP (dest, 0); - } - - if (GET_CODE (dest) == REG) - { - register int i; - - regno = REGNO (dest); - - /* A hard reg in a wide mode may really be multiple registers. - If so, mark all of them just like the first. */ - if (regno < FIRST_PSEUDO_REGISTER) - { - i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); - while (--i >= 0) - { - int r = regno + i; - rtx u; - - for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); - - /* Clobbers need not be ordered with respect to one - another, but sets must be ordered with respect to a - pending clobber. */ - if (code == SET) - { - free_INSN_LIST_list (&deps->reg_last_uses[r]); - for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); - SET_REGNO_REG_SET (reg_pending_sets, r); - } - else - SET_REGNO_REG_SET (reg_pending_clobbers, r); - - /* Function calls clobber all call_used regs. */ - if (global_regs[r] || (code == SET && call_used_regs[r])) - for (u = deps->last_function_call; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - } - } - else - { - rtx u; - - for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); - - if (code == SET) - { - free_INSN_LIST_list (&deps->reg_last_uses[regno]); - for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); - SET_REGNO_REG_SET (reg_pending_sets, regno); - } - else - SET_REGNO_REG_SET (reg_pending_clobbers, regno); - - /* Pseudos that are REG_EQUIV to something may be replaced - by that during reloading. We need only add dependencies for - the address in the REG_EQUIV note. */ - if (!reload_completed - && reg_known_equiv_p[regno] - && GET_CODE (reg_known_value[regno]) == MEM) - sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); - - /* Don't let it cross a call after scheduling if it doesn't - already cross one. */ - - if (REG_N_CALLS_CROSSED (regno) == 0) - for (u = deps->last_function_call; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - } - } - else if (GET_CODE (dest) == MEM) - { - /* Writing memory. */ - - if (deps->pending_lists_length > 32) - { - /* Flush all pending reads and writes to prevent the pending lists - from getting any larger. Insn scheduling runs too slowly when - these lists get long. The number 32 was chosen because it - seems like a reasonable number. When compiling GCC with itself, - this flush occurs 8 times for sparc, and 10 times for m88k using - the number 32. */ - flush_pending_lists (deps, insn, 0); - } - else - { - rtx u; - rtx pending, pending_mem; - - pending = deps->pending_read_insns; - pending_mem = deps->pending_read_mems; - while (pending) - { - if (anti_dependence (XEXP (pending_mem, 0), dest)) - add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); - - pending = XEXP (pending, 1); - pending_mem = XEXP (pending_mem, 1); - } - - pending = deps->pending_write_insns; - pending_mem = deps->pending_write_mems; - while (pending) - { - if (output_dependence (XEXP (pending_mem, 0), dest)) - add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); - - pending = XEXP (pending, 1); - pending_mem = XEXP (pending_mem, 1); - } - - for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - add_insn_mem_dependence (deps, &deps->pending_write_insns, - &deps->pending_write_mems, insn, dest); - } - sched_analyze_2 (deps, XEXP (dest, 0), insn); - } - - /* Analyze reads. */ - if (GET_CODE (x) == SET) - sched_analyze_2 (deps, SET_SRC (x), insn); -} - -/* Analyze the uses of memory and registers in rtx X in INSN. */ - -static void -sched_analyze_2 (deps, x, insn) - struct deps *deps; - rtx x; - rtx insn; -{ - register int i; - register int j; - register enum rtx_code code; - register const char *fmt; - - if (x == 0) - return; - - code = GET_CODE (x); - - switch (code) - { - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case CONST: - case LABEL_REF: - /* Ignore constants. Note that we must handle CONST_DOUBLE here - because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but - this does not mean that this insn is using cc0. */ - return; - -#ifdef HAVE_cc0 - case CC0: - /* User of CC0 depends on immediately preceding insn. */ - set_sched_group_p (insn); - return; -#endif - - case REG: - { - rtx u; - int regno = REGNO (x); - if (regno < FIRST_PSEUDO_REGISTER) - { - int i; - - i = HARD_REGNO_NREGS (regno, GET_MODE (x)); - while (--i >= 0) - { - int r = regno + i; - deps->reg_last_uses[r] - = alloc_INSN_LIST (insn, deps->reg_last_uses[r]); - - for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - /* ??? This should never happen. */ - for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - if (call_used_regs[r] || global_regs[r]) - /* Function calls clobber all call_used regs. */ - for (u = deps->last_function_call; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - } - } - else - { - deps->reg_last_uses[regno] - = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]); - - for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - /* ??? This should never happen. */ - for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - /* Pseudos that are REG_EQUIV to something may be replaced - by that during reloading. We need only add dependencies for - the address in the REG_EQUIV note. */ - if (!reload_completed - && reg_known_equiv_p[regno] - && GET_CODE (reg_known_value[regno]) == MEM) - sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); - - /* If the register does not already cross any calls, then add this - insn to the sched_before_next_call list so that it will still - not cross calls after scheduling. */ - if (REG_N_CALLS_CROSSED (regno) == 0) - add_dependence (deps->sched_before_next_call, insn, - REG_DEP_ANTI); - } - return; - } - - case MEM: - { - /* Reading memory. */ - rtx u; - rtx pending, pending_mem; - - pending = deps->pending_read_insns; - pending_mem = deps->pending_read_mems; - while (pending) - { - if (read_dependence (XEXP (pending_mem, 0), x)) - add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); - - pending = XEXP (pending, 1); - pending_mem = XEXP (pending_mem, 1); - } - - pending = deps->pending_write_insns; - pending_mem = deps->pending_write_mems; - while (pending) - { - if (true_dependence (XEXP (pending_mem, 0), VOIDmode, - x, rtx_varies_p)) - add_dependence (insn, XEXP (pending, 0), 0); - - pending = XEXP (pending, 1); - pending_mem = XEXP (pending_mem, 1); - } - - for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - /* Always add these dependencies to pending_reads, since - this insn may be followed by a write. */ - add_insn_mem_dependence (deps, &deps->pending_read_insns, - &deps->pending_read_mems, insn, x); - - /* Take advantage of tail recursion here. */ - sched_analyze_2 (deps, XEXP (x, 0), insn); - return; - } - - /* Force pending stores to memory in case a trap handler needs them. */ - case TRAP_IF: - flush_pending_lists (deps, insn, 1); - break; - - case ASM_OPERANDS: - case ASM_INPUT: - case UNSPEC_VOLATILE: - { - rtx u; - - /* Traditional and volatile asm instructions must be considered to use - and clobber all hard registers, all pseudo-registers and all of - memory. So must TRAP_IF and UNSPEC_VOLATILE operations. - - Consider for instance a volatile asm that changes the fpu rounding - mode. An insn should not be moved across this even if it only uses - pseudo-regs because it might give an incorrectly rounded result. */ - if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) - { - int max_reg = max_reg_num (); - for (i = 0; i < max_reg; i++) - { - for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - free_INSN_LIST_list (&deps->reg_last_uses[i]); - - for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - } - reg_pending_sets_all = 1; - - flush_pending_lists (deps, insn, 0); - } - - /* For all ASM_OPERANDS, we must traverse the vector of input operands. - We can not just fall through here since then we would be confused - by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate - traditional asms unlike their normal usage. */ - - if (code == ASM_OPERANDS) - { - for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) - sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn); - return; - } - break; - } - - case PRE_DEC: - case POST_DEC: - case PRE_INC: - case POST_INC: - /* These both read and modify the result. We must handle them as writes - to get proper dependencies for following instructions. We must handle - them as reads to get proper dependencies from this to previous - instructions. Thus we need to pass them to both sched_analyze_1 - and sched_analyze_2. We must call sched_analyze_2 first in order - to get the proper antecedent for the read. */ - sched_analyze_2 (deps, XEXP (x, 0), insn); - sched_analyze_1 (deps, x, insn); - return; - - case POST_MODIFY: - case PRE_MODIFY: - /* op0 = op0 + op1 */ - sched_analyze_2 (deps, XEXP (x, 0), insn); - sched_analyze_2 (deps, XEXP (x, 1), insn); - sched_analyze_1 (deps, x, insn); - return; - - default: - break; - } - - /* Other cases: walk the insn. */ - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - sched_analyze_2 (deps, XEXP (x, i), insn); - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - sched_analyze_2 (deps, XVECEXP (x, i, j), insn); - } -} - -/* Analyze an INSN with pattern X to find all dependencies. */ - -static void -sched_analyze_insn (deps, x, insn, loop_notes) - struct deps *deps; - rtx x, insn; - rtx loop_notes; -{ - register RTX_CODE code = GET_CODE (x); - rtx link; - int maxreg = max_reg_num (); - int i; - - if (code == COND_EXEC) - { - sched_analyze_2 (deps, COND_EXEC_TEST (x), insn); - - /* ??? Should be recording conditions so we reduce the number of - false dependancies. */ - x = COND_EXEC_CODE (x); - code = GET_CODE (x); - } - if (code == SET || code == CLOBBER) - sched_analyze_1 (deps, x, insn); - else if (code == PARALLEL) - { - register int i; - for (i = XVECLEN (x, 0) - 1; i >= 0; i--) - { - rtx sub = XVECEXP (x, 0, i); - code = GET_CODE (sub); - - if (code == COND_EXEC) - { - sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); - sub = COND_EXEC_CODE (sub); - code = GET_CODE (sub); - } - if (code == SET || code == CLOBBER) - sched_analyze_1 (deps, sub, insn); - else - sched_analyze_2 (deps, sub, insn); - } - } - else - sched_analyze_2 (deps, x, insn); - - /* Mark registers CLOBBERED or used by called function. */ - if (GET_CODE (insn) == CALL_INSN) - for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) - { - if (GET_CODE (XEXP (link, 0)) == CLOBBER) - sched_analyze_1 (deps, XEXP (link, 0), insn); - else - sched_analyze_2 (deps, XEXP (link, 0), insn); - } - - /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic - block, then we must be sure that no instructions are scheduled across it. - Otherwise, the reg_n_refs info (which depends on loop_depth) would - become incorrect. */ - - if (loop_notes) - { - int max_reg = max_reg_num (); - int schedule_barrier_found = 0; - rtx link; - - /* Update loop_notes with any notes from this insn. Also determine - if any of the notes on the list correspond to instruction scheduling - barriers (loop, eh & setjmp notes, but not range notes. */ - link = loop_notes; - while (XEXP (link, 1)) - { - if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG - || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END - || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG - || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END - || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP) - schedule_barrier_found = 1; - - link = XEXP (link, 1); - } - XEXP (link, 1) = REG_NOTES (insn); - REG_NOTES (insn) = loop_notes; - - /* Add dependencies if a scheduling barrier was found. */ - if (schedule_barrier_found) - { - for (i = 0; i < max_reg; i++) - { - rtx u; - for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - free_INSN_LIST_list (&deps->reg_last_uses[i]); - - for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - } - reg_pending_sets_all = 1; - - flush_pending_lists (deps, insn, 0); - } - - } - - /* Accumulate clobbers until the next set so that it will be output dependent - on all of them. At the next set we can clear the clobber list, since - subsequent sets will be output dependent on it. */ - EXECUTE_IF_SET_IN_REG_SET - (reg_pending_sets, 0, i, - { - free_INSN_LIST_list (&deps->reg_last_sets[i]); - free_INSN_LIST_list (&deps->reg_last_clobbers[i]); - deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX); - }); - EXECUTE_IF_SET_IN_REG_SET - (reg_pending_clobbers, 0, i, - { - deps->reg_last_clobbers[i] - = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]); - }); - CLEAR_REG_SET (reg_pending_sets); - CLEAR_REG_SET (reg_pending_clobbers); - - if (reg_pending_sets_all) - { - for (i = 0; i < maxreg; i++) - { - free_INSN_LIST_list (&deps->reg_last_sets[i]); - free_INSN_LIST_list (&deps->reg_last_clobbers[i]); - deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX); - } - - reg_pending_sets_all = 0; - } - - /* If a post-call group is still open, see if it should remain so. - This insn must be a simple move of a hard reg to a pseudo or - vice-versa. - - We must avoid moving these insns for correctness on - SMALL_REGISTER_CLASS machines, and for special registers like - PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all - hard regs for all targets. */ - - if (deps->in_post_call_group_p) - { - rtx tmp, set = single_set (insn); - int src_regno, dest_regno; - - if (set == NULL) - goto end_call_group; - - tmp = SET_DEST (set); - if (GET_CODE (tmp) == SUBREG) - tmp = SUBREG_REG (tmp); - if (GET_CODE (tmp) == REG) - dest_regno = REGNO (tmp); - else - goto end_call_group; - - tmp = SET_SRC (set); - if (GET_CODE (tmp) == SUBREG) - tmp = SUBREG_REG (tmp); - if (GET_CODE (tmp) == REG) - src_regno = REGNO (tmp); - else - goto end_call_group; - - if (src_regno < FIRST_PSEUDO_REGISTER - || dest_regno < FIRST_PSEUDO_REGISTER) - { - set_sched_group_p (insn); - CANT_MOVE (insn) = 1; - } - else - { - end_call_group: - deps->in_post_call_group_p = 0; - } - } -} - -/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS - for every dependency. */ - -static void -sched_analyze (deps, head, tail) - struct deps *deps; - rtx head, tail; -{ - register rtx insn; - register rtx u; - rtx loop_notes = 0; - - for (insn = head;; insn = NEXT_INSN (insn)) - { - if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) - { - /* Clear out the stale LOG_LINKS from flow. */ - free_INSN_LIST_list (&LOG_LINKS (insn)); - - /* Clear out stale SCHED_GROUP_P. */ - SCHED_GROUP_P (insn) = 0; - - /* Make each JUMP_INSN a scheduling barrier for memory - references. */ - if (GET_CODE (insn) == JUMP_INSN) - deps->last_pending_memory_flush - = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); - sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); - loop_notes = 0; - } - else if (GET_CODE (insn) == CALL_INSN) - { - rtx x; - register int i; - - /* Clear out stale SCHED_GROUP_P. */ - SCHED_GROUP_P (insn) = 0; - - CANT_MOVE (insn) = 1; - - /* Clear out the stale LOG_LINKS from flow. */ - free_INSN_LIST_list (&LOG_LINKS (insn)); - - /* Any instruction using a hard register which may get clobbered - by a call needs to be marked as dependent on this call. - This prevents a use of a hard return reg from being moved - past a void call (i.e. it does not explicitly set the hard - return reg). */ - - /* If this call is followed by a NOTE_INSN_SETJMP, then assume that - all registers, not just hard registers, may be clobbered by this - call. */ - - /* Insn, being a CALL_INSN, magically depends on - `last_function_call' already. */ - - if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE - && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP) - { - int max_reg = max_reg_num (); - for (i = 0; i < max_reg; i++) - { - for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - free_INSN_LIST_list (&deps->reg_last_uses[i]); - - for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - - for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), 0); - } - reg_pending_sets_all = 1; - - /* Add a pair of REG_SAVE_NOTEs which we will later - convert back into a NOTE_INSN_SETJMP note. See - reemit_notes for why we use a pair of NOTEs. */ - REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE, - GEN_INT (0), - REG_NOTES (insn)); - REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE, - GEN_INT (NOTE_INSN_SETJMP), - REG_NOTES (insn)); - } - else - { - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (call_used_regs[i] || global_regs[i]) - { - for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) - add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); - - SET_REGNO_REG_SET (reg_pending_clobbers, i); - } - } - - /* For each insn which shouldn't cross a call, add a dependence - between that insn and this call insn. */ - x = LOG_LINKS (deps->sched_before_next_call); - while (x) - { - add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI); - x = XEXP (x, 1); - } - free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call)); - - sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); - loop_notes = 0; - - /* In the absence of interprocedural alias analysis, we must flush - all pending reads and writes, and start new dependencies starting - from here. But only flush writes for constant calls (which may - be passed a pointer to something we haven't written yet). */ - flush_pending_lists (deps, insn, CONST_CALL_P (insn)); - - /* Depend this function call (actually, the user of this - function call) on all hard register clobberage. */ - - /* last_function_call is now a list of insns. */ - free_INSN_LIST_list (&deps->last_function_call); - deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); - - /* Before reload, begin a post-call group, so as to keep the - lifetimes of hard registers correct. */ - if (! reload_completed) - deps->in_post_call_group_p = 1; - } - - /* See comments on reemit_notes as to why we do this. - ??? Actually, the reemit_notes just say what is done, not why. */ - - else if (GET_CODE (insn) == NOTE - && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END)) - { - loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn), - loop_notes); - loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, - GEN_INT (NOTE_LINE_NUMBER (insn)), - loop_notes); - } - else if (GET_CODE (insn) == NOTE - && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END - || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP - && GET_CODE (PREV_INSN (insn)) != CALL_INSN))) - { - rtx rtx_region; - - if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) - rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); - else - rtx_region = GEN_INT (0); - - loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, - rtx_region, - loop_notes); - loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, - GEN_INT (NOTE_LINE_NUMBER (insn)), - loop_notes); - CONST_CALL_P (loop_notes) = CONST_CALL_P (insn); - } - - if (insn == tail) - return; - } - abort (); -} /* Macros and functions for keeping the priority queue sorted, and dealing with queueing and dequeueing of instructions. */ @@ -5305,25 +3973,6 @@ move_insn (insn, last) return retval; } -/* Return an insn which represents a SCHED_GROUP, which is - the last insn in the group. */ - -static rtx -group_leader (insn) - rtx insn; -{ - rtx prev; - - do - { - prev = insn; - insn = next_nonnote_insn (insn); - } - while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL)); - - return prev; -} - /* Use forward list scheduling to rearrange insns of block BB in region RGN, possibly bringing insns from subsequent blocks in the same region. */ @@ -5545,117 +4194,6 @@ debug_reg_vector (s) fprintf (sched_dump, "\n"); } -/* Examine insns in the range [ HEAD, TAIL ] and Use the backward - dependences from LOG_LINKS to build forward dependences in - INSN_DEPEND. */ - -static void -compute_forward_dependences (head, tail) - rtx head, tail; -{ - rtx insn, link; - rtx next_tail; - enum reg_note dep_type; - - next_tail = NEXT_INSN (tail); - for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - { - if (! INSN_P (insn)) - continue; - - insn = group_leader (insn); - - for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) - { - rtx x = group_leader (XEXP (link, 0)); - rtx new_link; - - if (x != XEXP (link, 0)) - continue; - -#ifdef ENABLE_CHECKING - /* If add_dependence is working properly there should never - be notes, deleted insns or duplicates in the backward - links. Thus we need not check for them here. - - However, if we have enabled checking we might as well go - ahead and verify that add_dependence worked properly. */ - if (GET_CODE (x) == NOTE - || INSN_DELETED_P (x) - || (forward_dependency_cache != NULL - && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], - INSN_LUID (insn))) - || (forward_dependency_cache == NULL - && find_insn_list (insn, INSN_DEPEND (x)))) - abort (); - if (forward_dependency_cache != NULL) - SET_BIT (forward_dependency_cache[INSN_LUID (x)], - INSN_LUID (insn)); -#endif - - new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); - - dep_type = REG_NOTE_KIND (link); - PUT_REG_NOTE_KIND (new_link, dep_type); - - INSN_DEPEND (x) = new_link; - INSN_DEP_COUNT (insn) += 1; - } - } -} - -/* Initialize variables for region data dependence analysis. - n_bbs is the number of region blocks. */ - -static void -init_deps (deps) - struct deps *deps; -{ - int maxreg = max_reg_num (); - deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx)); - deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx)); - deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx)); - - deps->pending_read_insns = 0; - deps->pending_read_mems = 0; - deps->pending_write_insns = 0; - deps->pending_write_mems = 0; - deps->pending_lists_length = 0; - deps->last_pending_memory_flush = 0; - deps->last_function_call = 0; - deps->in_post_call_group_p = 0; - - deps->sched_before_next_call - = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX, - NULL_RTX, 0, NULL_RTX, NULL_RTX); - LOG_LINKS (deps->sched_before_next_call) = 0; -} - -/* Free insn lists found in DEPS. */ - -static void -free_deps (deps) - struct deps *deps; -{ - int max_reg = max_reg_num (); - int i; - - /* Note this loop is executed max_reg * nr_regions times. It's first - implementation accounted for over 90% of the calls to free_INSN_LIST_list. - The list was empty for the vast majority of those calls. On the PA, not - calling free_INSN_LIST_list in those cases improves -O2 compile times by - 3-5% on average. */ - for (i = 0; i < max_reg; ++i) - { - if (deps->reg_last_clobbers[i]) - free_INSN_LIST_list (&deps->reg_last_clobbers[i]); - if (deps->reg_last_sets[i]) - free_INSN_LIST_list (&deps->reg_last_sets[i]); - if (deps->reg_last_uses[i]) - free_INSN_LIST_list (&deps->reg_last_uses[i]); - } -} - /* Add dependences so that branches are scheduled to run last in their block. */ @@ -6051,16 +4589,12 @@ schedule_region (rgn) int bb; int rgn_n_insns = 0; int sched_rgn_n_insns = 0; - regset_head reg_pending_sets_head; - regset_head reg_pending_clobbers_head; /* Set variables for the current region. */ current_nr_blocks = RGN_NR_BLOCKS (rgn); current_blocks = RGN_BLOCKS (rgn); - reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); - reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); - reg_pending_sets_all = 0; + init_deps_global (); /* Initializations for region data dependence analyisis. */ bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks); @@ -6218,8 +4752,7 @@ schedule_region (rgn) /* Done with this region. */ free_pending_lists (); - FREE_REG_SET (reg_pending_sets); - FREE_REG_SET (reg_pending_clobbers); + finish_deps_global (); free (bb_deps); diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c new file mode 100644 index 00000000000..7f9914cdd82 --- /dev/null +++ b/gcc/sched-deps.c @@ -0,0 +1,1399 @@ +/* Instruction scheduling pass. This file computes dependencies between + instructions. + Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, + 1999, 2000 Free Software Foundation, Inc. + Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, + and currently maintained by, Jim Wilson (wilson@cygnus.com) + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GNU CC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to the Free +the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "toplev.h" +#include "rtl.h" +#include "tm_p.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "regs.h" +#include "function.h" +#include "flags.h" +#include "insn-config.h" +#include "insn-attr.h" +#include "except.h" +#include "toplev.h" +#include "recog.h" +#include "sched-int.h" + +extern char *reg_known_equiv_p; +extern rtx *reg_known_value; + +static regset_head reg_pending_sets_head; +static regset_head reg_pending_clobbers_head; + +static regset reg_pending_sets; +static regset reg_pending_clobbers; +static int reg_pending_sets_all; + +/* To speed up the test for duplicate dependency links we keep a + record of dependencies created by add_dependence when the average + number of instructions in a basic block is very large. + + Studies have shown that there is typically around 5 instructions between + branches for typical C code. So we can make a guess that the average + basic block is approximately 5 instructions long; we will choose 100X + the average size as a very large basic block. + + Each insn has associated bitmaps for its dependencies. Each bitmap + has enough entries to represent a dependency on any other insn in + the insn chain. All bitmap for true dependencies cache is + allocated then the rest two ones are also allocated. */ +static sbitmap *true_dependency_cache; +static sbitmap *anti_dependency_cache; +static sbitmap *output_dependency_cache; + +/* To speed up checking consistency of formed forward insn + dependencies we use the following cache. Another possible solution + could be switching off checking duplication of insns in forward + dependencies. */ +#ifdef ENABLE_CHECKING +static sbitmap *forward_dependency_cache; +#endif + +static void remove_dependence PARAMS ((rtx, rtx)); +static void set_sched_group_p PARAMS ((rtx)); + +static void flush_pending_lists PARAMS ((struct deps *, rtx, int)); +static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx)); +static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx)); +static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx)); +static rtx group_leader PARAMS ((rtx)); + +/* Return the INSN_LIST containing INSN in LIST, or NULL + if LIST does not contain INSN. */ + +HAIFA_INLINE rtx +find_insn_list (insn, list) + rtx insn; + rtx list; +{ + while (list) + { + if (XEXP (list, 0) == insn) + return list; + list = XEXP (list, 1); + } + return 0; +} + +/* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 + otherwise. */ + +HAIFA_INLINE int +find_insn_mem_list (insn, x, list, list1) + rtx insn, x; + rtx list, list1; +{ + while (list) + { + if (XEXP (list, 0) == insn + && XEXP (list1, 0) == x) + return 1; + list = XEXP (list, 1); + list1 = XEXP (list1, 1); + } + return 0; +} + +/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the + LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type + of dependence that this link represents. */ + +void +add_dependence (insn, elem, dep_type) + rtx insn; + rtx elem; + enum reg_note dep_type; +{ + rtx link, next; + int present_p; + enum reg_note present_dep_type; + + /* Don't depend an insn on itself. */ + if (insn == elem) + return; + + /* We can get a dependency on deleted insns due to optimizations in + the register allocation and reloading or due to splitting. Any + such dependency is useless and can be ignored. */ + if (GET_CODE (elem) == NOTE) + return; + + /* If elem is part of a sequence that must be scheduled together, then + make the dependence point to the last insn of the sequence. + When HAVE_cc0, it is possible for NOTEs to exist between users and + setters of the condition codes, so we must skip past notes here. + Otherwise, NOTEs are impossible here. */ + next = next_nonnote_insn (elem); + if (next && SCHED_GROUP_P (next) + && GET_CODE (next) != CODE_LABEL) + { + /* Notes will never intervene here though, so don't bother checking + for them. */ + /* Hah! Wrong. */ + /* We must reject CODE_LABELs, so that we don't get confused by one + that has LABEL_PRESERVE_P set, which is represented by the same + bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be + SCHED_GROUP_P. */ + + rtx nnext; + while ((nnext = next_nonnote_insn (next)) != NULL + && SCHED_GROUP_P (nnext) + && GET_CODE (nnext) != CODE_LABEL) + next = nnext; + + /* Again, don't depend an insn on itself. */ + if (insn == next) + return; + + /* Make the dependence to NEXT, the last insn of the group, instead + of the original ELEM. */ + elem = next; + } + + present_p = 1; +#ifdef INSN_SCHEDULING + /* ??? No good way to tell from here whether we're doing interblock + scheduling. Possibly add another callback. */ +#if 0 + /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.) + No need for interblock dependences with calls, since + calls are not moved between blocks. Note: the edge where + elem is a CALL is still required. */ + if (GET_CODE (insn) == CALL_INSN + && (INSN_BB (elem) != INSN_BB (insn))) + return; +#endif + + /* If we already have a dependency for ELEM, then we do not need to + do anything. Avoiding the list walk below can cut compile times + dramatically for some code. */ + if (true_dependency_cache != NULL) + { + if (anti_dependency_cache == NULL || output_dependency_cache == NULL) + abort (); + if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem))) + present_dep_type = 0; + else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem))) + present_dep_type = REG_DEP_ANTI; + else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem))) + present_dep_type = REG_DEP_OUTPUT; + else + present_p = 0; + if (present_p && (int) dep_type >= (int) present_dep_type) + return; + } +#endif + + /* Check that we don't already have this dependence. */ + if (present_p) + for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) + if (XEXP (link, 0) == elem) + { +#ifdef INSN_SCHEDULING + /* Clear corresponding cache entry because type of the link + may be changed. */ + if (true_dependency_cache != NULL) + { + if (REG_NOTE_KIND (link) == REG_DEP_ANTI) + RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT + && output_dependency_cache) + RESET_BIT (output_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else + abort (); + } +#endif + + /* If this is a more restrictive type of dependence than the existing + one, then change the existing dependence to this type. */ + if ((int) dep_type < (int) REG_NOTE_KIND (link)) + PUT_REG_NOTE_KIND (link, dep_type); + +#ifdef INSN_SCHEDULING + /* If we are adding a dependency to INSN's LOG_LINKs, then + note that in the bitmap caches of dependency information. */ + if (true_dependency_cache != NULL) + { + if ((int)REG_NOTE_KIND (link) == 0) + SET_BIT (true_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) + SET_BIT (anti_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) + SET_BIT (output_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + } +#endif + return; + } + /* Might want to check one level of transitivity to save conses. */ + + link = alloc_INSN_LIST (elem, LOG_LINKS (insn)); + LOG_LINKS (insn) = link; + + /* Insn dependency, not data dependency. */ + PUT_REG_NOTE_KIND (link, dep_type); + +#ifdef INSN_SCHEDULING + /* If we are adding a dependency to INSN's LOG_LINKs, then note that + in the bitmap caches of dependency information. */ + if (true_dependency_cache != NULL) + { + if ((int)dep_type == 0) + SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); + else if (dep_type == REG_DEP_ANTI) + SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); + else if (dep_type == REG_DEP_OUTPUT) + SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); + } +#endif +} + +/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS + of INSN. Abort if not found. */ + +static void +remove_dependence (insn, elem) + rtx insn; + rtx elem; +{ + rtx prev, link, next; + int found = 0; + + for (prev = 0, link = LOG_LINKS (insn); link; link = next) + { + next = XEXP (link, 1); + if (XEXP (link, 0) == elem) + { + if (prev) + XEXP (prev, 1) = next; + else + LOG_LINKS (insn) = next; + +#ifdef INSN_SCHEDULING + /* If we are removing a dependency from the LOG_LINKS list, + make sure to remove it from the cache too. */ + if (true_dependency_cache != NULL) + { + if (REG_NOTE_KIND (link) == 0) + RESET_BIT (true_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) + RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) + RESET_BIT (output_dependency_cache[INSN_LUID (insn)], + INSN_LUID (elem)); + } +#endif + + free_INSN_LIST_node (link); + + found = 1; + } + else + prev = link; + } + + if (!found) + abort (); + return; +} + +/* Return an insn which represents a SCHED_GROUP, which is + the last insn in the group. */ + +static rtx +group_leader (insn) + rtx insn; +{ + rtx prev; + + do + { + prev = insn; + insn = next_nonnote_insn (insn); + } + while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL)); + + return prev; +} + +/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that + goes along with that. */ + +static void +set_sched_group_p (insn) + rtx insn; +{ + rtx link, prev; + + SCHED_GROUP_P (insn) = 1; + + /* There may be a note before this insn now, but all notes will + be removed before we actually try to schedule the insns, so + it won't cause a problem later. We must avoid it here though. */ + prev = prev_nonnote_insn (insn); + + /* Make a copy of all dependencies on the immediately previous insn, + and add to this insn. This is so that all the dependencies will + apply to the group. Remove an explicit dependence on this insn + as SCHED_GROUP_P now represents it. */ + + if (find_insn_list (prev, LOG_LINKS (insn))) + remove_dependence (insn, prev); + + for (link = LOG_LINKS (prev); link; link = XEXP (link, 1)) + add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link)); +} + +/* Process an insn's memory dependencies. There are four kinds of + dependencies: + + (0) read dependence: read follows read + (1) true dependence: read follows write + (2) anti dependence: write follows read + (3) output dependence: write follows write + + We are careful to build only dependencies which actually exist, and + use transitivity to avoid building too many links. */ + +/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. + The MEM is a memory reference contained within INSN, which we are saving + so that we can do memory aliasing on it. */ + +void +add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem) + struct deps *deps; + rtx *insn_list, *mem_list, insn, mem; +{ + register rtx link; + + link = alloc_INSN_LIST (insn, *insn_list); + *insn_list = link; + + link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list); + *mem_list = link; + + deps->pending_lists_length++; +} + +/* Make a dependency between every memory reference on the pending lists + and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush + the read list. */ + +static void +flush_pending_lists (deps, insn, only_write) + struct deps *deps; + rtx insn; + int only_write; +{ + rtx u; + rtx link; + + while (deps->pending_read_insns && ! only_write) + { + add_dependence (insn, XEXP (deps->pending_read_insns, 0), + REG_DEP_ANTI); + + link = deps->pending_read_insns; + deps->pending_read_insns = XEXP (deps->pending_read_insns, 1); + free_INSN_LIST_node (link); + + link = deps->pending_read_mems; + deps->pending_read_mems = XEXP (deps->pending_read_mems, 1); + free_EXPR_LIST_node (link); + } + while (deps->pending_write_insns) + { + add_dependence (insn, XEXP (deps->pending_write_insns, 0), + REG_DEP_ANTI); + + link = deps->pending_write_insns; + deps->pending_write_insns = XEXP (deps->pending_write_insns, 1); + free_INSN_LIST_node (link); + + link = deps->pending_write_mems; + deps->pending_write_mems = XEXP (deps->pending_write_mems, 1); + free_EXPR_LIST_node (link); + } + deps->pending_lists_length = 0; + + /* last_pending_memory_flush is now a list of insns. */ + for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + free_INSN_LIST_list (&deps->last_pending_memory_flush); + deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); +} + +/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC + rtx, X, creating all dependencies generated by the write to the + destination of X, and reads of everything mentioned. */ + +static void +sched_analyze_1 (deps, x, insn) + struct deps *deps; + rtx x; + rtx insn; +{ + register int regno; + register rtx dest = XEXP (x, 0); + enum rtx_code code = GET_CODE (x); + + if (dest == 0) + return; + + if (GET_CODE (dest) == PARALLEL + && GET_MODE (dest) == BLKmode) + { + register int i; + for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) + sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn); + if (GET_CODE (x) == SET) + sched_analyze_2 (deps, SET_SRC (x), insn); + return; + } + + while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) + { + if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) + { + /* The second and third arguments are values read by this insn. */ + sched_analyze_2 (deps, XEXP (dest, 1), insn); + sched_analyze_2 (deps, XEXP (dest, 2), insn); + } + dest = XEXP (dest, 0); + } + + if (GET_CODE (dest) == REG) + { + register int i; + + regno = REGNO (dest); + + /* A hard reg in a wide mode may really be multiple registers. + If so, mark all of them just like the first. */ + if (regno < FIRST_PSEUDO_REGISTER) + { + i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); + while (--i >= 0) + { + int r = regno + i; + rtx u; + + for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); + + /* Clobbers need not be ordered with respect to one + another, but sets must be ordered with respect to a + pending clobber. */ + if (code == SET) + { + free_INSN_LIST_list (&deps->reg_last_uses[r]); + for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); + SET_REGNO_REG_SET (reg_pending_sets, r); + } + else + SET_REGNO_REG_SET (reg_pending_clobbers, r); + + /* Function calls clobber all call_used regs. */ + if (global_regs[r] || (code == SET && call_used_regs[r])) + for (u = deps->last_function_call; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + } + } + else + { + rtx u; + + for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); + + if (code == SET) + { + free_INSN_LIST_list (&deps->reg_last_uses[regno]); + for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT); + SET_REGNO_REG_SET (reg_pending_sets, regno); + } + else + SET_REGNO_REG_SET (reg_pending_clobbers, regno); + + /* Pseudos that are REG_EQUIV to something may be replaced + by that during reloading. We need only add dependencies for + the address in the REG_EQUIV note. */ + if (!reload_completed + && reg_known_equiv_p[regno] + && GET_CODE (reg_known_value[regno]) == MEM) + sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); + + /* Don't let it cross a call after scheduling if it doesn't + already cross one. */ + + if (REG_N_CALLS_CROSSED (regno) == 0) + for (u = deps->last_function_call; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + } + } + else if (GET_CODE (dest) == MEM) + { + /* Writing memory. */ + + if (deps->pending_lists_length > 32) + { + /* Flush all pending reads and writes to prevent the pending lists + from getting any larger. Insn scheduling runs too slowly when + these lists get long. The number 32 was chosen because it + seems like a reasonable number. When compiling GCC with itself, + this flush occurs 8 times for sparc, and 10 times for m88k using + the number 32. */ + flush_pending_lists (deps, insn, 0); + } + else + { + rtx u; + rtx pending, pending_mem; + + pending = deps->pending_read_insns; + pending_mem = deps->pending_read_mems; + while (pending) + { + if (anti_dependence (XEXP (pending_mem, 0), dest)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + pending = deps->pending_write_insns; + pending_mem = deps->pending_write_mems; + while (pending) + { + if (output_dependence (XEXP (pending_mem, 0), dest)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + add_insn_mem_dependence (deps, &deps->pending_write_insns, + &deps->pending_write_mems, insn, dest); + } + sched_analyze_2 (deps, XEXP (dest, 0), insn); + } + + /* Analyze reads. */ + if (GET_CODE (x) == SET) + sched_analyze_2 (deps, SET_SRC (x), insn); +} + +/* Analyze the uses of memory and registers in rtx X in INSN. */ + +static void +sched_analyze_2 (deps, x, insn) + struct deps *deps; + rtx x; + rtx insn; +{ + register int i; + register int j; + register enum rtx_code code; + register const char *fmt; + + if (x == 0) + return; + + code = GET_CODE (x); + + switch (code) + { + case CONST_INT: + case CONST_DOUBLE: + case SYMBOL_REF: + case CONST: + case LABEL_REF: + /* Ignore constants. Note that we must handle CONST_DOUBLE here + because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but + this does not mean that this insn is using cc0. */ + return; + +#ifdef HAVE_cc0 + case CC0: + /* User of CC0 depends on immediately preceding insn. */ + set_sched_group_p (insn); + return; +#endif + + case REG: + { + rtx u; + int regno = REGNO (x); + if (regno < FIRST_PSEUDO_REGISTER) + { + int i; + + i = HARD_REGNO_NREGS (regno, GET_MODE (x)); + while (--i >= 0) + { + int r = regno + i; + deps->reg_last_uses[r] + = alloc_INSN_LIST (insn, deps->reg_last_uses[r]); + + for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + /* ??? This should never happen. */ + for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + if (call_used_regs[r] || global_regs[r]) + /* Function calls clobber all call_used regs. */ + for (u = deps->last_function_call; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + } + } + else + { + deps->reg_last_uses[regno] + = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]); + + for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + /* ??? This should never happen. */ + for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + /* Pseudos that are REG_EQUIV to something may be replaced + by that during reloading. We need only add dependencies for + the address in the REG_EQUIV note. */ + if (!reload_completed + && reg_known_equiv_p[regno] + && GET_CODE (reg_known_value[regno]) == MEM) + sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); + + /* If the register does not already cross any calls, then add this + insn to the sched_before_next_call list so that it will still + not cross calls after scheduling. */ + if (REG_N_CALLS_CROSSED (regno) == 0) + add_dependence (deps->sched_before_next_call, insn, + REG_DEP_ANTI); + } + return; + } + + case MEM: + { + /* Reading memory. */ + rtx u; + rtx pending, pending_mem; + + pending = deps->pending_read_insns; + pending_mem = deps->pending_read_mems; + while (pending) + { + if (read_dependence (XEXP (pending_mem, 0), x)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + pending = deps->pending_write_insns; + pending_mem = deps->pending_write_mems; + while (pending) + { + if (true_dependence (XEXP (pending_mem, 0), VOIDmode, + x, rtx_varies_p)) + add_dependence (insn, XEXP (pending, 0), 0); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + /* Always add these dependencies to pending_reads, since + this insn may be followed by a write. */ + add_insn_mem_dependence (deps, &deps->pending_read_insns, + &deps->pending_read_mems, insn, x); + + /* Take advantage of tail recursion here. */ + sched_analyze_2 (deps, XEXP (x, 0), insn); + return; + } + + /* Force pending stores to memory in case a trap handler needs them. */ + case TRAP_IF: + flush_pending_lists (deps, insn, 1); + break; + + case ASM_OPERANDS: + case ASM_INPUT: + case UNSPEC_VOLATILE: + { + rtx u; + + /* Traditional and volatile asm instructions must be considered to use + and clobber all hard registers, all pseudo-registers and all of + memory. So must TRAP_IF and UNSPEC_VOLATILE operations. + + Consider for instance a volatile asm that changes the fpu rounding + mode. An insn should not be moved across this even if it only uses + pseudo-regs because it might give an incorrectly rounded result. */ + if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) + { + int max_reg = max_reg_num (); + for (i = 0; i < max_reg; i++) + { + for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + free_INSN_LIST_list (&deps->reg_last_uses[i]); + + for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + } + reg_pending_sets_all = 1; + + flush_pending_lists (deps, insn, 0); + } + + /* For all ASM_OPERANDS, we must traverse the vector of input operands. + We can not just fall through here since then we would be confused + by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate + traditional asms unlike their normal usage. */ + + if (code == ASM_OPERANDS) + { + for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) + sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn); + return; + } + break; + } + + case PRE_DEC: + case POST_DEC: + case PRE_INC: + case POST_INC: + /* These both read and modify the result. We must handle them as writes + to get proper dependencies for following instructions. We must handle + them as reads to get proper dependencies from this to previous + instructions. Thus we need to pass them to both sched_analyze_1 + and sched_analyze_2. We must call sched_analyze_2 first in order + to get the proper antecedent for the read. */ + sched_analyze_2 (deps, XEXP (x, 0), insn); + sched_analyze_1 (deps, x, insn); + return; + + case POST_MODIFY: + case PRE_MODIFY: + /* op0 = op0 + op1 */ + sched_analyze_2 (deps, XEXP (x, 0), insn); + sched_analyze_2 (deps, XEXP (x, 1), insn); + sched_analyze_1 (deps, x, insn); + return; + + default: + break; + } + + /* Other cases: walk the insn. */ + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + sched_analyze_2 (deps, XEXP (x, i), insn); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + sched_analyze_2 (deps, XVECEXP (x, i, j), insn); + } +} + +/* Analyze an INSN with pattern X to find all dependencies. */ + +static void +sched_analyze_insn (deps, x, insn, loop_notes) + struct deps *deps; + rtx x, insn; + rtx loop_notes; +{ + register RTX_CODE code = GET_CODE (x); + rtx link; + int maxreg = max_reg_num (); + int i; + + if (code == COND_EXEC) + { + sched_analyze_2 (deps, COND_EXEC_TEST (x), insn); + + /* ??? Should be recording conditions so we reduce the number of + false dependancies. */ + x = COND_EXEC_CODE (x); + code = GET_CODE (x); + } + if (code == SET || code == CLOBBER) + sched_analyze_1 (deps, x, insn); + else if (code == PARALLEL) + { + register int i; + for (i = XVECLEN (x, 0) - 1; i >= 0; i--) + { + rtx sub = XVECEXP (x, 0, i); + code = GET_CODE (sub); + + if (code == COND_EXEC) + { + sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); + sub = COND_EXEC_CODE (sub); + code = GET_CODE (sub); + } + if (code == SET || code == CLOBBER) + sched_analyze_1 (deps, sub, insn); + else + sched_analyze_2 (deps, sub, insn); + } + } + else + sched_analyze_2 (deps, x, insn); + + /* Mark registers CLOBBERED or used by called function. */ + if (GET_CODE (insn) == CALL_INSN) + for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) + { + if (GET_CODE (XEXP (link, 0)) == CLOBBER) + sched_analyze_1 (deps, XEXP (link, 0), insn); + else + sched_analyze_2 (deps, XEXP (link, 0), insn); + } + + /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic + block, then we must be sure that no instructions are scheduled across it. + Otherwise, the reg_n_refs info (which depends on loop_depth) would + become incorrect. */ + + if (loop_notes) + { + int max_reg = max_reg_num (); + int schedule_barrier_found = 0; + rtx link; + + /* Update loop_notes with any notes from this insn. Also determine + if any of the notes on the list correspond to instruction scheduling + barriers (loop, eh & setjmp notes, but not range notes. */ + link = loop_notes; + while (XEXP (link, 1)) + { + if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG + || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END + || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG + || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END + || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP) + schedule_barrier_found = 1; + + link = XEXP (link, 1); + } + XEXP (link, 1) = REG_NOTES (insn); + REG_NOTES (insn) = loop_notes; + + /* Add dependencies if a scheduling barrier was found. */ + if (schedule_barrier_found) + { + for (i = 0; i < max_reg; i++) + { + rtx u; + for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + free_INSN_LIST_list (&deps->reg_last_uses[i]); + + for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + } + reg_pending_sets_all = 1; + + flush_pending_lists (deps, insn, 0); + } + + } + + /* Accumulate clobbers until the next set so that it will be output dependent + on all of them. At the next set we can clear the clobber list, since + subsequent sets will be output dependent on it. */ + EXECUTE_IF_SET_IN_REG_SET + (reg_pending_sets, 0, i, + { + free_INSN_LIST_list (&deps->reg_last_sets[i]); + free_INSN_LIST_list (&deps->reg_last_clobbers[i]); + deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX); + }); + EXECUTE_IF_SET_IN_REG_SET + (reg_pending_clobbers, 0, i, + { + deps->reg_last_clobbers[i] + = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]); + }); + CLEAR_REG_SET (reg_pending_sets); + CLEAR_REG_SET (reg_pending_clobbers); + + if (reg_pending_sets_all) + { + for (i = 0; i < maxreg; i++) + { + free_INSN_LIST_list (&deps->reg_last_sets[i]); + free_INSN_LIST_list (&deps->reg_last_clobbers[i]); + deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX); + } + + reg_pending_sets_all = 0; + } + + /* If a post-call group is still open, see if it should remain so. + This insn must be a simple move of a hard reg to a pseudo or + vice-versa. + + We must avoid moving these insns for correctness on + SMALL_REGISTER_CLASS machines, and for special registers like + PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all + hard regs for all targets. */ + + if (deps->in_post_call_group_p) + { + rtx tmp, set = single_set (insn); + int src_regno, dest_regno; + + if (set == NULL) + goto end_call_group; + + tmp = SET_DEST (set); + if (GET_CODE (tmp) == SUBREG) + tmp = SUBREG_REG (tmp); + if (GET_CODE (tmp) == REG) + dest_regno = REGNO (tmp); + else + goto end_call_group; + + tmp = SET_SRC (set); + if (GET_CODE (tmp) == SUBREG) + tmp = SUBREG_REG (tmp); + if (GET_CODE (tmp) == REG) + src_regno = REGNO (tmp); + else + goto end_call_group; + + if (src_regno < FIRST_PSEUDO_REGISTER + || dest_regno < FIRST_PSEUDO_REGISTER) + { + set_sched_group_p (insn); + CANT_MOVE (insn) = 1; + } + else + { + end_call_group: + deps->in_post_call_group_p = 0; + } + } +} + +/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS + for every dependency. */ + +void +sched_analyze (deps, head, tail) + struct deps *deps; + rtx head, tail; +{ + register rtx insn; + register rtx u; + rtx loop_notes = 0; + + for (insn = head;; insn = NEXT_INSN (insn)) + { + if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) + { + /* Clear out the stale LOG_LINKS from flow. */ + free_INSN_LIST_list (&LOG_LINKS (insn)); + + /* Clear out stale SCHED_GROUP_P. */ + SCHED_GROUP_P (insn) = 0; + + /* Make each JUMP_INSN a scheduling barrier for memory + references. */ + if (GET_CODE (insn) == JUMP_INSN) + deps->last_pending_memory_flush + = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); + sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); + loop_notes = 0; + } + else if (GET_CODE (insn) == CALL_INSN) + { + rtx x; + register int i; + + /* Clear out stale SCHED_GROUP_P. */ + SCHED_GROUP_P (insn) = 0; + + CANT_MOVE (insn) = 1; + + /* Clear out the stale LOG_LINKS from flow. */ + free_INSN_LIST_list (&LOG_LINKS (insn)); + + /* Any instruction using a hard register which may get clobbered + by a call needs to be marked as dependent on this call. + This prevents a use of a hard return reg from being moved + past a void call (i.e. it does not explicitly set the hard + return reg). */ + + /* If this call is followed by a NOTE_INSN_SETJMP, then assume that + all registers, not just hard registers, may be clobbered by this + call. */ + + /* Insn, being a CALL_INSN, magically depends on + `last_function_call' already. */ + + if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE + && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP) + { + int max_reg = max_reg_num (); + for (i = 0; i < max_reg; i++) + { + for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + free_INSN_LIST_list (&deps->reg_last_uses[i]); + + for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + + for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), 0); + } + reg_pending_sets_all = 1; + + /* Add a pair of REG_SAVE_NOTEs which we will later + convert back into a NOTE_INSN_SETJMP note. See + reemit_notes for why we use a pair of NOTEs. */ + REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE, + GEN_INT (0), + REG_NOTES (insn)); + REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE, + GEN_INT (NOTE_INSN_SETJMP), + REG_NOTES (insn)); + } + else + { + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (call_used_regs[i] || global_regs[i]) + { + for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + + SET_REGNO_REG_SET (reg_pending_clobbers, i); + } + } + + /* For each insn which shouldn't cross a call, add a dependence + between that insn and this call insn. */ + x = LOG_LINKS (deps->sched_before_next_call); + while (x) + { + add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI); + x = XEXP (x, 1); + } + free_INSN_LIST_list (&LOG_LINKS (deps->sched_before_next_call)); + + sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); + loop_notes = 0; + + /* In the absence of interprocedural alias analysis, we must flush + all pending reads and writes, and start new dependencies starting + from here. But only flush writes for constant calls (which may + be passed a pointer to something we haven't written yet). */ + flush_pending_lists (deps, insn, CONST_CALL_P (insn)); + + /* Depend this function call (actually, the user of this + function call) on all hard register clobberage. */ + + /* last_function_call is now a list of insns. */ + free_INSN_LIST_list (&deps->last_function_call); + deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); + + /* Before reload, begin a post-call group, so as to keep the + lifetimes of hard registers correct. */ + if (! reload_completed) + deps->in_post_call_group_p = 1; + } + + /* See comments on reemit_notes as to why we do this. + ??? Actually, the reemit_notes just say what is done, not why. */ + + else if (GET_CODE (insn) == NOTE + && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG + || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END)) + { + loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn), + loop_notes); + loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, + GEN_INT (NOTE_LINE_NUMBER (insn)), + loop_notes); + } + else if (GET_CODE (insn) == NOTE + && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG + || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END + || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG + || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END + || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP + && GET_CODE (PREV_INSN (insn)) != CALL_INSN))) + { + rtx rtx_region; + + if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG + || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) + rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); + else + rtx_region = GEN_INT (0); + + loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, + rtx_region, + loop_notes); + loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, + GEN_INT (NOTE_LINE_NUMBER (insn)), + loop_notes); + CONST_CALL_P (loop_notes) = CONST_CALL_P (insn); + } + + if (insn == tail) + return; + } + abort (); +} + +/* Examine insns in the range [ HEAD, TAIL ] and Use the backward + dependences from LOG_LINKS to build forward dependences in + INSN_DEPEND. */ + +void +compute_forward_dependences (head, tail) + rtx head, tail; +{ + rtx insn, link; + rtx next_tail; + enum reg_note dep_type; + + next_tail = NEXT_INSN (tail); + for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + { + if (! INSN_P (insn)) + continue; + + insn = group_leader (insn); + + for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) + { + rtx x = group_leader (XEXP (link, 0)); + rtx new_link; + + if (x != XEXP (link, 0)) + continue; + +#ifdef ENABLE_CHECKING + /* If add_dependence is working properly there should never + be notes, deleted insns or duplicates in the backward + links. Thus we need not check for them here. + + However, if we have enabled checking we might as well go + ahead and verify that add_dependence worked properly. */ + if (GET_CODE (x) == NOTE + || INSN_DELETED_P (x) + || (forward_dependency_cache != NULL + && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], + INSN_LUID (insn))) + || (forward_dependency_cache == NULL + && find_insn_list (insn, INSN_DEPEND (x)))) + abort (); + if (forward_dependency_cache != NULL) + SET_BIT (forward_dependency_cache[INSN_LUID (x)], + INSN_LUID (insn)); +#endif + + new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); + + dep_type = REG_NOTE_KIND (link); + PUT_REG_NOTE_KIND (new_link, dep_type); + + INSN_DEPEND (x) = new_link; + INSN_DEP_COUNT (insn) += 1; + } + } +} + +/* Initialize variables for region data dependence analysis. + n_bbs is the number of region blocks. */ + +void +init_deps (deps) + struct deps *deps; +{ + int maxreg = max_reg_num (); + deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx)); + deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx)); + deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx)); + + deps->pending_read_insns = 0; + deps->pending_read_mems = 0; + deps->pending_write_insns = 0; + deps->pending_write_mems = 0; + deps->pending_lists_length = 0; + deps->last_pending_memory_flush = 0; + deps->last_function_call = 0; + deps->in_post_call_group_p = 0; + + deps->sched_before_next_call + = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX, + NULL_RTX, 0, NULL_RTX, NULL_RTX); + LOG_LINKS (deps->sched_before_next_call) = 0; +} + +/* Free insn lists found in DEPS. */ + +void +free_deps (deps) + struct deps *deps; +{ + int max_reg = max_reg_num (); + int i; + + /* Note this loop is executed max_reg * nr_regions times. It's first + implementation accounted for over 90% of the calls to free_INSN_LIST_list. + The list was empty for the vast majority of those calls. On the PA, not + calling free_INSN_LIST_list in those cases improves -O2 compile times by + 3-5% on average. */ + for (i = 0; i < max_reg; ++i) + { + if (deps->reg_last_clobbers[i]) + free_INSN_LIST_list (&deps->reg_last_clobbers[i]); + if (deps->reg_last_sets[i]) + free_INSN_LIST_list (&deps->reg_last_sets[i]); + if (deps->reg_last_uses[i]) + free_INSN_LIST_list (&deps->reg_last_uses[i]); + } +} + +/* If it is profitable to use them, initialize caches for tracking + dependency informatino. LUID is the number of insns to be scheduled, + it is used in the estimate of profitability. */ + +void +init_dependency_caches (luid) + int luid; +{ + /* ?!? We could save some memory by computing a per-region luid mapping + which could reduce both the number of vectors in the cache and the size + of each vector. Instead we just avoid the cache entirely unless the + average number of instructions in a basic block is very high. See + the comment before the declaration of true_dependency_cache for + what we consider "very high". */ + if (luid / n_basic_blocks > 100 * 5) + { + true_dependency_cache = sbitmap_vector_alloc (luid, luid); + sbitmap_vector_zero (true_dependency_cache, luid); + anti_dependency_cache = sbitmap_vector_alloc (luid, luid); + sbitmap_vector_zero (anti_dependency_cache, luid); + output_dependency_cache = sbitmap_vector_alloc (luid, luid); + sbitmap_vector_zero (output_dependency_cache, luid); +#ifdef ENABLE_CHECKING + forward_dependency_cache = sbitmap_vector_alloc (luid, luid); + sbitmap_vector_zero (forward_dependency_cache, luid); +#endif + } +} + +/* Free the caches allocated in init_dependency_caches. */ + +void +free_dependency_caches () +{ + if (true_dependency_cache) + { + free (true_dependency_cache); + true_dependency_cache = NULL; + free (anti_dependency_cache); + anti_dependency_cache = NULL; + free (output_dependency_cache); + output_dependency_cache = NULL; +#ifdef ENABLE_CHECKING + free (forward_dependency_cache); + forward_dependency_cache = NULL; +#endif + } +} + +/* Initialize some global variables needed by the dependency analysis + code. */ + +void +init_deps_global () +{ + reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); + reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); + reg_pending_sets_all = 0; +} + +/* Free everything used by the dependency analysis code. */ + +void +finish_deps_global () +{ + FREE_REG_SET (reg_pending_sets); + FREE_REG_SET (reg_pending_clobbers); +} diff --git a/gcc/sched-int.h b/gcc/sched-int.h index bf14faa4ca2..faa4a8b788a 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -23,6 +23,70 @@ the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA /* Forward declaration. */ struct ready_list; +/* Describe state of dependencies used during sched_analyze phase. */ +struct deps +{ + /* The *_insns and *_mems are paired lists. Each pending memory operation + will have a pointer to the MEM rtx on one list and a pointer to the + containing insn on the other list in the same place in the list. */ + + /* We can't use add_dependence like the old code did, because a single insn + may have multiple memory accesses, and hence needs to be on the list + once for each memory access. Add_dependence won't let you add an insn + to a list more than once. */ + + /* An INSN_LIST containing all insns with pending read operations. */ + rtx pending_read_insns; + + /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ + rtx pending_read_mems; + + /* An INSN_LIST containing all insns with pending write operations. */ + rtx pending_write_insns; + + /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ + rtx pending_write_mems; + + /* Indicates the combined length of the two pending lists. We must prevent + these lists from ever growing too large since the number of dependencies + produced is at least O(N*N), and execution time is at least O(4*N*N), as + a function of the length of these pending lists. */ + int pending_lists_length; + + /* The last insn upon which all memory references must depend. + This is an insn which flushed the pending lists, creating a dependency + between it and all previously pending memory references. This creates + a barrier (or a checkpoint) which no memory reference is allowed to cross. + + This includes all non constant CALL_INSNs. When we do interprocedural + alias analysis, this restriction can be relaxed. + This may also be an INSN that writes memory if the pending lists grow + too large. */ + rtx last_pending_memory_flush; + + /* The last function call we have seen. All hard regs, and, of course, + the last function call, must depend on this. */ + rtx last_function_call; + + /* Used to keep post-call psuedo/hard reg movements together with + the call. */ + int in_post_call_group_p; + + /* The LOG_LINKS field of this is a list of insns which use a pseudo + register that does not already cross a call. We create + dependencies between each of those insn and the next call insn, + to ensure that they won't cross a call after scheduling is done. */ + rtx sched_before_next_call; + + /* Element N is the next insn that sets (hard or pseudo) register + N within the current basic block; or zero, if there is no + such insn. Needed for new registers which may be introduced + by splitting insns. */ + rtx *reg_last_uses; + rtx *reg_last_sets; + rtx *reg_last_clobbers; +}; + /* This structure holds some state of the current scheduling pass, and contains some function pointers that abstract out some of the non-generic functionality from functions such as schedule_block or schedule_insn. @@ -63,6 +127,71 @@ struct sched_info int queue_must_finish_empty; }; +extern struct sched_info *current_sched_info; + +/* Indexed by INSN_UID, the collection of all data associated with + a single instruction. */ + +struct haifa_insn_data +{ + /* A list of insns which depend on the instruction. Unlike LOG_LINKS, + it represents forward dependancies. */ + rtx depend; + + /* The line number note in effect for each insn. For line number + notes, this indicates whether the note may be reused. */ + rtx line_note; + + /* Logical uid gives the original ordering of the insns. */ + int luid; + + /* A priority for each insn. */ + int priority; + + /* The number of incoming edges in the forward dependency graph. + As scheduling proceds, counts are decreased. An insn moves to + the ready queue when its counter reaches zero. */ + int dep_count; + + /* An encoding of the blockage range function. Both unit and range + are coded. */ + unsigned int blockage; + + /* Number of instructions referring to this insn. */ + int ref_count; + + /* The minimum clock tick at which the insn becomes ready. This is + used to note timing constraints for the insns in the pending list. */ + int tick; + + short cost; + + /* An encoding of the function units used. */ + short units; + + /* This weight is an estimation of the insn's contribution to + register pressure. */ + short reg_weight; + + /* Some insns (e.g. call) are not allowed to move across blocks. */ + unsigned int cant_move : 1; + + /* Set if there's DEF-USE dependance between some speculatively + moved load insn and this one. */ + unsigned int fed_by_spec_load : 1; + unsigned int is_load_insn : 1; +}; + +extern struct haifa_insn_data *h_i_d; + +/* Accessor macros for h_i_d. There are more in haifa-sched.c. */ +#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) +#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) +#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) +#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) + +extern FILE *sched_dump; + #ifndef __GNUC__ #define __inline #endif @@ -70,3 +199,35 @@ struct sched_info #ifndef HAIFA_INLINE #define HAIFA_INLINE __inline #endif + +/* Functions in sched-vis.c. */ +extern void init_target_units PARAMS ((void)); +extern void insn_print_units PARAMS ((rtx)); +extern void init_block_visualization PARAMS ((void)); +extern void print_block_visualization PARAMS ((const char *)); +extern void visualize_scheduled_insns PARAMS ((int)); +extern void visualize_no_unit PARAMS ((rtx)); +extern void visualize_stall_cycles PARAMS ((int)); +extern void visualize_alloc PARAMS ((void)); +extern void visualize_free PARAMS ((void)); + +/* Functions in sched-deps.c. */ +extern void add_dependence PARAMS ((rtx, rtx, enum reg_note)); +extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, + rtx)); +extern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); +extern void init_deps PARAMS ((struct deps *)); +extern void free_deps PARAMS ((struct deps *)); +extern void init_deps_global PARAMS ((void)); +extern void finish_deps_global PARAMS ((void)); +extern void compute_forward_dependences PARAMS ((rtx, rtx)); +extern int find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx)); +extern rtx find_insn_list PARAMS ((rtx, rtx)); +extern void init_dependency_caches PARAMS ((int)); +extern void free_dependency_caches PARAMS ((void)); + +/* Functions in haifa-sched.c. */ +extern int insn_unit PARAMS ((rtx)); +extern rtx get_unit_last_insn PARAMS ((int)); +extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); + |
