From patchwork Mon Aug 30 14:54:52 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Schmidt X-Patchwork-Id: 63047 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 5030FB70F2 for ; Tue, 31 Aug 2010 00:55:20 +1000 (EST) Received: (qmail 15051 invoked by alias); 30 Aug 2010 14:55:19 -0000 Received: (qmail 15040 invoked by uid 22791); 30 Aug 2010 14:55:17 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, TW_CP, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 30 Aug 2010 14:55:09 +0000 Received: (qmail 9657 invoked from network); 30 Aug 2010 14:55:07 -0000 Received: from unknown (HELO ?84.152.177.148?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 30 Aug 2010 14:55:07 -0000 Message-ID: <4C7BC63C.8070506@codesourcery.com> Date: Mon, 30 Aug 2010 16:54:52 +0200 From: Bernd Schmidt User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.7) Gecko/20100724 Thunderbird/3.1.1 MIME-Version: 1.0 To: GCC Patches Subject: Scheduler patch: Remove insns that can't be issued from the ready list Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org I'm working on a new port which requires accurate scheduling for correctness. This patch, and another which I'll submit afterwards, is necessary to make it work. The problem here is that the ready list can contain insns that can't be issued in the current cycle. When we pick an insn, we try state_transition, and if that fails, we queue the insn for a later cycle and try to pick a different insn. This interacts badly with my code in target_sched_reorder, where I also need to detect certain cases in which an insn can't be issued. Assume the ready list contains two insns, and the target specific code detects that one of these can't be issued. It will be moved to the end of the ready list by target_sched_reorder, which then returns 1 to indicate that only the first insn on the ready list should be issued. However, if schedule_block then finds that this insn can't be issued at the moment due to a resource conflict, it will pick the second insn and issue it. This patch changes schedule_block to earlier get rid of insns which cannot be issued in the current cycle, before target_sched_reorder is called. Bootstrapped and regression tested on i686-linux. It appears to cause no changes to generated code. Ok? Bernd * haifa-sched.c (delay_ready_insns_with_resource_conflict): New function. (schedule_block): Use it whenever we add insns to the ready list. Remove code that was moved into the new function. Index: haifa-sched.c =================================================================== --- haifa-sched.c (revision 163516) +++ haifa-sched.c (working copy) @@ -2761,6 +2762,59 @@ choose_ready (struct ready_list *ready, } } +/* Examine all insns on the ready list and queue those which can't be + 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. 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 int +delay_ready_insns_with_resource_conflict (state_t temp_state, + bool first_cycle_insn_p) +{ + int min_cost = INT_MAX; + int i; + + restart: + for (i = 0; i < ready.n_ready; i++) + { + rtx insn = ready_element (&ready, i); + int cost = 0; + + if (recog_memoized (insn) < 0) + { + if (!first_cycle_insn_p + && (GET_CODE (PATTERN (insn)) == ASM_INPUT + || asm_noperands (PATTERN (insn)) >= 0)) + cost = 1; + } + else if (sched_pressure_p) + cost = 0; + else + { + 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 >= 1) + { + if (cost < min_cost) + min_cost = cost; + ready_remove (&ready, i); + queue_insn (insn, cost); + goto restart; + } + } + if (ready.n_ready == 0) + return min_cost; + return 0; +} + /* Use forward list scheduling to rearrange insns of block pointed to by TARGET_BB, possibly bringing insns from subsequent blocks in the same region. */ @@ -2768,7 +2822,7 @@ choose_ready (struct ready_list *ready, void schedule_block (basic_block *target_bb) { - int i, first_cycle_insn_p; + int i; int can_issue_more; state_t temp_state = NULL; /* It is used for multipass scheduling. */ int sort_p, advance, start_clock_var; @@ -2907,6 +2961,10 @@ schedule_block (basic_block *target_bb) debug_ready_list (&ready); } advance -= clock_var - start_clock_var; + + if (advance <= 0) + advance = delay_ready_insns_with_resource_conflict (temp_state, + true); } while (advance > 0); @@ -2974,7 +3032,6 @@ schedule_block (basic_block *target_bb) else can_issue_more = issue_rate; - first_cycle_insn_p = 1; cycle_issued_insns = 0; for (;;) { @@ -3059,44 +3116,6 @@ schedule_block (basic_block *target_bb) } sort_p = TRUE; - memcpy (temp_state, curr_state, dfa_state_size); - if (recog_memoized (insn) < 0) - { - asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT - || asm_noperands (PATTERN (insn)) >= 0); - if (!first_cycle_insn_p && asm_p) - /* This is asm insn which is tried to be issued on the - cycle not first. Issue it on the next cycle. */ - cost = 1; - else - /* A USE insn, or something else we don't need to - understand. We can't pass these directly to - state_transition because it will trigger a - fatal error for unrecognizable insns. */ - cost = 0; - } - else if (sched_pressure_p) - cost = 0; - else - { - cost = state_transition (temp_state, insn); - if (cost < 0) - cost = 0; - else if (cost == 0) - cost = 1; - } - - if (cost >= 1) - { - queue_insn (insn, cost); - if (SCHED_GROUP_P (insn)) - { - advance = cost; - break; - } - - continue; - } if (current_sched_info->can_schedule_ready_p && ! (*current_sched_info->can_schedule_ready_p) (insn)) @@ -3143,11 +3162,18 @@ schedule_block (basic_block *target_bb) reemit_notes (insn); last_scheduled_insn = insn; - if (memcmp (curr_state, temp_state, dfa_state_size) != 0) - { - cycle_issued_insns++; - memcpy (curr_state, temp_state, dfa_state_size); + if (recog_memoized (insn) >= 0) + { + if (!sched_pressure_p) + { + cost = state_transition (curr_state, insn); + gcc_assert (cost < 0); + cycle_issued_insns++; + } } + else + asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT + || asm_noperands (PATTERN (insn)) >= 0); if (targetm.sched.variable_issue) can_issue_more = @@ -3163,11 +3189,12 @@ schedule_block (basic_block *target_bb) /* After issuing an asm insn we should start a new cycle. */ if (advance == 0 && asm_p) advance = 1; + else if (advance == 0 && ready.n_ready > 0) + advance = delay_ready_insns_with_resource_conflict (temp_state, false); + if (advance != 0) break; - first_cycle_insn_p = 0; - /* Sort the ready list based on priority. This must be redone here, as schedule_insn may have readied additional insns that will not be sorted correctly. */