From patchwork Tue Nov 8 00:23:01 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1701041 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.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: legolas.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=roL+0+xS; 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 ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4N5pjl6pjGz23lW for ; Tue, 8 Nov 2022 11:23:35 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DDB19385842A for ; Tue, 8 Nov 2022 00:23:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DDB19385842A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1667867011; bh=KrNw/lhM1GQSAtEzbQoKWDGkiC7hahhoL3hvUUvG9Ns=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=roL+0+xSLTCI0dLkjOai9b7mnhct3g6H2pJZU7WE1iq3CSmg6VfTKlreQ+fhrjvBv jRKwIGCcqyro7yvpcQ+Oa5EfARFVAZIRqeDRiD0kJjkh/mBzIy0c8vt5hB30WSfIS4 cCyqJ0wQu7p4Fd//ehtpm7t2Al2l5wa7E0lpPyoE= 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 ABF9E3858C2F for ; Tue, 8 Nov 2022 00:23:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org ABF9E3858C2F Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-672-UEQZooUjNzihAelFv0zQOg-1; Mon, 07 Nov 2022 19:23:06 -0500 X-MC-Unique: UEQZooUjNzihAelFv0zQOg-1 Received: by mail-qk1-f198.google.com with SMTP id bl21-20020a05620a1a9500b006fa35db066aso11552158qkb.19 for ; Mon, 07 Nov 2022 16:23:06 -0800 (PST) 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=oVg0a26N3XmKl0mG5h04vAQbhAgUNykvvNzp8A2vm/8=; b=ORV3brJV5kvMyVhgFX8hUMKK901iGvezwdmsYV0LyiMC/f+Ip3aQcZKZnaEi8qKyR6 l/Oh/eZ0vz+wKYUi5bU6qf9rsxerR//lv3SDrx1j+C7gnxnpp4tUc5lSIFNzXgRElzxT OZdQzupVefle2uNniMNxI37UKrKLBWVEaRodj0YyV6kgDThN4mxh6ASSbh8nUV6hjmCQ hysyG9MHuQ7bOepgZWEJTS6r6hZc7hxpiTEJD9YS5o3FJcycS4kO8NYASSmrFbFinlKJ UKzaeYkljAAbFKsGDRvOUDwN0nd+RxzuFiKZu9zDnQ4FaemcnVlsJf6SZdxOFrO/9MmA xIfA== X-Gm-Message-State: ACrzQf1C1n93yXx/DITA2pXm+SzOdTZjekxT4x7Mg/km4XlL4cw7z+S5 w+1EZRsnalplMgqiajbTK6q1cHGfYyDlKe0bdCOIu01xzBK0I2XGKeGHQvlEywpKFXl17jI/osK d/AdVfBOpTRjTCBfJjWGD1CjhAzV2p5ziUXPen8bT9Nl+lwS5orxKhDghpAjZy9psZyfNYA== X-Received: by 2002:a0c:90a2:0:b0:47b:6b36:f94a with SMTP id p31-20020a0c90a2000000b0047b6b36f94amr47977201qvp.26.1667866984761; Mon, 07 Nov 2022 16:23:04 -0800 (PST) X-Google-Smtp-Source: AMsMyM6jlMQIrGOQRhynxGp2f5BDDOlPDS8hSkh0OzN5pyC3x9QmiLaGEXAoG//Dz+xjqUG/GO5GbA== X-Received: by 2002:a0c:90a2:0:b0:47b:6b36:f94a with SMTP id p31-20020a0c90a2000000b0047b6b36f94amr47977180qvp.26.1667866984400; Mon, 07 Nov 2022 16:23:04 -0800 (PST) Received: from [192.168.0.135] ([104.219.120.208]) by smtp.gmail.com with ESMTPSA id d14-20020ac851ce000000b0035d08c1da35sm7163506qtn.45.2022.11.07.16.23.02 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Nov 2022 16:23:03 -0800 (PST) Message-ID: <3a76b0ec-98eb-503a-c8f1-8dd5946435b3@redhat.com> Date: Mon, 7 Nov 2022 19:23:01 -0500 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 Cc: "hernandez, aldy" Subject: [COMMITTED] PR tree-optimization/104530 - Add transitive inferred range processing. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.8 required=5.0 tests=BAYES_00, BODY_8BITS, 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" During VRP block walk, global ranges are "finalized" during the walk.  The statement will never be revisited, so the global becomes unchanging. we add inferred ranges when operands of a statement imply further value restrictions.  The most common of these is a de-reference of a pointer implies non-null. These inferred ranges can potentially have transitive effects on values which have already been calculated. Its a form of recalculation, but only effects things after the inferred range. ie:   b.0_1 = b;   _2 = b.0_1 == 0B;  // _2 global range is [0,1]   _3 = (int) _2;       // _3 global range is [0,1]   c = _3;   _5 = *b.0_1;      // b.0_1 is now [1, +INF]   a = _5;   d.3_7 = d;   _8 = _3 % d.3_7;   if (_8 != 0) after the assignment to _5, b.0_1 has a inferred range of non-zero. when we evaluate _8, we only know that _3 is [0,1], therefore _8 is [0,1]  and we cannot fold the following condition. This patch introduces a check before we evaluate the final condition where we check if any inferred ranges introduced in the block affect any of the global values that were calculated.  If they do, the stateemnt is reevalauted using the inferred ranges, and if the result is better, that range is also added as a "transitive" inferred range. In the above case, we register the inferred range for b.0_1:    on-exit update b.0_1 in BB2 : [irange] int * [1, +INF] And then before evaluating the final condition, make a pass thru the block and add the "transitive" inferred ranges: Checking for transitive inferred ranges in BB 2    on-exit update _2 in BB2 : [irange] _Bool [0, 0] NONZERO 0x0    on-exit update _3 in BB2 : [irange] int [0, 0] NONZERO 0x0    on-exit update _8 in BB2 : [irange] int [0, 0] NONZERO 0x0 which then allows us to fold the statement without impacting the global values. Inferred ranges are available to all on-exit calculations, and thus will feed any following blocks. Performance is reasonable, with a less than 1% hit to VRP, and 0.03% overall. Bootstrapped on x86_64-pc-linux-gnu with no regeressions. Pushed. Andrew commit c838119946c9f75f1e42f4320275355822cc86fc Author: Andrew MacLeod Date: Mon Nov 7 15:07:35 2022 -0500 Add transitive inferred range processing. Rewalk statements at the end of a block to see if any inferred ranges affect earlier calculations and register those as inferred ranges. gcc/ PR tree-optimization/104530 * gimple-range-cache.cc (ranger_cache::register_inferred_value): New. Split from: (ranger_cache::apply_inferred_ranges): Move setting cache to separate function. * gimple-range-cache.h (register_inferred_value): New prototype. * gimple-range-infer.cc (infer_range_manager::has_range_p): New. * gimple-range-infer.h (has_range_p): New prototype. * gimple-range.cc (register_transitive_inferred_ranges): New. * gimple-range.h (register_transitive_inferred_ranges): New proto. * tree-vrp.cc (rvrp_folder::fold_stmt): Check for transitive inferred ranges at the end of the block before folding final stmt. gcc/testsuite/ * gcc.dg/pr104530.c: New. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 89e2403acce..ce5a0c8155e 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1544,8 +1544,27 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, return true; } -// This routine is used during a block walk to move the state of non-null for -// any operands on stmt S to nonnull. +// This routine will register an inferred value in block BB, and possibly +// update the on-entry cache if appropriate. + +void +ranger_cache::register_inferred_value (const vrange &ir, tree name, + basic_block bb) +{ + Value_Range r (TREE_TYPE (name)); + if (!m_on_entry.get_bb_range (r, name, bb)) + exit_range (r, name, bb, RFD_READ_ONLY); + if (r.intersect (ir)) + { + m_on_entry.set_bb_range (name, bb, r); + // If this range was invariant before, remove invariance. + if (!m_gori.has_edge_range_p (name)) + m_gori.set_range_invariant (name, false); + } +} + +// This routine is used during a block walk to adjust any inferred ranges +// of operands on stmt S. void ranger_cache::apply_inferred_ranges (gimple *s) @@ -1574,17 +1593,6 @@ ranger_cache::apply_inferred_ranges (gimple *s) tree name = infer.name (x); m_exit.add_range (name, bb, infer.range (x)); if (update) - { - Value_Range r (TREE_TYPE (name)); - if (!m_on_entry.get_bb_range (r, name, bb)) - exit_range (r, name, bb, RFD_READ_ONLY); - if (r.intersect (infer.range (x))) - { - m_on_entry.set_bb_range (name, bb, r); - // If this range was invariant before, remove invariance. - if (!m_gori.has_edge_range_p (name)) - m_gori.set_range_invariant (name, false); - } - } + register_inferred_value (infer.range (x), name, bb); } } diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 45053b5873a..8e3ae8f58c6 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -87,6 +87,7 @@ public: void propagate_updated_value (tree name, basic_block bb); + void register_inferred_value (const vrange &r, tree name, basic_block bb); void apply_inferred_ranges (gimple *s); gori_compute m_gori; infer_range_manager m_exit; diff --git a/gcc/gimple-range-infer.cc b/gcc/gimple-range-infer.cc index 010b34a6bde..8714ef2ed41 100644 --- a/gcc/gimple-range-infer.cc +++ b/gcc/gimple-range-infer.cc @@ -252,6 +252,17 @@ infer_range_manager::get_nonzero (tree name) return *(m_nonzero[v]); } +// Return TRUE if there are any range inferences in block BB. + +bool +infer_range_manager::has_range_p (basic_block bb) +{ + if (bb->index >= (int)m_on_exit.length ()) + return false; + bitmap b = m_on_exit[bb->index].m_names; + return b && !bitmap_empty_p (b); +} + // Return TRUE if NAME has a range inference in block BB. bool diff --git a/gcc/gimple-range-infer.h b/gcc/gimple-range-infer.h index adfe1fd8c69..10705e046d3 100644 --- a/gcc/gimple-range-infer.h +++ b/gcc/gimple-range-infer.h @@ -62,6 +62,7 @@ public: void add_range (tree name, basic_block bb, const vrange &r); void add_nonzero (tree name, basic_block bb); bool has_range_p (tree name, basic_block bb); + bool has_range_p (basic_block bb); bool maybe_adjust_range (vrange &r, tree name, basic_block bb); private: class exit_range_head diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 806386918bd..2885d0fa21e 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -482,6 +482,54 @@ gimple_ranger::register_inferred_ranges (gimple *s) m_cache.apply_inferred_ranges (s); } +// This function will walk the statements in BB to determine if any +// discovered inferred ranges in the block have any transitive effects, +// and if so, register those effects in BB. + +void +gimple_ranger::register_transitive_inferred_ranges (basic_block bb) +{ + // Return if there are no inferred ranges in BB. + infer_range_manager &infer = m_cache.m_exit; + if (!infer.has_range_p (bb)) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n", + bb->index); + + for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); + gsi_next (&si)) + { + gimple *s = gsi_stmt (si); + tree lhs = gimple_get_lhs (s); + // If the LHS alreayd has an inferred effect, leave it be. + if (!gimple_range_ssa_p (lhs) || infer.has_range_p (lhs, bb)) + continue; + // Pick up global value. + Value_Range g (TREE_TYPE (lhs)); + range_of_expr (g, lhs); + + // If either dependency has an inferred range, check if recalculating + // the LHS is different than the global value. If so, register it as + // an inferred range as well. + Value_Range r (TREE_TYPE (lhs)); + r.set_undefined (); + tree name1 = gori ().depend1 (lhs); + tree name2 = gori ().depend2 (lhs); + if ((name1 && infer.has_range_p (name1, bb)) + || (name2 && infer.has_range_p (name2, bb))) + { + // Check if folding S produces a different result. + if (fold_range (r, s, this) && g != r) + { + infer.add_range (lhs, bb, r); + m_cache.register_inferred_value (r, lhs, bb); + } + } + } +} + // When a statement S has changed since the result was cached, re-evaluate // and update the global cache. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 22e05f645f8..dfe8199b8b0 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -62,6 +62,7 @@ public: auto_edge_flag non_executable_edge_flag; bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); void register_inferred_ranges (gimple *s); + void register_transitive_inferred_ranges (basic_block bb); protected: bool fold_range_internal (vrange &r, gimple *s, tree name); void prefill_name (vrange &r, tree name); diff --git a/gcc/testsuite/gcc.dg/pr104530.c b/gcc/testsuite/gcc.dg/pr104530.c new file mode 100644 index 00000000000..1ec10154e1b --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr104530.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void foo(void); + +static int a, *b = &a, c, d = 1; + +int main() { + c = 0 == b; + a = *b; + if (c % d) + for (; d; --d) + foo(); + b = 0; +} + + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */ + diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 39f7eb7a75e..3393c73a7db 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -4501,6 +4501,15 @@ public: bool fold_stmt (gimple_stmt_iterator *gsi) override { + gimple *s = gsi_stmt (*gsi); + // If this is a block ending condition, and there are inferred ranges, + // reparse the block to see if there are any transitive inferred ranges. + if (is_a (s)) + { + basic_block bb = gimple_bb (s); + if (bb && s == gimple_outgoing_range_stmt_p (bb)) + m_ranger->register_transitive_inferred_ranges (bb); + } bool ret = m_simplifier.simplify (gsi); if (!ret) ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);