From patchwork Fri Jun 10 16:31:19 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 633829 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 3rR73c2NgZz9ssM for ; Sat, 11 Jun 2016 02:31:39 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=OcUdv+Va; 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:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=LH0ZFRJf0rGOzZreCv3kcQozDqVYHcyl2AYaxBWU6b1N1pjKTp trSqylSmX09BeIsNNUXRrjs/dKpXdhXkVb2NxySj5fhtAWBbGcvpqj8j5Lc6Kil4 2j1PRjG1V/PxCAW4kM1xXCoOVRVeMhhSAipVr9LgIW7/VLfcZxJ4bkUXY= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=r7jly1qKOXkGqyvIuA1uHX+ekSs=; b=OcUdv+VaHjrA1ut3wvtz CmBlxfRBT4bJnRSW4lByeioMaI/9KITRuPTKWVNfBB04dKmS9+wsUnmGf1lgp54F W87+Z/LTWmaV9Do4Pm3TOB44Y8J/2e2FH0wrNqdO2wXG//emyK1wP8K0r61dvzhI ZVIquUKlLGuojmaI9UTVqdQ= Received: (qmail 87388 invoked by alias); 10 Jun 2016 16:31:32 -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 87365 invoked by uid 89); 10 Jun 2016 16:31:32 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.3 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=opportunity, management 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; Fri, 10 Jun 2016 16:31:22 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 9AF7572D35 for ; Fri, 10 Jun 2016 16:31:20 +0000 (UTC) Received: from localhost.localdomain (ovpn-116-42.phx2.redhat.com [10.3.116.42]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u5AGVJ0I004595 for ; Fri, 10 Jun 2016 12:31:20 -0400 To: gcc-patches From: Jeff Law Subject: [PR tree-optimization/71335] Fix thread path management in backwards threader Message-ID: Date: Fri, 10 Jun 2016 10:31:19 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 MIME-Version: 1.0 X-IsSubscribed: yes As previously noted, there's a buglet in the handling of the stack-of-blocks representation of the thread path in the backwards threader. In particular there's a case where we can get the same block pushed onto that stack twice. My workaround for that lameness could result in incorrect code if the last block in the path actually branches back to itself as seen in the 71335 testcase. This patch removes the hacks and avoids putting the duplicate on the stack-of-blocks path earlier. Bootstrapped and regression tested on x86_64 linux. Additionally, I did bootstraps and regression testing with additional verification that the state of the stack was unchanged across the call to fsm_find_control_statement_thread_paths (that verification is not in this patch, but could be easily added as a follow-up). Installed on the trunk, Jeff commit c2ffa8b6472e2d87763eeece99762fe3e5ab057a Author: law Date: Fri Jun 10 16:23:06 2016 +0000 PR tree-optimization/71335 * tree-ssa-threadbackward.c (profitable_jump_thread_path): Filter out zero length paths here. (convert_and_register_jump_thread_path): Remove hacks related to duplicated blocks in the jump thread path. (fsm_find_control_statement_thread_paths): Avoid putting the same block on the thread path twice, but ensure the thread path is unchanged from the caller's point of view. PR tree-optimization/71335 * gcc.c-torture/execute/pr71335.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237312 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index af96025..bd9476e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2016-06-10 Jeff Law + + PR tree-optimization/71335 + * tree-ssa-threadbackward.c (profitable_jump_thread_path): Filter out + zero length paths here. + (convert_and_register_jump_thread_path): Remove hacks related to + duplicated blocks in the jump thread path. + (fsm_find_control_statement_thread_paths): Avoid putting the same + block on the thread path twice, but ensure the thread path is + unchanged from the caller's point of view. + 2016-06-10 Jan Hubicka * predict.c (predict_loops): Remove PRED_LOOP_BRANCH. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 71a2db1..b76e477 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2016-06-10 Jeff Law + + PR tree-optimization/71335 + * gcc.c-torture/execute/pr71335.c: New test. + 2016-06-10 David Malcolm * gcc.dg/plugin/must-tail-call-2.c: Remove all details from diff --git a/gcc/testsuite/gcc.c-torture/execute/pr71335.c b/gcc/testsuite/gcc.c-torture/execute/pr71335.c new file mode 100644 index 0000000..cbfd990 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr71335.c @@ -0,0 +1,13 @@ +int a; +int +main () +{ + int b = 0; + while (a < 0 || b) + { + b = 0; + for (; b < 9; b++) + ; + } + exit (0); +} diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 57f1f5c..139d376 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -109,6 +109,19 @@ profitable_jump_thread_path (vec *&path, /* Note BBI is not in the path yet, hence the +1 in the test below to make sure BBI is accounted for in the path length test. */ int path_length = path->length (); + + /* We can get a length of 0 here when the statement that + makes a conditional generate a compile-time constant + result is in the same block as the conditional. + + That's not really a jump threading opportunity, but instead is + simple cprop & simplification. We could handle it here if we + wanted by wiring up all the incoming edges. If we run this + early in IPA, that might be worth doing. For now we just + reject that case. */ + if (path_length == 0) + return NULL; + if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -376,34 +389,12 @@ convert_and_register_jump_thread_path (vec *&path, basic_block bb1 = (*path)[path->length () - j - 1]; basic_block bb2 = (*path)[path->length () - j - 2]; - /* This can happen when we have an SSA_NAME as a PHI argument and - its initialization block is the head of the PHI argument's - edge. */ - if (bb1 == bb2) - continue; - edge e = find_edge (bb1, bb2); gcc_assert (e); jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD); jump_thread_path->safe_push (x); } - /* As a consequence of the test for duplicate blocks in the path - above, we can get a path with no blocks. This happens if a - conditional can be fully evaluated at compile time using just - defining statements in the same block as the test. - - When we no longer push the block associated with a PHI argument - onto the stack, then this as well as the test in the loop above - can be removed. */ - if (jump_thread_path->length () == 0) - { - jump_thread_path->release (); - delete jump_thread_path; - path->pop (); - return; - } - /* Add the edge taken when the control variable has value ARG. */ jump_thread_edge *x = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); @@ -579,10 +570,19 @@ fsm_find_control_statement_thread_paths (tree name, else { + /* profitable_jump_thread_path is going to push the current + block onto the path. But the path will always have the current + block at this point. So we can just pop it. */ + path->pop (); + edge taken_edge = profitable_jump_thread_path (path, var_bb, name, arg); if (taken_edge) convert_and_register_jump_thread_path (path, taken_edge); + + /* And put the current block back onto the path so that the + state of the stack is unchanged when we leave. */ + vec_safe_push (path, var_bb); } }