From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com [IPv6:2a00:1450:4864:20::52b]) by sourceware.org (Postfix) with ESMTPS id 94DEE3858403 for ; Thu, 22 Sep 2022 12:34:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 94DEE3858403 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ed1-x52b.google.com with SMTP id e18so13405271edj.3 for ; Thu, 22 Sep 2022 05:34:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date; bh=1vKMFB9oh5ndpW7OOcdRkQ2l//pIYJ5EKxixd6rM1/4=; b=GXPQiRd6gIe+cfOKBjBHW8RRLA7PaybQx9pWSxPMkpt8ugQFx98hkMmxMErAdtkxnI rLPphvjfE+ezoFE7H98JQglaRLsRzpecu2pe9tnxvzI4ZqqWD61wHwH8F78DQ44Wbnux F1qElf7sjEz94QM37u3Ryww0pBelZLAIw93HlK2rxfadCktX/Pfyz50qtCLtZ3VPaCXN KRCr4cinnu1e5/u+9nZtYOr2U5nkHluXDF/yYDKd1mM+FP20+GUr7/yTR8tM+6KHC81X QK/IZMGqTLyxWtaCEBk7HheFgfs055Q8IQxu3NQNHGbUzgGfmvKLrq7MHLnu7atr1gLj PEeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=1vKMFB9oh5ndpW7OOcdRkQ2l//pIYJ5EKxixd6rM1/4=; b=YrVgtKFj2joTfg9eJCEZFHIDofJjE5QO5yXCJueSXR5bv8khZ67gkvBnlp7XADLQvG uLNTipYcZgozNp29l8n6ZdoylFWvWPKJ+toAhhK1AcseXXZ6Og340SWBu+bShhiHati2 OmoF5BiUqjVLHTfGTpXqnTQPujcZCcL+1ieJtEm+jLXlkwRpgkIxCfO4UKo3x2VLDNbT 9cSDdLLJolHJpcaznKtL8h43NhQEI9FFolbeUyJKMVJ19w0VY8JKfsFjoa6ju2STwu3A RZNcUJGBHUTyE5DIDUXra/6k0t78rC2/abrRg7Tq3VHJ3zfLldlCLIdN/TfIKE8Qi8XR tDnQ== X-Gm-Message-State: ACrzQf30AA14WNPjw5Vbv/RmnlCaur5R0JirTOwF5XGUV4XkFOcuZSYv ZIr8MEwbzzZBqLAykIkUJDnUcpP3UrCAnLuZBVE= X-Google-Smtp-Source: AMsMyM4Nqg9/+R+Qm0BnULFkkXKztsdKvQNxerQ/gwW7qBOHBpbb7Huc0+2Pkno4tZEJXrKL3SXOqfcQt67zAEpJTpI= X-Received: by 2002:a05:6402:1849:b0:453:ba03:9e41 with SMTP id v9-20020a056402184900b00453ba039e41mr3123439edy.202.1663850072012; Thu, 22 Sep 2022 05:34:32 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Thu, 22 Sep 2022 14:34:19 +0200 Message-ID: Subject: Re: PING^2: [PATCH v5] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction To: Di Zhao OS Cc: "gcc-patches@gcc.gnu.org" Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,KAM_SHORT,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: On Wed, Sep 7, 2022 at 9:30 AM Di Zhao OS wrote: > > Gentle ping again. So I got the chance to review the change again on the travel to GNU Cauldron 2022. There's quite some factoring / moving of stuff in the patch. I've already pushed to trunk a change that factores out can_track_predicate_on_edge (your vn_tracking_edge), factoring out is_vn_valid_at_bb also looks useful, so I'll followup with a similar change. I'm going to attach a commented quoted patch (because that's what I produced during the travel). An overall comment (also in that attachment) would be "why are equivalences recorded in the expression hash table at all? Are they not predicated values of an SSA name and thus should be a vn_pval chain in vn_ssa_aux itself? conditional equivalences are expensive to handle (so are the existing predicated values which I do not like too much and which, frankly, I've probably designed too general - ATM we only ever insert predicated values 'true' and 'false' which could be used to simplify a lot of logic but would break this patch?) At some point I wanted to see whether we can use ranger relations for all of this. Then, for "true" equivalence tracking it might be interesting to explore "path value numbering", aka allow revisiting code from the equivalence op defs to the equivalence producing edge(s) with the equivalence fully reflected in the value number. The interesting thing might be that we can track whether there's any equivalence on the side and based on use heuristic decide whether that's going to pay off. It might be also possible to re-use this to improve jump threading costing. If we'd be able to "fork" the VN state we could re-run from the later definition of an equivalence to the point it is established. So, overall I wasn't able to get at what this patch will catch and what it will not catch - that is, to what extent equivalences affect previously and future recorded expressions. Plus the implementation feels like it bolts on the wrong place. As I'm not happy with my predicated values implementation either I'm of course a bit biased here (note the implementation was mostly added to avoid regressions with respect to the previous VN implementation and I should probably make it less general and more optimized - but as said, using ranger might be an option here). You have one testcase, ssa-fre-102.c, that seems to require VN with equivalences, the others should be catched by rangers relation handling, no?" I've looked into using ranger for what the existing predicated value handling does, plus catch more cases transparently. I'm not sure rangers equivalences handling is a good fit so to handle those an approach like yours might be necessary. Note I'm not really happy about the patch as-is (nor I am happy about what I implemented with predicated values - sorry for that). I'm not even sure equivalences can be handled "nicely" :/ Thanks, Richard. > Thanks, > Di Zhao > > > -----Original Message----- > > From: Di Zhao OS > > Sent: Tuesday, July 12, 2022 2:08 AM > > To: 'gcc-patches@gcc.gnu.org' > > Cc: 'Richard Biener' > > Subject: PING: [PATCH v5] tree-optimization/101186 - extend FRE with > > "equivalence map" for condition prediction > > > > Updated the patch in the attachment, so it can apply. > > > > Thanks, > > Di Zhao > > > > > -----Original Message----- > > > From: Di Zhao OS > > > Sent: Sunday, May 29, 2022 11:59 PM > > > To: gcc-patches@gcc.gnu.org > > > Cc: Richard Biener > > > Subject: [PATCH v5] tree-optimization/101186 - extend FRE with "equivalence > > > map" for condition prediction > > > > > > Hi, attached is a new version of the patch. The changes are: > > > - Skip using temporary equivalences for floating-point values, because > > > folding expressions can generate incorrect values. For example, > > > operations on 0.0 and -0.0 may have different results. > > > - Avoid inserting duplicated back-refs from value-number to predicates. > > > - Disable fre in testsuite/g++.dg/pr83541.C . > > > > > > Summary of the previous versions: > > > https://gcc.gnu.org/pipermail/gcc-patches/2021-December/587346.html > > > > > > Is the patch still considered? > > > > > > Thanks, > > > Di Zhao > > > > > > --- > > > > > > Extend FRE with temporary equivalences. > > > > > > 2022-05-29 Di Zhao > > > > > > gcc/ChangeLog: > > > PR tree-optimization/101186 > > > * tree-ssa-sccvn.c (VN_INFO): remove assertions (there could be a > > > predicate already). > > > (dominated_by_p_w_unex): Moved upward. > > > (vn_nary_op_get_predicated_value): Moved upward. > > > (is_vn_valid_at_bb): Check if vn_pval is valid at BB. > > > (lookup_equiv_head): Lookup the "equivalence head" of given node. > > > (lookup_equiv_heads): Lookup the "equivalence head"s of given nodes. > > > (vn_tracking_edge): Extracted utility function. > > > (init_vn_nary_op_from_stmt): Insert and lookup by "equivalence > > head"s. > > > (vn_nary_op_insert_into): Insert new value at the front. > > > (vn_nary_op_insert_pieces_predicated_1): Insert as predicated values > > > from pieces. > > > (fold_const_from_equiv_heads): Fold N-ary expression of equiv-heads. > > > (push_new_nary_ref): Insert a back-reference to vn_nary_op_t. > > > (val_equiv_insert): Record temporary equivalence. > > > (vn_nary_op_insert_pieces_predicated): Record equivalences instead > > of > > > some predicates; insert back-refs. > > > (record_equiv_from_prev_phi_1): Record temporary equivalences > > > generated > > > by PHI nodes. > > > (record_equiv_from_prev_phi): Given an outgoing edge of a > > conditional > > > expression taken, record equivalences generated by PHI nodes. > > > (visit_nary_op): Add lookup previous results of N-ary operations by > > > equivalences. > > > (insert_related_predicates_on_edge): Some predicates can be computed > > > from equivalences, no need to insert them. > > > (process_bb): Add lookup predicated values by equivalences. > > > (struct unwind_state): Unwind state of back-refs to vn_nary_op_t. > > > (do_unwind): Unwind the back-refs to vn_nary_op_t. > > > (do_rpo_vn): Update back-reference unwind state. > > > * tree-ssa-sccvn.h (struct nary_ref): hold a lists of references to > > > the > > > nary map entries. > > > > > > gcc/testsuite/ChangeLog: > > > > > > * g++.dg/pr83541.C: Disable fre. > > > * gcc.dg/tree-ssa/pr68619-2.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-1.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-2.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-3.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-5.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-7.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-8.c: Disable fre. > > > * gcc.dg/tree-ssa/pr71947-9.c: Disable fre. > > > * gcc.dg/tree-ssa/vrp03.c: Disable fre. > > > * gcc.dg/tree-ssa/ssa-fre-100.c: New test. > > > * gcc.dg/tree-ssa/ssa-fre-101.c: New test. > > > * gcc.dg/tree-ssa/ssa-fre-102.c: New test. > > > * gcc.dg/tree-ssa/ssa-pre-34.c: New test.