From patchwork Tue Nov 15 16:19: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: 695117 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 3tJCJy4bCXz9syB for ; Wed, 16 Nov 2016 03:19:46 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="HZYqtAqu"; 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 :subject:to:references:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=kvcs3xNs0KtFGe7Cd bLM8i0x/tJMv80T2lQU5+kAHQ+jYdbvArR1MForK5gIMYBu8FN2wZeuwf6VKvBJQ Iej7m3HYpLQsFl85fZXzWH7kovusPrlt860MtVuttR+1+uaP3DADxmdEr3Oj4Tf+ rcV4LhBBO2fDMv2pg9n/3EwVDQ= 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 :subject:to:references:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=JarR6gYWYXwnIF2BaBMSFUB KIK0=; b=HZYqtAquRQnxDSVSuCeIFEyUUR93etY7ocTqUcYWqumVWXDF8UwjVMz QJyySHmy5gpEoqje91U6cgmERAwNr/8A3tc4FqcToW5h1RzPhFcJh3F5I4YzR1q5 cPt67jXFZE1qcL1XLBqbSc7TpUIf7gQ1eIXFB1tQZwa7Iw1VLCHE= Received: (qmail 66531 invoked by alias); 15 Nov 2016 16:19:36 -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 66495 invoked by uid 89); 15 Nov 2016 16:19:35 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.7 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=traverse, arcarchh, UD:arc-arch.h, arc-arch.h 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; Tue, 15 Nov 2016 16:19:21 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) (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 EF7738535A for ; Tue, 15 Nov 2016 16:19:19 +0000 (UTC) Received: from localhost.localdomain (ovpn-116-64.phx2.redhat.com [10.3.116.64]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id uAFGJJQk026734 for ; Tue, 15 Nov 2016 11:19:19 -0500 Subject: Re: Some backward threader refactoring To: gcc-patches References: From: Jeff Law Message-ID: Date: Tue, 15 Nov 2016 09:19:19 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes On 11/14/2016 02:39 AM, Jeff Law wrote: > > > I was looking at the possibility of dropping threading from VRP1/VRP2 or > DOM1/DOM2 in favor of the backwards threader -- the obvious idea being > to recover some compile-time for gcc-7. > > Of the old-style threader passes (VRP1, VRP2, DOM1, DOM2), VRP2 is by > far the least useful. But I can't see a path to removing it in the > gcc-7 timeframe. > > Looking at what is caught by VRP and DOM threaders is quite interesting. > VRP obviously catches stuff with ranges, some fairly complex. While > you might think that querying range info in the backwards threader would > work, the problem is we lose way too much information as we drop > ASSERT_EXPRs. (Recall that the threader runs while we're still in VRP > and thus has access to the ASSERT_EXPRs). > > The DOM threaders catch stuff through state, simplifications and > bi-directional propagation of equivalences created by conditionals. > > The most obvious limitation of the backwards walking threader is that it > only looks at PHIs, copies and constant initializations. Other > statements are ignored and stop the backwards walk. > > I've got a fair amount of support for walking through unary and limited > form binary expressions that I believe can be extended based on needs. > But that's not quite ready for stage1 close. However, some of the > refactoring to make those changes easier to implement is ready. > > This patch starts to break down fsm_find_control_statement_thread_paths > into more manageable hunks. > > One such hunk is sub-path checking. Essentially we're looking to add a > range of blocks to the thread path as we move from one def site to > another in the IL. There aren't any functional changes in that > refactoring. It's really just to make f_f_c_s_t_p easier to grok. > > f_f_c_s_t_p has inline code to recursively walk backwards through PHI > nodes as well as assignments that are copies and constant initialization > terminals. Pulling that handling out results in a f_f_c_s_t_p that fits > on a page. It's just a hell of a lot easier to see what's going on. > > The handling of assignments is slightly improved in this patch. > Essentially we only considered a const initialization using an > INTEGER_CST as a proper terminal node. But certainly other constants > are useful -- ADDR_EXPR in particular and are now handled. I'll mirror > that improvement in the PHI node routines tomorrow. > > Anyway, this is really just meant to make it easier to start extending > the GIMPLE_ASSIGN handling. > > Bootstrapped and regression tested on x86_64-linux-gnu. > > I've got function comments for the new routines on a local branch. I'll > get those installed before committing. Final version attached. Only change was allowing tcc_constant rather than just INTEGER_CST in PHIs and the addition of comments. Bootstrapped and regression tested on x86, installing on the trunk. Jeff commit 4cbde473b184922d6c8423a7a63bdbb86de32b33 Author: Jeff Law Date: Tue Nov 15 09:16:26 2016 -0700 * tree-ssa-threadbackward.c (fsm_find_thread_path): Remove unneeded parameter. Callers changed. (check-subpath_and_update_thread_path): Extracted from fsm_find_control_statement_thread_paths. (handle_phi, handle_assignment, handle_assignment_p): Likewise. (handle_phi, handle_assignment): Allow any constant node, not just INTEGER_CST. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1e8475f..a54423a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2016-11-15 Jeff Law + + * tree-ssa-threadbackward.c (fsm_find_thread_path): Remove unneeded + parameter. Callers changed. + (check-subpath_and_update_thread_path): Extracted from + fsm_find_control_statement_thread_paths. + (handle_phi, handle_assignment, handle_assignment_p): Likewise. + (handle_phi, handle_assignment): Allow any constant node, not + just INTEGER_CST. + 2016-11-15 Claudiu Zissulescu * config/arc/arc-arch.h: New file. diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index fd7d855..203e20e 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -62,14 +62,12 @@ get_gimple_control_stmt (basic_block bb) /* Return true if the CFG contains at least one path from START_BB to END_BB. When a path is found, record in PATH the blocks from END_BB to START_BB. VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound - the recursion to basic blocks belonging to LOOP. - SPEED_P indicate that we could increase code size to improve the code path */ + the recursion to basic blocks belonging to LOOP. */ static bool fsm_find_thread_path (basic_block start_bb, basic_block end_bb, vec *&path, - hash_set *visited_bbs, loop_p loop, - bool speed_p) + hash_set *visited_bbs, loop_p loop) { if (loop != start_bb->loop_father) return false; @@ -85,8 +83,7 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, start_bb->succs) - if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop, - speed_p)) + if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) { vec_safe_push (path, start_bb); return true; @@ -427,6 +424,222 @@ convert_and_register_jump_thread_path (vec *path, --max_threaded_paths; } +/* While following a chain of SSA_NAME definitions, we jumped from a definition + in LAST_BB to a definition in VAR_BB (walking backwards). + + Verify there is a single path between the blocks and none of the blocks + in the path is already in VISITED_BBS. If so, then update VISISTED_BBS, + add the new blocks to PATH and return TRUE. Otherwise return FALSE. + + Store the length of the subpath in NEXT_PATH_LENGTH. */ + +static bool +check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, + hash_set *visited_bbs, + vec *&path, + int *next_path_length) +{ + edge e; + int e_count = 0; + edge_iterator ei; + vec *next_path; + vec_alloc (next_path, 10); + + FOR_EACH_EDGE (e, ei, last_bb->preds) + { + hash_set *visited_bbs = new hash_set; + + if (fsm_find_thread_path (new_bb, e->src, next_path, visited_bbs, + e->src->loop_father)) + ++e_count; + + delete visited_bbs; + + /* If there is more than one path, stop. */ + if (e_count > 1) + { + vec_free (next_path); + return false; + } + } + + /* Stop if we have not found a path: this could occur when the recursion + is stopped by one of the bounds. */ + if (e_count == 0) + { + vec_free (next_path); + return false; + } + + /* Make sure we haven't already visited any of the nodes in + NEXT_PATH. Don't add them here to avoid pollution. */ + for (unsigned int i = 0; i < next_path->length () - 1; i++) + { + if (visited_bbs->contains ((*next_path)[i])) + { + vec_free (next_path); + return false; + } + } + + /* Now add the nodes to VISISTED_BBS. */ + for (unsigned int i = 0; i < next_path->length () - 1; i++) + visited_bbs->add ((*next_path)[i]); + + /* Append all the nodes from NEXT_PATH to PATH. */ + vec_safe_splice (path, next_path); + *next_path_length = next_path->length (); + vec_free (next_path); + + return true; +} + +static void fsm_find_control_statement_thread_paths (tree, + hash_set *, + vec *&, + bool, bool); + +/* Given PHI which defines NAME in block VAR_BB, recurse through the + PHI's arguments searching for paths where NAME will ultimately have + a constant value. + + VISITED_BBS tracks the blocks that have been encountered. + + PATH contains the series of blocks to traverse that will result in + NAME having a constant value. + + SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node. + + SPEED_P indicates if we are optimizing for speed over space. */ + +static void +handle_phi (gphi *phi, tree name, basic_block var_bb, + hash_set *visited_bbs, + vec *&path, + bool seen_loop_phi, bool speed_p) +{ + /* Iterate over the arguments of PHI. */ + for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) + { + tree arg = gimple_phi_arg_def (phi, i); + basic_block bbi = gimple_phi_arg_edge (phi, i)->src; + + /* Skip edges pointing outside the current loop. */ + if (!arg || var_bb->loop_father != bbi->loop_father) + continue; + + if (TREE_CODE (arg) == SSA_NAME) + { + vec_safe_push (path, bbi); + /* Recursively follow SSA_NAMEs looking for a constant + definition. */ + fsm_find_control_statement_thread_paths (arg, visited_bbs, path, + seen_loop_phi, speed_p); + + path->pop (); + continue; + } + + if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) + continue; + + /* If this is a profitable jump thread path, then convert it + into the canonical form and register it. */ + bool irreducible = false; + edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg, + speed_p, &irreducible); + if (taken_edge) + { + convert_and_register_jump_thread_path (path, taken_edge); + path->pop (); + + if (irreducible) + vect_free_loop_info_assumptions ((*path)[0]->loop_father); + } + } +} + +/* Return TRUE if STMT is a gimple assignment we want to either directly + handle or recurse through. Return FALSE otherwise. + + Note that adding more cases here requires adding cases to handle_assignment + below. */ + +static bool +handle_assignment_p (gimple *stmt) +{ + if (is_gimple_assign (stmt)) + { + enum tree_code def_code = gimple_assign_rhs_code (stmt); + + /* If the RHS is an SSA_NAME, then we will recurse through it. + Go ahead and filter out cases where the SSA_NAME is a default + definition. There's little to be gained by trying to handle that. */ + if (def_code == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (stmt))) + return true; + + /* If the RHS is a constant, then it's a terminal that we'll want + to handle as well. */ + if (TREE_CODE_CLASS (def_code) == tcc_constant) + return true; + } + + /* Anything not explicitly allowed is not handled. */ + return false; +} + +/* Given STMT which defines NAME in block VAR_BB, recurse through the + PHI's arguments searching for paths where NAME will ultimately have + a constant value. + + VISITED_BBS tracks the blocks that have been encountered. + + PATH contains the series of blocks to traverse that will result in + NAME having a constant value. + + SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node. + + SPEED_P indicates if we are optimizing for speed over space. */ + +static void +handle_assignment (gimple *stmt, tree name, basic_block var_bb, + hash_set *visited_bbs, + vec *&path, + bool seen_loop_phi, bool speed_p) +{ + tree arg = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (arg) == SSA_NAME) + fsm_find_control_statement_thread_paths (arg, visited_bbs, + path, seen_loop_phi, speed_p); + + 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 (); + + bool irreducible = false; + edge taken_edge = profitable_jump_thread_path (path, var_bb, + name, arg, speed_p, + &irreducible); + if (taken_edge) + { + convert_and_register_jump_thread_path (path, taken_edge); + path->pop (); + + if (irreducible) + vect_free_loop_info_assumptions ((*path)[0]->loop_father); + } + + /* 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); + } +} + /* 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. @@ -461,9 +674,8 @@ fsm_find_control_statement_thread_paths (tree name, >= (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) + if (is_gimple_assign (def_stmt) + && ! handle_assignment_p (def_stmt)) return; /* Avoid infinite recursion. */ @@ -486,143 +698,25 @@ fsm_find_control_statement_thread_paths (tree name, different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */ if (var_bb != last_bb_in_path) { - edge e; - int e_count = 0; - edge_iterator ei; - vec *next_path; - vec_alloc (next_path, 10); - /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path will already be in VISITED_BBS. When they are not equal, then we must ensure that first block is accounted for to ensure we do not create bogus jump threading paths. */ visited_bbs->add ((*path)[0]); - FOR_EACH_EDGE (e, ei, last_bb_in_path->preds) - { - hash_set *visited_bbs = new hash_set; - - if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs, - e->src->loop_father, speed_p)) - ++e_count; - - delete visited_bbs; - - /* If there is more than one path, stop. */ - if (e_count > 1) - { - vec_free (next_path); - return; - } - } - - /* Stop if we have not found a path: this could occur when the recursion - is stopped by one of the bounds. */ - if (e_count == 0) - { - vec_free (next_path); - return; - } - - /* Make sure we haven't already visited any of the nodes in - NEXT_PATH. Don't add them here to avoid pollution. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - { - if (visited_bbs->contains ((*next_path)[i])) - { - vec_free (next_path); - return; - } - } - - /* Now add the nodes to VISISTED_BBS. */ - for (unsigned int i = 0; i < next_path->length () - 1; i++) - visited_bbs->add ((*next_path)[i]); - - /* Append all the nodes from NEXT_PATH to PATH. */ - vec_safe_splice (path, next_path); - next_path_length = next_path->length (); - vec_free (next_path); + if (!check_subpath_and_update_thread_path (last_bb_in_path, var_bb, + visited_bbs, path, + &next_path_length)) + return; } gcc_assert (path->last () == var_bb); - /* Iterate over the arguments of PHI. */ - unsigned int i; 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); - basic_block bbi = gimple_phi_arg_edge (phi, i)->src; - - /* Skip edges pointing outside the current loop. */ - if (!arg || var_bb->loop_father != bbi->loop_father) - continue; - - if (TREE_CODE (arg) == SSA_NAME) - { - vec_safe_push (path, bbi); - /* Recursively follow SSA_NAMEs looking for a constant - definition. */ - fsm_find_control_statement_thread_paths (arg, visited_bbs, path, - seen_loop_phi, speed_p); - - path->pop (); - continue; - } - - if (TREE_CODE (arg) != INTEGER_CST) - continue; - - /* If this is a profitable jump thread path, then convert it - into the canonical form and register it. */ - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg, - speed_p, &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } - } - } + handle_phi (as_a (def_stmt), name, var_bb, + visited_bbs, path, seen_loop_phi, speed_p); else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - { - tree arg = gimple_assign_rhs1 (def_stmt); - - if (TREE_CODE (arg) == SSA_NAME) - fsm_find_control_statement_thread_paths (arg, visited_bbs, - path, seen_loop_phi, speed_p); - - 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 (); - - bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, var_bb, - name, arg, speed_p, - &irreducible); - if (taken_edge) - { - convert_and_register_jump_thread_path (path, taken_edge); - path->pop (); - - if (irreducible) - vect_free_loop_info_assumptions ((*path)[0]->loop_father); - } - - /* 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); - } - } + handle_assignment (def_stmt, name, var_bb, + visited_bbs, path, seen_loop_phi, speed_p); /* Remove all the nodes that we added from NEXT_PATH. */ if (next_path_length) @@ -652,7 +746,7 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) else if (code == GIMPLE_COND) { if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME - && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST + && TREE_CODE_CLASS (TREE_CODE (gimple_cond_rhs (stmt))) == tcc_constant && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))) || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))) name = gimple_cond_lhs (stmt);