From patchwork Tue Aug 9 08:22:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 56613 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 49470385782C for ; Tue, 9 Aug 2022 08:23:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 49470385782C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660033391; bh=wNQU169ZatXkrwE7FvRyCkAUq/gl4SpAZCZ00+VsVfM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=lC7ynnMbDp1D4T8uDNBzIzL8o4+4ytFDtzpXpoTp6RQnh9/i18PfdF3QVkYlRbf/+ CszirVvkx1fuvg8AZVFtQ3PvR5elDR7jEX80hQVH78s0PN+LFq77qfXtdu9WzjRu9C RZcLzjlitErPkWjXQL6cHd4iXzmzFQ2xSh6o85Mo= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id CB0BD3858C20 for ; Tue, 9 Aug 2022 08:22:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CB0BD3858C20 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id CF1D61FB82 for ; Tue, 9 Aug 2022 08:22:40 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id C90052C196 for ; Tue, 9 Aug 2022 08:22:40 +0000 (UTC) Date: Tue, 9 Aug 2022 08:22:40 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/2] tree-optimization/106514 - add --param max-jump-thread-paths User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220809082311.49470385782C@sourceware.org> The following adds a limit for the exponential greedy search of the backwards jump threader. The idea is to limit the search space in a way that the paths considered are the same if the search were in BFS order rather than DFS. In particular it stops considering incoming edges into a block if the product of the in-degrees of blocks on the path exceeds the specified limit. When considering the low stmt copying limit of 7 (or 1 in the size optimize case) this means the degenerate case with maximum search space is a sequence of conditions with no actual code B1 |\ | empty |/ B2 |\ ... Bn |\ GIMPLE_CONDs are costed 2, an equivalent GIMPLE_SWITCH already 4, so we reach 7 already with 3 middle conditions (B1 and Bn do not count). The search space would be 2^4 == 16 to reach this. The FSM threads historically allowed for a thread length of 10 but is really looking for a single multiway branch threaded across the backedge. I've chosen the default of the new parameter to 64 which effectively limits the outdegree of the switch statement (the cases reaching the backedge) to that number (divided by 2 until I add some special pruning for FSM threads due to the loop header indegree). The testcase ssa-dom-thread-7.c requires 56 at the moment (as said, some special FSM thread pruning of considered edges would bring it down to half of that), but we now get one more threading and quite some more in later threadfull. This testcase seems to be difficult to check for expected transforms. The new testcases add the degenerate case we currently thread (without deciding whether that's a good idea ...) plus one with an approripate limit that should prevent the threading. This obsoletes the mentioned --param max-fsm-thread-length but I am not removing it as part of this patch. When the search space is limited the thread stmt size limit effectively provides max-fsm-thread-length. The param with its default does not help PR106514 enough to unleash path searching with the higher FSM stmt count limit. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/106514 * params.opt (max-jump-thread-paths): New. * doc/invoke.texi (max-jump-thread-paths): Document. * tree-ssa-threadbackward.cc (back_threader::find_paths_to_names): Honor max-jump-thread-paths, take overall_path argument. (back_threader::find_paths): Pass 1 as initial overall_path. * gcc.dg/tree-ssa/ssa-thread-16.c: New testcase. * gcc.dg/tree-ssa/ssa-thread-17.c: Likewise. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust. --- gcc/doc/invoke.texi | 7 ++++++ gcc/params.opt | 4 ++++ .../gcc.dg/tree-ssa/ssa-dom-thread-7.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c | 24 +++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c | 7 ++++++ gcc/tree-ssa-threadbackward.cc | 20 +++++++++++----- 6 files changed, 57 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 92f7aaead74..f01696696bf 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -14754,6 +14754,13 @@ optimizing. Maximum number of statements allowed in a block that needs to be duplicated when threading jumps. +@item max-jump-thread-paths +The maximum number of paths to consider when searching for jump threading +opportunities. When arriving at a block incoming edges are only considered +if the number of paths to be searched sofar multiplied by the incoming +edge degree does not exhaust the specified maximum number of paths to +consider. + @item max-fields-for-field-sensitive Maximum number of fields in a structure treated in a field sensitive manner during pointer analysis. diff --git a/gcc/params.opt b/gcc/params.opt index 2f9c9cf27dd..132987343c6 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -582,6 +582,10 @@ Bound on the number of iterations the brute force # of iterations analysis algor Common Joined UInteger Var(param_max_jump_thread_duplication_stmts) Init(15) Param Optimization Maximum number of statements allowed in a block that needs to be duplicated when threading jumps. +-param=max-jump-thread-paths= +Common Joined UInteger Var(param_max_jump_thread_paths) Init(64) IntegerRange(1, 65536) Param Optimization +Search space limit for the backwards jump threader. + -param=max-last-value-rtl= Common Joined UInteger Var(param_max_last_value_rtl) Init(10000) Param Optimization The maximum number of RTL nodes that can be recorded as combiner's last value. 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 aa06db5e223..47b8fdfa29a 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 @@ -11,7 +11,7 @@ to change decisions in switch expansion which in turn can expose new jump threading opportunities. Skip the later tests on aarch64. */ /* { dg-final { scan-tree-dump-not "Jumps threaded" "dom3" { target { ! aarch64*-*-* } } } } */ -/* { dg-final { scan-tree-dump "Jumps threaded: 8" "thread2" { target { ! aarch64*-*-* } } } } */ +/* { dg-final { scan-tree-dump "Jumps threaded: 9" "thread2" { target { ! aarch64*-*-* } } } } */ /* { dg-final { scan-tree-dump "Jumps threaded: 18" "thread2" { target { aarch64*-*-* } } } } */ enum STATE { diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c new file mode 100644 index 00000000000..f96170b073d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-16.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-threadfull1-details" } */ + +int res; +void foo (int a, int b, int c, int d, int e) +{ + if (a > 100) + res = 3; + if (b != 5) + res = 5; + if (c == 29) + res = 7; + if (d < 2) + res = 9; + /* Accounting whoes makes this not catched. */ +#if 0 + if (e != 37) + res = 11; +#endif + if (a < 10) + res = 13; +} + +/* { dg-final { scan-tree-dump "SUCCESS" "threadfull1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c new file mode 100644 index 00000000000..94ee6666788 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-17.c @@ -0,0 +1,7 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-threadfull1-details --param max-jump-thread-paths=15" } */ + +#include "ssa-thread-16.c" + +/* With limiting the search space we should no longer consider this path. */ +/* { dg-final { scan-tree-dump-not "SUCCESS" "threadfull1" } } */ diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index 0acbfb0624c..bb1ef514abf 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -90,7 +90,7 @@ private: bool debug_counter (); edge maybe_register_path (); void maybe_register_path_dump (edge taken_edge); - void find_paths_to_names (basic_block bb, bitmap imports); + void find_paths_to_names (basic_block bb, bitmap imports, unsigned); edge find_taken_edge (const vec &path); edge find_taken_edge_cond (const vec &path, gcond *); edge find_taken_edge_switch (const vec &path, gswitch *); @@ -337,9 +337,12 @@ back_threader::find_taken_edge_cond (const vec &path, // INTERESTING bitmap, and register any such paths. // // BB is the current path being processed. +// +// OVERALL_PATHS is the search space up to this block void -back_threader::find_paths_to_names (basic_block bb, bitmap interesting) +back_threader::find_paths_to_names (basic_block bb, bitmap interesting, + unsigned overall_paths) { if (m_visited_bbs.add (bb)) return; @@ -352,8 +355,10 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting) || maybe_register_path ())) ; - // Continue looking for ways to extend the path - else + // Continue looking for ways to extend the path but limit the + // search space along a branch + else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds)) + <= (unsigned)param_max_jump_thread_paths) { // For further greedy searching we want to remove interesting // names defined in BB but add ones on the PHI edges for the @@ -407,7 +412,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting) unwind.quick_push (def); } } - find_paths_to_names (e->src, new_interesting); + find_paths_to_names (e->src, new_interesting, overall_paths); // Restore new_interesting. We leave m_imports alone since // we do not prune defs in BB from it and separately keeping // track of which bits to unwind isn't worth the trouble. @@ -417,6 +422,9 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting) } } } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " FAIL: Search space limit %d reached.\n", + param_max_jump_thread_paths); // Reset things to their original state. m_path.pop (); @@ -447,7 +455,7 @@ back_threader::find_paths (basic_block bb, tree name) auto_bitmap interesting; bitmap_copy (interesting, m_imports); - find_paths_to_names (bb, interesting); + find_paths_to_names (bb, interesting, 1); } } From patchwork Tue Aug 9 08:23:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 56614 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4331D385782C for ; Tue, 9 Aug 2022 08:24:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4331D385782C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660033445; bh=pvPuALInt3cf/Fq3N4msHyn97LohJfoSd2r7Rzd2iC8=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=FnLZsmGKAHqiqKmmuyNpob+1hrMxu7/Z6qTkT+SreaJG81qA/5bjWSII7m5LfA1Fx NexYUTBT3CtqrZ2qUapcqkQvaKU691IiNyXYnwrQ77eL43UE2XMidGPbBhZADjA5Kq 0sdJuitB2uzihmwI2i4KDxhe5S4IWQfGA27uAFHc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 0A7C13858025 for ; Tue, 9 Aug 2022 08:23:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0A7C13858025 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 3B35B20067 for ; Tue, 9 Aug 2022 08:23:35 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 3677C2C196 for ; Tue, 9 Aug 2022 08:23:35 +0000 (UTC) Date: Tue, 9 Aug 2022 08:23:35 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [PATCH 2/2] Remove --param max-fsm-thread-length User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Message-Id: <20220809082405.4331D385782C@sourceware.org> This removes max-fsm-thread-length which is obsoleted by max-jump-thread-paths. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * doc/invoke.texi (max-fsm-thread-length): Remove. * params.opt (max-fsm-thread-length): Likewise. * tree-ssa-threadbackward.cc (back_threader_profitability::profitable_path_p): Do not check max-fsm-thread-length. --- gcc/doc/invoke.texi | 3 --- gcc/params.opt | 4 ---- gcc/tree-ssa-threadbackward.cc | 9 --------- 3 files changed, 16 deletions(-) diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index f01696696bf..58e422041e4 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -15262,9 +15262,6 @@ Emit instrumentation calls to __tsan_func_entry() and __tsan_func_exit(). Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path. -@item max-fsm-thread-length -Maximum number of basic blocks on a jump thread path. - @item threader-debug threader-debug=[none|all] Enables verbose dumping of the threader solver. diff --git a/gcc/params.opt b/gcc/params.opt index 132987343c6..201b5c9f56f 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -498,10 +498,6 @@ The maximum number of nested indirect inlining performed by early inliner. Common Joined UInteger Var(param_max_fields_for_field_sensitive) Param Maximum number of fields in a structure before pointer analysis treats the structure as a single variable. --param=max-fsm-thread-length= -Common Joined UInteger Var(param_max_fsm_thread_length) Init(10) IntegerRange(1, 999999) Param Optimization -Maximum number of basic blocks on a jump thread path. - -param=max-fsm-thread-path-insns= Common Joined UInteger Var(param_max_fsm_thread_path_insns) Init(100) IntegerRange(1, 999999) Param Optimization Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path. diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index bb1ef514abf..741c923e1a6 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -568,15 +568,6 @@ back_threader_profitability::profitable_path_p (const vec &m_path, if (m_path.length () <= 1) return false; - if (m_path.length () > (unsigned) param_max_fsm_thread_length) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " FAIL: Jump-thread path not considered: " - "the number of basic blocks on the path " - "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n"); - return false; - } - int n_insns = 0; gimple_stmt_iterator gsi; loop_p loop = m_path[0]->loop_father;