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: 5227 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 ED80023E08 for ; Mon, 21 Nov 2011 05:07:20 +0000 (UTC) Received: from mail-fx0-f52.google.com (mail-fx0-f52.google.com [209.85.161.52]) by fiordland.canonical.com (Postfix) with ESMTP id C6059A182C5 for ; Mon, 21 Nov 2011 05:07:20 +0000 (UTC) Received: by faaa26 with SMTP id a26so10322211faa.11 for ; Sun, 20 Nov 2011 21:07:20 -0800 (PST) Received: by 10.152.135.179 with SMTP id pt19mr7820987lab.47.1321852040571; Sun, 20 Nov 2011 21:07:20 -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.152.41.198 with SMTP id h6cs101425lal; Sun, 20 Nov 2011 21:07:19 -0800 (PST) Received: by 10.42.244.137 with SMTP id lq9mr12000141icb.28.1321852037106; Sun, 20 Nov 2011 21:07:17 -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 j8si2480657icn.89.2011.11.20.21.07.16 (version=TLSv1/SSLv3 cipher=OTHER); Sun, 20 Nov 2011 21:07:17 -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 iadj38 with SMTP id j38so8237713iad.37 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 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; }