From patchwork Mon Nov 21 05:07:16 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Revital Eres X-Patchwork-Id: 126683 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 577C2B7201 for ; Mon, 21 Nov 2011 16:07:41 +1100 (EST) Received: (qmail 18457 invoked by alias); 21 Nov 2011 05:07:35 -0000 Received: (qmail 18447 invoked by uid 22791); 21 Nov 2011 05:07:33 -0000 X-SWARE-Spam-Status: No, hits=-2.0 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, TW_DD X-Spam-Check-By: sourceware.org Received: from mail-iy0-f175.google.com (HELO mail-iy0-f175.google.com) (209.85.210.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 21 Nov 2011 05:07:17 +0000 Received: by iahk25 with SMTP id k25so7373794iah.20 for ; Sun, 20 Nov 2011 21:07:16 -0800 (PST) MIME-Version: 1.0 Received: by 10.42.163.202 with SMTP id d10mr11938400icy.47.1321852036161; Sun, 20 Nov 2011 21:07:16 -0800 (PST) Received: by 10.50.159.135 with HTTP; Sun, 20 Nov 2011 21:07:16 -0800 (PST) Date: Mon, 21 Nov 2011 07:07:16 +0200 Message-ID: Subject: [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 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, 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. Thanks, Revital Changelog: * modulo-sched.c (rows_reverse): New field in struct partial_schedule. (create_partial_schedule, free_partial_schedule, ps_insert_empty_row, ps_insn_advance_column, ps_insn_find_column, remove_node_from_ps, reset_partial_schedule, rotate_partial_schedule, verify_partial_schedule): Update the new field. Index: modulo-sched.c =================================================================== --- modulo-sched.c (revision 181149) +++ 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_reverse_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_reverse_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_reverse_new[row] = ps->rows_reverse[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_reverse_new[row + 1] = ps->rows_reverse[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_reverse); + ps->rows_reverse = rows_reverse_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_reverse[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_reverse = (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_reverse); 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_reverse = (ps_insn_ptr *) xrealloc (ps->rows_reverse, new_ii + * sizeof (ps_insn_ptr)); + memset (ps->rows_reverse, 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,15 @@ 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) + { + if (ps_i->prev_in_row) + ps->rows_reverse[row] = ps_i->prev_in_row; + else + ps->rows_reverse[row] = NULL; + } + if (! ps_i->prev_in_row) { gcc_assert (ps_i == ps->rows[row]); @@ -3048,6 +3075,8 @@ ps_insn_find_column (partial_schedule_pt } else ps->rows[row] = ps_i; + + ps->rows_reverse[row] = ps_i; return true; } @@ -3070,6 +3099,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_reverse[row] = ps_i; + return true; } @@ -3116,6 +3148,9 @@ ps_insn_advance_column (partial_schedule if (prev) prev->next_in_row = next; + if (ps_i->next_in_row == NULL) + ps->rows_reverse[row] = ps_i; + return true; } @@ -3298,14 +3333,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_reverse = ps->rows_reverse[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_reverse[row] = ps->rows_reverse[row + 1]; ps->rows_length[row] = ps->rows_length[row + 1]; } + ps->rows_reverse[last_row] = rows_reverse; ps->rows[last_row] = first_row; ps->rows_length[last_row] = first_row_length; }