diff options
| -rw-r--r-- | gcc/ChangeLog | 53 | ||||
| -rw-r--r-- | gcc/Makefile.in | 3 | ||||
| -rw-r--r-- | gcc/haifa-sched.c | 789 | ||||
| -rw-r--r-- | gcc/modulo-sched.c | 1 | ||||
| -rw-r--r-- | gcc/sched-deps.c | 22 | ||||
| -rw-r--r-- | gcc/sched-ebb.c | 167 | ||||
| -rw-r--r-- | gcc/sched-int.h | 31 | ||||
| -rw-r--r-- | gcc/sched-rgn.c | 1 | ||||
| -rw-r--r-- | gcc/sel-sched-ir.c | 4 |
9 files changed, 983 insertions, 88 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 157ad42..0f5c3ae3 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,56 @@ +2011-07-14 Bernd Schmidt <bernds@codesourcery.com> + + * haifa-sched.c: Include "hashtab.h" + (sched_no_dce): New global variable. + (INSN_EXACT_TICK, INSN_TICK_ESTIMATE, FEEDS_BACKTRACK_INSN, + SHADOW_P): New macros. + (last_clock_var, cycle_issued_insns): Move declarations. + (must_backtrack): New static variable. + (struct delay_pair): New structure. + (delay_htab, delay_htab_i2): New static variables. + (delay_hash_i1, delay_hash_i2, delay_i1_eq, delay_i2_eq, + record_delay_slot_pair, pair_delay, add_delay_dependencies): New + functions. + (dep_cost_1): If delay pairs exist, try to look up the insns and + use the correct pair delay if we find them. + (rank-for_schedule): Tweak priority for insns that must be scheduled + soon to avoid backtracking. + (queue_insn): Detect conditions which force backtracking. + (ready_add): Likewise. + (struct sched_block_state): Add member shadows_only_p. + (struct haifa_save_data): New structure. + (backtrack_queue): New static variable. + (mark_backtrack_feeds, copy_insn_list, save_backtrack_point, + unschedule_insns_until, restore_last_backtrack_point, + free_topmost_backtrack_point, free_backtrack_queue, + estimate_insn_tick, estimate_shadow_tick): New functions. + (prune_ready_list): New arg shadows_only_p. All callers changed. + If true, remove everything that isn't SHADOW_P. Look up delay + pairs and estimate ticks to avoid scheduling the first insn too + early. + (verify_shadows): New function. + (schedule_block): Add machinery to enable backtracking. + (sched_init): Take sched_no_dce into account when setting + DF_LR_RUN_DCE. + (free_delay_pairs): New function. + (init_h_i_d): Initialize INSN_EXACT_TICK. + * Makefile.in (haifa-sched.o): Add $(HASHTAB_H). + * sched-deps.c (sd_unresolve_dep): New function. + * sched-int. (struct haifa_sched_info): New fields save_state + and restore_state. + (struct _haifa_insn_data): New fields exact_tick, tick_estimate, + feeds_backtrack_insn and shadow_p. + (DO_BACKTRACKING): New value in enum SCHED_FLAGS. + (sched_no_dce): Declare variable. + (record_delay_slot_pair, free_delay_pairs, add_delay_dependencies, + sd_unresolve_dep): Declare functions. + * modulo-sched.c (sms_sched_info): Clear the two new fields. + * sched-rgn.c (rgn_const_sched_info): Likewise. + * sel-sched-ir.c (sched_sel_haifa_sched_info): Likewise. + * sched-ebb.c (save_ebb_state, restore_ebb_state): New functions. + (ebb_sched_info): Add them for the two new fields. + (add_deps_for_risky_insns): Call add_delay_dependencies. + 2011-07-13 Michael Meissner <meissner@linux.vnet.ibm.com> * config/rs6000/rs6000.opt (-mpointers-to-nested-functions): diff --git a/gcc/Makefile.in b/gcc/Makefile.in index cd4f782..0fded4e 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -3397,7 +3397,8 @@ modulo-sched.o : modulo-sched.c $(DDG_H) $(CONFIG_H) $(CONFIG_H) $(SYSTEM_H) \ haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(FUNCTION_H) \ $(INSN_ATTR_H) $(DIAGNOSTIC_CORE_H) $(RECOG_H) $(EXCEPT_H) $(TM_P_H) $(TARGET_H) output.h \ - $(PARAMS_H) $(DBGCNT_H) $(CFGLOOP_H) ira.h $(EMIT_RTL_H) $(COMMON_TARGET_H) + $(PARAMS_H) $(DBGCNT_H) $(CFGLOOP_H) ira.h $(EMIT_RTL_H) $(COMMON_TARGET_H) \ + $(HASHTAB_H) sched-deps.o : sched-deps.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(RTL_H) $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \ $(FUNCTION_H) $(INSN_ATTR_H) $(DIAGNOSTIC_CORE_H) $(RECOG_H) $(EXCEPT_H) cselib.h \ diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 5eba79e..3630924 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "ira.h" #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ +#include "hashtab.h" #ifdef INSN_SCHEDULING @@ -158,6 +159,10 @@ along with GCC; see the file COPYING3. If not see int issue_rate; +/* This can be set to true by a backend if the scheduler should not + enable a DCE pass. */ +bool sched_no_dce; + /* sched-verbose controls the amount of debugging output the scheduler prints. It is controlled by -fsched-verbose=N: N>0 and no -DSR : the output is directed to stderr. @@ -178,7 +183,11 @@ FILE *sched_dump = 0; struct common_sched_info_def *common_sched_info; #define INSN_TICK(INSN) (HID (INSN)->tick) +#define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick) +#define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate) #define INTER_TICK(INSN) (HID (INSN)->inter_tick) +#define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn) +#define SHADOW_P(INSN) (HID (INSN)->shadow_p) /* If INSN_TICK of an instruction is equal to INVALID_TICK, then it should be recalculated from scratch. */ @@ -303,6 +312,18 @@ static struct ready_list *readyp = &ready; /* Scheduling clock. */ static int clock_var; +/* Clock at which the previous instruction was issued. */ +static int last_clock_var; + +/* Set to true if, when queuing a shadow insn, we discover that it would be + scheduled too late. */ +static bool must_backtrack; + +/* The following variable value is number of essential insns issued on + the current cycle. An insn is essential one if it changes the + processors state. */ +int cycle_issued_insns; + /* This records the actual schedule. It is built up during the main phase of schedule_block, and afterwards used to reorder the insns in the RTL. */ static VEC(rtx, heap) *scheduled_insns; @@ -487,6 +508,147 @@ haifa_classify_insn (const_rtx insn) return haifa_classify_rtx (PATTERN (insn)); } +/* A structure to record a pair of insns where the first one is a real + insn that has delay slots, and the second is its delayed shadow. + I1 is scheduled normally and will emit an assembly instruction, + while I2 describes the side effect that takes place at the + transition between cycles CYCLES and (CYCLES + 1) after I1. */ +struct delay_pair +{ + struct delay_pair *next_same_i1; + rtx i1, i2; + int cycles; +}; + +/* Two hash tables to record delay_pairs, one indexed by I1 and the other + indexed by I2. */ +static htab_t delay_htab; +static htab_t delay_htab_i2; + +/* Returns a hash value for X (which really is a delay_pair), based on + hashing just I1. */ +static hashval_t +delay_hash_i1 (const void *x) +{ + return htab_hash_pointer (((const struct delay_pair *) x)->i1); +} + +/* Returns a hash value for X (which really is a delay_pair), based on + hashing just I2. */ +static hashval_t +delay_hash_i2 (const void *x) +{ + return htab_hash_pointer (((const struct delay_pair *) x)->i2); +} + +/* Return nonzero if I1 of pair X is the same as that of pair Y. */ +static int +delay_i1_eq (const void *x, const void *y) +{ + return ((const struct delay_pair *) x)->i1 == y; +} + +/* Return nonzero if I2 of pair X is the same as that of pair Y. */ +static int +delay_i2_eq (const void *x, const void *y) +{ + return ((const struct delay_pair *) x)->i2 == y; +} + +/* This function can be called by a port just before it starts the + final scheduling pass. It records the fact that an instruction + with delay slots has been split into two insns, I1 and I2. The + first one will be scheduled normally and initiates the operation. + The second one is a shadow which must follow a specific number of + CYCLES after I1; its only purpose is to show the side effect that + occurs at that cycle in the RTL. If a JUMP_INSN or a CALL_INSN has + been split, I1 should be a normal INSN, while I2 retains the + original insn type. */ + +void +record_delay_slot_pair (rtx i1, rtx i2, int cycles) +{ + struct delay_pair *p = XNEW (struct delay_pair); + struct delay_pair **slot; + + p->i1 = i1; + p->i2 = i2; + p->cycles = cycles; + + if (!delay_htab) + { + delay_htab = htab_create (10, delay_hash_i1, delay_i1_eq, NULL); + delay_htab_i2 = htab_create (10, delay_hash_i2, delay_i2_eq, free); + } + slot = ((struct delay_pair **) + htab_find_slot_with_hash (delay_htab, i1, htab_hash_pointer (i1), + INSERT)); + p->next_same_i1 = *slot; + *slot = p; + slot = ((struct delay_pair **) + htab_find_slot_with_hash (delay_htab_i2, i2, htab_hash_pointer (i2), + INSERT)); + *slot = p; +} + +/* For a pair P of insns, return the fixed distance in cycles from the first + insn after which the second must be scheduled. */ +static int +pair_delay (struct delay_pair *p) +{ + return p->cycles; +} + +/* Given an insn INSN, add a dependence on its delayed shadow if it + has one. Also try to find situations where shadows depend on each other + and add dependencies to the real insns to limit the amount of backtracking + needed. */ +void +add_delay_dependencies (rtx insn) +{ + struct delay_pair *pair; + sd_iterator_def sd_it; + dep_t dep; + + if (!delay_htab) + return; + + pair + = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn, + htab_hash_pointer (insn)); + if (!pair) + return; + add_dependence (insn, pair->i1, REG_DEP_ANTI); + + FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep) + { + rtx pro = DEP_PRO (dep); + struct delay_pair *other_pair + = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, pro, + htab_hash_pointer (pro)); + if (!other_pair) + continue; + if (pair_delay (other_pair) >= pair_delay (pair)) + { + if (sched_verbose >= 4) + { + fprintf (sched_dump, ";;\tadding dependence %d <- %d\n", + INSN_UID (other_pair->i1), + INSN_UID (pair->i1)); + fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n", + INSN_UID (pair->i1), + INSN_UID (pair->i2), + pair_delay (pair)); + fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n", + INSN_UID (other_pair->i1), + INSN_UID (other_pair->i2), + pair_delay (other_pair)); + } + add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI); + } + } +} + /* Forward declarations. */ static int priority (rtx); @@ -857,6 +1019,22 @@ dep_cost_1 (dep_t link, dw_t dw) if (DEP_COST (link) != UNKNOWN_DEP_COST) return DEP_COST (link); + if (delay_htab) + { + struct delay_pair *delay_entry; + delay_entry + = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, used, + htab_hash_pointer (used)); + if (delay_entry) + { + if (delay_entry->i1 == insn) + { + DEP_COST (link) = pair_delay (delay_entry); + return DEP_COST (link); + } + } + } + /* A USE insn should never require the value used to be computed. This allows the computation of a function's result and parameter values to overlap the return and call. We don't care about the @@ -1213,6 +1391,17 @@ rank_for_schedule (const void *x, const void *y) else return INSN_TICK (tmp) - INSN_TICK (tmp2); } + + /* If we are doing backtracking in this schedule, prefer insns that + have forward dependencies with negative cost against an insn that + was already scheduled. */ + if (current_sched_info->flags & DO_BACKTRACKING) + { + priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp); + if (priority_val) + return priority_val; + } + /* Prefer insn with higher priority. */ priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp); @@ -1325,6 +1514,7 @@ queue_insn (rtx insn, int n_cycles, const char *reason) { int next_q = NEXT_Q_AFTER (q_ptr, n_cycles); rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]); + int new_tick; gcc_assert (n_cycles <= max_insn_queue_index); gcc_assert (!DEBUG_INSN_P (insn)); @@ -1341,6 +1531,21 @@ queue_insn (rtx insn, int n_cycles, const char *reason) } QUEUE_INDEX (insn) = next_q; + + if (current_sched_info->flags & DO_BACKTRACKING) + { + new_tick = clock_var + n_cycles; + if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick) + INSN_TICK (insn) = new_tick; + + if (INSN_EXACT_TICK (insn) != INVALID_TICK + && INSN_EXACT_TICK (insn) < clock_var + n_cycles) + { + must_backtrack = true; + if (sched_verbose >= 2) + fprintf (sched_dump, ";;\t\tcausing a backtrack.\n"); + } + } } /* Remove INSN from queue. */ @@ -1400,6 +1605,12 @@ ready_add (struct ready_list *ready, rtx insn, bool first_p) gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY); QUEUE_INDEX (insn) = QUEUE_READY; + + if (INSN_EXACT_TICK (insn) != INVALID_TICK + && INSN_EXACT_TICK (insn) < clock_var) + { + must_backtrack = true; + } } /* Remove the element with the highest priority from the ready list and @@ -1546,9 +1757,6 @@ advance_one_cycle (void) fprintf (sched_dump, ";;\tAdvanced a state.\n"); } -/* Clock at which the previous instruction was issued. */ -static int last_clock_var; - /* Update register pressure after scheduling INSN. */ static void update_register_pressure (rtx insn) @@ -1644,6 +1852,9 @@ struct sched_block_state { /* True if no real insns have been scheduled in the current cycle. */ bool first_cycle_insn_p; + /* True if a shadow insn has been scheduled in the current cycle, which + means that no more normal insns can be issued. */ + bool shadows_only_p; /* Initialized with the machine's issue rate every cycle, and updated by calls to the variable_issue hook. */ int can_issue_more; @@ -1900,6 +2111,377 @@ remove_notes (rtx head, rtx tail) } } +/* A structure to record enough data to allow us to backtrack the scheduler to + a previous state. */ +struct haifa_saved_data +{ + /* Next entry on the list. */ + struct haifa_saved_data *next; + + /* Backtracking is associated with scheduling insns that have delay slots. + DELAY_PAIR points to the structure that contains the insns involved, and + the number of cycles between them. */ + struct delay_pair *delay_pair; + + /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */ + void *fe_saved_data; + /* Data used by the backend. */ + void *be_saved_data; + + /* Copies of global state. */ + int clock_var, last_clock_var; + struct ready_list ready; + state_t curr_state; + + rtx last_scheduled_insn; + rtx last_nondebug_scheduled_insn; + int cycle_issued_insns; + + /* Copies of state used in the inner loop of schedule_block. */ + struct sched_block_state sched_block; + + /* We don't need to save q_ptr, as its value is arbitrary and we can set it + to 0 when restoring. */ + int q_size; + rtx *insn_queue; +}; + +/* A record, in reverse order, of all scheduled insns which have delay slots + and may require backtracking. */ +static struct haifa_saved_data *backtrack_queue; + +/* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according + to SET_P. */ +static void +mark_backtrack_feeds (rtx insn, int set_p) +{ + sd_iterator_def sd_it; + dep_t dep; + FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep) + { + FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p; + } +} + +/* Make a copy of the INSN_LIST list LINK and return it. */ +static rtx +copy_insn_list (rtx link) +{ + rtx new_queue; + rtx *pqueue = &new_queue; + + for (; link; link = XEXP (link, 1)) + { + rtx x = XEXP (link, 0); + rtx newlink = alloc_INSN_LIST (x, NULL); + *pqueue = newlink; + pqueue = &XEXP (newlink, 1); + } + *pqueue = NULL_RTX; + return new_queue; +} + +/* Save the current scheduler state so that we can backtrack to it + later if necessary. PAIR gives the insns that make it necessary to + save this point. SCHED_BLOCK is the local state of schedule_block + that need to be saved. */ +static void +save_backtrack_point (struct delay_pair *pair, + struct sched_block_state sched_block) +{ + int i; + struct haifa_saved_data *save = XNEW (struct haifa_saved_data); + + save->curr_state = xmalloc (dfa_state_size); + memcpy (save->curr_state, curr_state, dfa_state_size); + + save->ready.first = ready.first; + save->ready.n_ready = ready.n_ready; + save->ready.n_debug = ready.n_debug; + save->ready.veclen = ready.veclen; + save->ready.vec = XNEWVEC (rtx, ready.veclen); + memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx)); + + save->insn_queue = XNEWVEC (rtx, max_insn_queue_index + 1); + save->q_size = q_size; + for (i = 0; i <= max_insn_queue_index; i++) + { + int q = NEXT_Q_AFTER (q_ptr, i); + save->insn_queue[i] = copy_insn_list (insn_queue[q]); + } + + save->clock_var = clock_var; + save->last_clock_var = last_clock_var; + save->cycle_issued_insns = cycle_issued_insns; + save->last_scheduled_insn = last_scheduled_insn; + save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn; + + save->sched_block = sched_block; + + if (current_sched_info->save_state) + save->fe_saved_data = (*current_sched_info->save_state) (); + + if (targetm.sched.alloc_sched_context) + { + save->be_saved_data = targetm.sched.alloc_sched_context (); + targetm.sched.init_sched_context (save->be_saved_data, false); + } + else + save->be_saved_data = NULL; + + save->delay_pair = pair; + + save->next = backtrack_queue; + backtrack_queue = save; + + while (pair) + { + mark_backtrack_feeds (pair->i2, 1); + INSN_TICK (pair->i2) = INVALID_TICK; + INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair); + SHADOW_P (pair->i2) = true; + pair = pair->next_same_i1; + } +} + +/* Pop entries from the SCHEDULED_INSNS vector up to and including INSN. + Restore their dependencies to an unresolved state, and mark them as + queued nowhere. */ + +static void +unschedule_insns_until (rtx insn) +{ + for (;;) + { + rtx last; + sd_iterator_def sd_it; + dep_t dep; + + last = VEC_pop (rtx, scheduled_insns); + + /* This will be changed by restore_backtrack_point if the insn is in + any queue. */ + QUEUE_INDEX (last) = QUEUE_NOWHERE; + if (last != insn) + INSN_TICK (last) = INVALID_TICK; + + for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW); + sd_iterator_cond (&sd_it, &dep);) + { + rtx con = DEP_CON (dep); + TODO_SPEC (con) |= HARD_DEP; + INSN_TICK (con) = INVALID_TICK; + sd_unresolve_dep (sd_it); + } + + if (last == insn) + break; + } +} + +/* Restore scheduler state from the topmost entry on the backtracking queue. + PSCHED_BLOCK_P points to the local data of schedule_block that we must + overwrite with the saved data. + The caller must already have called unschedule_insns_until. */ + +static void +restore_last_backtrack_point (struct sched_block_state *psched_block) + +{ + rtx link; + int i; + struct haifa_saved_data *save = backtrack_queue; + + backtrack_queue = save->next; + + if (current_sched_info->restore_state) + (*current_sched_info->restore_state) (save->fe_saved_data); + + if (targetm.sched.alloc_sched_context) + { + targetm.sched.set_sched_context (save->be_saved_data); + targetm.sched.free_sched_context (save->be_saved_data); + } + + /* Clear the QUEUE_INDEX of everything in the ready list or one + of the queues. */ + if (ready.n_ready > 0) + { + rtx *first = ready_lastpos (&ready); + for (i = 0; i < ready.n_ready; i++) + { + QUEUE_INDEX (first[i]) = QUEUE_NOWHERE; + INSN_TICK (first[i]) = INVALID_TICK; + } + } + for (i = 0; i <= max_insn_queue_index; i++) + { + int q = NEXT_Q_AFTER (q_ptr, i); + + for (link = insn_queue[q]; link; link = XEXP (link, 1)) + { + rtx x = XEXP (link, 0); + QUEUE_INDEX (x) = QUEUE_NOWHERE; + INSN_TICK (x) = INVALID_TICK; + } + free_INSN_LIST_list (&insn_queue[q]); + } + + free (ready.vec); + ready = save->ready; + + if (ready.n_ready > 0) + { + rtx *first = ready_lastpos (&ready); + for (i = 0; i < ready.n_ready; i++) + { + QUEUE_INDEX (first[i]) = QUEUE_READY; + INSN_TICK (first[i]) = save->clock_var; + } + } + + q_ptr = 0; + q_size = save->q_size; + for (i = 0; i <= max_insn_queue_index; i++) + { + int q = NEXT_Q_AFTER (q_ptr, i); + + insn_queue[q] = save->insn_queue[q]; + + for (link = insn_queue[q]; link; link = XEXP (link, 1)) + { + rtx x = XEXP (link, 0); + QUEUE_INDEX (x) = i; + INSN_TICK (x) = save->clock_var + i; + } + } + free (save->insn_queue); + + clock_var = save->clock_var; + last_clock_var = save->last_clock_var; + cycle_issued_insns = save->cycle_issued_insns; + last_scheduled_insn = save->last_scheduled_insn; + last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn; + + *psched_block = save->sched_block; + + memcpy (curr_state, save->curr_state, dfa_state_size); + free (save->curr_state); + + mark_backtrack_feeds (save->delay_pair->i2, 0); + + free (save); + + for (save = backtrack_queue; save; save = save->next) + { + mark_backtrack_feeds (save->delay_pair->i2, 1); + } +} + +/* Discard all data associated with the topmost entry in the backtrack + queue. If RESET_TICK is false, we just want to free the data. If true, + we are doing this because we discovered a reason to backtrack. In the + latter case, also reset the INSN_TICK for the shadow insn. */ +static void +free_topmost_backtrack_point (bool reset_tick) +{ + struct haifa_saved_data *save = backtrack_queue; + int i; + + backtrack_queue = save->next; + + if (reset_tick) + { + struct delay_pair *pair = save->delay_pair; + while (pair) + { + INSN_TICK (pair->i2) = INVALID_TICK; + INSN_EXACT_TICK (pair->i2) = INVALID_TICK; + pair = pair->next_same_i1; + } + } + if (targetm.sched.free_sched_context) + targetm.sched.free_sched_context (save->be_saved_data); + if (current_sched_info->restore_state) + free (save->fe_saved_data); + for (i = 0; i <= max_insn_queue_index; i++) + free_INSN_LIST_list (&save->insn_queue[i]); + free (save->insn_queue); + free (save->curr_state); + free (save->ready.vec); + free (save); +} + +/* Free the entire backtrack queue. */ +static void +free_backtrack_queue (void) +{ + while (backtrack_queue) + free_topmost_backtrack_point (false); +} + +/* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of + instructions we've previously encountered, a set bit prevents + recursion. BUDGET is a limit on how far ahead we look, it is + reduced on recursive calls. Return true if we produced a good + estimate, or false if we exceeded the budget. */ +static bool +estimate_insn_tick (bitmap processed, rtx insn, int budget) +{ + sd_iterator_def sd_it; + dep_t dep; + int earliest = INSN_TICK (insn); + + FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) + { + rtx pro = DEP_PRO (dep); + int t; + + if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED) + gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn)); + else + { + int cost = dep_cost (dep); + if (cost >= budget) + return false; + if (!bitmap_bit_p (processed, INSN_LUID (pro))) + { + if (!estimate_insn_tick (processed, pro, budget - cost)) + return false; + } + gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK); + t = INSN_TICK_ESTIMATE (pro) + cost; + if (earliest == INVALID_TICK || t > earliest) + earliest = t; + } + } + bitmap_set_bit (processed, INSN_LUID (insn)); + INSN_TICK_ESTIMATE (insn) = earliest; + return true; +} + +/* Examine the pair of insns in P, and estimate (optimistically, assuming + infinite resources) the cycle in which the delayed shadow can be issued. + Return the number of cycles that must pass before the real insn can be + issued in order to meet this constraint. */ +static int +estimate_shadow_tick (struct delay_pair *p) +{ + bitmap_head processed; + int t; + bool cutoff; + bitmap_initialize (&processed, 0); + + cutoff = !estimate_insn_tick (&processed, p->i2, + max_insn_queue_index + pair_delay (p)); + bitmap_clear (&processed); + if (cutoff) + return max_insn_queue_index; + t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1); + if (t > 0) + return t; + return 0; +} /* Return the head and tail pointers of ebb starting at BEG and ending at END. */ @@ -2467,11 +3049,6 @@ struct choice_entry function max_issue. */ static struct choice_entry *choice_stack; -/* The following variable value is number of essential insns issued on - the current cycle. An insn is essential one if it changes the - processors state. */ -int cycle_issued_insns; - /* This holds the value of the target dfa_lookahead hook. */ int dfa_lookahead; @@ -2884,10 +3461,18 @@ commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb) issued in this cycle. TEMP_STATE is temporary scheduler state we can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns have been issued for the current cycle, which means it is valid to - issue an asm statement. */ + issue an asm statement. + + If SHADOWS_ONLY_P is true, we eliminate all real insns and only + leave those for which SHADOW_P is true. + + Return the number of cycles we must + advance to find the next ready instruction, or zero if there remain + insns on the ready list. */ static void -prune_ready_list (state_t temp_state, bool first_cycle_insn_p) +prune_ready_list (state_t temp_state, bool first_cycle_insn_p, + bool shadows_only_p) { int i; @@ -2898,7 +3483,12 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p) int cost = 0; const char *reason = "resource conflict"; - if (recog_memoized (insn) < 0) + if (shadows_only_p && !DEBUG_INSN_P (insn) && !SHADOW_P (insn)) + { + cost = 1; + reason = "not a shadow"; + } + else if (recog_memoized (insn) < 0) { if (!first_cycle_insn_p && (GET_CODE (PATTERN (insn)) == ASM_INPUT @@ -2910,12 +3500,34 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p) cost = 0; else { + int delay_cost = 0; + + if (delay_htab) + { + struct delay_pair *delay_entry; + delay_entry + = (struct delay_pair *)htab_find_with_hash (delay_htab, insn, + htab_hash_pointer (insn)); + while (delay_entry && delay_cost == 0) + { + delay_cost = estimate_shadow_tick (delay_entry); + if (delay_cost > max_insn_queue_index) + delay_cost = max_insn_queue_index; + delay_entry = delay_entry->next_same_i1; + } + } + memcpy (temp_state, curr_state, dfa_state_size); cost = state_transition (temp_state, insn); if (cost < 0) cost = 0; else if (cost == 0) cost = 1; + if (cost < delay_cost) + { + cost = delay_cost; + reason = "shadow tick"; + } } if (cost >= 1) { @@ -2926,6 +3538,60 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p) } } +/* Called when we detect that the schedule is impossible. We examine the + backtrack queue to find the earliest insn that caused this condition. */ + +static struct haifa_saved_data * +verify_shadows (void) +{ + struct haifa_saved_data *save, *earliest_fail = NULL; + for (save = backtrack_queue; save; save = save->next) + { + int t; + struct delay_pair *pair = save->delay_pair; + rtx i1 = pair->i1; + + for (; pair; pair = pair->next_same_i1) + { + rtx i2 = pair->i2; + + if (QUEUE_INDEX (i2) == QUEUE_SCHEDULED) + continue; + + t = INSN_TICK (i1) + pair_delay (pair); + if (t < clock_var) + { + if (sched_verbose >= 2) + fprintf (sched_dump, + ";;\t\tfailed delay requirements for %d/%d (%d->%d)" + ", not ready\n", + INSN_UID (pair->i1), INSN_UID (pair->i2), + INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2)); + earliest_fail = save; + break; + } + if (QUEUE_INDEX (i2) >= 0) + { + int queued_for = INSN_TICK (i2); + + if (t < queued_for) + { + if (sched_verbose >= 2) + fprintf (sched_dump, + ";;\t\tfailed delay requirements for %d/%d" + " (%d->%d), queued too late\n", + INSN_UID (pair->i1), INSN_UID (pair->i2), + INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2)); + earliest_fail = save; + break; + } + } + } + } + + return earliest_fail; +} + /* Use forward list scheduling to rearrange insns of block pointed to by TARGET_BB, possibly bringing insns from subsequent blocks in the same region. */ @@ -2955,6 +3621,8 @@ schedule_block (basic_block *target_bb) haifa_recovery_bb_recently_added_p = false; + backtrack_queue = NULL; + /* Debug info. */ if (sched_verbose) dump_new_block_header (0, *target_bb, head, tail); @@ -3051,6 +3719,8 @@ schedule_block (basic_block *target_bb) gcc_assert (VEC_length (rtx, scheduled_insns) == 0); sort_p = TRUE; + must_backtrack = false; + /* Loop until all the insns in BB are scheduled. */ while ((*current_sched_info->schedule_more_p) ()) { @@ -3080,18 +3750,21 @@ schedule_block (basic_block *target_bb) while (advance > 0); if (ready.n_ready > 0) - prune_ready_list (temp_state, true); + prune_ready_list (temp_state, true, false); if (ready.n_ready == 0) continue; + if (must_backtrack) + goto do_backtrack; ls.first_cycle_insn_p = true; + ls.shadows_only_p = false; cycle_issued_insns = 0; ls.can_issue_more = issue_rate; for (;;) { rtx insn; int cost; - bool asm_p = false; + bool asm_p; if (sort_p && ready.n_ready > 0) { @@ -3130,6 +3803,7 @@ schedule_block (basic_block *target_bb) if (ls.first_cycle_insn_p && !ready.n_ready) break; + resume_after_backtrack: /* Allow the target to reorder the list, typically for better instruction bundling. */ if (sort_p @@ -3236,6 +3910,22 @@ schedule_block (basic_block *target_bb) goto restart_choose_ready; } + if (delay_htab) + { + /* If this insn is the first part of a delay-slot pair, record a + backtrack point. */ + struct delay_pair *delay_entry; + delay_entry + = (struct delay_pair *)htab_find_with_hash (delay_htab, insn, + htab_hash_pointer (insn)); + if (delay_entry) + { + save_backtrack_point (delay_entry, ls); + if (sched_verbose >= 2) + fprintf (sched_dump, ";;\t\tsaving backtrack point\n"); + } + } + /* DECISION is made. */ if (TODO_SPEC (insn) & SPECULATIVE) @@ -3275,18 +3965,70 @@ schedule_block (basic_block *target_bb) ls.can_issue_more--; advance = schedule_insn (insn); + if (SHADOW_P (insn)) + ls.shadows_only_p = true; + /* After issuing an asm insn we should start a new cycle. */ if (advance == 0 && asm_p) advance = 1; + + if (must_backtrack) + break; + if (advance != 0) break; ls.first_cycle_insn_p = false; if (ready.n_ready > 0) - prune_ready_list (temp_state, false); + prune_ready_list (temp_state, false, ls.shadows_only_p); } - } + do_backtrack: + if (!must_backtrack) + for (i = 0; i < ready.n_ready; i++) + { + rtx insn = ready_element (&ready, i); + if (INSN_EXACT_TICK (insn) == clock_var) + { + must_backtrack = true; + clock_var++; + break; + } + } + while (must_backtrack) + { + struct haifa_saved_data *failed; + rtx failed_insn; + + must_backtrack = false; + failed = verify_shadows (); + gcc_assert (failed); + + failed_insn = failed->delay_pair->i1; + unschedule_insns_until (failed_insn); + while (failed != backtrack_queue) + free_topmost_backtrack_point (true); + restore_last_backtrack_point (&ls); + if (sched_verbose >= 2) + fprintf (sched_dump, ";;\t\trewind to cycle %d\n", clock_var); + /* Delay by at least a cycle. This could cause additional + backtracking. */ + queue_insn (failed_insn, 1, "backtracked"); + advance = 0; + if (must_backtrack) + continue; + if (ready.n_ready > 0) + goto resume_after_backtrack; + else + { + if (clock_var == 0 && ls.first_cycle_insn_p) + goto end_schedule; + advance = 1; + break; + } + } + } + end_schedule: /* Debug info. */ if (sched_verbose) { @@ -3364,6 +4106,8 @@ schedule_block (basic_block *target_bb) current_sched_info->head = head; current_sched_info->tail = tail; + + free_backtrack_queue (); } /* Set_priorities: compute priority of each insn in the block. */ @@ -3488,7 +4232,8 @@ sched_init (void) init_alias_analysis (); - df_set_flags (DF_LR_RUN_DCE); + if (!sched_no_dce) + df_set_flags (DF_LR_RUN_DCE); df_note_add_problem (); /* More problems needed for interloop dep calculation in SMS. */ @@ -3653,6 +4398,17 @@ sched_finish (void) #endif } +/* Free all delay_pair structures that were recorded. */ +void +free_delay_pairs (void) +{ + if (delay_htab) + { + htab_empty (delay_htab); + htab_empty (delay_htab_i2); + } +} + /* Fix INSN_TICKs of the instructions in the current block as well as INSN_TICKs of their dependents. HEAD and TAIL are the begin and the end of the current scheduled block. */ @@ -5453,6 +6209,7 @@ init_h_i_d (rtx insn) INSN_COST (insn) = -1; QUEUE_INDEX (insn) = QUEUE_NOWHERE; INSN_TICK (insn) = INVALID_TICK; + INSN_EXACT_TICK (insn) = INVALID_TICK; INTER_TICK (insn) = INVALID_TICK; TODO_SPEC (insn) = HARD_DEP; } diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c index e9749b2..85e24d4 100644 --- a/gcc/modulo-sched.c +++ b/gcc/modulo-sched.c @@ -283,6 +283,7 @@ static struct haifa_sched_info sms_sched_info = 0, 0, NULL, NULL, NULL, NULL, + NULL, NULL, 0 }; diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c index 4ceea72..0bba96c 100644 --- a/gcc/sched-deps.c +++ b/gcc/sched-deps.c @@ -1301,6 +1301,28 @@ sd_resolve_dep (sd_iterator_def sd_it) INSN_RESOLVED_FORW_DEPS (pro)); } +/* Perform the inverse operation of sd_resolve_dep. Restore the dependence + pointed to by SD_IT to unresolved state. */ +void +sd_unresolve_dep (sd_iterator_def sd_it) +{ + dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); + dep_t dep = DEP_NODE_DEP (node); + rtx pro = DEP_PRO (dep); + rtx con = DEP_CON (dep); + + if ((current_sched_info->flags & DO_SPECULATION) + && (DEP_STATUS (dep) & SPECULATIVE)) + move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con), + INSN_SPEC_BACK_DEPS (con)); + else + move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con), + INSN_HARD_BACK_DEPS (con)); + + move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro), + INSN_FORW_DEPS (pro)); +} + /* Make TO depend on all the FROM's producers. If RESOLVED_P is true add dependencies to the resolved lists. */ void diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c index 6bb223b..47ce342 100644 --- a/gcc/sched-ebb.c +++ b/gcc/sched-ebb.c @@ -74,6 +74,25 @@ static void ebb_add_block (basic_block, basic_block); static basic_block advance_target_bb (basic_block, rtx); static void ebb_fix_recovery_cfg (int, int, int); +/* Allocate memory and store the state of the frontend. Return the allocated + memory. */ +static void * +save_ebb_state (void) +{ + int *p = XNEW (int); + *p = sched_rgn_n_insns; + return p; +} + +/* Restore the state of the frontend from P_, then free it. */ +static void +restore_ebb_state (void *p_) +{ + int *p = (int *)p_; + sched_rgn_n_insns = *p; + free (p_); +} + /* Return nonzero if there are more insns that should be scheduled. */ static int @@ -295,6 +314,10 @@ static struct haifa_sched_info ebb_sched_info = begin_schedule_ready, begin_move_insn, advance_target_bb, + + save_ebb_state, + restore_ebb_state, + SCHED_EBB /* We can create new blocks in begin_schedule_ready (). */ | NEW_BBS @@ -377,76 +400,80 @@ add_deps_for_risky_insns (rtx head, rtx tail) basic_block last_block = NULL, bb; for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) - if (control_flow_insn_p (insn)) - { - bb = BLOCK_FOR_INSN (insn); - bb->aux = last_block; - last_block = bb; - last_jump = insn; - } - else if (INSN_P (insn) && last_jump != NULL_RTX) - { - classification = haifa_classify_insn (insn); - prev = last_jump; - switch (classification) - { - case PFREE_CANDIDATE: - if (flag_schedule_speculative_load) - { - bb = earliest_block_with_similiar_load (last_block, insn); - if (bb) - { - bb = (basic_block) bb->aux; - if (!bb) - break; - prev = BB_END (bb); - } - } - /* Fall through. */ - case TRAP_RISKY: - case IRISKY: - case PRISKY_CANDIDATE: - /* ??? We could implement better checking PRISKY_CANDIDATEs - analogous to sched-rgn.c. */ - /* We can not change the mode of the backward - dependency because REG_DEP_ANTI has the lowest - rank. */ - if (! sched_insns_conditions_mutex_p (insn, prev)) - { - dep_def _dep, *dep = &_dep; - - init_dep (dep, prev, insn, REG_DEP_ANTI); - - if (!(current_sched_info->flags & USE_DEPS_LIST)) - { - enum DEPS_ADJUST_RESULT res; - - res = sd_add_or_update_dep (dep, false); - - /* We can't change an existing dependency with - DEP_ANTI. */ - gcc_assert (res != DEP_CHANGED); - } - else - { - if ((current_sched_info->flags & DO_SPECULATION) - && (spec_info->mask & BEGIN_CONTROL)) - DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL, - MAX_DEP_WEAK); - - sd_add_or_update_dep (dep, false); - - /* Dep_status could have been changed. - No assertion here. */ - } - } - - break; - - default: - break; - } - } + { + add_delay_dependencies (insn); + if (control_flow_insn_p (insn)) + { + bb = BLOCK_FOR_INSN (insn); + bb->aux = last_block; + last_block = bb; + last_jump = insn; + } + else if (INSN_P (insn) && last_jump != NULL_RTX) + { + classification = haifa_classify_insn (insn); + prev = last_jump; + + switch (classification) + { + case PFREE_CANDIDATE: + if (flag_schedule_speculative_load) + { + bb = earliest_block_with_similiar_load (last_block, insn); + if (bb) + { + bb = (basic_block) bb->aux; + if (!bb) + break; + prev = BB_END (bb); + } + } + /* Fall through. */ + case TRAP_RISKY: + case IRISKY: + case PRISKY_CANDIDATE: + /* ??? We could implement better checking PRISKY_CANDIDATEs + analogous to sched-rgn.c. */ + /* We can not change the mode of the backward + dependency because REG_DEP_ANTI has the lowest + rank. */ + if (! sched_insns_conditions_mutex_p (insn, prev)) + { + dep_def _dep, *dep = &_dep; + + init_dep (dep, prev, insn, REG_DEP_ANTI); + + if (!(current_sched_info->flags & USE_DEPS_LIST)) + { + enum DEPS_ADJUST_RESULT res; + + res = sd_add_or_update_dep (dep, false); + + /* We can't change an existing dependency with + DEP_ANTI. */ + gcc_assert (res != DEP_CHANGED); + } + else + { + if ((current_sched_info->flags & DO_SPECULATION) + && (spec_info->mask & BEGIN_CONTROL)) + DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL, + MAX_DEP_WEAK); + + sd_add_or_update_dep (dep, false); + + /* Dep_status could have been changed. + No assertion here. */ + } + } + + break; + + default: + break; + } + } + } /* Maintain the invariant that bb->aux is clear after use. */ while (last_block) { diff --git a/gcc/sched-int.h b/gcc/sched-int.h index 8b39a22c..348a3cc 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -603,6 +603,13 @@ struct haifa_sched_info The first parameter is the current basic block in EBB. */ basic_block (*advance_target_bb) (basic_block, rtx); + /* Allocate memory, store the frontend scheduler state in it, and + return it. */ + void *(*save_state) (void); + /* Restore frontend scheduler state from the argument, and free the + memory. */ + void (*restore_state) (void *); + /* ??? FIXME: should use straight bitfields inside sched_info instead of this flag field. */ unsigned int flags; @@ -762,10 +769,18 @@ struct _haifa_insn_data used to note timing constraints for the insns in the pending list. */ int tick; + /* For insns that are scheduled at a fixed difference from another, + this records the tick in which they must be ready. */ + int exact_tick; + /* INTER_TICK is used to adjust INSN_TICKs of instructions from the subsequent blocks in a region. */ int inter_tick; + /* Used temporarily to estimate an INSN_TICK value for an insn given + current knowledge. */ + int tick_estimate; + /* See comment on QUEUE_INDEX macro in haifa-sched.c. */ int queue_index; @@ -775,6 +790,14 @@ struct _haifa_insn_data moved load insn and this one. */ unsigned int fed_by_spec_load : 1; unsigned int is_load_insn : 1; + /* Nonzero if this insn has negative-cost forward dependencies against + an already scheduled insn. */ + unsigned int feeds_backtrack_insn : 1; + + /* Nonzero if this insn is a shadow of another, scheduled after a fixed + delay. We only emit shadows at the end of a cycle, with no other + real insns following them. */ + unsigned int shadow_p : 1; /* '> 0' if priority is valid, '== 0' if priority was not yet computed, @@ -1017,7 +1040,8 @@ enum SCHED_FLAGS { Results in generation of data and control speculative dependencies. Requires USE_DEPS_LIST set. */ DO_SPECULATION = USE_DEPS_LIST << 1, - SCHED_RGN = DO_SPECULATION << 1, + DO_BACKTRACKING = DO_SPECULATION << 1, + SCHED_RGN = DO_BACKTRACKING << 1, SCHED_EBB = SCHED_RGN << 1, /* Scheduler can possibly create new basic blocks. Used for assertions. */ NEW_BBS = SCHED_EBB << 1, @@ -1304,7 +1328,11 @@ extern int *ebb_head; extern int current_nr_blocks; extern int current_blocks; extern int target_bb; +extern bool sched_no_dce; +extern void record_delay_slot_pair (rtx, rtx, int); +extern void free_delay_pairs (void); +extern void add_delay_dependencies (rtx); extern bool sched_is_disabled_for_current_region_p (void); extern void sched_rgn_init (bool); extern void sched_rgn_finish (void); @@ -1478,6 +1506,7 @@ extern dep_t sd_find_dep_between (rtx, rtx, bool); extern void sd_add_dep (dep_t, bool); extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool); extern void sd_resolve_dep (sd_iterator_def); +extern void sd_unresolve_dep (sd_iterator_def); extern void sd_copy_back_deps (rtx, rtx, bool); extern void sd_delete_dep (sd_iterator_def); extern void sd_debug_lists (rtx, sd_list_types_def); diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c index aa9c81d..b4d4c81 100644 --- a/gcc/sched-rgn.c +++ b/gcc/sched-rgn.c @@ -2371,6 +2371,7 @@ static const struct haifa_sched_info rgn_const_sched_info = begin_schedule_ready, NULL, advance_target_bb, + NULL, NULL, SCHED_RGN }; diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c index de7629a..ac48325 100644 --- a/gcc/sel-sched-ir.c +++ b/gcc/sel-sched-ir.c @@ -5700,6 +5700,10 @@ static struct haifa_sched_info sched_sel_haifa_sched_info = NULL, /* begin_schedule_ready */ NULL, /* begin_move_insn */ NULL, /* advance_target_bb */ + + NULL, + NULL, + SEL_SCHED | NEW_BBS }; |