From patchwork Wed Jan 22 21:28:09 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 313420 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id A711D2C00AF for ; Thu, 23 Jan 2014 08:28:22 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=XFFjoX7OJb4Vskl7t4H/5v6iek4CzJr1em5pZBVAbij4jZ teCpSB3EpxwORWB0E4VfD5qo5wl9LQ58vSYTzR1x2XF758uvnDlpkAmygrl2SeQB EkNFfDDup20VmS0bIErJO2Unnl4UgPn1YgxI+/nl9CQcTeHYorV+0DSWPRqTw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=gCb/1GI1yHrrW4NBZOjpY/79VLE=; b=KkH0+Ik/DcpFCANbsUEz o991eqmNt/au/DDMCGk1DucsOFmewKsEceFaivnrDbpxUW+C9tGHmkLIn2KGI0/q dXaOufkqjidAS34ggdDNeaj2lDobbpV0wZgARzsUug/zrRZ9rKk9Ed3SYG/OGVMJ z+ilBnT+gVCx2o5nSgolNOk= Received: (qmail 17019 invoked by alias); 22 Jan 2014 21:28:15 -0000 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 Received: (qmail 16971 invoked by uid 89); 22 Jan 2014 21:28:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 22 Jan 2014 21:28:11 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s0MLSA4q008374 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 22 Jan 2014 16:28:10 -0500 Received: from stumpy.slc.redhat.com ([10.3.113.16]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s0MLS9wo006284 for ; Wed, 22 Jan 2014 16:28:10 -0500 Message-ID: <52E037E9.2060203@redhat.com> Date: Wed, 22 Jan 2014 14:28:09 -0700 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: gcc-patches Subject: [PATCH][tree-optimization/59597] Reinstate code to cancel some jump threads X-IsSubscribed: yes I had taken this code out as the original cases I'd encountered were better handled by reorganization the order in which we thread blocks. However, as seen in 59597, there's still clearly cases where a jump threading path with a joiner block can have a threaded subpath. Threading the joiner block in this case is just wasteful (compile-time, memory consumption, code bloat) and as seen in 59597 can inhibit optimizations and result in significant performance degradations. So this brings that code back with some improvements in the debugging dumps so we can see when it happens. It should restore the performance of the sample code in 59597 back to where we were a while ago. Bootstrapped & regression tested on x86_64-unknown-linux-gnu, confirmed the testcase's runtime is dramatically improved as well. Installed on the trunk. Jeff diff --git a/gcc/ChangeLog b/gcc/ChangeLog index bcbb7dd..ea08f1f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2014-01-22 Jeff Law + + PR tree-optimization/59597 + * tree-ssa-threadupdate.c (dump_jump_thread_path): Move to earlier + in file. Accept new argument REGISTERING and use it to modify + dump output appropriately. + (register_jump_thread): Corresponding changes. + (mark_threaded_blocks): Reinstate code to cancel unprofitable + thread paths involving joiner blocks. Add code to dump cancelled + jump threading paths. + 2014-01-21 Vladimir Makarov PR rtl-optimization/59896 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 447d3c7..b7d7ce3 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2014-01-22 Jeff Law + + PR tree-optimization/59597 + * gcc.dg/tree-ssa/pr59597.c: New test. + 2014-01-22 Bill Schmidt * gcc.dg/vmx/insert-vsx-be-order.c: New. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr59597.c b/gcc/testsuite/gcc.dg/tree-ssa/pr59597.c new file mode 100644 index 0000000..814d299 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr59597.c @@ -0,0 +1,55 @@ +/* { dg-do compile } */ +/* { dg-options "-Ofast -fdump-tree-vrp1-details" } */ + +typedef unsigned short u16; +typedef unsigned char u8; +typedef unsigned int u32; +#define NNN 10 + +u32 f[NNN], t[NNN]; + +u16 Calc_crc8(u8 data, u16 crc ) +{ + u8 i=0,x16=0,carry=0; + for (i = 0; i < 8; i++) + { + x16 = (u8)((data & 1) ^ ((u8)crc & 1)); + data >>= 1; + + if (x16 == 1) + { + crc ^= 0x4002; + carry = 1; + } + else + carry = 0; + crc >>= 1; + if (carry) + crc |= 0x8000; + else + crc &= 0x7fff; + } + return crc; +} +int main (int argc, char argv[]) +{ + int i, j; u16 crc; + for (j = 0; j < 10000000; j++) + { + for (i = 0; i < NNN; i++) + { + f[i] = random(i); + t[i] = random(NNN - i - 1); + } + for (i=0; i static inline int equal (const value_type *, const compare_type *); }; +/* Dump a jump threading path, including annotations about each + edge in the path. */ + +static void +dump_jump_thread_path (FILE *dump_file, vec path, + bool registering) +{ + fprintf (dump_file, + " %s jump thread: (%d, %d) incoming edge; ", + (registering ? "Registering" : "Cancelling"), + path[0]->e->src->index, path[0]->e->dest->index); + + for (unsigned int i = 1; i < path.length (); i++) + { + /* We can get paths with a NULL edge when the final destination + of a jump thread turns out to be a constant address. We dump + those paths when debugging, so we have to be prepared for that + possibility here. */ + if (path[i]->e == NULL) + continue; + + if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK) + fprintf (dump_file, " (%d, %d) joiner; ", + path[i]->e->src->index, path[i]->e->dest->index); + if (path[i]->type == EDGE_COPY_SRC_BLOCK) + fprintf (dump_file, " (%d, %d) normal;", + path[i]->e->src->index, path[i]->e->dest->index); + if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK) + fprintf (dump_file, " (%d, %d) nocopy;", + path[i]->e->src->index, path[i]->e->dest->index); + } + fputc ('\n', dump_file); +} + /* Simple hashing function. For any given incoming edge E, we're going to be most concerned with the final destination of its jump thread path. So hash on the block index of the final edge in the path. */ @@ -1394,16 +1428,61 @@ mark_threaded_blocks (bitmap threaded_blocks) edge e; edge_iterator ei; - /* Move the jump threading requests from PATHS to each edge - which starts a jump thread path. */ + /* It is possible to have jump threads in which one is a subpath + of the other. ie, (A, B), (B, C), (C, D) where B is a joiner + block and (B, C), (C, D) where no joiner block exists. + + When this occurs ignore the jump thread request with the joiner + block. It's totally subsumed by the simpler jump thread request. + + This results in less block copying, simpler CFGs. More importantly, + when we duplicate the joiner block, B, in this case we will create + a new threading opportunity that we wouldn't be able to optimize + until the next jump threading iteration. + + So first convert the jump thread requests which do not require a + joiner block. */ for (i = 0; i < paths.length (); i++) { vec *path = paths[i]; - edge e = (*path)[0]->e; - e->aux = (void *)path; - bitmap_set_bit (tmp, e->dest->index); + + if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK) + { + edge e = (*path)[0]->e; + e->aux = (void *)path; + bitmap_set_bit (tmp, e->dest->index); + } } + /* Now iterate again, converting cases where we want to thread + through a joiner block, but only if no other edge on the path + already has a jump thread attached to it. */ + for (i = 0; i < paths.length (); i++) + { + vec *path = paths[i]; + + if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK) + { + unsigned int j; + + for (j = 0; j < path->length (); j++) + if ((*path)[j]->e->aux != NULL) + break; + + /* If we iterated through the entire path without exiting the loop, + then we are good to go, attach the path to the starting edge. */ + if (j == path->length ()) + { + edge e = (*path)[0]->e; + e->aux = path; + bitmap_set_bit (tmp, e->dest->index); + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + { + dump_jump_thread_path (dump_file, *path, false); + } + } + } /* If optimizing for size, only thread through block if we don't have @@ -1712,38 +1791,6 @@ delete_jump_thread_path (vec *path) path->release(); } -/* Dump a jump threading path, including annotations about each - edge in the path. */ - -static void -dump_jump_thread_path (FILE *dump_file, vec path) -{ - fprintf (dump_file, - " Registering jump thread: (%d, %d) incoming edge; ", - path[0]->e->src->index, path[0]->e->dest->index); - - for (unsigned int i = 1; i < path.length (); i++) - { - /* We can get paths with a NULL edge when the final destination - of a jump thread turns out to be a constant address. We dump - those paths when debugging, so we have to be prepared for that - possibility here. */ - if (path[i]->e == NULL) - continue; - - if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK) - fprintf (dump_file, " (%d, %d) joiner; ", - path[i]->e->src->index, path[i]->e->dest->index); - if (path[i]->type == EDGE_COPY_SRC_BLOCK) - fprintf (dump_file, " (%d, %d) normal;", - path[i]->e->src->index, path[i]->e->dest->index); - if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK) - fprintf (dump_file, " (%d, %d) nocopy;", - path[i]->e->src->index, path[i]->e->dest->index); - } - fputc ('\n', dump_file); -} - /* Register a jump threading opportunity. We queue up all the jump threading opportunities discovered by a pass and update the CFG and SSA form all at once. @@ -1770,7 +1817,7 @@ register_jump_thread (vec *path) { fprintf (dump_file, "Found NULL edge in jump threading path. Cancelling jump thread:\n"); - dump_jump_thread_path (dump_file, *path); + dump_jump_thread_path (dump_file, *path, false); } delete_jump_thread_path (path); @@ -1778,7 +1825,7 @@ register_jump_thread (vec *path) } if (dump_file && (dump_flags & TDF_DETAILS)) - dump_jump_thread_path (dump_file, *path); + dump_jump_thread_path (dump_file, *path, true); if (!paths.exists ()) paths.create (5);