From patchwork Fri Oct 15 14:25:36 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1541719 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.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=sTZKbUWH; dkim-atps=neutral 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=) 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 bilbo.ozlabs.org (Postfix) with ESMTPS id 4HW7qz3vdMz9sR4 for ; Sat, 16 Oct 2021 01:26:39 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0A0913857C70 for ; Fri, 15 Oct 2021 14:26:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0A0913857C70 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1634307997; bh=5rNXz1fs05d5+ckSAjDacKKkKlpoED5x7xMXssCiSo4=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=sTZKbUWHLnErtT5b6lP/uIMMLdkd92f49481BlthUNt0ZrzbLDJG9M5lsVf4qseLi 3h+YOeScuoSWQcpb58zy9+QACj2MzHIiWKVWD5p8S/Fg9Epd/eahc1CgN+NqURQ5Fn vcS17su2Z8mUztpm2KAIYqccITdbBpHbX9iwO20E= 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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 1E80A385802D for ; Fri, 15 Oct 2021 14:25:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1E80A385802D 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-253-HMPPDJK2N0GUFZ4ZeRUCYA-1; Fri, 15 Oct 2021 10:25:53 -0400 X-MC-Unique: HMPPDJK2N0GUFZ4ZeRUCYA-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 B4E9A101B4A0; Fri, 15 Oct 2021 14:25:52 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.195.66]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 8F5AF708E0; Fri, 15 Oct 2021 14:25:42 +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 19FEPdSs324539 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 15 Oct 2021 16:25:40 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 19FEPd34324538; Fri, 15 Oct 2021 16:25:39 +0200 To: GCC patches , Jeff Law Subject: [PATCH] Allow fully resolving backward jump threading passes. Date: Fri, 15 Oct 2021 16:25:36 +0200 Message-Id: <20211015142535.324483-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.1 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, RCVD_IN_MSPIKE_H2, 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" This refactors the backward threader pass so that it can be called in either fully resolving mode, or in classic mode where any unknowns default to VARYING. Doing so opens the door for "pass_thread_jumps_full" which has the resolving bits set. This pass has not been added to the pipeline, but with it in place, we can now experiment with it to see how to reduce the number of jump threaders. The first suspect will probably be enabling fully resolving in the backward threader pass immediately preceeding VRP2, and removing the VRP2 threader pass. Now that VRP and the backward threader are sharing a solver, and most of the threads get handcuffed by cancel_threads(), we should have a variety of scenarios to try. In the process, I have cleaned up things to make it trivial to see what the difference between the 3 variants are (early jump threading, quick jump threading without resolving SSAs, and fully resolving jump threading). Since I moved stuff around, it's probably easier to just look at the last section in tree-ssa-threadbackward to see how it's all laid out. No functional changes as the new pass hasn't been added to the pipeline. OK pending tests? gcc/ChangeLog: * tree-pass.h (make_pass_thread_jumps_full): New. * tree-ssa-threadbackward.c (pass_thread_jumps::gate): Inline. (try_thread_blocks): Add resolve and speed arguments. (pass_thread_jumps::execute): Inline. (do_early_thread_jumps): New. (do_thread_jumps): New. (make_pass_thread_jumps): (pass_early_thread_jumps::gate): Inline. (pass_early_thread_jumps::execute): Inline. (class pass_thread_jumps_full): New. --- gcc/tree-pass.h | 1 + gcc/tree-ssa-threadbackward.c | 178 ++++++++++++++++++++-------------- 2 files changed, 108 insertions(+), 71 deletions(-) diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 84477a47b88..d379769a943 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -407,6 +407,7 @@ extern gimple_opt_pass *make_pass_cd_dce (gcc::context *ctxt); extern gimple_opt_pass *make_pass_call_cdce (gcc::context *ctxt); extern gimple_opt_pass *make_pass_merge_phi (gcc::context *ctxt); extern gimple_opt_pass *make_pass_thread_jumps (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_thread_jumps_full (gcc::context *ctxt); extern gimple_opt_pass *make_pass_early_thread_jumps (gcc::context *ctxt); extern gimple_opt_pass *make_pass_split_crit_edges (gcc::context *ctxt); extern gimple_opt_pass *make_pass_laddress (gcc::context *ctxt); diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 8cc92a484fe..62f936a9651 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -114,7 +114,7 @@ private: static const edge UNREACHABLE_EDGE; // Set to TRUE if unknown SSA names along a path should be resolved // with the ranger. Otherwise, unknown SSA names are assumed to be - // VARYING. Setting to true more precise but slower. + // VARYING. Setting to true is more precise but slower. bool m_resolve; }; @@ -925,47 +925,15 @@ back_threader_registry::register_path (const vec &m_path, return true; } -namespace { - -const pass_data pass_data_thread_jumps = -{ - GIMPLE_PASS, - "thread", - OPTGROUP_NONE, - TV_TREE_SSA_THREAD_JUMPS, - ( PROP_cfg | PROP_ssa ), - 0, - 0, - 0, - TODO_update_ssa, -}; - -class pass_thread_jumps : public gimple_opt_pass -{ -public: - pass_thread_jumps (gcc::context *ctxt) - : gimple_opt_pass (pass_data_thread_jumps, ctxt) - {} - - opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); } - virtual bool gate (function *); - virtual unsigned int execute (function *); -}; - -bool -pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) -{ - return flag_thread_jumps && flag_expensive_optimizations; -} - -// Try to thread blocks in FUN. Return TRUE if any jump thread paths were -// registered. +// Try to thread blocks in FUN. RESOLVE is TRUE when fully resolving +// unknown SSAs. SPEED is TRUE when optimizing for speed. +// +// Return TRUE if any jump thread paths were registered. static bool -try_thread_blocks (function *fun) +try_thread_blocks (function *fun, bool resolve, bool speed) { - /* Try to thread each block with more than one successor. */ - back_threader threader (/*speed=*/true, /*resolve=*/false); + back_threader threader (speed, resolve); basic_block bb; FOR_EACH_BB_FN (bb, fun) { @@ -975,24 +943,27 @@ try_thread_blocks (function *fun) return threader.thread_through_all_blocks (/*peel_loop_headers=*/true); } -unsigned int -pass_thread_jumps::execute (function *fun) +static unsigned int +do_early_thread_jumps (function *fun, bool resolve) { - loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); + loop_optimizer_init (AVOID_CFG_MODIFICATIONS); - bool changed = try_thread_blocks (fun); + try_thread_blocks (fun, resolve, /*speed=*/false); loop_optimizer_finalize (); - - return changed ? TODO_cleanup_cfg : 0; -} - + return 0; } -gimple_opt_pass * -make_pass_thread_jumps (gcc::context *ctxt) +static unsigned int +do_thread_jumps (function *fun, bool resolve) { - return new pass_thread_jumps (ctxt); + loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); + + bool changed = try_thread_blocks (fun, resolve, /*speed=*/true); + + loop_optimizer_finalize (); + + return changed ? TODO_cleanup_cfg : 0; } namespace { @@ -1010,6 +981,33 @@ const pass_data pass_data_early_thread_jumps = ( TODO_cleanup_cfg | TODO_update_ssa ), }; +const pass_data pass_data_thread_jumps = +{ + GIMPLE_PASS, + "thread", + OPTGROUP_NONE, + TV_TREE_SSA_THREAD_JUMPS, + ( PROP_cfg | PROP_ssa ), + 0, + 0, + 0, + TODO_update_ssa, +}; + +const pass_data pass_data_thread_jumps_full = +{ + GIMPLE_PASS, + "thread-full", + OPTGROUP_NONE, + TV_TREE_SSA_THREAD_JUMPS, + ( PROP_cfg | PROP_ssa ), + 0, + 0, + 0, + TODO_update_ssa, +}; + +// Early jump threading pass optimizing for size. class pass_early_thread_jumps : public gimple_opt_pass { public: @@ -1017,36 +1015,74 @@ public: : gimple_opt_pass (pass_data_early_thread_jumps, ctxt) {} - opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); } - virtual bool gate (function *); - virtual unsigned int execute (function *); + opt_pass * clone () override + { + return new pass_early_thread_jumps (m_ctxt); + } + bool gate (function *) override + { + return flag_thread_jumps; + } + unsigned int execute (function *fun) override + { + return do_early_thread_jumps (fun, /*resolve=*/false); + } }; -bool -pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED) +// Jump threading pass without resolving of unknown SSAs. +class pass_thread_jumps : public gimple_opt_pass { - return flag_thread_jumps; -} +public: + pass_thread_jumps (gcc::context *ctxt) + : gimple_opt_pass (pass_data_thread_jumps, ctxt) + {} + opt_pass * clone (void) override + { + return new pass_thread_jumps (m_ctxt); + } + bool gate (function *) override + { + return flag_thread_jumps && flag_expensive_optimizations; + } + unsigned int execute (function *fun) override + { + return do_thread_jumps (fun, /*resolve=*/false); + } +}; -unsigned int -pass_early_thread_jumps::execute (function *fun) +// Jump threading pass that fully resolves unknown SSAs. +class pass_thread_jumps_full : public gimple_opt_pass { - loop_optimizer_init (AVOID_CFG_MODIFICATIONS); +public: + pass_thread_jumps_full (gcc::context *ctxt) + : gimple_opt_pass (pass_data_thread_jumps_full, ctxt) + {} + opt_pass * clone (void) override + { + return new pass_thread_jumps (m_ctxt); + } + bool gate (function *) override + { + return flag_thread_jumps && flag_expensive_optimizations; + } + unsigned int execute (function *fun) override + { + return do_thread_jumps (fun, /*resolve=*/true); + } +}; - /* Try to thread each block with more than one successor. */ - back_threader threader (/*speed_p=*/false, /*resolve=*/false); - basic_block bb; - FOR_EACH_BB_FN (bb, fun) - { - if (EDGE_COUNT (bb->succs) > 1) - threader.maybe_thread_block (bb); - } - threader.thread_through_all_blocks (/*peel_loop_headers=*/true); +} // namespace { - loop_optimizer_finalize (); - return 0; +gimple_opt_pass * +make_pass_thread_jumps (gcc::context *ctxt) +{ + return new pass_thread_jumps (ctxt); } +gimple_opt_pass * +make_pass_thread_jumps_full (gcc::context *ctxt) +{ + return new pass_thread_jumps_full (ctxt); } gimple_opt_pass *