From patchwork Tue May 24 16:58:18 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 625742 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 3rDhSP71dlz9sRZ for ; Wed, 25 May 2016 02:58:29 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=NAFGcnWN; 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=aoIYP3x4RLhRP4QPPjaufRtOi4ycSXhSWbgdrUnXRkWlXhz+24Ae8 1KP2mtA+IhZQMOM3oYcUc7w7BOlCoiRwzWLZ/XjUY60TgAynITiwxOnPp3NGIeU5 n+UFez9w2Mc5aZbGYM7DE2i5mA2cophnvJdtT3HR0/4zdunI4uZEXk= 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=EoqcEPQZc+6Xr9g1+tD4xmlizB8=; b=NAFGcnWNnkRyqUdhLFo5 VmNqdlGvzzG/d4x3/D9ukEq1iELsOUdgaTzJHPRx4TvgE0ttwX12+FdgLoqCrf6X VvGX5Y7mCh/cI7hoVxdJptZis/yNlH8FUwAsaNIkp60agGiamxBHSfNd3mlpBo9c rC/s5G+ohEl0qWt68GLGsn0= Received: (qmail 72264 invoked by alias); 24 May 2016 16:58:22 -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 72252 invoked by uid 89); 24 May 2016 16:58:21 -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=H*MI:bd4a 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; Tue, 24 May 2016 16:58:20 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) (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 3A9297F370 for ; Tue, 24 May 2016 16:58:19 +0000 (UTC) Received: from localhost.localdomain (ovpn-116-172.phx2.redhat.com [10.3.116.172]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u4OGwI45010549 for ; Tue, 24 May 2016 12:58:18 -0400 From: Jeff Law Subject: More backwards/FSM jump thread refactoring and extension To: gcc-patches Message-ID: Date: Tue, 24 May 2016 10:58:18 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.0 MIME-Version: 1.0 X-IsSubscribed: yes Here's the next patch which does a bit more refactoring in the backwards jump threader and extends the backwards jump threader to handle simple copies and constant initializations. The extension isn't all that useful right now -- while it does fire often during bootstraps, its doing so for cases that would be caught slightly later (within the same pass). As a result there's no changes in the testsuite. The extension becomes useful in an upcoming patch where the backwards threader is disentangled from DOM/VRP entirely. In that mode the threader can't depend on cprop to have eliminated the copies and propagated as many constants as possible into PHI arguments. Bootstrapped and regression tested on x86_64 linux. Installing on the trunk. Jeff commit 913a4b1f209105a774789311094e90986db322fb Author: Jeff Law Date: Tue May 24 11:56:50 2016 -0400 * tree-ssa-threadbackwards.c (convert_and_register_jump_thread_path): New function, extracted from... (fsm_find_control_statement_thread_paths): Here. Use the new function. Allow simple copies and constant initializations in the SSA chain. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2b20cc8..9442109 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2016-05-24 Jeff Law + + * tree-ssa-threadbackwards.c (convert_and_register_jump_thread_path): + New function, extracted from... + (fsm_find_control_statement_thread_paths): Here. Use the new function. + Allow simple copies and constant initializations in the SSA chain. + 2016-05-24 Marek Polacek PR c/71249 diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 73ab4ea..4d0fd9c 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -356,6 +356,44 @@ profitable_jump_thread_path (vec *&path, return taken_edge; } +/* PATH is vector of blocks forming a jump threading path in reverse + order. TAKEN_EDGE is the edge taken from path[0]. + + Convert that path into the form used by register_jump_thread and + register the path. */ + +static void +convert_and_register_jump_thread_path (vec *&path, + edge taken_edge) +{ + vec *jump_thread_path = new vec (); + + /* Record the edges between the blocks in PATH. */ + for (unsigned int j = 0; j < path->length () - 1; j++) + { + basic_block bb1 = (*path)[path->length () - j - 1]; + basic_block bb2 = (*path)[path->length () - j - 2]; + 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); + } + + /* 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); + jump_thread_path->safe_push (x); + + register_jump_thread (jump_thread_path); + --max_threaded_paths; + + /* Remove BBI from the path. */ + path->pop (); +} + /* We trace the value of the SSA_NAME NAME back through any phi nodes looking for places where it gets a constant value and save the path. Stop after having recorded MAX_PATHS jump threading paths. */ @@ -377,24 +415,30 @@ fsm_find_control_statement_thread_paths (tree name, if (var_bb == NULL) return; - /* For the moment we assume that an SSA chain only contains phi nodes, and - eventually one of the phi arguments will be an integer constant. In the - future, this could be extended to also handle simple assignments of - arithmetic operations. */ + /* We allow the SSA chain to contains PHIs and simple copies and constant + initializations. */ if (gimple_code (def_stmt) != GIMPLE_PHI - || (gimple_phi_num_args (def_stmt) + && gimple_code (def_stmt) != GIMPLE_ASSIGN) + return; + + if (gimple_code (def_stmt) == GIMPLE_PHI + && (gimple_phi_num_args (def_stmt) >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS))) return; + if (gimple_code (def_stmt) == GIMPLE_ASSIGN + && gimple_assign_rhs_code (def_stmt) != INTEGER_CST + && gimple_assign_rhs_code (def_stmt) != SSA_NAME) + return; + /* Avoid infinite recursion. */ if (visited_bbs->add (var_bb)) return; - gphi *phi = as_a (def_stmt); int next_path_length = 0; basic_block last_bb_in_path = path->last (); - if (loop_containing_stmt (phi)->header == gimple_bb (phi)) + if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) { /* Do not walk through more than one loop PHI node. */ if (seen_loop_phi) @@ -469,9 +513,9 @@ fsm_find_control_statement_thread_paths (tree name, /* Iterate over the arguments of PHI. */ unsigned int i; - if (gimple_phi_num_args (phi) - < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)) + if (gimple_code (def_stmt) == GIMPLE_PHI) { + gphi *phi = as_a (def_stmt); for (i = 0; i < gimple_phi_num_args (phi); i++) { tree arg = gimple_phi_arg_def (phi, i); @@ -500,32 +544,23 @@ fsm_find_control_statement_thread_paths (tree name, into the canonical form and register it. */ edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg); if (taken_edge) - { - vec *jump_thread_path - = new vec (); - - /* Record the edges between the blocks in PATH. */ - for (unsigned int j = 0; j < path->length () - 1; j++) - { - edge e = find_edge ((*path)[path->length () - j - 1], - (*path)[path->length () - j - 2]); - gcc_assert (e); - jump_thread_edge *x - = new jump_thread_edge (e, EDGE_FSM_THREAD); - jump_thread_path->safe_push (x); - } - - /* 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); - jump_thread_path->safe_push (x); + convert_and_register_jump_thread_path (path, taken_edge); + } + } + else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) + { + tree arg = gimple_assign_rhs1 (def_stmt); - register_jump_thread (jump_thread_path); - --max_threaded_paths; + if (TREE_CODE (arg) == SSA_NAME) + fsm_find_control_statement_thread_paths (arg, visited_bbs, + path, seen_loop_phi); - /* Remove BBI from the path. */ - path->pop (); - } + else + { + edge taken_edge = profitable_jump_thread_path (path, var_bb, + name, arg); + if (taken_edge) + convert_and_register_jump_thread_path (path, taken_edge); } }