From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 8B67E3858D33 for ; Tue, 31 Jan 2023 20:10:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8B67E3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1675195844; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=FbYXeIgCkzDFFCFfV1tVOnh4NJMzoX8a1nKW+UQaVnE=; b=G7tAEnQ0rBrq6OiFMlqEeFkIMNL4v56DoAV8MNLxvJHvPhGuh2wz0w1IZYXLF8LE6gIS82 vfRjRE53bkI/yTvLAYUWqh4E5WJdghFl+16vo5prgBJ+4YEjBIFiwixYgpcZi+nZTEDICE ceBCrAOcA18kpz7IpRMloLO8KfzOtt4= Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-620-qP_KdCCMNOKhlTxWQbnKdw-1; Tue, 31 Jan 2023 15:10:42 -0500 X-MC-Unique: qP_KdCCMNOKhlTxWQbnKdw-1 Received: by mail-qk1-f199.google.com with SMTP id g6-20020ae9e106000000b00720f9e6e3e2so3533989qkm.13 for ; Tue, 31 Jan 2023 12:10:42 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:cc:to:from:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=7xVF6YqKn/S21Yut1VWx95sX9Tod3dypcdgrKMpG0j4=; b=E/lttoo1H6hxW/aodapetUWQ3OsxDmK9H7HfM4Rr9A1GiIQKUsDdPNABbW7kG0OF/E JWp0u93slpmx/Ia+Dzdx+ATJSOGBImD8rLHepvcLmsDm7cstbeYSWboYXHLC2eus6aEN jUG9s+iIdYUcN8yjb1ClVFkIWiN83WkSbMlt6V57euE9T0SGiEK3eolMloVQYGYS4V2V 5QuEjc6UWpDpA/VJpY8oI1x34jO/11bBI4sykRn3LD44Fg/zXSxcvw3krSvLOdEP4y0P SDsZQHl7MIp5RwelHw4oLQVM5x7QoaDsJKn4dgXYN6EdwDcWRsGX6XuCpte4u7zUUCy6 rejQ== X-Gm-Message-State: AO0yUKX7ZHxJxUvvwOHGB9it3NMZWyMd3S4lo2PbY4Wfb/+Wp3r1MFc6 NLqBHz6ADLggOXMJxCmTRmQc2BZrzOYNMRiQLrzi7CdDXVaHpWghuqNDVlupM8vVjr4XoeFiyff DLvWXUPlBKdT7aiXLEQeFmy6jAj+h/Zv6nqbDnk9shq2eLjc2e9rwlUKIQ6ksf8EaD9pTHA== X-Received: by 2002:ac8:7d94:0:b0:3b8:5057:377b with SMTP id c20-20020ac87d94000000b003b85057377bmr19919567qtd.65.1675195841932; Tue, 31 Jan 2023 12:10:41 -0800 (PST) X-Google-Smtp-Source: AK7set/UHS4DKezaJEwiS2oDFQYeBihyZqyGz9e4y4+EG8JuJlMSS7llhfLhF6DBg6duIFdJCivTkQ== X-Received: by 2002:ac8:7d94:0:b0:3b8:5057:377b with SMTP id c20-20020ac87d94000000b003b85057377bmr19919531qtd.65.1675195841595; Tue, 31 Jan 2023 12:10:41 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::fa90? ([2607:fea8:a263:f600::fa90]) by smtp.gmail.com with ESMTPSA id u9-20020ae9c009000000b0072526a43ef7sm2225362qkk.120.2023.01.31.12.10.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 31 Jan 2023 12:10:40 -0800 (PST) Message-ID: <4edb00e2-4691-bdd4-1b4d-12e6b9983ad7@redhat.com> Date: Tue, 31 Jan 2023 15:10:39 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.0 From: Andrew MacLeod To: gcc-patches Cc: "hernandez, aldy" Subject: [PATCH] PR tree-optimization/108356 - Ranger cache - always use range_from_dom when updating. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------25DZBrL1ihjutEce2Ky09Lzi" Content-Language: en-US X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,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 List-Id: This is a multi-part message in MIME format. --------------25DZBrL1ihjutEce2Ky09Lzi Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit This turned out to be a more interesting problem than I wanted. the situation boils down to: # g_5 = PHI <0(2), 2(8)>   if (g_5 <= 1)     goto ; [INV] :   if (g_5 != 0)     goto ; [INV]   else     goto ; [INV]   :   c = 0;   :     goto ; [INV]  We globally know that g_5 is [0,0][2,2] we also know that 10->4 , g_5 will be [0,0] Which means we also know that that the branch in bb_4 will never be taken, and will always go to bb 8. THis is all processed in EVRP, the branch is changed, and the next time VRP is called, we blow the block with c = 0 like we want... Unfortunately it doesnt happen within EVRP because when this updated range for g_5 is propagated in the cache, it was tripping over a shotcut which tried to avoid using lookups when it thinks it didnt matter, and would occasionally drop back to the global range. In particular, the cache had originally propagated [0,0][2,2] as the on entry range to bb8. when we rewrite the branch, we mark 4->7 and 7->8  as unexecutable edges, then propagate the new range for g_5..  This requires recalculating the existing range on entry to bb8. It properly picked up [0,0] from 4->8, but when the cache query checked the range from 7->8, it discovered that no value was yet set, so instead of looking it up, it fell back to the global range of [0,0][2,2].  If it properly calculates that edge instead, it comes up with UNDEFINED (as it is unexecutable) and results in [0,0]... and EVRP then also removes the block is c = 0 in. By picking up the global value, it still thought 2 was a possibility later on, and a single VRP pass couldn't eliminate the branch ultimately leading to the store... it required a second one with the adjusted CFG to catch it. This patch tells the cache to always do a read-only scan of the dominator tree to find the nearest actual value and use that instead.  This may solve other lingering weird propagation issues. I also ran a performance run on this change. It does slow VRP by down about 1%, but the overall change is nominal at around 0.05%. Bootstraps on x86_64-pc-linux-gnu with no regressions.  OK? Andrew --------------25DZBrL1ihjutEce2Ky09Lzi Content-Type: text/x-patch; charset=UTF-8; name="0001-Ranger-cache-always-use-range_from_dom-when-updating.patch" Content-Disposition: attachment; filename*0="0001-Ranger-cache-always-use-range_from_dom-when-updating.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSBkZGI5ZGYyNTRlZDJiYzVmMTFiZGRlMjEzZTE0ODVkNzk3MWEyNWQ5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBBbmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4K RGF0ZTogVHVlLCAxMCBKYW4gMjAyMyAxMzo0MDo1NiAtMDUwMApTdWJqZWN0OiBbUEFUQ0hdIFJh bmdlciBjYWNoZSAtIGFsd2F5cyB1c2UgcmFuZ2VfZnJvbV9kb20gd2hlbiB1cGRhdGluZy4KCldo ZW4gdXBkYXRpbmcgYW4gZXhpc3RpbmcgcmFuZ2UsIGlmIHdlIGRvbnQgcXVlcnkgdGhlIGRvbSB0 cmVlLCB3ZSBjYW4KZ2V0IHRoZSBnbG9iYWwgcmFuZ2UgaW5zdGVhZCBvZiBhIHByb3BlciByYW5n ZSBvbiBzb21lIGluY29taW5nIGVkZ2VzCndoaWNoIGNhdXNlIHRoZSByYW5nZSB0byBub3QgYmUg cmVmaW5lZCBwcm9wZXJseS4KCglQUiB0cmVlLW9wdGltaXphdGlvbi8xMDgzNTYKCWdjYy8KCSog Z2ltcGxlLXJhbmdlLWNhY2hlLmNjIChyYW5nZXJfY2FjaGU6OnJhbmdlX29uX2VkZ2UpOiBBbHdh eXMKCWRvIGEgc2VhcmNoIG9mIHRoZSBET00gdHJlZSBmb3IgYSByYW5nZS4KCglnY2MvdGVzdHN1 aXRlLwoJKiBnY2MuZGcvcHIxMDgzNTYuYzogTmV3LgotLS0KIGdjYy9naW1wbGUtcmFuZ2UtY2Fj aGUuY2MgICAgICAgfCAgMiArLQogZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDgzNTYuYyB8IDIz ICsrKysrKysrKysrKysrKysrKysrKysrCiAyIGZpbGVzIGNoYW5nZWQsIDI0IGluc2VydGlvbnMo KyksIDEgZGVsZXRpb24oLSkKIGNyZWF0ZSBtb2RlIDEwMDY0NCBnY2MvdGVzdHN1aXRlL2djYy5k Zy9wcjEwODM1Ni5jCgpkaWZmIC0tZ2l0IGEvZ2NjL2dpbXBsZS1yYW5nZS1jYWNoZS5jYyBiL2dj Yy9naW1wbGUtcmFuZ2UtY2FjaGUuY2MKaW5kZXggYTgyMDJmMGU4OTUuLjIwYzQ0NGJjNGY0IDEw MDY0NAotLS0gYS9nY2MvZ2ltcGxlLXJhbmdlLWNhY2hlLmNjCisrKyBiL2djYy9naW1wbGUtcmFu Z2UtY2FjaGUuY2MKQEAgLTk5OCw3ICs5OTgsNyBAQCBib29sCiByYW5nZXJfY2FjaGU6OnJhbmdl X29uX2VkZ2UgKHZyYW5nZSAmciwgZWRnZSBlLCB0cmVlIGV4cHIpCiB7CiAgIGlmIChnaW1wbGVf cmFuZ2Vfc3NhX3AgKGV4cHIpKQotICAgIHJldHVybiBlZGdlX3JhbmdlIChyLCBlLCBleHByLCBS RkRfTk9ORSk7CisgICAgcmV0dXJuIGVkZ2VfcmFuZ2UgKHIsIGUsIGV4cHIsIFJGRF9SRUFEX09O TFkpOwogICByZXR1cm4gZ2V0X3RyZWVfcmFuZ2UgKHIsIGV4cHIsIE5VTEwpOwogfQogCmRpZmYg LS1naXQgYS9nY2MvdGVzdHN1aXRlL2djYy5kZy9wcjEwODM1Ni5jIGIvZ2NjL3Rlc3RzdWl0ZS9n Y2MuZGcvcHIxMDgzNTYuYwpuZXcgZmlsZSBtb2RlIDEwMDY0NAppbmRleCAwMDAwMDAwMDAwMC4u MWRmNmIyNzhlNDUKLS0tIC9kZXYvbnVsbAorKysgYi9nY2MvdGVzdHN1aXRlL2djYy5kZy9wcjEw ODM1Ni5jCkBAIC0wLDAgKzEsMjMgQEAKKy8qIHsgZGctZG8gY29tcGlsZSB9ICovCisvKiB7IGRn LW9wdGlvbnMgIi1PMiAtZmR1bXAtdHJlZS1vcHRpbWl6ZWQiIH0gKi8KKworY2hhciBhOworc3Rh dGljIGNoYXIgYyA9IDM7CitjaGFyIGQ7Cit2b2lkIGZvbygpOworc2hvcnQoYikoc2hvcnQgZSwg c2hvcnQgZikgeyByZXR1cm4gZSArIGY7IH0KK2ludCBtYWluKCkgeworICB1bnNpZ25lZCBnID0g MDsKKyAgaWYgKGMpCisgICAgOworICBlbHNlCisgICAgZm9vKCk7CisgIGZvciAoOyBnIDwgMjsg ZyA9IGIoZywgMikpIHsKKyAgICBkID0gZyA/IDAgOiBhOworICAgIGlmIChnKQorICAgICAgYyA9 IDA7CisgIH0KK30KKworCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAtbm90ICJmb28i ICJvcHRpbWl6ZWQiIH0gfSAqLwotLSAKMi4zOS4wCgo= --------------25DZBrL1ihjutEce2Ky09Lzi--