From patchwork Thu Aug 5 09:48:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1513846 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=xWVpUOWa; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GgP3H3MyPz9sCD for ; Thu, 5 Aug 2021 19:49:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 91157384403E for ; Thu, 5 Aug 2021 09:49:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 91157384403E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1628156983; bh=Zmpq9+ZgNHLW4D9AoO6AGGdanWMxFhl2Ar8nWlvR8uE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=xWVpUOWa0fWaenOMQk5JZ54FCmOiM+vsz1PcfhEkVclVxDLyiG4/XJ/MxOHEnoIf3 okl1CP8wHmvUfIqBNHHBurF38RXu6D2xLFrLcrgg/FjORgdmKPW1Rt+xDrnXDjtVMa b2WfjtQxC2vXiP9tS8q0AwtFdxUHel0oRbSyZSaA= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 67A76386483D for ; Thu, 5 Aug 2021 09:48:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 67A76386483D Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-388-PqVIEDUlOsi1QP8o3vTYFg-1; Thu, 05 Aug 2021 05:48:56 -0400 X-MC-Unique: PqVIEDUlOsi1QP8o3vTYFg-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D456E760C6; Thu, 5 Aug 2021 09:48:55 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.158]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 37D82781EB; Thu, 5 Aug 2021 09:48:55 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 1759mq9m3143064 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Thu, 5 Aug 2021 11:48:52 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 1759mpL33143063; Thu, 5 Aug 2021 11:48:51 +0200 To: GCC patches , Jeff Law Subject: [PATCH] Remove legacy back threader. Date: Thu, 5 Aug 2021 11:48:22 +0200 Message-Id: <20210805094821.3143012-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" At this point I don't see any use for the legacy mode, which I had originally left in place during the transition. This patch removes the legacy back threader, and cleans up the code a bit. There are no functional changes to the non-legacy code. Tested on x86-64 Linux. OK? gcc/ChangeLog: * doc/invoke.texi: Remove docs for threader-mode param. * flag-types.h (enum threader_mode): Remove. * params.opt: Remove threader-mode param. * tree-ssa-threadbackward.c (class back_threader): Remove path_is_unreachable_p. Make find_paths private. Add maybe_thread and thread_through_all_blocks. Remove reference marker for m_registry. Remove reference marker for m_profit. (back_threader::back_threader): Adjust for registry and profit not being references. (dump_path): Move down. (debug): Move down. (class thread_jumps): Remove. (class back_threader_registry): Remove m_all_paths. Remove destructor. (thread_jumps::thread_through_all_blocks): Move to back_threader class. (fsm_find_thread_path): Remove (back_threader::maybe_thread): New. (back_threader::thread_through_all_blocks): Move from thread_jumps. (back_threader_registry::back_threader_registry): Remove m_all_paths. (back_threader_registry::~back_threader_registry): Remove. (thread_jumps::find_taken_edge): Remove. (thread_jumps::check_subpath_and_update_thread_path): Remove. (thread_jumps::maybe_register_path): Remove. (thread_jumps::handle_phi): Remove. (handle_assignment_p): Remove. (thread_jumps::handle_assignment): Remove. (thread_jumps::fsm_find_control_statement_thread_paths): Remove. (thread_jumps::find_jump_threads_backwards): Remove. (thread_jumps::find_jump_threads_backwards_with_ranger): Remove. (try_thread_blocks): Rename find_jump_threads_backwards to maybe_thread. (pass_early_thread_jumps::execute): Same. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Remove call into the legacy code and adjust for ranger threader. --- gcc/doc/invoke.texi | 3 - gcc/flag-types.h | 7 - gcc/params.opt | 13 - .../gcc.dg/tree-ssa/ssa-dom-thread-7.c | 3 +- gcc/tree-ssa-threadbackward.c | 539 ++---------------- 5 files changed, 61 insertions(+), 504 deletions(-) diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 4efc8b757ec..65bb9981f02 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -13421,9 +13421,6 @@ Setting to 0 disables the analysis completely. @item modref-max-escape-points Specifies the maximum number of escape points tracked by modref per SSA-name. -@item threader-mode -Specifies the mode the backwards threader should run in. - @item profile-func-internal-id A parameter to control whether to use function internal id in profile database lookup. If the value is 0, the compiler uses an id that diff --git a/gcc/flag-types.h b/gcc/flag-types.h index e39673f6716..e43d1de490d 100644 --- a/gcc/flag-types.h +++ b/gcc/flag-types.h @@ -454,13 +454,6 @@ enum evrp_mode EVRP_MODE_RVRP_DEBUG = EVRP_MODE_RVRP_ONLY | EVRP_MODE_DEBUG }; -/* Backwards threader mode. */ -enum threader_mode -{ - THREADER_MODE_LEGACY = 0, - THREADER_MODE_RANGER = 1 -}; - /* Modes of OpenACC 'kernels' constructs handling. */ enum openacc_kernels { diff --git a/gcc/params.opt b/gcc/params.opt index aa2fb4047b6..92b003e38cb 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -1010,19 +1010,6 @@ Maximum depth of DFS walk used by modref escape analysis. Common Joined UInteger Var(param_modref_max_escape_points) Init(256) Param Optimization Maximum number of escape points tracked by modref per SSA-name. --param=threader-mode= -Common Joined Var(param_threader_mode) Enum(threader_mode) Init(THREADER_MODE_RANGER) Param Optimization ---param=threader-mode=[legacy|ranger] Specifies the mode the backwards threader should run in. - -Enum -Name(threader_mode) Type(enum threader_mode) UnknownError(unknown threader mode %qs) - -EnumValue -Enum(threader_mode) String(legacy) Value(THREADER_MODE_LEGACY) - -EnumValue -Enum(threader_mode) String(ranger) Value(THREADER_MODE_RANGER) - -param=tm-max-aggregate-size= Common Joined UInteger Var(param_tm_max_aggregate_size) Init(9) Param Optimization Size in bytes after which thread-local aggregates should be instrumented with the logging functions instead of save/restore pairs. 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 1c2d12aa9ea..5fc2145a432 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,6 +1,5 @@ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-thread1-stats -fdump-tree-thread2-stats -fdump-tree-dom2-stats -fdump-tree-thread3-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats -fno-guess-branch-probability" } */ -/* { dg-additional-options "--param=threader-mode=legacy" } */ /* Here we have the same issue as was commented in ssa-dom-thread-6.c. The PHI coming into the threader has a lot more constants, so the @@ -17,7 +16,7 @@ $ diff clean/a.c.105t.mergephi2 a.c.105t.mergephi2 basically tracking the switch index better through multiple paths. */ -/* { dg-final { scan-tree-dump "Jumps threaded: 19" "thread1" } } */ +/* { dg-final { scan-tree-dump "Jumps threaded: 18" "thread1" } } */ /* { dg-final { scan-tree-dump "Jumps threaded: 8" "thread2" } } */ /* { dg-final { scan-tree-dump-not "Jumps threaded" "dom2" } } */ diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 91ce443b1b2..266b98a39e2 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -51,12 +51,10 @@ class back_threader_registry { public: back_threader_registry (int max_allowable_paths); - ~back_threader_registry (); bool register_path (const vec &, edge taken); bool thread_through_all_blocks (); private: - vec> m_all_paths; jump_thread_path_registry m_lowlevel_registry; const int m_max_allowable_paths; int m_threaded_paths; @@ -77,19 +75,16 @@ private: const bool m_speed_p; }; -// Ranger based backwards threader. - class back_threader { - // Temporary until we remove old code. - friend bool path_is_unreachable_p (const vec &); - public: - back_threader (back_threader_profitability &, back_threader_registry &); + back_threader (bool speed_p); ~back_threader (); - void find_paths (basic_block bb, tree name); + void maybe_thread (basic_block bb); + bool thread_through_all_blocks (); private: + void find_paths (basic_block bb, tree name); void maybe_register_path (edge taken_edge); bool find_paths_to_names (basic_block bb, bitmap imports); bool resolve_def (tree name, bitmap interesting, vec worklist); @@ -98,8 +93,8 @@ private: edge find_taken_edge_cond (const vec &path, gcond *); edge find_taken_edge_switch (const vec &path, gswitch *); - back_threader_registry &m_registry; - back_threader_profitability &m_profit; + back_threader_registry m_registry; + back_threader_profitability m_profit; gimple_ranger m_ranger; path_range_query m_solver; @@ -123,10 +118,9 @@ private: // in a the given direction. const edge back_threader::UNREACHABLE_EDGE = (edge) -1; -back_threader::back_threader (back_threader_profitability &profit, - back_threader_registry ®istry) - : m_registry (registry), - m_profit (profit), +back_threader::back_threader (bool speed_p) + : m_registry (param_max_fsm_thread_paths), + m_profit (speed_p), m_solver (m_ranger) { m_last_stmt = NULL; @@ -456,74 +450,9 @@ back_threader::find_paths (basic_block bb, tree name) } } -// Dump a sequence of BBs through the CFG. - -DEBUG_FUNCTION void -dump_path (FILE *dump_file, const vec &path) -{ - for (size_t i = 0; i < path.length (); ++i) - { - fprintf (dump_file, "BB%d", path[i]->index); - if (i + 1 < path.length ()) - fprintf (dump_file, " <- "); - } - fprintf (dump_file, "\n"); -} - -DEBUG_FUNCTION void -debug (const vec &path) -{ - dump_path (stderr, path); -} - -class thread_jumps -{ -public: - thread_jumps (bool speed_p = true) - : m_profit (speed_p), - m_registry (param_max_fsm_thread_paths), - m_back_threader (m_profit, m_registry) - { } - void find_jump_threads_backwards (basic_block bb); - void find_jump_threads_backwards_with_ranger (basic_block bb); - bool thread_through_all_blocks (); - -private: - void maybe_register_path (const vec &m_path, - tree name, - edge taken_edge); - edge find_taken_edge (const vec &path, tree arg); - void handle_assignment (gimple *stmt, basic_block def_bb); - void handle_phi (gphi *phi, basic_block def_bb); - void fsm_find_control_statement_thread_paths (tree name); - bool check_subpath_and_update_thread_path (basic_block last_bb, - basic_block new_bb, - int *next_path_length); - - /* Hash to keep track of seen bbs. */ - hash_set m_visited_bbs; - /* Current path we're analyzing. */ - auto_vec m_path; - /* Tracks if we have recursed through a loop PHI node. */ - bool m_seen_loop_phi; - - tree m_name; - back_threader_profitability m_profit; - back_threader_registry m_registry; - back_threader m_back_threader; -}; - -// Perform the actual jump threading for the all queued paths. - -bool -thread_jumps::thread_through_all_blocks () -{ - return m_registry.thread_through_all_blocks (); -} - -/* Simple helper to get the last statement from BB, which is assumed - to be a control statement. Return NULL if the last statement is - not a control statement. */ +// Simple helper to get the last statement from BB, which is assumed +// to be a control statement. Return NULL if the last statement is +// not a control statement. static gimple * get_gimple_control_stmt (basic_block bb) @@ -540,55 +469,65 @@ get_gimple_control_stmt (basic_block bb) return NULL; } -/* 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. LOCAL_VISITED_BBS is used to make sure we - don't fall into an infinite loop. Bound the recursion to basic - blocks belonging to LOOP. */ +// Search backwards from BB looking for paths where the final +// conditional maybe threaded to a successor block. Record such paths +// for jump threading. -static bool -fsm_find_thread_path (basic_block start_bb, basic_block end_bb, - vec &path, - hash_set &local_visited_bbs, - loop_p loop) +void +back_threader::maybe_thread (basic_block bb) { - if (loop != start_bb->loop_father) - return false; + gimple *stmt = get_gimple_control_stmt (bb); + if (!stmt) + return; - if (start_bb == end_bb) - { - path.safe_push (start_bb); - return true; - } + enum gimple_code code = gimple_code (stmt); + tree name; + if (code == GIMPLE_SWITCH) + name = gimple_switch_index (as_a (stmt)); + else if (code == GIMPLE_COND) + name = gimple_cond_lhs (stmt); + else if (code == GIMPLE_GOTO) + name = gimple_goto_dest (stmt); + else + name = NULL; - if (!local_visited_bbs.add (start_bb)) + find_paths (bb, name); +} + +// Perform the actual jump threading for the all queued paths. + +bool +back_threader::thread_through_all_blocks () +{ + return m_registry.thread_through_all_blocks (); +} + +// Dump a sequence of BBs through the CFG. + +DEBUG_FUNCTION void +dump_path (FILE *dump_file, const vec &path) +{ + for (size_t i = 0; i < path.length (); ++i) { - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, start_bb->succs) - if (fsm_find_thread_path (e->dest, end_bb, path, local_visited_bbs, - loop)) - { - path.safe_push (start_bb); - return true; - } + fprintf (dump_file, "BB%d", path[i]->index); + if (i + 1 < path.length ()) + fprintf (dump_file, " <- "); } + fprintf (dump_file, "\n"); +} - return false; +DEBUG_FUNCTION void +debug (const vec &path) +{ + dump_path (stderr, path); } back_threader_registry::back_threader_registry (int max_allowable_paths) : m_max_allowable_paths (max_allowable_paths) { - m_all_paths.create (5); m_threaded_paths = 0; } -back_threader_registry::~back_threader_registry () -{ - m_all_paths.release (); -} - bool back_threader_registry::thread_through_all_blocks () { @@ -881,39 +820,6 @@ back_threader_profitability::profitable_path_p (const vec &m_path, return true; } -/* Return the taken edge out of a path, assuming that the underlying assignment - or PHI SSA resolves to ARG. */ - -edge -thread_jumps::find_taken_edge (const vec &path, tree arg) -{ - if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) - return NULL; - - gcc_checking_assert (!path.is_empty ()); - gimple *stmt = get_gimple_control_stmt (m_path[0]); - - /* We have found a constant value for ARG. For GIMPLE_SWITCH - and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND - we need to substitute, fold and simplify so we can determine - the edge taken out of the last block. */ - if (gimple_code (stmt) == GIMPLE_COND) - { - enum tree_code cond_code = gimple_cond_code (stmt); - - /* We know the underyling format of the condition. */ - arg = fold_binary (cond_code, boolean_type_node, - arg, gimple_cond_rhs (stmt)); - } - - /* If this path threaded through the loop latch back into the - same loop and the destination does not dominate the loop - latch, then this thread would create an irreducible loop. - - We have to know the outgoing edge to figure this out. */ - return ::find_taken_edge (m_path[0], arg); -} - /* The current path PATH is a vector of blocks forming a jump threading path in reverse order. TAKEN_EDGE is the edge taken from path[0]. @@ -962,331 +868,6 @@ back_threader_registry::register_path (const vec &m_path, return true; } -/* While following a chain of SSA_NAME definitions, we jumped from a - definition in LAST_BB to a definition in NEW_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. */ - -bool -thread_jumps::check_subpath_and_update_thread_path (basic_block last_bb, - basic_block new_bb, - int *next_path_length) -{ - edge e; - int e_count = 0; - edge_iterator ei; - auto_vec next_path; - - FOR_EACH_EDGE (e, ei, last_bb->preds) - { - hash_set local_visited_bbs; - - if (fsm_find_thread_path (new_bb, e->src, next_path, - local_visited_bbs, e->src->loop_father)) - ++e_count; - - /* If there is more than one path, stop. */ - if (e_count > 1) - 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) - 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 + 1 < next_path.length (); i++) - { - if (m_visited_bbs.contains (next_path[i])) - return false; - } - - /* Now add the nodes to VISISTED_BBS. */ - for (unsigned int i = 0; i + 1 < next_path.length (); i++) - m_visited_bbs.add (next_path[i]); - - /* Append all the nodes from NEXT_PATH to PATH. */ - m_path.safe_splice (next_path); - *next_path_length = next_path.length (); - - return true; -} - -/* If this is a profitable jump thread path, register it. - - NAME is an SSA NAME with a possible constant value of ARG on PATH. - - DEF_BB is the basic block that ultimately defines the constant. */ - -void -thread_jumps::maybe_register_path (const vec &m_path, - tree name, - edge taken_edge) -{ - bool irreducible = false; - bool profitable = m_profit.profitable_path_p (m_path, name, taken_edge, - &irreducible); - if (profitable) - { - if (!m_registry.register_path (m_path, taken_edge)) - return; - - if (irreducible) - vect_free_loop_info_assumptions (m_path[0]->loop_father); - } -} - -/* Given PHI which defines NAME in block DEF_BB, recurse through the - PHI's arguments searching for paths where NAME will ultimately have - a constant value. - - PATH contains the series of blocks to traverse that will result in - NAME having a constant value. */ - -void -thread_jumps::handle_phi (gphi *phi, basic_block def_bb) -{ - /* 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 || def_bb->loop_father != bbi->loop_father) - continue; - - if (TREE_CODE (arg) == SSA_NAME) - { - m_path.safe_push (bbi); - /* Recursively follow SSA_NAMEs looking for a constant - definition. */ - fsm_find_control_statement_thread_paths (arg); - - m_path.pop (); - continue; - } - - m_path.safe_push (bbi); - edge taken_edge = find_taken_edge (m_path, arg); - if (taken_edge) - maybe_register_path (m_path, m_name, taken_edge); - m_path.pop (); - } -} - -/* 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 DEF_BB, recurse through the - PHI's arguments searching for paths where NAME will ultimately have - a constant value. - - PATH contains the series of blocks to traverse that will result in - NAME having a constant value. */ - -void -thread_jumps::handle_assignment (gimple *stmt, basic_block def_bb) -{ - tree arg = gimple_assign_rhs1 (stmt); - - if (TREE_CODE (arg) == SSA_NAME) - fsm_find_control_statement_thread_paths (arg); - else - { - if (CHECKING_P) - { - gcc_assert (!m_path.is_empty ()); - basic_block top = m_path[m_path.length () - 1]; - gcc_assert (top == def_bb); - } - edge taken_edge = find_taken_edge (m_path, arg); - if (taken_edge) - maybe_register_path (m_path, m_name, taken_edge); - } -} - -/* 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. */ - -void -thread_jumps::fsm_find_control_statement_thread_paths (tree name) -{ - /* If NAME appears in an abnormal PHI, then don't try to trace its - value back through PHI nodes. */ - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) - return; - - gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block def_bb = gimple_bb (def_stmt); - - if (def_bb == NULL) - return; - - /* We allow the SSA chain to contains PHIs and simple copies and constant - initializations. */ - if (gimple_code (def_stmt) != GIMPLE_PHI - && gimple_code (def_stmt) != GIMPLE_ASSIGN) - return; - - if (gimple_code (def_stmt) == GIMPLE_PHI - && (gimple_phi_num_args (def_stmt) - >= (unsigned) param_fsm_maximum_phi_arguments)) - return; - - if (is_gimple_assign (def_stmt) - && ! handle_assignment_p (def_stmt)) - return; - - /* Avoid infinite recursion. */ - if (m_visited_bbs.add (def_bb)) - return; - - int next_path_length = 0; - basic_block last_bb_in_path = m_path.last (); - - if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt)) - { - /* Do not walk through more than one loop PHI node. */ - if (m_seen_loop_phi) - return; - m_seen_loop_phi = true; - } - - /* Following the chain of SSA_NAME definitions, we jumped from a definition in - LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are - different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */ - if (def_bb != last_bb_in_path) - { - /* When DEF_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. */ - m_visited_bbs.add (m_path[0]); - if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb, - &next_path_length)) - return; - } - - gcc_assert (m_path.last () == def_bb); - - if (gimple_code (def_stmt) == GIMPLE_PHI) - handle_phi (as_a (def_stmt), def_bb); - else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - handle_assignment (def_stmt, def_bb); - - /* Remove all the nodes that we added from NEXT_PATH. */ - if (next_path_length) - m_path.truncate (m_path.length () - next_path_length); -} - -/* Search backwards from BB looking for paths where NAME (an SSA_NAME) - is a constant. Record such paths for jump threading. - - It is assumed that BB ends with a control statement and that by - finding a path where NAME is a constant, we can thread the path. - SPEED_P indicates that we could increase code size to improve the - code path. */ - -void -thread_jumps::find_jump_threads_backwards (basic_block bb) -{ - if (param_threader_mode & THREADER_MODE_RANGER) - { - find_jump_threads_backwards_with_ranger (bb); - return; - } - - gimple *stmt = get_gimple_control_stmt (bb); - if (!stmt) - return; - - enum gimple_code code = gimple_code (stmt); - tree name = NULL; - if (code == GIMPLE_SWITCH) - name = gimple_switch_index (as_a (stmt)); - else if (code == GIMPLE_GOTO) - name = gimple_goto_dest (stmt); - else if (code == GIMPLE_COND) - { - if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME - && 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); - } - - if (!name || TREE_CODE (name) != SSA_NAME) - return; - - /* Initialize pass local data that's different for each BB. */ - m_path.truncate (0); - m_path.safe_push (bb); - m_visited_bbs.empty (); - m_seen_loop_phi = false; - m_name = name; - - fsm_find_control_statement_thread_paths (name); -} - -// Like find_jump_threads_backwards(), but using ranger. - -void -thread_jumps::find_jump_threads_backwards_with_ranger (basic_block bb) -{ - gimple *stmt = get_gimple_control_stmt (bb); - if (!stmt) - return; - - enum gimple_code code = gimple_code (stmt); - tree name = NULL; - if (code == GIMPLE_SWITCH) - name = gimple_switch_index (as_a (stmt)); - else if (code == GIMPLE_GOTO) - name = gimple_goto_dest (stmt); - else if (code == GIMPLE_COND) - name = gimple_cond_lhs (stmt); - - m_name = name; - m_back_threader.find_paths (bb, name); -} - namespace { const pass_data pass_data_thread_jumps = @@ -1327,12 +908,12 @@ static bool try_thread_blocks (function *fun) { /* Try to thread each block with more than one successor. */ - thread_jumps threader; + back_threader threader (/*speed_p=*/true); basic_block bb; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - threader.find_jump_threads_backwards (bb); + threader.maybe_thread (bb); } return threader.thread_through_all_blocks (); } @@ -1397,12 +978,12 @@ pass_early_thread_jumps::execute (function *fun) loop_optimizer_init (AVOID_CFG_MODIFICATIONS); /* Try to thread each block with more than one successor. */ - thread_jumps threader (/*speed_p=*/false); + back_threader threader (/*speed_p=*/false); basic_block bb; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - threader.find_jump_threads_backwards (bb); + threader.maybe_thread (bb); } threader.thread_through_all_blocks ();