From patchwork Tue Nov 1 13:20:00 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 13658 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp2961302wru; Tue, 1 Nov 2022 06:21:18 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7SyYS+JuyvCNHQXPwnQZACZpn+cFFUgFR1qSWxiq79OeE2Ch9PhQp7pboDdrk6l/cqtCQk X-Received: by 2002:a17:906:4917:b0:7ad:f9d6:9435 with SMTP id b23-20020a170906491700b007adf9d69435mr201596ejq.238.1667308878074; Tue, 01 Nov 2022 06:21:18 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1667308878; cv=none; d=google.com; s=arc-20160816; b=0YtbDTWj1LF6tojFHZBQglecoo2SZFu3MDUEVJBxTlZKLTIA1HAHz2S1St27ApxX5w WfzOTfT2wW2DssKiWz8b01EgfUyrkNO7XkS92M+fhC52aaVrtUNBPEayxfP1utXffEKi 1OBOtpoLuhrM2L8aqBDHp6NyC3aU3+7NYLOAPJ8okmx3ZA48nErPlTFcXxIE12FeTjAs 3GOwt7MWVdMMMvyCSuctssgJeec9zFeayVRolgS3kpOvJbS0B1Co8uHN48YRgyoI1neT zSyJ38aDQCjzkFf00eM6wkcLrGw6cYhEfL4JmoSbwk1PS5b1KosCWLbo8ryNO6mG2YmB GfLw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=+Q9ZuumXDv4QS5WRcxE5J1/lGG9Z4gkKMWM+UInOkvc=; b=JtKZ4psY0GIdMO5LDoclkL6bnSiadXYkuhvinXa6D5aVPt7zJYCz9mQWbzlkAi5+kW dRWK8yECp2WYv1IVapR6FwCB2AcCZOH9Nh+0sRPrXYnYI0xtrlOPjoZ7r0QcdW/PLu9N cl6X9TQUsDgCl/TruI+4Ft+6GALmIbxcCFb0NLgMAYKkX6xRDE/9OvuX8wJKPYoQW+Mk 36P820k7d2wC4hsYMUn0PxAxBf45ybZaYAR6L8IJLbIuFcE2o5dKL20hqwAx1e/Q7jEt X13pHaMMgFmJZI3fku9cekO3Rsl03FeEtuAX+GBLKrz/g6CawcULw7X9AQ7n41aragZt doeQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=PmgJeuqk; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id hq13-20020a1709073f0d00b0078d8cc2006csi14099909ejc.697.2022.11.01.06.21.17 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 01 Nov 2022 06:21:18 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=PmgJeuqk; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 63B9338576A0 for ; Tue, 1 Nov 2022 13:20:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 63B9338576A0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1667308852; bh=+Q9ZuumXDv4QS5WRcxE5J1/lGG9Z4gkKMWM+UInOkvc=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=PmgJeuqk+yYFR41YeZ4da+R7fZtl4S/7bQoxJI+9tKrVCt/d/NMgQdxoBeZuTpGfV zBDFx2vQBqrjK5aOIz0N2XbXOWqnGesdP/Mq8SSMDPhtg2jzSh2QHR90Wa76uxIb7Y 7yKdRAWtKy6Fifx2oJfkjiji1HA3mxW4Cc7U/eOE= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 542F3385737B for ; Tue, 1 Nov 2022 13:20:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 542F3385737B Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-633-yn_V3gTIOq62IxQBrB_qmQ-1; Tue, 01 Nov 2022 09:20:03 -0400 X-MC-Unique: yn_V3gTIOq62IxQBrB_qmQ-1 Received: by mail-qv1-f71.google.com with SMTP id ng1-20020a0562143bc100b004bb706b3a27so7721064qvb.20 for ; Tue, 01 Nov 2022 06:20:03 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=eFfDQNS4eO+4zZk9xm90q0+FSP8cBT7XY8g5sH2VAXM=; b=nhxP2sBCZDvDIyDbgeGhJawoKO3XlwjA1L1AG2Tqwm0Ipibgk38g5ob9AfC7qAK/6T Dk4swY9rZ1JawLotclyiB4yc5Lp6qoYa7EN7+MBvGed3N+qtjW/08S06Q2fCNCGngSLV YQncyiYN4gGnFcPDehI66lVqVgCUrRdxYtX0D04KzxMtWnpDGh0SGEcnoqnZusqumew3 86gjDzebVu664njUFdHlP+wCxqAkyFMbFN8wFCyvSaZjL1Csm092LwTu3uwRet3kgPcJ zu9HhykQ3yyRxMWLYQr8Ndf8oVdRWeHEARg3kyFXT87pZ1bLg7RmSP1D33RMkNd6syQp rgag== X-Gm-Message-State: ACrzQf0Bos7810VXEHVJcIrK3pUAw/FXc7039Vd6rbQM0QEDZDeY3HVe oKGt/dFGDpafOMFdHkS/+x0VnNDqyKrp6IFBFwRfmKK5QK78gjyMr96tLMR1hWPyNAT7/U+L0MT so+Y8eMyppCn4HK/EQ9aaS3UDrU2vjFtACY66JbEkpPX1jM5cEul5Z6C10+3dR2TPZzU9JA== X-Received: by 2002:a05:620a:6083:b0:6fa:326e:9d18 with SMTP id dx3-20020a05620a608300b006fa326e9d18mr5959682qkb.5.1667308802223; Tue, 01 Nov 2022 06:20:02 -0700 (PDT) X-Received: by 2002:a05:620a:6083:b0:6fa:326e:9d18 with SMTP id dx3-20020a05620a608300b006fa326e9d18mr5959663qkb.5.1667308801859; Tue, 01 Nov 2022 06:20:01 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::72c3? ([2607:fea8:a263:f600::72c3]) by smtp.gmail.com with ESMTPSA id q25-20020a37f719000000b006fa16fe93bbsm6356797qkj.15.2022.11.01.06.20.00 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 01 Nov 2022 06:20:01 -0700 (PDT) Message-ID: <3e171105-8cae-e91d-ecc5-87c534b18cc1@redhat.com> Date: Tue, 1 Nov 2022 09:20:00 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED] Remove builtin_unreachable in ranger VRP. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.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_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1748300073945027796?= X-GMAIL-MSGID: =?utf-8?q?1748300073945027796?= Removal of __builtin_unreachable calls were being handled in an inconsistent way, and Im not convinced always correctly.   This removes them in the ranger VRP pass, and sets the global range appropriately. This new approach should be consistent. After VRP runs, it uses ranger to query all the uses of every export affected by an edge leading to an unreachable builtin. It calculates their range at those use locations, and then verifies that the range at the end of the function also reflects those restrictions. If that all holds true, then the unreachable call is removed and the global range updated.  If that does not hold true, then the global range is not set as the condition guarding the unreachable is contextual. if this is also the final VRP pass, the unreachable call is removed regardless. Otherwise it is left so other pases can still pick up the contextual ranges This will only happen when ranger is the default VRP1 pass (not enabled yet), although this code will trigger to ensure all unreachables are removed in VRP2. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 7b1cdca6d6d594a8a9d88062252212e145f2f4eb Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 31 Oct 2022 15:18:00 -0400 Subject: [PATCH 3/3] Remove builtin_unreachable in VRP Removal of __builtin_unreachable calls were handled in an inconsistent way. This removes then in the VRP pass, and sets the global range appropriately. * tree-vrp.cc (class remove_unreachable): New. (remove_unreachable::maybe_register_block): New. (remove_unreachable::remove_and_update_globals): New. (rvrp_folder::rvrp_folder): Initialize m_unreachable. (rvrp_folder::post_fold_bb): Maybe register unreachable block. (rvrp_folder::m_unreachable): New member. (execute_ranger_vrp): Add final_pass flag, remove unreachables. --- gcc/tree-vrp.cc | 190 +++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 187 insertions(+), 3 deletions(-) diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index e5a292bb875..f0e4d37bef0 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -51,6 +51,183 @@ along with GCC; see the file COPYING3. If not see #include "value-pointer-equiv.h" #include "gimple-fold.h" #include "tree-dfa.h" +#include "tree-ssa-dce.h" + +// This class is utilized by VRP and ranger to remove __builtin_unreachable +// calls, and reflect any resulting global ranges. +// +// maybe_register_block () is called on basic blocks, and if that block +// matches the pattern of one branch being a builtin_unreachable, register +// the resulting executable edge in a list. +// +// After all blocks have been processed, remove_and_update_globals() will +// - check all exports from registered blocks +// - ensure the cache entry of each export is set with the appropriate range +// - rewrite the conditions to take the executable edge +// - perform DCE on any feeding instructions to those rewritten conditions +// +// Then each of the immediate use chain of each export is walked, and a new +// global range created by unioning the ranges at all remaining use locations. + +class remove_unreachable { +public: + remove_unreachable (gimple_ranger &r) : m_ranger (r) { m_list.create (30); } + ~remove_unreachable () { m_list.release (); } + void maybe_register_block (basic_block bb); + bool remove_and_update_globals (bool final_p); + vec m_list; + gimple_ranger &m_ranger; +}; + +// Check if block BB has a __builtin_unreachable () call on one arm, and +// register the executable edge if so. + +void +remove_unreachable::maybe_register_block (basic_block bb) +{ + gimple *s = gimple_outgoing_range_stmt_p (bb); + if (!s || gimple_code (s) != GIMPLE_COND) + return; + + edge e0 = EDGE_SUCC (bb, 0); + basic_block bb0 = e0->dest; + bool un0 = EDGE_COUNT (bb0->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (bb0)); + edge e1 = EDGE_SUCC (bb, 1); + basic_block bb1 = e1->dest; + bool un1 = EDGE_COUNT (bb1->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (bb1)); + + // If the 2 blocks are not different, ignore. + if (un0 == un1) + return; + + if (un0) + m_list.safe_push (e1); + else + m_list.safe_push (e0); +} + +// Process the edges in the list, change the conditions and removing any +// dead code feeding those conditions. Calculate the range of any +// names that may have been exported from those blocks, and determine if +// there is any updates to their global ranges.. +// FINAL_P indicates all builtin_unreachable calls should be removed. +// Return true if any builtin_unreachables/globals eliminated/updated. + +bool +remove_unreachable::remove_and_update_globals (bool final_p) +{ + if (m_list.length () == 0) + return false; + + bool change = false; + tree name; + unsigned i; + bitmap_iterator bi; + auto_bitmap all_exports; + for (i = 0; i < m_list.length (); i++) + { + edge e = m_list[i]; + gimple *s = gimple_outgoing_range_stmt_p (e->src); + gcc_checking_assert (gimple_code (s) == GIMPLE_COND); + bool lhs_p = TREE_CODE (gimple_cond_lhs (s)) == SSA_NAME; + bool rhs_p = TREE_CODE (gimple_cond_rhs (s)) == SSA_NAME; + // Do not remove __builtin_unreachable if it confers a relation, or + // that relation will be lost in subsequent passes. Unless its the + // final pass. + if (!final_p && lhs_p && rhs_p) + continue; + // If this is already a constant condition, don't look either + if (!lhs_p && !rhs_p) + continue; + + bool dominate_exit_p = true; + FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori (), e->src, name) + { + // Ensure the cache is set for NAME in the succ block. + Value_Range r(TREE_TYPE (name)); + Value_Range ex(TREE_TYPE (name)); + m_ranger.range_on_entry (r, e->dest, name); + m_ranger.range_on_entry (ex, EXIT_BLOCK_PTR_FOR_FN (cfun), name); + // If the range produced by this __builtin_unreachacble expression + // is not fully reflected in the range at exit, then it does not + // dominate the exit of the funciton. + if (ex.intersect (r)) + dominate_exit_p = false; + } + + // If the exit is dominated, add to the export list. Otherwise if this + // isn't the final VRP pass, leave the call in the IL. + if (dominate_exit_p) + bitmap_ior_into (all_exports, m_ranger.gori ().exports (e->src)); + else if (!final_p) + continue; + + change = true; + // Rewrite the condition. + if (e->flags & EDGE_TRUE_VALUE) + gimple_cond_make_true (as_a (s)); + else + gimple_cond_make_false (as_a (s)); + update_stmt (s); + } + + if (bitmap_empty_p (all_exports)) + return false; + // Invoke DCE on all exported names to elimnate dead feeding defs + auto_bitmap dce; + bitmap_copy (dce, all_exports); + // Don't attempt to DCE parameters. + EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi) + if (SSA_NAME_IS_DEFAULT_DEF (ssa_name (i))) + bitmap_clear_bit (dce, i); + simple_dce_from_worklist (dce); + + // Loop over all uses of each name and find maximal range. This is the + // new global range. + use_operand_p use_p; + imm_use_iterator iter; + EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi) + { + name = ssa_name (i); + if (!name || SSA_NAME_IN_FREE_LIST (name)) + continue; + Value_Range r (TREE_TYPE (name)); + Value_Range exp_range (TREE_TYPE (name)); + r.set_undefined (); + FOR_EACH_IMM_USE_FAST (use_p, iter, name) + { + gimple *use_stmt = USE_STMT (use_p); + if (is_gimple_debug (use_stmt)) + continue; + if (!m_ranger.range_of_expr (exp_range, name, use_stmt)) + exp_range.set_varying (TREE_TYPE (name)); + r.union_ (exp_range); + if (r.varying_p ()) + break; + } + // Include the on-exit range to ensure non-dominated unreachables + // don't incorrectly impact the global range. + m_ranger.range_on_entry (exp_range, EXIT_BLOCK_PTR_FOR_FN (cfun), name); + r.union_ (exp_range); + if (r.varying_p () || r.undefined_p ()) + continue; + if (!set_range_info (name, r)) + continue; + change = true; + if (dump_file) + { + fprintf (dump_file, "Global Exported (via unreachable): "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " = "); + gimple_range_global (r, name); + r.dump (dump_file); + fputc ('\n', dump_file); + } + } + return change; +} /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ @@ -4260,6 +4437,7 @@ class rvrp_folder : public substitute_and_fold_engine public: rvrp_folder (gimple_ranger *r) : substitute_and_fold_engine (), + m_unreachable (*r), m_simplifier (r, r->non_executable_edge_flag) { m_ranger = r; @@ -4312,6 +4490,8 @@ public: void post_fold_bb (basic_block bb) override { m_pta->leave (bb); + if (cfun->after_inlining) + m_unreachable.maybe_register_block (bb); } void pre_fold_stmt (gimple *stmt) override @@ -4328,6 +4508,7 @@ public: return ret; } + remove_unreachable m_unreachable; private: DISABLE_COPY_AND_ASSIGN (rvrp_folder); gimple_ranger *m_ranger; @@ -4339,7 +4520,8 @@ private: from anywhere to perform a VRP pass, including from EVRP. */ unsigned int -execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p) +execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, + bool final_p) { loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); @@ -4350,6 +4532,8 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p) gimple_ranger *ranger = enable_ranger (fun, false); rvrp_folder folder (ranger); folder.substitute_and_fold (); + // Remove tagged builtin-unreachable and maybe update globals. + folder.m_unreachable.remove_and_update_globals (final_p); if (dump_file && (dump_flags & TDF_DETAILS)) ranger->dump (dump_file); @@ -4428,11 +4612,11 @@ public: { // Early VRP pass. if (my_pass == 0) - return execute_ranger_vrp (fun, /*warn_array_bounds_p=*/false); + return execute_ranger_vrp (fun, /*warn_array_bounds_p=*/false, false); if ((my_pass == 1 && param_vrp1_mode == VRP_MODE_RANGER) || (my_pass == 2 && param_vrp2_mode == VRP_MODE_RANGER)) - return execute_ranger_vrp (fun, warn_array_bounds_p); + return execute_ranger_vrp (fun, warn_array_bounds_p, my_pass == 2); return execute_vrp (fun, warn_array_bounds_p); } -- 2.37.3