From patchwork Wed Jan 27 19:20:47 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 574139 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 1F67D14056B for ; Thu, 28 Jan 2016 06:21:00 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=MruX/jwp; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:message-id:date:mime-version:content-type; q=dns; s= default; b=GxCPoM9VqlIOaiGgm4YtpnVkoBZw+BX2BR9JEAFdsKe+ZZqIfZ9ZE lspDg+Nl3kU9WVm4EkFPljF3YFTF9uz8yPufkMCgFz+bKba0loQ/xQJ6BIuhM34L yDGuWT6qfd0Z9S8qzLFUcchU+p1gGjn3Gw+UwyOBg5A1APzS0NbFrw= 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:from :subject:to:message-id:date:mime-version:content-type; s= default; bh=IYSVh3pDGZCsd3NALg7zR+w8u+I=; b=MruX/jwpB9wtICbuqLHp L4c0EmId0yPOEEI+yIr0maC+L7DhELl87ptUyY13r3tZqAa8lEBV1k3ITlEKvKUD SShoAcnQk+NMq8lf7T7VAOgWqqDEa8SnRoMmWQoEYNuaCWOdlznXVGnTjdPjTYED az9JnnVieAQ00f5g1sBHr3c= Received: (qmail 128157 invoked by alias); 27 Jan 2016 19:20:52 -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 128136 invoked by uid 89); 27 Jan 2016 19:20:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=5000, spotted, 159, Maximum 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 27 Jan 2016 19:20:49 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (Postfix) with ESMTPS id 154A9C0A9CF4 for ; Wed, 27 Jan 2016 19:20:48 +0000 (UTC) Received: from slagheap.utah.redhat.com (ovpn-113-73.phx2.redhat.com [10.3.113.73]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u0RJKltt006256 for ; Wed, 27 Jan 2016 14:20:47 -0500 From: Jeff Law Subject: [P2][PR tree-optimization/68398] Refine when we allow the FSM threader to create irreducible inner loops To: gcc-patches Message-ID: <56A9188F.1080803@redhat.com> Date: Wed, 27 Jan 2016 12:20:47 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 X-IsSubscribed: yes Right now we only allow the FSM threader to create an irreducible inner loop when it's able to eliminate a multiway branch. The theory being that the multiway branch is very expensive and potentially outweighs the value of loop optimizations. That was a fine start, but as seen in 68398, further refinement is desirable. Essentially in the 68398 case, we want to thread through the latch to a point in the loop that does not dominate the latch -- thus creating an irreducible inner loop. But in the 68398 case, we aren't eliminating a multiway branch, just a simple conditional branch. I stared at the jump threading paths, cfg and overall code for a long time over the last few days pondering what characteristics are important here. In the end it seems so simple. If the path has a high number of blocks relative to the number of statements in the path, then the path (and subsequent irreducible loop) really isn't likely to be helped by loop optimizations to begin with -- essentially the jump thread path is just a series of conditional branches where we know the result of the last one -- and there's very little computation going on in the path. So that's what I'm keying on -- the ratio of blocks to statements in the path. The higher that ratio, the more inclined we are to allow creation of the irreducible inner loop. FWIW, I did look at simply allowing irreducible loops after the loop optimizers were complete -- that doesn't resolve the issues here. We need it to happen early so that the rest of the optimization pipeline (including dom, vrp2, dom2) see the jump-threaded code and refine it further. We may still want to make that kind of change, but I'd like to see code that benefits from such a change rather than blindly going forward with it. Going back to that ratio of blocks to statements. We were counting PHIs in the thread path against the statement count. Except for the final block, those PHIs are going to be const/copy propagated away. So the code to count the PHIs was moved out of the loop and just looks at PHIs in the final block in the path. Second we want to be able to compare the number of statements and the number of blocks in a jump threading path. In particular we'd like to look at ratios between the two. So there's two controlling PARAMS to scale the raw numbers, which then makes it easier to build ratios. So we can say that once the number of blocks exceeds the number of statements by 1.5X, then allow creation of the irreducible loop (that's done by scaling the blocks by 3 and statements by 2. Testing. For the testcase in 68398, this improves things by another percent or two in terms of raw instruction counts. I get something like 206k-207k instruction references. For pr66752-3.c the heuristic fires and we handle all 3 jump threads during VRP1 and obviously we continue to collapse away all 3 tests of FLAG. For vrp46.c, ssa-dom-thread-2{c,d}.c I added statements on the jump threading path so that the heuristic wouldn't fire to preserve the spirit of those tests. ssa-dom-thread-2{h,g}.c new tests, copied from the original ssa-dom-thread-2{c,d} which show the heuristic firing. ssa-dom-thread-7.c does more threading early as the heuristic fires there. So its expected output was adjusted. Bootstrapped and regression tested on x86_64 linux. Installing on the trunk. This also fixes 3 minor issues Bernd spotted in the last round of changes. Jeff commit a5b3ed5d29ceb18b9e257894661f328462f581c8 Author: law Date: Wed Jan 27 19:19:47 2016 +0000 PR tree-optimization/68398 * params.def (PARAM_FSM_SCALE_PATH_STMTS): New parameter. (PARAM_FSM_SCALE_PATH_BLOCKS): Likewise. * tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths): Only count PHIs in the last block in the path. The others will const/copy propagate away. Add heuristic to allow more irreducible subloops to be created when it is likely profitable to do so. * tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths): Fix typo in comment. Use gsi_after_labels and remove the GIMPLE_LABEL check from within the loop. Use gsi_next_nondebug rather than gsi_next. PR tree-optimization/68398 * gcc.dg/tree-ssa/pr66752-3.c: Update expected output. * gcc.dg/tree-ssa/ssa-dom-thread-2c.c: Add extra statements on thread path to avoid new heuristic allowing more irreducible regions * gcc.dg/tree-ssa/ssa-dom-thread-2d.c: Likewise. * gcc.dg/tree-ssa/vrp46.c: Likewise. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output. * gcc.dg/tree-ssa/ssa-dom-thread-2g.c: New test. * gcc.dg/tree-ssa/ssa-dom-thread-2h.c: Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@232897 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1973060..76c7af2 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2016-01-27 Jeff Law + + PR tree-optimization/68398 + PR tree-optimization/69196 + * params.def (PARAM_FSM_SCALE_PATH_STMTS): New parameter. + (PARAM_FSM_SCALE_PATH_BLOCKS): Likewise. + * tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths): + Only count PHIs in the last block in the path. The others will + const/copy propagate away. Add heuristic to allow more irreducible + subloops to be created when it is likely profitable to do so. + + * tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths): + Fix typo in comment. Use gsi_after_labels and remove the GIMPLE_LABEL + check from within the loop. Use gsi_next_nondebug rather than gsi_next. + 2016-01-27 Jakub Jelinek PR lto/69254 diff --git a/gcc/params.def b/gcc/params.def index 88971c7..0722ad7 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1145,6 +1145,16 @@ DEFPARAM (PARAM_CHKP_MAX_CTOR_SIZE, "constructor generated by Pointer Bounds Checker.", 5000, 100, 0) +DEFPARAM (PARAM_FSM_SCALE_PATH_STMTS, + "fsm-scale-path-stmts", + "Scale factor to apply to the number of statements in a threading path when comparing to the number of (scaled) blocks.", + 2, 1, 10) + +DEFPARAM (PARAM_FSM_SCALE_PATH_BLOCKS, + "fsm-scale-path-blocks", + "Scale factor to apply to the number of blocks in a threading path when comparing to the number of (scaled) statements.", + 3, 1, 10) + DEFPARAM (PARAM_MAX_FSM_THREAD_PATH_INSNS, "max-fsm-thread-path-insns", "Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path.", diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 2cad0c2..22a124a 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,16 @@ +2016-01-25 Jeff Law + + PR tree-optimization/68398 + PR tree-optimization/69196 + * gcc.dg/tree-ssa/pr66752-3.c: Update expected output. + * gcc.dg/tree-ssa/ssa-dom-thread-2c.c: Add extra statements on thread + path to avoid new heuristic allowing more irreducible regions + * gcc.dg/tree-ssa/ssa-dom-thread-2d.c: Likewise. + * gcc.dg/tree-ssa/vrp46.c: Likewise. + * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output. + * gcc.dg/tree-ssa/ssa-dom-thread-2g.c: New test. + * gcc.dg/tree-ssa/ssa-dom-thread-2h.c: Likewise. + 2016-01-27 Marek Polacek PR c/68062 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c index 6eeaca5..2949cbb 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr66752-3.c @@ -32,10 +32,9 @@ foo (int N, int c, int b, int *a) pt--; } -/* There are 3 FSM jump threading opportunities, one of which will - get filtered. */ -/* { dg-final { scan-tree-dump-times "Registering FSM" 2 "vrp1"} } */ -/* { dg-final { scan-tree-dump-times "FSM would create irreducible loop" 1 "vrp1"} } */ +/* There are 3 FSM jump threading opportunities, all of which will be + realized, which will eliminate testing of FLAG, completely. */ +/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "vrp1"} } */ /* There should be no assignments or references to FLAG. */ /* { dg-final { scan-tree-dump-not "flag" "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2c.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2c.c index f3e37bd..f914676 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2c.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2c.c @@ -1,4 +1,4 @@ -/* { dg-do compile } */ +/* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats" } */ void foo(); @@ -15,6 +15,9 @@ void dont_thread_1 (void) do { + bla (); + bla (); + bla (); if (first) foo (); else diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2d.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2d.c index 9b4637a..a04aabf 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2d.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2d.c @@ -1,4 +1,4 @@ -/* { dg-do compile } */ +/* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats" } */ void foo(); @@ -13,6 +13,9 @@ void dont_thread_2 (int first) do { + bla (); + bla (); + bla (); if (first) foo (); else diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2g.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2g.c new file mode 100644 index 0000000..6d1ff5d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2g.c @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats" } */ + +void foo(); +void bla(); +void bar(); + +void dont_thread_1 (void) +{ + int i = 0; + int first = 1; + + do + { + if (first) + foo (); + else + bar (); + + first = 0; + bla (); + } while (i++ < 100); +} + +/* { dg-final { scan-tree-dump "Jumps threaded: 2" "vrp1"} } */ +/* { dg-final { scan-tree-dump "Jumps threaded: 1" "dom2"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2h.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2h.c new file mode 100644 index 0000000..61705e1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-2h.c @@ -0,0 +1,29 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats" } */ + +void foo(); +void bla(); +void bar(); + +/* Avoid threading in the following case, to prevent creating subloops. */ + +void dont_thread_2 (int first) +{ + int i = 0; + + do + { + if (first) + foo (); + else + bar (); + + first = 0; + bla (); + } while (i++ < 100); +} + +/* Peeling off the first iteration would make threading through + the loop latch safe, but we don't do that currently. */ +/* { dg-final { scan-tree-dump "Jumps threaded: 1" "vrp1"} } */ +/* { dg-final { scan-tree-dump "Jumps threaded: 1" "dom2"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c index 93c767c..a7a737b 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c @@ -1,8 +1,9 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats -fdump-tree-dom3-stats" } */ -/* { dg-final { scan-tree-dump "Jumps threaded: 7" "vrp1" } } */ +/* { dg-options "-O2 -fdump-tree-vrp1-stats -fdump-tree-dom2-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats" } */ +/* { dg-final { scan-tree-dump "Jumps threaded: 19" "vrp1" } } */ /* { dg-final { scan-tree-dump "Jumps threaded: 12" "dom2" } } */ -/* { dg-final { scan-tree-dump "Jumps threaded: 3" "dom3" } } */ +/* { dg-final { scan-tree-dump-not "Jumps threaded" "dom3" } } */ +/* { dg-final { scan-tree-dump-not "Jumps threaded" "vrp2" } } */ enum STATE { S0=0, diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c index 64c65d0..8923eb4 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c @@ -12,6 +12,8 @@ func_18 ( int t ) for (0; 1; ++l_889) { int t1 = 0; + func_98 (0); + func_98 (0); if (func_81 (1)) { int rhs = l_895; diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 131630e..735009c 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -266,7 +266,7 @@ fsm_find_control_statement_thread_paths (tree name, basic_block bb = (*path)[j]; /* Remember, blocks in the path are stored in opposite order - in the PATH array. The last entry in the array reprensents + in the PATH array. The last entry in the array represents the block with an outgoing edge that we will redirect to the jump threading path. Thus we don't care about that block's loop father, nor how many statements are in that block because @@ -280,33 +280,19 @@ fsm_find_control_statement_thread_paths (tree name, break; } - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + for (gsi = gsi_after_labels (bb); + !gsi_end_p (gsi); + gsi_next_nondebug (&gsi)) { gimple *stmt = gsi_stmt (gsi); /* Do not count empty statements and labels. */ if (gimple_code (stmt) != GIMPLE_NOP - && gimple_code (stmt) != GIMPLE_LABEL && !(gimple_code (stmt) == GIMPLE_ASSIGN && gimple_assign_rhs_code (stmt) == ASSERT_EXPR) && !is_gimple_debug (stmt)) ++n_insns; } - gphi_iterator gsip; - for (gsip = gsi_start_phis (bb); - !gsi_end_p (gsip); - gsi_next (&gsip)) - { - gphi *phi = gsip.phi (); - tree dst = gimple_phi_result (phi); - - /* We consider any non-virtual PHI as a statement since it - count result in a constant assignment or copy - operation. */ - if (!virtual_operand_p (dst)) - ++n_insns; - } - /* We do not look at the block with the threaded branch in this loop. So if any block with a last statement that is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a @@ -360,6 +346,24 @@ fsm_find_control_statement_thread_paths (tree name, == DOMST_NONDOMINATING)) creates_irreducible_loop = true; + /* PHIs in the final target and only the final target will need + to be duplicated. So only count those against the number + of statements. */ + gphi_iterator gsip; + for (gsip = gsi_start_phis (taken_edge->dest); + !gsi_end_p (gsip); + gsi_next (&gsip)) + { + gphi *phi = gsip.phi (); + tree dst = gimple_phi_result (phi); + + /* We consider any non-virtual PHI as a statement since it + count result in a constant assignment or copy + operation. */ + if (!virtual_operand_p (dst)) + ++n_insns; + } + if (path_crosses_loops) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -379,10 +383,18 @@ fsm_find_control_statement_thread_paths (tree name, continue; } - /* We avoid creating irreducible loops unless we thread through + /* We avoid creating irreducible inner loops unless we thread through a multiway branch, in which case we have deemed it worth losing other - loop optimizations later. */ - if (!threaded_multiway_branch && creates_irreducible_loop) + loop optimizations later. + + We also consider it worth creating an irreducible inner loop if + the number of copied statement is low relative to the length of + the path -- in that case there's little the traditional loop optimizer + would have done anyway, so an irreducible loop is not so bad. */ + if (!threaded_multiway_branch && creates_irreducible_loop + && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS) + > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))) + { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file,