From patchwork Mon Sep 19 11:19:15 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1295 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5044:0:0:0:0:0 with SMTP id h4csp909610wrt; Mon, 19 Sep 2022 04:20:04 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6zFiqfTzAbVoGuqpaB7hnKeCOgIkL7y1Aay82LoTTaqtaOYbvDGNB4B8bewHyXxsAqFGMy X-Received: by 2002:a17:906:5d06:b0:77f:f4e8:f342 with SMTP id g6-20020a1709065d0600b0077ff4e8f342mr12647237ejt.729.1663586403851; Mon, 19 Sep 2022 04:20:03 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1663586403; cv=none; d=google.com; s=arc-20160816; b=YFXk0J2Pk06G4/ksS5zlZMWw7ZvHlL1mxpfPOLL4oSEplnNmbyRk2QuYKHq5mKuAw5 qiFb7CjkYU9Hy6uGs34he8bDRchhBHbXTi0qxo9VzQeMSybTLEV1CheqAtbVGvX2qrWp 2NJPLBVfXYDsgoB+CWkt1fhEoUfWdvASu29hM1fJYWPADySannYjcLFk+31P8EzxxY2P 1luFG/LAJX0eL4q8NC2aPOkR/vqpEcvz9JLwhaoYlvhaP1uIa8T3IQw28gR1w2rWpaWe ZFd75B2mOpWEQjZflCpnXyag/Ecwzyn0k5NRTHw5wfcPQY18YVCz8ZtoSmVtLwEjx1yY MQzg== 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:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=Z6hmGr+tc5xGNiWfaxh6WQk3bIut1j/rrWAg84kWlqU=; b=ixReK+R3C4FgHD7o9Qw1Se1pJ7Tp4yLyHU3Tw+NEkfdFCht4MyrPp4l3SsmjCWY9f9 Zg7Odg5mNfcTcoVa0BP+ca/THLVxEF/2/d4HsPuozRuFe6UrJIRBgVri4yxL6GF2sGWC MsoGHIC3gbO+7ejH2XF4x6wzH3Tdn4Z2aMXSqOdjGwOm+Xivq5bp4eiFWUeAdUYeKV4g mJ2NIcU7+dTr+L+KVgOA4+K6gixALgfgQplwrjWweagcoyviDRKZIesDS3HFdO1ly2Eg cld9Zg9mU6GyRASRR97X+REpCCN/ItDtJZhSSjOVwCpxZH1eutDFARHHTEpFzlEsMpp2 2pTw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=YAU0uqnJ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id w1-20020a05640234c100b004486d3bcacdsi10974553edc.5.2022.09.19.04.20.03 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 19 Sep 2022 04:20:03 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=YAU0uqnJ; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 2371B3858C53 for ; Mon, 19 Sep 2022 11:20:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2371B3858C53 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1663586402; bh=Z6hmGr+tc5xGNiWfaxh6WQk3bIut1j/rrWAg84kWlqU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=YAU0uqnJBC0QB8lT2PltqudBr/x+6tz+bO8Tv1bwRBXSwYrqCCHFYQiJNRZzPN/Ny Q0SC73EkBhODz+xdR/RzowURi4Q8/L5qLpigM2/iYiEInJQITTXniADrLQXRWhxG8t m9UdkwWr+QwBzYK3ipi2x7qQX16+SsvlNAjvlKIU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 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) 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) To: gcc-patches@gcc.gnu.org Subject: [PATCH][RFH] Wire ranger into FRE MIME-Version: 1.0 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 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: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener 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?1744396777435928347?= X-GMAIL-MSGID: =?utf-8?q?1744396777435928347?= 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);