From patchwork Wed Aug 3 19:38:04 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 56529 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 2DAC63858413 for ; Wed, 3 Aug 2022 19:38:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2DAC63858413 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1659555521; bh=cTJJjdRIzVXp9RGUZSjTamrZLvlQh1YOOlwAzFkLjOM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=T6RnjMBnv8aVr8HZVTfT/lHrJXWzGXuRH90UwfxdfcyCBE9BjFSgt2OJbvbnAuUjz kVvH8SbpgxKNYljGk0zoEC6FIPtrRMdt0hji1OXaHVRHnL0EAjWXKNaa/XU7WllfHw wFnNdBz3GQSh1v24hU6BfGty/QZi0T1GCYmiA11Q= 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 DE6EB3858C39 for ; Wed, 3 Aug 2022 19:38:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DE6EB3858C39 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-404-eVpcapgfMhaFs2vTmxBA3A-1; Wed, 03 Aug 2022 15:38:08 -0400 X-MC-Unique: eVpcapgfMhaFs2vTmxBA3A-1 Received: by mail-qk1-f198.google.com with SMTP id l15-20020a05620a28cf00b006b46997c070so14394537qkp.20 for ; Wed, 03 Aug 2022 12:38:08 -0700 (PDT) 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:cc:from:subject; bh=zig0YqZNRh/mUsk1OAnIh0+jXVWLzbyi+o6hax1Qnbg=; b=lDqX9aVthen6Nx6OKarh7uOSRd9uxzriVto1hr/TARW8Z1af2+JbK4hBYPaGB3zt/n XUcYkqWxdsofnmnmF7TxKFRjU3w9bLQBbPNCIomfLqfFFZrTi8a9IfmsOB8Tc2rkJF1G x68F9udmAFi+RCqAH3qq4TMga4JUwgm78OyBSv0K/JJw/ec45t35wRJeQh3LTqB21fgM SLVrFLM4uReQES3pfUBYq2FTTeHuYm0Ry1BJVH3JrLOpebDiVZ2OeNYeDxQxPQYn/vNN lmdEoLHcYn31caOoIV92KZ/XjtXnmW2IvFtLhKv/a4Br3cnsVLJ5fSTTqNPaAhRX76YJ sx5g== X-Gm-Message-State: AJIora+flHWLIASLmneLkjbyxwo7vxaLpCBz2L2pJ4Ky7ptvjfgrqByN Evsinl34GD4yOqk1cFQ4btoaVe6Nimcy30Cj/e7ZunJu+S9UO0mcMwdCMW/5x/+YzkSJeltzVkp RdrnvZSr4FQc1NpQv8l3GQiin+ZD6nQLhHuXjlU4eqH+u2OzbCmnSg8IjG5NdFm060lgWig== X-Received: by 2002:a05:622a:11c9:b0:31e:e3c5:5cbf with SMTP id n9-20020a05622a11c900b0031ee3c55cbfmr24156982qtk.491.1659555487810; Wed, 03 Aug 2022 12:38:07 -0700 (PDT) X-Google-Smtp-Source: AGRyM1tzGTkNACV40mdP/8uyjWu1OPuDDyxH+IVnwc7294ymy5v9gohTL2P4mNbRv0BnKlFFJcFWgQ== X-Received: by 2002:a05:622a:11c9:b0:31e:e3c5:5cbf with SMTP id n9-20020a05622a11c900b0031ee3c55cbfmr24156964qtk.491.1659555487495; Wed, 03 Aug 2022 12:38:07 -0700 (PDT) Received: from [192.168.0.135] ([104.219.120.152]) by smtp.gmail.com with ESMTPSA id m7-20020a378a07000000b006b648d016f3sm12795947qkd.126.2022.08.03.12.38.05 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 03 Aug 2022 12:38:06 -0700 (PDT) Message-ID: <813dc76e-7042-5768-bfec-4d44e13b0964@redhat.com> Date: Wed, 3 Aug 2022 15:38:04 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 To: gcc-patches Subject: [COMMITTED] tree-optimization/106514 - Do not walk equivalence set in path_oracle::killing_def. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.1 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, 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The path oracles killing_def () routine was removing an ssa-name from each equivalence in the set.  This was busy work that did not need to be done. when checking for an equivalence between A and B, the path oracle requires that A be in B's set and B be in A's set.  By setting the equivalence set for A to contain *just* A, there is no need to visit all the equivalences and remove them. Aldy ran it thru the thread counter, and there was no difference in the number of threads found. The testcase in the PR on my machine ran in the following times: there no difference i the default time, but with the specified option  -O2 --param max-jump-thread-duplication-stmts=30 : before patch: backwards jump threading           :  11.64 ( 92%)   0.00 (  0%) 11.71 ( 91%)    24  (  0%) TOTAL                           :  12.70          0.07 12.83           47M After patch: backwards jump threading           :   1.96 ( 65%)   0.01 ( 10%)   1.99 ( 64%)    24  (  0%) TOTAL                           :   3.00          0.10 3.12           47M Clearly more work to do, but much better for a start.  next up, why is compute_ranges-in_block () taking over 50% of the time now. This was bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed. Andrew commit 19ffb35d17474bb4dd3eb78963c28d10b5362321 Author: Andrew MacLeod Date: Wed Aug 3 13:55:42 2022 -0400 Do not walk equivalence set in path_oracle::killing_def. When killing a def in the path ranger, there is no need to walk the set of existing equivalences clearing bits. An equivalence match requires that both ssa-names have to be in each others set. As killing_def creates a new empty set contianing only the current def, it already ensures false equivaelnces won't happen. PR tree-optimization/106514 * value-relation.cc (path_oracle::killing_def) Do not walk the equivalence set clearing bits. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index a447021214f..3f0957ccdd6 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1400,16 +1400,7 @@ path_oracle::killing_def (tree ssa) unsigned v = SSA_NAME_VERSION (ssa); bitmap_set_bit (m_killed_defs, v); - - // Walk the equivalency list and remove SSA from any equivalencies. - if (bitmap_bit_p (m_equiv.m_names, v)) - { - for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next) - if (bitmap_bit_p (ptr->m_names, v)) - bitmap_clear_bit (ptr->m_names, v); - } - else - bitmap_set_bit (m_equiv.m_names, v); + bitmap_set_bit (m_equiv.m_names, v); // Now add an equivalency with itself so we don't look to the root oracle. bitmap b = BITMAP_ALLOC (&m_bitmaps);