[COMMITTED] tree-optimization/106514 - Do not walk equivalence set in path_oracle::killing_def.
Message ID | 813dc76e-7042-5768-bfec-4d44e13b0964@redhat.com |
---|---|
State | New, archived |
Headers |
Return-Path: <gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org> Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6a10:b5d6:b0:2b9:3548:2db5 with SMTP id v22csp549931pxt; Wed, 3 Aug 2022 12:38:57 -0700 (PDT) X-Google-Smtp-Source: AA6agR6D9ea1NVtXq+ZOIjddbt36pXpJ8+Myw+E0JcjgMoIaga2Yr+NMUziO6S7x0RXUw2BfPYTu X-Received: by 2002:a17:907:72cf:b0:730:8bea:f741 with SMTP id du15-20020a17090772cf00b007308beaf741mr11495128ejc.527.1659555536758; Wed, 03 Aug 2022 12:38:56 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1659555536; cv=none; d=google.com; s=arc-20160816; b=xfg+XEphaBYLcMvvEHKfmSWA1lDk3gc8xY7nnaOZV54UxEnwZVmSJJl81bDVcvrpJH nAu6Q0Mz5bXib8o6bSA5eoS/yw17DqazxX5RwVQtor/bJ1OlU+vrUIKnN0BB/UySEXhP 4lA8gPXO4qkI7MgWaoZ1d7d6UdmtJIFEVheZnyBpnfkHwz82qMQL5H702h3V189KZnJG JtXmfAwMu1uyeZ3PFnF9o4BkdnAd92C9RYmHXxOazTQm7Lbfp0s/JJRqgdEbpQj1xTvp Ck053wL5PeltPC1vC+n53Lhu3SDl2LIEjGsZnPPH3mpi43ZLgXXKKBJYojPhlnYM4w5+ NkeQ== 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:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=cTJJjdRIzVXp9RGUZSjTamrZLvlQh1YOOlwAzFkLjOM=; b=grwVZCZTh8V3acT7hjNIDqk1OFi8TqhWYQthi9hnQA7ypLircsT7TejzmFDzBTeKEj wfAC51CUwrLLkBCrq3O5BuOW8eVhkYhDI0PgpZkxF8RinNY40pnve31WRqNyL+cgv/Ug xB7F4uJo/LDB/xwPfyMwYnIX42xJJP+FlrqBjFQlnyYZ60i4L0OXu0SE1fJt43V1wSgc E2J6DdYrEmMugh9xYKycIKt+p6fWVc/T5Vgq1d/J5xD5gxEXiFD6nHOeHuo30isr53xE H1XkdYd6JGtj5OEqNaDOwfyUp8eAmRtHi/qDpjaEno+Cp1VzCUTgUuEVi27m7IKlJ+WG 2eYA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=mfMX7wkH; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id e21-20020a17090658d500b007307f95bc5dsi5872556ejs.383.2022.08.03.12.38.56 for <ouuuleilei@gmail.com> (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 03 Aug 2022 12:38:56 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=mfMX7wkH; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 893913858297 for <ouuuleilei@gmail.com>; Wed, 3 Aug 2022 19:38:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 893913858297 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1659555535; bh=cTJJjdRIzVXp9RGUZSjTamrZLvlQh1YOOlwAzFkLjOM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=mfMX7wkHVILvJ8VkbiqQIlwvfc8OcSPWQau10Ma4WvVon6VpnPrvwKh28eTSH7asP E4ob7owNSakgAjATMqedHuevgaNeVDOfpX00Ss5XtAGYxFnW31gIHE8nBB3RoHn0rD hmIhcza4GqacsQm39oJeGJ4YDD8rsGYj5E+Smq30= 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 <gcc-patches@gcc.gnu.org>; 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 <gcc-patches@gcc.gnu.org>; 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-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 <gcc-patches@gcc.gnu.org> 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-Type: multipart/mixed; boundary="------------XOT5t0R7NDwzb5ZW0eDkn2CY" 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 <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> From: Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> Reply-To: Andrew MacLeod <amacleod@redhat.com> Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org> X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1740170106443062212?= X-GMAIL-MSGID: =?utf-8?q?1740170106443062212?= |
Series |
[COMMITTED] tree-optimization/106514 - Do not walk equivalence set in path_oracle::killing_def.
|
|
Commit Message
Andrew MacLeod
Aug. 3, 2022, 7:38 p.m. UTC
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 <amacleod@redhat.com> 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);