From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 48FD83858D1E for ; Mon, 19 Sep 2022 11:19:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 48FD83858D1E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 353182237D; Mon, 19 Sep 2022 11:19:16 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1663586356; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=Z6hmGr+tc5xGNiWfaxh6WQk3bIut1j/rrWAg84kWlqU=; b=0e2odaYvhZwn9ZJipPTs0c0XL0pIxhgBvwVNcNLXeWTVnOTu1ttwQsg7wAoyWxZyuiEJYO OpQwrQM5u+a+ZzRZrET9qlJfjj2YJaTpIsL/1pYT8JqWrn/NpsW5FSN0kcjnsHl//SpvBJ w3ztJZko4u206FYzpTE95JzS38EEEdo= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1663586356; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=Z6hmGr+tc5xGNiWfaxh6WQk3bIut1j/rrWAg84kWlqU=; b=w1j9OHPbGsDQ7sLagsH5qoh3bne3We8mmeTnyvNyaBc/8sha5B0SBQ15AKbVize6o6rJL9 EZVHKTUqWcrzKuAw== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 192EE13A96; Mon, 19 Sep 2022 11:19:16 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id bFXPBDRQKGPTCAAAMHmgww (envelope-from ); Mon, 19 Sep 2022 11:19:16 +0000 Date: Mon, 19 Sep 2022 13:19:15 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: aldyh@redhat.com, amacleod@redhat.com Subject: [PATCH][RFH] Wire ranger into FRE MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20220919111916.192EE13A96@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,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 List-Id: The following is an attempt to utilize ranger for simplification of conditionals during value-numbering. It fails the added testcase because it seems the fur source is only involved when processing the stmt to be folded but not when filling the cache of ranges on the operand use->def chain. When not iterating that's not a problem since earlier stmts have operands eliminated but when not iterating or when elimination is disabled the IL remains unchanged. When iterating it will probably do things wrong due to the lack of pruning the chache for the region we unwind and when doing region based VN it likely picks up stale EDGE_EXECUTABLE when leaving the region over the entry because there's no way to stop "local" cache prefilling when leaving the region (and just using global ranges from there). Knowing path-range-query it's probably possible to clone all the block walking and cache filling, making a special variant for value-numbering but I wonder whether that's really what's intended? I would probably need to implement a special range_of_expr and range_of_stmt for this and keep my own cache? Basically a region_range_query with wired in valueization? * tree-ssa-sccvn.cc (...): ... --- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c | 15 ++++ gcc/tree-ssa-sccvn.cc | 77 ++++++++++++++++++--- gcc/tree-ssa-sccvn.h | 3 +- 3 files changed, 83 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c new file mode 100644 index 00000000000..f479a322b70 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-100.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-fre1" } */ + +int foo (int *p, int *q) +{ + if (*p > 0 && *q > 0) + { + int v = *p + *q; + if (v > 0) + return *q; + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "known outgoing edge" 1 "fre1" } } */ diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc index 74b8d8d18ef..2753200c2c2 100644 --- a/gcc/tree-ssa-sccvn.cc +++ b/gcc/tree-ssa-sccvn.cc @@ -73,6 +73,7 @@ along with GCC; see the file COPYING3. If not see #include "fold-const-call.h" #include "ipa-modref-tree.h" #include "ipa-modref.h" +#include "gimple-range.h" #include "tree-ssa-sccvn.h" /* This algorithm is based on the SCC algorithm presented by Keith @@ -360,10 +361,11 @@ static vn_ssa_aux_t last_pushed_avail; correct. */ static vn_tables_t valid_info; +tree (*vn_valueize) (tree); /* Valueization hook for simplify_replace_tree. Valueize NAME if it is an SSA name, otherwise just return it. */ -tree (*vn_valueize) (tree); + static tree vn_valueize_for_srt (tree t, void* context ATTRIBUTE_UNUSED) { @@ -380,6 +382,36 @@ vn_valueize_for_srt (tree t, void* context ATTRIBUTE_UNUSED) return res; } +class vn_fur : public fur_depend +{ +public: + vn_fur (gimple *s, gori_compute *g, range_query *q) + : fur_depend (s, g, q) {} + virtual bool get_operand (vrange &, tree); + virtual bool get_phi_operand (vrange &, tree, edge); +}; + +bool +vn_fur::get_operand (vrange &r, tree op) +{ + return fur_depend::get_operand (r, vn_valueize (op)); +} + +bool +vn_fur::get_phi_operand (vrange &r, tree op, edge e) +{ + // ??? Check region boundary, avoid walking ourside of the region + // somehow? Possibly when initializing the ranger object? + // or can/should we simply return 'false' when we arrive with + // e being the entry edge? What about for non-PHIs? Can we + // somehow force to only use the global range and stop caching + // after that? + if (e->flags & EDGE_EXECUTABLE) + return fur_depend::get_phi_operand (r, vn_valueize (op), e); + r.set_undefined (); + return true; +} + /* This represents the top of the VN lattice, which is the universal value. */ @@ -7292,12 +7324,12 @@ eliminate_with_rpo_vn (bitmap inserted_exprs) static unsigned do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, - bool iterate, bool eliminate, vn_lookup_kind kind); + bool iterate, bool eliminate, vn_lookup_kind kind, gimple_ranger *); void run_rpo_vn (vn_lookup_kind kind) { - do_rpo_vn_1 (cfun, NULL, NULL, true, false, kind); + do_rpo_vn_1 (cfun, NULL, NULL, true, false, kind, NULL); /* ??? Prune requirement of these. */ constant_to_value_id = new hash_table (23); @@ -7580,7 +7612,8 @@ insert_related_predicates_on_edge (enum tree_code code, tree *ops, edge pred_e) static unsigned process_bb (rpo_elim &avail, basic_block bb, bool bb_visited, bool iterate_phis, bool iterate, bool eliminate, - bool do_region, bitmap exit_bbs, bool skip_phis) + bool do_region, bitmap exit_bbs, bool skip_phis, + gimple_ranger *ranger) { unsigned todo = 0; edge_iterator ei; @@ -7766,6 +7799,20 @@ process_bb (rpo_elim &avail, basic_block bb, } } } + if (!val && ranger) + { + int_range_max r; + fold_using_range f; + // ??? We get here with not valueized operands but + // the fur_source only is involved for operands of + // this very stmt, not when ranger prefills its cache + // walking use->def edges. + vn_fur src (last, &ranger->gori (), ranger); + tree tem; + if (f.fold_stmt (r, last, src) + && r.singleton_p (&tem)) + val = tem; + } if (val) e = find_taken_edge (bb, val); if (! e) @@ -7997,7 +8044,8 @@ do_unwind (unwind_state *to, rpo_elim &avail) static unsigned do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, - bool iterate, bool eliminate, vn_lookup_kind kind) + bool iterate, bool eliminate, vn_lookup_kind kind, + gimple_ranger *ranger) { unsigned todo = 0; default_vn_walk_kind = kind; @@ -8213,7 +8261,8 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, todo |= process_bb (avail, bb, rpo_state[idx].visited != 0, rpo_state[idx].iterate, - iterate, eliminate, do_region, exit_bbs, false); + iterate, eliminate, do_region, exit_bbs, false, + ranger); rpo_state[idx].visited++; /* Verify if changed values flow over executable outgoing backedges @@ -8326,7 +8375,8 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, nblk++; todo |= process_bb (avail, bb, false, false, false, eliminate, do_region, exit_bbs, - skip_entry_phis && bb == entry->dest); + skip_entry_phis && bb == entry->dest, + ranger); rpo_state[idx].visited++; FOR_EACH_EDGE (e, ei, bb->succs) @@ -8419,14 +8469,17 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs, If ITERATE is true then treat backedges optimistically as not executed and iterate. If ELIMINATE is true then perform elimination, otherwise leave that to the caller. - KIND specifies the amount of work done for handling memory operations. */ + KIND specifies the amount of work done for handling memory operations. + When RANGER is specified use that to simplify conditionals. */ unsigned do_rpo_vn (function *fn, edge entry, bitmap exit_bbs, - bool iterate, bool eliminate, vn_lookup_kind kind) + bool iterate, bool eliminate, vn_lookup_kind kind, + gimple_ranger *ranger) { auto_timevar tv (TV_TREE_RPO_VN); - unsigned todo = do_rpo_vn_1 (fn, entry, exit_bbs, iterate, eliminate, kind); + unsigned todo = do_rpo_vn_1 (fn, entry, exit_bbs, iterate, eliminate, kind, + ranger); free_rpo_vn (); return todo; } @@ -8482,7 +8535,9 @@ pass_fre::execute (function *fun) if (iterate_p) loop_optimizer_init (AVOID_CFG_MODIFICATIONS); - todo = do_rpo_vn_1 (fun, NULL, NULL, iterate_p, true, VN_WALKREWRITE); + gimple_ranger ranger; + todo = do_rpo_vn_1 (fun, NULL, NULL, iterate_p, true, VN_WALKREWRITE, + &ranger); //!iterate_p ? &ranger : NULL); free_rpo_vn (); if (iterate_p) diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h index abcf7e666c2..b9c4ac787b4 100644 --- a/gcc/tree-ssa-sccvn.h +++ b/gcc/tree-ssa-sccvn.h @@ -298,7 +298,8 @@ tree vn_nary_simplify (vn_nary_op_t); unsigned do_rpo_vn (function *, edge, bitmap, /* iterate */ bool = false, /* eliminate */ bool = true, - vn_lookup_kind = VN_WALKREWRITE); + vn_lookup_kind = VN_WALKREWRITE, + class gimple_ranger * = NULL); /* Private interface for PRE. */ void run_rpo_vn (vn_lookup_kind); -- 2.35.3