From patchwork Fri May 6 18:22:22 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Easwaran Raman X-Patchwork-Id: 94424 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 B6AD7B6FB6 for ; Sat, 7 May 2011 04:22:45 +1000 (EST) Received: (qmail 28590 invoked by alias); 6 May 2011 18:22:43 -0000 Received: (qmail 28579 invoked by uid 22791); 6 May 2011 18:22:42 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, SPF_HELO_PASS, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 06 May 2011 18:22:25 +0000 Received: from kpbe19.cbf.corp.google.com (kpbe19.cbf.corp.google.com [172.25.105.83]) by smtp-out.google.com with ESMTP id p46IMO1M014780 for ; Fri, 6 May 2011 11:22:24 -0700 Received: from pzk10 (pzk10.prod.google.com [10.243.19.138]) by kpbe19.cbf.corp.google.com with ESMTP id p46IMAGY021904 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Fri, 6 May 2011 11:22:23 -0700 Received: by pzk10 with SMTP id 10so2234898pzk.35 for ; Fri, 06 May 2011 11:22:22 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.14.1 with SMTP id 1mr2148882wfn.239.1304706142587; Fri, 06 May 2011 11:22:22 -0700 (PDT) Received: by 10.142.230.18 with HTTP; Fri, 6 May 2011 11:22:22 -0700 (PDT) Date: Fri, 6 May 2011 11:22:22 -0700 Message-ID: Subject: [google] Backport r172837 and r172788 to google/main From: Easwaran Raman To: gcc-patches@gcc.gnu.org X-System-Of-Record: true X-IsSubscribed: yes 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 Backported r172788 and r172837 from trunk to google/main. 2011-05-06 Easwaran Raman Backport r172837: * cfgexpand.c (stack_var): Remove OFFSET... (add_stack_var): ...and its reference here... (expand_stack_vars): ...and here. (stack_var_cmp): Sort by descending order of size. (partition_stack_vars): Change heuristic. (union_stack_vars): Fix to reflect changes in partition_stack_vars. (dump_stack_var_partition): Add newline after each partition. 2011-05-06 Easwaran Raman Backport r172788: * cfgexpand.c (add_alias_set_conflicts): Add conflicts with a variable containing union type only with -fstrict-aliasing. testsuite/ChangeLog.google-main: 2011-05-06 Easwaran Raman Backport r172837: * gcc.dg/stack-layout-2.c: New test. 2011-05-06 Easwaran Raman Backport r172788: * gcc.dg/stack-layout-1.c: New test. Index: gcc/testsuite/gcc.dg/stack-layout-1.c =================================================================== --- gcc/testsuite/gcc.dg/stack-layout-1.c (revision 0) +++ gcc/testsuite/gcc.dg/stack-layout-1.c (revision 173499) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-strict-aliasing -fdump-rtl-expand" } */ +union U { + int a; + float b; +}; +struct A { + union U u1; + char a[100]; +}; +void bar (struct A *); +void foo () + { + { + struct A a; + bar (&a); + } + { + struct A a; + bar (&a); + } + } + +/* { dg-final { scan-rtl-dump-times "Partition" 1 "expand" } } */ +/* { dg-final { cleanup-rtl-dump "expand" } } */ Index: gcc/testsuite/gcc.dg/stack-layout-2.c =================================================================== --- gcc/testsuite/gcc.dg/stack-layout-2.c (revision 0) +++ gcc/testsuite/gcc.dg/stack-layout-2.c (revision 173499) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-rtl-expand" } */ +void bar( char *); +int foo() +{ + int i=0; + { + char a[8000]; + bar(a); + i += a[0]; + } + { + char a[8192]; + char b[32]; + bar(a); + i += a[0]; + bar(b); + i += a[0]; + } + return i; +} +/* { dg-final { scan-rtl-dump "size 8192" "expand" } } */ +/* { dg-final { scan-rtl-dump "size 32" "expand" } } */ Index: gcc/cfgexpand.c =================================================================== --- gcc/cfgexpand.c (revision 173498) +++ gcc/cfgexpand.c (revision 173499) @@ -158,11 +158,6 @@ struct stack_var /* The Variable. */ tree decl; - /* The offset of the variable. During partitioning, this is the - offset relative to the partition. After partitioning, this - is relative to the stack frame. */ - HOST_WIDE_INT offset; - /* Initially, the size of the variable. Later, the size of the partition, if this variable becomes it's partition's representative. */ HOST_WIDE_INT size; @@ -267,7 +262,6 @@ add_stack_var (tree decl) v = &stack_vars[stack_vars_num]; v->decl = decl; - v->offset = 0; v->size = tree_low_cst (DECL_SIZE_UNIT (SSAVAR (decl)), 1); /* Ensure that all variables have size, so that &a != &b for any two variables that are simultaneously live. */ @@ -372,8 +366,9 @@ add_alias_set_conflicts (void) to elements will conflict. In case of unions we have to be careful as type based aliasing rules may say access to the same memory does not conflict. So play - safe and add a conflict in this case. */ - || contains_union) + safe and add a conflict in this case when + -fstrict-aliasing is used. */ + || (contains_union && flag_strict_aliasing)) add_stack_var_conflict (i, j); } } @@ -403,9 +398,9 @@ stack_var_cmp (const void *a, const void *b) return (int)largeb - (int)largea; /* Secondary compare on size, decreasing */ - if (sizea < sizeb) - return -1; if (sizea > sizeb) + return -1; + if (sizea < sizeb) return 1; /* Tertiary compare on true alignment, decreasing. */ @@ -564,28 +559,19 @@ update_alias_info_with_stack_vars (void) /* A subroutine of partition_stack_vars. The UNION portion of a UNION/FIND partitioning algorithm. Partitions A and B are known to be non-conflicting. - Merge them into a single partition A. + Merge them into a single partition A. */ - At the same time, add OFFSET to all variables in partition B. At the end - of the partitioning process we've have a nice block easy to lay out within - the stack frame. */ - static void -union_stack_vars (size_t a, size_t b, HOST_WIDE_INT offset) +union_stack_vars (size_t a, size_t b) { - size_t i, last; struct stack_var *vb = &stack_vars[b]; bitmap_iterator bi; unsigned u; - /* Update each element of partition B with the given offset, - and merge them into partition A. */ - for (last = i = b; i != EOC; last = i, i = stack_vars[i].next) - { - stack_vars[i].offset += offset; - stack_vars[i].representative = a; - } - stack_vars[last].next = stack_vars[a].next; + gcc_assert (stack_vars[b].next == EOC); + /* Add B to A's partition. */ + stack_vars[b].next = stack_vars[a].next; + stack_vars[b].representative = a; stack_vars[a].next = b; /* Update the required alignment of partition A to account for B. */ @@ -605,16 +591,13 @@ static void partitions constrained by the interference graph. The overall algorithm used is as follows: - Sort the objects by size. + Sort the objects by size in descending order. For each object A { S = size(A) O = 0 loop { Look for the largest non-conflicting object B with size <= S. UNION (A, B) - offset(B) = O - O += size(B) - S -= size(B) } } */ @@ -636,24 +619,23 @@ partition_stack_vars (void) for (si = 0; si < n; ++si) { size_t i = stack_vars_sorted[si]; - HOST_WIDE_INT isize = stack_vars[i].size; unsigned int ialign = stack_vars[i].alignb; - HOST_WIDE_INT offset = 0; - for (sj = si; sj-- > 0; ) + /* Ignore objects that aren't partition representatives. If we + see a var that is not a partition representative, it must + have been merged earlier. */ + if (stack_vars[i].representative != i) + continue; + + for (sj = si + 1; sj < n; ++sj) { size_t j = stack_vars_sorted[sj]; - HOST_WIDE_INT jsize = stack_vars[j].size; unsigned int jalign = stack_vars[j].alignb; /* Ignore objects that aren't partition representatives. */ if (stack_vars[j].representative != j) continue; - /* Ignore objects too large for the remaining space. */ - if (isize < jsize) - continue; - /* Ignore conflicting objects. */ if (stack_var_conflict_p (i, j)) continue; @@ -664,25 +646,8 @@ partition_stack_vars (void) != (jalign * BITS_PER_UNIT <= MAX_SUPPORTED_STACK_ALIGNMENT)) continue; - /* Refine the remaining space check to include alignment. */ - if (offset & (jalign - 1)) - { - HOST_WIDE_INT toff = offset; - toff += jalign - 1; - toff &= -(HOST_WIDE_INT)jalign; - if (isize - (toff - offset) < jsize) - continue; - - isize -= toff - offset; - offset = toff; - } - /* UNION the objects, placing J at OFFSET. */ - union_stack_vars (i, j, offset); - - isize -= jsize; - if (isize == 0) - break; + union_stack_vars (i, j); } } @@ -712,9 +677,8 @@ dump_stack_var_partition (void) { fputc ('\t', dump_file); print_generic_expr (dump_file, stack_vars[j].decl, dump_flags); - fprintf (dump_file, ", offset " HOST_WIDE_INT_PRINT_DEC "\n", - stack_vars[j].offset); } + fputc ('\n', dump_file); } } @@ -863,10 +827,9 @@ expand_stack_vars (bool (*pred) (tree)) partition. */ for (j = i; j != EOC; j = stack_vars[j].next) { - gcc_assert (stack_vars[j].offset <= stack_vars[i].size); expand_one_stack_var_at (stack_vars[j].decl, base, base_align, - stack_vars[j].offset + offset); + offset); } }