From patchwork Sun Dec 18 06:37:44 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Revital Eres X-Patchwork-Id: 5836 Return-Path: X-Original-To: patchwork@peony.canonical.com Delivered-To: patchwork@peony.canonical.com Received: from fiordland.canonical.com (fiordland.canonical.com [91.189.94.145]) by peony.canonical.com (Postfix) with ESMTP id D06AB23E18 for ; Sun, 18 Dec 2011 06:37:48 +0000 (UTC) Received: from mail-ey0-f180.google.com (mail-ey0-f180.google.com [209.85.215.180]) by fiordland.canonical.com (Postfix) with ESMTP id BD10FA1872E for ; Sun, 18 Dec 2011 06:37:48 +0000 (UTC) Received: by eaac11 with SMTP id c11so851498eaa.11 for ; Sat, 17 Dec 2011 22:37:48 -0800 (PST) Received: by 10.204.156.219 with SMTP id y27mr3873066bkw.125.1324190268524; Sat, 17 Dec 2011 22:37:48 -0800 (PST) X-Forwarded-To: linaro-patchwork@canonical.com X-Forwarded-For: patch@linaro.org linaro-patchwork@canonical.com Delivered-To: patches@linaro.org Received: by 10.204.40.4 with SMTP id i4cs99223bke; Sat, 17 Dec 2011 22:37:47 -0800 (PST) Received: by 10.50.34.164 with SMTP id a4mr17558425igj.66.1324190264916; Sat, 17 Dec 2011 22:37:44 -0800 (PST) Received: from mail-iy0-f178.google.com (mail-iy0-f178.google.com [209.85.210.178]) by mx.google.com with ESMTPS id j3si3771988igz.13.2011.12.17.22.37.44 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 17 Dec 2011 22:37:44 -0800 (PST) Received-SPF: neutral (google.com: 209.85.210.178 is neither permitted nor denied by best guess record for domain of revital.eres@linaro.org) client-ip=209.85.210.178; Authentication-Results: mx.google.com; spf=neutral (google.com: 209.85.210.178 is neither permitted nor denied by best guess record for domain of revital.eres@linaro.org) smtp.mail=revital.eres@linaro.org Received: by iagf6 with SMTP id f6so8256976iag.37 for ; Sat, 17 Dec 2011 22:37:44 -0800 (PST) MIME-Version: 1.0 Received: by 10.50.171.5 with SMTP id aq5mr19028177igc.76.1324190264088; Sat, 17 Dec 2011 22:37:44 -0800 (PST) Received: by 10.42.164.201 with HTTP; Sat, 17 Dec 2011 22:37:44 -0800 (PST) In-Reply-To: References: Date: Sun, 18 Dec 2011 08:37:44 +0200 Message-ID: Subject: Re: [PATCH SMS 1/2, RFC] Support traversing PS in reverse order From: Revital Eres To: Ayal Zaks Cc: richard sandiford , gcc-patches@gcc.gnu.org, Patch Tracking Hello, >> This patch support the estimation of register pressure in SMS. >> Although GCC is in stage 3 I would appreciate comments on it. >> Thanks to Richard and Ayal for discussing the implementation and their insights. >> >> This part of the patch enables iterating on the partial schedule in the >> reverse order (from the last instruction the the first). >> >> Tested and bootstrap with the other patches in the series on >> ppc64-redhat-linux, >> enabling SMS on loops with SC 1. >> >> Comments are welcome. >> > > This looks fine. Please rename rows_reverse to rows_last as discussed, > and simplify the bit that tracks last_in_row in ps_insn_find_column(). > Thanks, > Ayal. > Thanks, attached is the new version of the patch following your comments. Tested and bootstrap with the other patches in the series on ppc64-redhat-linux, enabling SMS on loops with SC 1. Revital * modulo-sched.c (rows_last): New field in struct partial_schedule. (create_partial_schedule, free_partial_schedule, ps_insert_empty_row, ps_insn_advance_column, remove_node_from_ps, reset_partial_schedule, rotate_partial_schedule, verify_partial_schedule): Update the new field. (ps_insn_find_column): Likewise and remove last_in_row. Index: modulo-sched.c =================================================================== --- modulo-sched.c (revision 181763) +++ modulo-sched.c (working copy) @@ -177,6 +177,10 @@ struct partial_schedule /* rows[i] points to linked list of insns scheduled in row i (0<=inum_nodes. */ VEC (ps_reg_move_info, heap) *reg_moves; @@ -2272,6 +2276,7 @@ ps_insert_empty_row (partial_schedule_pt { ps_insn_ptr crr_insn; ps_insn_ptr *rows_new; + ps_insn_ptr *rows_last_new; int ii = ps->ii; int new_ii = ii + 1; int row; @@ -2290,10 +2295,12 @@ 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_last_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_last_new[row] = ps->rows_last[row]; rows_length_new[row] = ps->rows_length[row]; ps->rows[row] = NULL; for (crr_insn = rows_new[row]; @@ -2315,6 +2322,7 @@ ps_insert_empty_row (partial_schedule_pt for (row = split_row; row < ii; row++) { rows_new[row + 1] = ps->rows[row]; + rows_last_new[row + 1] = ps->rows_last[row]; rows_length_new[row + 1] = ps->rows_length[row]; ps->rows[row] = NULL; for (crr_insn = rows_new[row + 1]; @@ -2337,6 +2345,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_last); + ps->rows_last = rows_last_new; free (ps->rows_length); ps->rows_length = rows_length_new; ps->ii = new_ii; @@ -2428,6 +2438,9 @@ verify_partial_schedule (partial_schedul popcount (sched_nodes) == number of insns in ps. */ gcc_assert (SCHED_TIME (u) >= ps->min_cycle); gcc_assert (SCHED_TIME (u) <= ps->max_cycle); + if (ps->rows_length[row] == length) + gcc_assert (ps->rows_last[row] == crr_insn); + } gcc_assert (ps->rows_length[row] == length); @@ -2837,6 +2850,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_last = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr)); ps->rows_length = (int *) xcalloc (ii, sizeof (int)); ps->reg_moves = NULL; ps->ii = ii; @@ -2885,6 +2899,7 @@ free_partial_schedule (partial_schedule_ free_ps_insns (ps); free (ps->rows); + free (ps->rows_last); free (ps->rows_length); free (ps); } @@ -2903,6 +2918,9 @@ 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_last = (ps_insn_ptr *) xrealloc (ps->rows_last, new_ii + * sizeof (ps_insn_ptr)); + memset (ps->rows_last, 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; @@ -2960,6 +2978,10 @@ remove_node_from_ps (partial_schedule_pt gcc_assert (ps && ps_i); row = SMODULO (ps_i->cycle, ps->ii); + + if (! ps_i->next_in_row) + ps->rows_last[row] = ps_i->prev_in_row; + if (! ps_i->prev_in_row) { gcc_assert (ps_i == ps->rows[row]); @@ -2992,7 +3014,6 @@ ps_insn_find_column (partial_schedule_pt ps_insn_ptr next_ps_i; ps_insn_ptr first_must_follow = NULL; ps_insn_ptr last_must_precede = NULL; - ps_insn_ptr last_in_row = NULL; int row; if (! ps_i) @@ -3024,9 +3045,7 @@ ps_insn_find_column (partial_schedule_pt if (must_precede && TEST_BIT (must_precede, next_ps_i->id) && JUMP_P (ps_rtl_insn (ps, next_ps_i->id))) - return false; - - last_in_row = next_ps_i; + return false; } /* The closing branch is scheduled as well. Make sure there is no @@ -3036,18 +3055,20 @@ ps_insn_find_column (partial_schedule_pt { if (first_must_follow) return false; - if (last_in_row) + + if (ps->rows_last[row]) { /* Make the branch the last in the row. New instructions will be inserted at the beginning of the row or after the last must_precede instruction thus the branch is guaranteed to remain the last instruction in the row. */ - last_in_row->next_in_row = ps_i; - ps_i->prev_in_row = last_in_row; - ps_i->next_in_row = NULL; + ps->rows_last[row]->next_in_row = ps_i; + ps_i->prev_in_row = ps->rows_last[row]; } else - ps->rows[row] = ps_i; + ps->rows[row] = ps_i; + + ps->rows_last[row] = ps_i; return true; } @@ -3070,6 +3091,9 @@ ps_insn_find_column (partial_schedule_pt ps_i->next_in_row->prev_in_row = ps_i; } + if (! ps_i->next_in_row) + ps->rows_last[row] = ps_i; + return true; } @@ -3116,6 +3140,9 @@ ps_insn_advance_column (partial_schedule if (prev) prev->next_in_row = next; + if (ps_i->next_in_row == NULL) + ps->rows_last[row] = ps_i; + return true; } @@ -3298,14 +3325,17 @@ rotate_partial_schedule (partial_schedul for (i = 0; i < backward_rotates; i++) { ps_insn_ptr first_row = ps->rows[0]; + ps_insn_ptr rows_last = ps->rows_last[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_last[row] = ps->rows_last[row + 1]; ps->rows_length[row] = ps->rows_length[row + 1]; } + ps->rows_last[last_row] = rows_last; ps->rows[last_row] = first_row; ps->rows_length[last_row] = first_row_length; }