From patchwork Tue Jun 14 06:27:32 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Revital Eres X-Patchwork-Id: 100284 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 6F670B6FAC for ; Tue, 14 Jun 2011 16:27:54 +1000 (EST) Received: (qmail 25662 invoked by alias); 14 Jun 2011 06:27:52 -0000 Received: (qmail 25654 invoked by uid 22791); 14 Jun 2011 06:27:51 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, TW_DD X-Spam-Check-By: sourceware.org Received: from mail-ew0-f47.google.com (HELO mail-ew0-f47.google.com) (209.85.215.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 14 Jun 2011 06:27:36 +0000 Received: by ewy5 with SMTP id 5so2107133ewy.20 for ; Mon, 13 Jun 2011 23:27:34 -0700 (PDT) MIME-Version: 1.0 Received: by 10.213.2.202 with SMTP id 10mr172527ebk.110.1308032852513; Mon, 13 Jun 2011 23:27:32 -0700 (PDT) Received: by 10.213.27.203 with HTTP; Mon, 13 Jun 2011 23:27:32 -0700 (PDT) In-Reply-To: References: Date: Tue, 14 Jun 2011 09:27:32 +0300 Message-ID: Subject: Re: [PATCH, SMS 1/4] Fix calculation of row_rest_count From: Revital Eres To: Ayal Zaks Cc: gcc-patches@gcc.gnu.org, Patch Tracking 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 Hello, > Please add the following: > o A clarification that rows_length is used only (as an optimization) to > back off quickly from trying to schedule a node in a full row; that is, to > avoid running through futile DFA state transitions. > o An assert that ps->rows_length[i] equals the number of nodes in ps->rows > [i] (e.g., in verify_partial_schedule(); and then recheck...). Done. Besides the additions to address your comments I also added two more bits to update rows_length field into rotate_partial_schedule () and ps_insert_empty_row () that were missing in the previous implementation of the patch. The patch was re-tested on top of the patch to fix violation of memory dependence (http://gcc.gnu.org/ml/gcc-patches/2011-06/msg00960.html) as follows: On ppc64-redhat-linux regtest as well as bootstrap with SMS flags, enabling SMS also on loops with stage count 1. Regtested on SPU. On arm-linux-gnueabi bootstrap c language with SMS flags enabling SMS also on loops with stage count 1 and currently regtseted on c,c++. OK for mainline with these changes once regtests on arm-linux-gnueabi completes? Thanks, Revital * modulo-sched.c (struct ps_insn): Remove row_rest_count field. (struct partial_schedule): Add rows_length field. (verify_partial_schedule): Check rows_length. (ps_insert_empty_row): Handle rows_length. (create_partial_schedule): Likewise. (free_partial_schedule): Likewise. (reset_partial_schedule): Likewise. (create_ps_insn): Remove rest_count argument. (remove_node_from_ps): Update rows_length. (add_node_to_ps): Update rows_length and call create_ps_insn without passing row_rest_count. (rotate_partial_schedule): Update rows_length. Index: modulo-sched.c =================================================================== --- modulo-sched.c (revision 173786) +++ modulo-sched.c (working copy) @@ -134,8 +134,6 @@ struct ps_insn ps_insn_ptr next_in_row, prev_in_row; - /* The number of nodes in the same row that come after this node. */ - int row_rest_count; }; /* Holds the partial schedule as an array of II rows. Each entry of the @@ -149,6 +147,12 @@ struct partial_schedule /* rows[i] points to linked list of insns scheduled in row i (0<=iii; int new_ii = ii + 1; int row; + int *rows_length_new; verify_partial_schedule (ps, sched_nodes); @@ -1922,9 +1927,11 @@ ps_insert_empty_row (partial_schedule_pt rotate_partial_schedule (ps, PS_MIN_CYCLE (ps)); rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr)); + rows_length_new = (int *) xcalloc (new_ii, sizeof (int)); for (row = 0; row < split_row; row++) { rows_new[row] = ps->rows[row]; + rows_length_new[row] = ps->rows_length[row]; ps->rows[row] = NULL; for (crr_insn = rows_new[row]; crr_insn; crr_insn = crr_insn->next_in_row) @@ -1945,6 +1952,7 @@ ps_insert_empty_row (partial_schedule_pt for (row = split_row; row < ii; row++) { rows_new[row + 1] = ps->rows[row]; + rows_length_new[row + 1] = ps->rows_length[row]; ps->rows[row] = NULL; for (crr_insn = rows_new[row + 1]; crr_insn; crr_insn = crr_insn->next_in_row) @@ -1966,6 +1974,8 @@ ps_insert_empty_row (partial_schedule_pt + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0); free (ps->rows); ps->rows = rows_new; + free (ps->rows_length); + ps->rows_length = rows_length_new; ps->ii = new_ii; gcc_assert (ps->min_cycle >= 0); @@ -2041,16 +2051,23 @@ verify_partial_schedule (partial_schedul ps_insn_ptr crr_insn; for (row = 0; row < ps->ii; row++) - for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row) - { - ddg_node_ptr u = crr_insn->node; - - gcc_assert (TEST_BIT (sched_nodes, u->cuid)); - /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by - popcount (sched_nodes) == number of insns in ps. */ - gcc_assert (SCHED_TIME (u) >= ps->min_cycle); - gcc_assert (SCHED_TIME (u) <= ps->max_cycle); - } + { + int length = 0; + + for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row) + { + ddg_node_ptr u = crr_insn->node; + + length++; + gcc_assert (TEST_BIT (sched_nodes, u->cuid)); + /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by + popcount (sched_nodes) == number of insns in ps. */ + gcc_assert (SCHED_TIME (u) >= ps->min_cycle); + gcc_assert (SCHED_TIME (u) <= ps->max_cycle); + } + + gcc_assert (ps->rows_length[row] == length); + } } @@ -2456,6 +2473,7 @@ create_partial_schedule (int ii, ddg_ptr { partial_schedule_ptr ps = XNEW (struct partial_schedule); ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr)); + ps->rows_length = (int *) xcalloc (ii, sizeof (int)); ps->ii = ii; ps->history = history; ps->min_cycle = INT_MAX; @@ -2494,6 +2512,7 @@ free_partial_schedule (partial_schedule_ return; free_ps_insns (ps); free (ps->rows); + free (ps->rows_length); free (ps); } @@ -2511,6 +2530,8 @@ reset_partial_schedule (partial_schedule ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii * sizeof (ps_insn_ptr)); memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr)); + ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int)); + memset (ps->rows_length, 0, new_ii * sizeof (int)); ps->ii = new_ii; ps->min_cycle = INT_MAX; ps->max_cycle = INT_MIN; @@ -2539,14 +2560,13 @@ print_partial_schedule (partial_schedule /* Creates an object of PS_INSN and initializes it to the given parameters. */ static ps_insn_ptr -create_ps_insn (ddg_node_ptr node, int rest_count, int cycle) +create_ps_insn (ddg_node_ptr node, int cycle) { ps_insn_ptr ps_i = XNEW (struct ps_insn); ps_i->node = node; ps_i->next_in_row = NULL; ps_i->prev_in_row = NULL; - ps_i->row_rest_count = rest_count; ps_i->cycle = cycle; return ps_i; @@ -2579,6 +2599,8 @@ remove_node_from_ps (partial_schedule_pt if (ps_i->next_in_row) ps_i->next_in_row->prev_in_row = ps_i->prev_in_row; } + + ps->rows_length[row] -= 1; free (ps_i); return true; } @@ -2735,17 +2757,12 @@ add_node_to_ps (partial_schedule_ptr ps, sbitmap must_precede, sbitmap must_follow) { ps_insn_ptr ps_i; - int rest_count = 1; int row = SMODULO (cycle, ps->ii); - if (ps->rows[row] - && ps->rows[row]->row_rest_count >= issue_rate) + if (ps->rows_length[row] >= issue_rate) return NULL; - if (ps->rows[row]) - rest_count += ps->rows[row]->row_rest_count; - - ps_i = create_ps_insn (node, rest_count, cycle); + ps_i = create_ps_insn (node, cycle); /* Finds and inserts PS_I according to MUST_FOLLOW and MUST_PRECEDE. */ @@ -2755,6 +2772,7 @@ add_node_to_ps (partial_schedule_ptr ps, return NULL; } + ps->rows_length[row] += 1; return ps_i; } @@ -2910,11 +2928,16 @@ rotate_partial_schedule (partial_schedul for (i = 0; i < backward_rotates; i++) { ps_insn_ptr first_row = ps->rows[0]; + int first_row_length = ps->rows_length[0]; for (row = 0; row < last_row; row++) - ps->rows[row] = ps->rows[row+1]; + { + ps->rows[row] = ps->rows[row + 1]; + ps->rows_length[row] = ps->rows_length[row + 1]; + } ps->rows[last_row] = first_row; + ps->rows_length[last_row] = first_row_length; } ps->max_cycle -= start_cycle;