From patchwork Tue Aug 2 18:33:13 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1663123 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=htGn9fn2; 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 (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4Ly3Xn5t9Qz9s5W for ; Wed, 3 Aug 2022 04:33:44 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5BCE33858031 for ; Tue, 2 Aug 2022 18:33:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5BCE33858031 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1659465221; bh=ryuF/Sp/SVfYUJHx9e496N3P4P0r9qU75dFQNp3VIC8=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=htGn9fn2OG6cDzFc1eLoTZYcC5RQtW4ke91Xp0mJfNEBGjd5XLSerWY/BF3ci2P4p G6iVBnNAFK7voK1dWhabhbdQ/87YFwZgljQEJY+bF08IRUNP8J84+X5yIDZo7wjG7r iZ05ucbHhHAbaOqh/5xWpqUzRlsgss51iCA3BKjE= 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 ESMTPS id D68DB3858296 for ; Tue, 2 Aug 2022 18:33:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D68DB3858296 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-330-pp8GUKNLPwqYSduWz03mOA-1; Tue, 02 Aug 2022 14:33:17 -0400 X-MC-Unique: pp8GUKNLPwqYSduWz03mOA-1 Received: by mail-qv1-f71.google.com with SMTP id er2-20020a056214190200b00474479acbcfso8836718qvb.23 for ; Tue, 02 Aug 2022 11:33:17 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=fFh808DfGSM7525sqDeyLoH2qiSBMtPG9fJyBvqOydE=; b=M4P9EfLjyPbKCstpAne4sc08wuXAxqDGCAi5ZB7lyBW7I6djK8WfhtAOXgSzOrwYmc scBing80wuibOqTylJQpFTDPfGElMoAeXh1gsjngWUK3Qm8Lq/mOyqIws/EDIkwnawX1 SihKddkR63jQPaCLCsing4D4ZXaxKqA1AHCO6ZOvSs+0paudPd2WJNmorCtJOUMYxN4o dbo5gE8atjagvpQZEgZMf/CsykXMsgSrLIB8EkA3vvBQ3lBcM/3PTmtqPzP7GLs20UAy szjLZn3YGUrsoYYqChKlXNC+r322ki4ioe9hbqPQ+gPXnb9wTD92StV/fi/+KjUimD8e 1wVA== X-Gm-Message-State: AJIora87GWl+zvZaQnzDHd8WMNf7FF4WmC5pgHTVcWtkBKbnCYhPuotC YvpaQkwD3jVs62MvTzTGx6zkz02IHxKOv+/gEXoIrN4ZACnuMHwB8yguWdHwHcvohYujpsVFead 7Ld5tiqgNkUWiOrxDVTyJltTZslJRrVkXY1+HaYVZLAMxqO9lzvj515VjdhJxW+oZi5Hjjg== X-Received: by 2002:a05:620a:31c:b0:6b5:d5a5:687f with SMTP id s28-20020a05620a031c00b006b5d5a5687fmr16094231qkm.375.1659465196859; Tue, 02 Aug 2022 11:33:16 -0700 (PDT) X-Google-Smtp-Source: AGRyM1vfPoEWoXXGpVnhoHEcJygdWFNHOtKLvu6TyEzIfs4Z0zegsD4Eh6gNNcGp2SrHwX3ivucz1A== X-Received: by 2002:a05:620a:31c:b0:6b5:d5a5:687f with SMTP id s28-20020a05620a031c00b006b5d5a5687fmr16094211qkm.375.1659465196519; Tue, 02 Aug 2022 11:33:16 -0700 (PDT) Received: from [192.168.0.135] ([104.219.120.152]) by smtp.gmail.com with ESMTPSA id de33-20020a05620a372100b006b8b3f2772bsm3663762qkb.44.2022.08.02.11.33.14 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 02 Aug 2022 11:33:15 -0700 (PDT) Message-ID: <6ac18e26-9691-cdc1-496e-123290c3d541@redhat.com> Date: Tue, 2 Aug 2022 14:33:13 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 To: gcc-patches Subject: [COMMITTED] PR tree-optimization/106474 - Check equivalencies when calculating range on entry. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.6 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, 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This PR demonstrates a case where evaluating equivalencies can assist VRP in refining values. Previous revisions did not do this due to the expense of calculating or checking for equivalencies everytime we process a use. Earlier change to range_from_dom provided modes for the cache to query, and in particular, it has a mode which can query the DOM tree, but not update the cache.   This tends to be quite quick, and will not cause any memory increases. We can also check if an ssa-name has had any outgoing range calculated thus far, and can significantly trim the number of equivalences that need to be examined. This patch adjusts the on-entry propagator to check if there are any existing equivalence ranges before it updates the cache and returns the on-entry value to ranger. This causes a very marginal slowdown of 0.34% building gcc across the 2 VRP passes using ranger.. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew commit 53f7b80929978dd2773f58cfd0c2cfa49f54538e Author: Andrew MacLeod Date: Fri Jul 29 12:05:38 2022 -0400 Check equivalencies when calculating range on entry. When propagating on-entry values in the cache, checking if any equivalence has a known value can improve results. No new calculations are made. Only queries via dominators which do not populate the cache are checked. PR tree-optimization/106474 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Query range of equivalences that may contribute to the range. gcc/testsuite/ * g++.dg/pr106474.C: New. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index d9e160c9a2a..4782d47265e 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1211,13 +1211,56 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // Check if a dominators can supply the range. if (range_from_dom (block_result, name, bb, RFD_FILL)) { - m_on_entry.set_bb_range (name, bb, block_result); if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "Filled from dominator! : "); block_result.dump (dump_file); fprintf (dump_file, "\n"); } + // See if any equivalences can refine it. + if (m_oracle) + { + unsigned i; + bitmap_iterator bi; + // Query equivalences in read-only mode. + const_bitmap equiv = m_oracle->equiv_set (name, bb); + EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi) + { + if (i == SSA_NAME_VERSION (name)) + continue; + tree equiv_name = ssa_name (i); + basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name)); + + // Check if the equiv has any ranges calculated. + if (!m_gori.has_edge_range_p (equiv_name)) + continue; + + // Check if the equiv definition dominates this block + if (equiv_bb == bb || + (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb))) + continue; + + Value_Range equiv_range (TREE_TYPE (equiv_name)); + if (range_from_dom (equiv_range, equiv_name, bb, RFD_READ_ONLY)) + { + if (block_result.intersect (equiv_range)) + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "Equivalence update! : "); + print_generic_expr (dump_file, equiv_name, TDF_SLIM); + fprintf (dump_file, "had range : "); + equiv_range.dump (dump_file); + fprintf (dump_file, " refining range to :"); + block_result.dump (dump_file); + fprintf (dump_file, "\n"); + } + } + } + } + } + + m_on_entry.set_bb_range (name, bb, block_result); gcc_checking_assert (m_workback.length () == 0); return; } diff --git a/gcc/testsuite/g++.dg/pr106474.C b/gcc/testsuite/g++.dg/pr106474.C new file mode 100644 index 00000000000..6cd37a20643 --- /dev/null +++ b/gcc/testsuite/g++.dg/pr106474.C @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp " } */ + +void foo(); +static void __attribute__ ((noinline)) DCEMarker0_() {foo ();} + +void f(bool s, bool c) { + if ((!c == !s) && !c) { + if (s) { + DCEMarker0_(); + } + } +} + +// With equivalences, vrp should be able to remove all IFs. +/* { dg-final { scan-tree-dump-not "goto" "evrp" } } */