From patchwork Wed Jan 19 01:36:22 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 50211 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 194FF3857C7F for ; Wed, 19 Jan 2022 01:36:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 194FF3857C7F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1642556218; bh=1QJJJd+yguqBuEZBlgix8xcx59ZArGjPb6LKH5j3roM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=ERn5LLM/4XweO5SZfDp5ncefLdrQ2ROIs/E13w4tmFdX7h5vEPKGKM2XLEiyMx4x/ b1lmu3ovFhl8vPikSIAr+u6ayTlviSsJYKGTSmW6O1rhsePX2BKtaMFl12b6JKLA+k 9CU58BxUzaUOSwyQeoxyRju746AWMAFYHnNNew6Y= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id D13BB3858032 for ; Wed, 19 Jan 2022 01:36:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D13BB3858032 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-225-rPt7jxcnNVCcE-VJprWPAg-1; Tue, 18 Jan 2022 20:36:26 -0500 X-MC-Unique: rPt7jxcnNVCcE-VJprWPAg-1 Received: by mail-qk1-f197.google.com with SMTP id y185-20020a3764c2000000b0047a8c8b3febso764518qkb.1 for ; Tue, 18 Jan 2022 17:36:26 -0800 (PST) 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:from:subject:cc; bh=pm1oPDqKlROTgJIRIXWmhp48MfgGvdgXpk+CUffLLYM=; b=yxeJoYg61YKOyCQKQvNS7Q5CdFDFKGS3vi4J+VKOG3a6o8/S8aLpxLq3rYJRKOPRb1 fK7nRN7UX6OrJAfDUkK4IKbc2SmS/XHlfP5l/rehDebrcEzTku1HBar5T+CDoXKTVU3C 24fFaf3npkxtL2Nut7GBd8Trm5X0GUHrR0AYYOYWz0OVC2Gly/vbUQJLNC3zGs7XpTeS L7GQVGIy/1SNVogUL+6BkBThfhsLIVk3vkAnacK7ma+n0sV65X6jvxMJ6Nw6U25POz58 J4PChPy7QzVe7bQHwtDve91usyKMmNT+QPGQ0/BnaRxmX16O49b3AwD6KOtgr/D3xxnW iITQ== X-Gm-Message-State: AOAM531sNSY8tW/Cj+ZTbX+8k65n4suMLbbKWXsfFaJ0aFfKe+xt+NTl uWjnGvqhpe1nTRkdD/RT5gfxbF5XfPtYQ7xvCGeHDUZyk87zLBgx/cyVAffCLtEdhvJbacyzP8U aW+2FMlZAR6ja8O9VvOGu3qiHhWCuPWUQNC2LgVO3ob9juvLyahRLli/2qSX5CMBxyZtibw== X-Received: by 2002:a05:6214:258b:: with SMTP id fq11mr13578563qvb.19.1642556185466; Tue, 18 Jan 2022 17:36:25 -0800 (PST) X-Google-Smtp-Source: ABdhPJwNzsg+8jITRNUQwZA4wDeuojwDqe92yFczlLQF8NnMAa1Qqh6/y7px9CChMsusGNAbrc+A8A== X-Received: by 2002:a05:6214:258b:: with SMTP id fq11mr13578543qvb.19.1642556185052; Tue, 18 Jan 2022 17:36:25 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00:e36d:32da:80f:d4e1? ([2607:fea8:a262:5f00:e36d:32da:80f:d4e1]) by smtp.gmail.com with ESMTPSA id i67sm11094924qkf.69.2022.01.18.17.36.23 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 18 Jan 2022 17:36:24 -0800 (PST) Message-ID: <79a04182-b37f-0074-20f7-7ebf2aef197c@redhat.com> Date: Tue, 18 Jan 2022 20:36:22 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.1 To: gcc-patches Subject: [PATCH] tree-optimization/103721 - Only add equivalencies that are still valid. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.0 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_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This patch happens to fix the PR, but I believe it only papers over a deeper issue that is uncovered in PR104067. That said, examination of the issue uncovered an oversight in the way equivalence sets are merged by the equivalence oracle.  I have not seen an instance via the ranger, but I suspect its just a matter of time. Equivalences sets are added to the basic block in which they occur.   By default, the definition of an SSA_NAME create an equivalence in the DEF block containing just the name itself. Other equivalences are added as they are encountered in their respective basic blocks, and are created by combining whatever equivalence is active (via query) in that block with the new equivalence.  An equivalence introduced by an edge is currently only added the edge destination is a block with a single predecessor.  It is then added to that block. When a query is made for the equivalence set for b_2 at BBx, a walk up the dominance tree is made looking for the first block which has an equivalence containing b_2.  This then becomes the equivalence set for B2 at BBx. If this set contains f_8, before we know that f_8 and b_2 actually equivalent, we query the equivalence set of f_8 at BBx. If it comes back with the same set, then the 2 names are equivalent.  if the set is different, then they are not. This allows us to register equivalences as we see them without worrying about invalidating other equivalences.  Rather, we defer validation until we actually care, and pay the cost at the query point. This PR has exposed a flaw in how we register equivalence sets around back edges which could potentially show up somewhere. searchvolume_5 was use in previous blocks along the back edge and has an equivalence set of {_5, world_7} in BB8   # searchVolume_11 = PHI <1(4), 0(3)>      { _11 }   # currentVolume_8 = searchVolume_5        { _5, _8 , world_7 }     # searchVolume_5 = PHI     { _5, _11 }   # currentVolume_6 = PHI When an equivalence is added for currentVolume_6, a query is made for the equivalence set for currentVolume_8, which returns the set  {_5, _8, world_7 }.   Currently, this is simply combined with {_6} via a bitwise OR to produce {_5, _6, _8, world_7 }.  This is incorrect as _5's equivalence set is now {_5, _11}. _6 and _8 dont appear to be directly related to _5, so we were missing it.   What should be happening is when we merge the equivalence set for currentVolume_6 and  currentVolume_8, each member of the set should be verified by the same criteria the query uses... ie, ask for the equiv set for _5, _8, and world_7 at BB9, and if it is different than this set, it isn't added. This would then create the correct equivalence set  { _6, _8, world_7 }, as the query for _5 would come back with {_5, _11} and not evaluate as equivalent. And yes, PHIS all happen in parallel... We don't need to worry about ordering because even if the PHI hadn't been processed in this order, the definition would have provided a default of { _5 }, and thus still not been equivalent and still won't be added to the set. Anyway, even tho I think there is an additional problem in this PR, I wanted to get approval and check this code in under this PR since it does need to be fixed, and was uncovered here.  We wont close the PR until we are sure the underlying issue is resolved. I will also see if I can come up with some kind of test case in the meantime as well. Bootstraps on x86_64-pc-linux-gnu with no regressions.   Overall compile time is very nominal.. less than a 0.1% impact on the EVRP/VRP passes, so the cost is miniscule. OK for trunk? Andrew commit 100d007b7fdd00dfdf272a4b944832eb1df193bb Author: Andrew MacLeod Date: Tue Jan 18 12:42:02 2022 -0500 Only add equivalencies that are still valid. When equivalencies sets are merged, each member of the set should be queried to ensure its still valid rather than a bulk union. * value-relation.cc (relation_oracle::valid_equivs): Query and add if valid members of a set. (equiv_oracle::register_equiv): Call valid_equivs rather than bitmap direct operations. (path_oracle::register_equiv): Ditto. * value-relation.h (relation_oracle::valid_equivs): New prototype. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 32ca693c464..0134e0328ba 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -188,6 +188,23 @@ relation_transitive (relation_kind r1, relation_kind r2) return rr_transitive_table[r1 - VREL_FIRST][r2 - VREL_FIRST]; } +// Given an equivalence set EQUIV, set all the bits in B that are still valid +// members of EQUIV in basic block BB. + +void +relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb) +{ + unsigned i; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi) + { + tree ssa = ssa_name (i); + const_bitmap ssa_equiv = equiv_set (ssa, bb); + if (ssa_equiv == equivs) + bitmap_set_bit (b, i); + } +} + // ------------------------------------------------------------------------- // The very first element in the m_equiv chain is actually just a summary @@ -364,7 +381,7 @@ equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) // Otherwise create an equivalence for this block which is a copy // of equiv, the add V to the set. bitmap b = BITMAP_ALLOC (&m_bitmaps); - bitmap_copy (b, equiv->m_names); + valid_equivs (b, equiv->m_names, bb); bitmap_set_bit (b, v); return b; } @@ -378,32 +395,32 @@ bitmap equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, equiv_chain *equiv_2) { - // If equiv_1 is alreayd in BB, use it as the combined set. + // If equiv_1 is already in BB, use it as the combined set. if (equiv_1->m_bb == bb) { - bitmap_ior_into (equiv_1->m_names, equiv_2->m_names); + valid_equivs (equiv_1->m_names, equiv_2->m_names, bb); // Its hard to delete from a single linked list, so // just clear the second one. if (equiv_2->m_bb == bb) bitmap_clear (equiv_2->m_names); else - // Ensure equiv_2s names are in the summary for BB. - bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); + // Ensure the new names are in the summary for BB. + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); return NULL; } // If equiv_2 is in BB, use it for the combined set. if (equiv_2->m_bb == bb) { - bitmap_ior_into (equiv_2->m_names, equiv_1->m_names); - // Add equiv_1 names into the summary. - bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); + valid_equivs (equiv_2->m_names, equiv_1->m_names, bb); + // Ensure the new names are in the summary. + bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); return NULL; } // At this point, neither equivalence is from this block. bitmap b = BITMAP_ALLOC (&m_bitmaps); - bitmap_copy (b, equiv_1->m_names); - bitmap_ior_into (b, equiv_2->m_names); + valid_equivs (b, equiv_1->m_names, bb); + valid_equivs (b, equiv_2->m_names, bb); return b; } @@ -1289,8 +1306,8 @@ path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) // Don't mess around, simply create a new record and insert it first. bitmap b = BITMAP_ALLOC (&m_bitmaps); - bitmap_copy (b, equiv_1); - bitmap_ior_into (b, equiv_2); + valid_equivs (b, equiv_1, bb); + valid_equivs (b, equiv_2, bb); equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 44d0796d939..d840234f355 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -96,6 +96,8 @@ public: virtual void dump (FILE *, basic_block) const = 0; virtual void dump (FILE *) const = 0; void debug () const; +protected: + void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb); }; // This class represents an equivalency set, and contains a link to the next