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 21071382EB97 for ; Tue, 22 Feb 2022 16:40:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 21071382EB97 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-140--TFlykSdN7aYxE62OVNKbQ-1; Tue, 22 Feb 2022 11:40:20 -0500 X-MC-Unique: -TFlykSdN7aYxE62OVNKbQ-1 Received: by mail-qk1-f199.google.com with SMTP id i189-20020a3786c6000000b00646d7b30998so134550qkd.10 for ; Tue, 22 Feb 2022 08:40:20 -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:cc:from:subject; bh=wpZMpmKLdE+rDadNXcPXs2C/tKyTtQygxmkWXd3TdzY=; b=y0vjLiFgQII+WGUpB4xUGz4cqjo4LoXDsd1Hw/wzf+1MNMwV6iDbvU04rRgkMpPSbU 3t2hX2bALuwtZPF6NMhMLuYyESOhwnc8EDae155v6s55lldP3kVwUn4B3smU5meVLdls VxxZbf+urBgfcEQy9d56PB26EWIXk6DZ24DfvS/1/CU0JQFDfbGEit22B/rTVuM2xtBH kv1Y21kswYbHKWA/TZj3aySJJzG0279G69EHA4UnRAV3Zc8zsMLEgXyq6ZxYuZwJIhPR Fm0UiEBbGo/4s1FlaYiCHHn3VfuO/VTWzTxQ58ynRvccaCkvTQqO+IVamvgW7GaHcMN6 bX8A== X-Gm-Message-State: AOAM530+XPjrvREpVtqH6ma5oPU7ysqlckVxlS/QRchcxAEOdQzSmnEZ RPsKe+UiYByn8T0gk1u8ig0tie5YPFop3a3NHehi+VSLajior+vdqbS+1xl09442kxe9Ypyc9mE ZzEmetvriIK6jNvZXo8ZTpKdo4d/gE31SHRBvPKzs9l9RKbfFKU81e5GYFAu3ReVscm8sAQ== X-Received: by 2002:a37:688c:0:b0:507:db8b:b71a with SMTP id d134-20020a37688c000000b00507db8bb71amr15467084qkc.396.1645548019877; Tue, 22 Feb 2022 08:40:19 -0800 (PST) X-Google-Smtp-Source: ABdhPJxiF0ySVgbpx+8qsGYRjO/o/6PVvyXRbaO/geJj5N/+fvAgCtOOn3qz4SZuK8h1hyLqU7aKFA== X-Received: by 2002:a37:688c:0:b0:507:db8b:b71a with SMTP id d134-20020a37688c000000b00507db8bb71amr15467051qkc.396.1645548019484; Tue, 22 Feb 2022 08:40:19 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id d18sm45340qty.70.2022.02.22.08.40.18 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Feb 2022 08:40:18 -0800 (PST) Message-ID: <16cb11c5-c46e-b0ae-2813-52f141414a41@redhat.com> Date: Tue, 22 Feb 2022 11:40:17 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.6.0 To: gcc-patches Cc: Aldy Hernandez , Jakub Jelinek From: Andrew MacLeod Subject: [PATCH 2/2] tree-optimization/104530 - Mark defs dependent on non-null stale. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------cB01Zus8wIfvGfWFnc5MMUF7" Content-Language: en-CA X-Spam-Status: No, score=-10.6 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_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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-List-Received-Date: Tue, 22 Feb 2022 16:40:23 -0000 This is a multi-part message in MIME format. --------------cB01Zus8wIfvGfWFnc5MMUF7 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit This patch simply leverages the existing computation machinery to re-evaluate values dependent on a newly found non-null value Ranger associates a monotonically increasing temporal value with every def as it is defined.  When that value is used, we check if any of the values used in the definition have been updated, making the current cached global value stale.  This makes the evaluation lazy, if there are no more uses, we will never re-evaluate. When an ssa-name is marked non-null it does not change the global value, and thus will not invalidate any global values.  This patch marks any definitions in the block which are dependent on the non-null value as stale.  This will cause them to be re-evaluated when they are next used. Imports: b.0_1  d.3_7 Exports: b.0_1  _2  _3  d.3_7  _8          _2 : b.0_1(I)          _3 : b.0_1(I)  _2          _8 : b.0_1(I)  _2  _3  d.3_7(I)    b.0_1 = b;     _2 = b.0_1 == 0B;     _3 = (int) _2;     c = _3;     _5 = *b.0_1;        <<-- from this point b.0_1 is [+1, +INF]     a = _5;     d.3_7 = d;     _8 = _3 % d.3_7;     if (_8 != 0) when _5 is defined, and n.0_1 becomes non-null,  we mark the dependent names that are exports and defined in this block as stale.  so _2, _3 and _8. When _8 is being calculated, _3 is stale, and causes it to be recomputed.  it is dependent on _2, alsdo stale, so it is also recomputed, and we end up with   _2 == [0, 0]   _3 == [0 ,0] and _8 = [0, 0] And then we can fold away the condition. The side effect is that _2 and _3 are globally changed to be [0, 0], but this is OK because it is the definition block, so it dominates all other uses of these names, and they should be [0,0] upon exit anyway.  The previous patch ensure that the global values written to SSA_NAME_RANGE_INFO is the correct [0,1] for both _2 and _3. The patch would have been even smaller if I already had a mark_stale method.   I thought there was one, but I guess it never made it in from lack of need at the time.   The only other tweak was to make the value stale if the dependent value was the same as the definitions. This bootstraps on x86_64-pc-linux-gnu with no regressions. Re-running to ensure. OK for trunk? or defer to stage 1? Andrew --------------cB01Zus8wIfvGfWFnc5MMUF7 Content-Type: text/x-patch; charset=UTF-8; name="0002-Mark-defs-dependent-on-non-null-stale.patch" Content-Disposition: attachment; filename="0002-Mark-defs-dependent-on-non-null-stale.patch" Content-Transfer-Encoding: base64 RnJvbSBhN2U0ZTVmMDQ4OTk4MTdjYWNjM2ViZTVjYzNmZjJkNDg5NDg5MzA5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBBbmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4K RGF0ZTogVHVlLCAyMiBGZWIgMjAyMiAwOTo1ODowMCAtMDUwMApTdWJqZWN0OiBbUEFUQ0ggMi8y XSBNYXJrIGRlZnMgZGVwZW5kZW50IG9uIG5vbi1udWxsIHN0YWxlLgoKV2hlbiBhIG5hbWUgaXMg bWFya2VkIGFzIG5vbi1udWxsLCBmaW5kIGFsbCBleHBvcnRzIGZyb20gdGhlIGJsb2NrLCBhbmQg bWFyayB0aGVpciB0aW1lc3RhbXAgYXMgc3RhbGUuIEFueSBmb2xsb3dpbmcgdXNlIG9mIHRoZSBu YW1lIHdpbGwgdHJpZ2dlciBhIHJlY29tcHV0YWlvbiB1c2luZyB0aGUgbmV3IG5vbi1udWxsIHJh bmdlLgoKCVBSIHRyZWUtb3B0aW1pemF0aW9uLzEwNDUzMAoJZ2NjLwoJKiBnaW1wbGUtcmFuZ2Ut Y2FjaGUuY2MgKHRlbXBvcmFsX2NhY2hlOjpzZXRfc3RhbGUpOiBOZXcuCgkodGVtcG9yYWxfY2Fj aGU6OmN1cnJlbnRfcCk6IElkZW50aWNhbCB0aW1lc3RhbXAgaXMgbm90IGN1cnJlbnQuCgkocmFu Z2VyX2NhY2hlOjp1cGRhdGVfdG9fbm9ubnVsbCk6IE1hcmsgYW55IGV4cG9ydCBkZWZpbmVkIGlu IHRoaXMKCWJsb2NrIHN0YWxlIGlmIGl0IGlzIGRlcGVuZGVudCBvbiB0aGlzIG5hbWUuCgoJZ2Nj L3Rlc3RzdWl0ZS8KCSogZ2NjLmRnL3ByMTA0NTMwLmM6IE5ldy4KLS0tCiBnY2MvZ2ltcGxlLXJh bmdlLWNhY2hlLmNjICAgICAgIHwgMjYgKysrKysrKysrKysrKysrKysrKysrKysrLS0KIGdjYy90 ZXN0c3VpdGUvZ2NjLmRnL3ByMTA0NTMwLmMgfCAxNyArKysrKysrKysrKysrKysrKwogMiBmaWxl cyBjaGFuZ2VkLCA0MSBpbnNlcnRpb25zKCspLCAyIGRlbGV0aW9ucygtKQogY3JlYXRlIG1vZGUg MTAwNjQ0IGdjYy90ZXN0c3VpdGUvZ2NjLmRnL3ByMTA0NTMwLmMKCmRpZmYgLS1naXQgYS9nY2Mv Z2ltcGxlLXJhbmdlLWNhY2hlLmNjIGIvZ2NjL2dpbXBsZS1yYW5nZS1jYWNoZS5jYwppbmRleCA2 MTMxMzUyNjZhNC4uZGViYzkzNzY3YTkgMTAwNjQ0Ci0tLSBhL2djYy9naW1wbGUtcmFuZ2UtY2Fj aGUuY2MKKysrIGIvZ2NjL2dpbXBsZS1yYW5nZS1jYWNoZS5jYwpAQCAtNjk2LDYgKzY5Niw3IEBA IHB1YmxpYzoKICAgYm9vbCBjdXJyZW50X3AgKHRyZWUgbmFtZSwgdHJlZSBkZXAxLCB0cmVlIGRl cDIpIGNvbnN0OwogICB2b2lkIHNldF90aW1lc3RhbXAgKHRyZWUgbmFtZSk7CiAgIHZvaWQgc2V0 X2Fsd2F5c19jdXJyZW50ICh0cmVlIG5hbWUpOworICB2b2lkIHNldF9zdGFsZSAodHJlZSBuYW1l KTsKIHByaXZhdGU6CiAgIHVuc2lnbmVkIHRlbXBvcmFsX3ZhbHVlICh1bnNpZ25lZCBzc2EpIGNv bnN0OwogCkBAIC03NDAsOSArNzQxLDkgQEAgdGVtcG9yYWxfY2FjaGU6OmN1cnJlbnRfcCAodHJl ZSBuYW1lLCB0cmVlIGRlcDEsIHRyZWUgZGVwMikgY29uc3QKICAgLy8gQW55IG5vbi1yZWdpc3Rl cmVkIGRlcGVuZGVuY2llcyB3aWxsIGhhdmUgYSB2YWx1ZSBvZiAwIGFuZCB0aHVzIGJlIG9sZGVy LgogICAvLyBSZXR1cm4gdHJ1ZSBpZiB0aW1lIGlzIG5ld2VyIHRoYW4gZWl0aGVyIGRlcGVuZGVu dC4KIAotICBpZiAoZGVwMSAmJiB0cyA8IHRlbXBvcmFsX3ZhbHVlIChTU0FfTkFNRV9WRVJTSU9O IChkZXAxKSkpCisgIGlmIChkZXAxICYmIHRzIDw9IHRlbXBvcmFsX3ZhbHVlIChTU0FfTkFNRV9W RVJTSU9OIChkZXAxKSkpCiAgICAgcmV0dXJuIGZhbHNlOwotICBpZiAoZGVwMiAmJiB0cyA8IHRl bXBvcmFsX3ZhbHVlIChTU0FfTkFNRV9WRVJTSU9OIChkZXAyKSkpCisgIGlmIChkZXAyICYmIHRz IDw9IHRlbXBvcmFsX3ZhbHVlIChTU0FfTkFNRV9WRVJTSU9OIChkZXAyKSkpCiAgICAgcmV0dXJu IGZhbHNlOwogCiAgIHJldHVybiB0cnVlOwpAQCAtNzU5LDYgKzc2MCwxOCBAQCB0ZW1wb3JhbF9j YWNoZTo6c2V0X3RpbWVzdGFtcCAodHJlZSBuYW1lKQogICBtX3RpbWVzdGFtcFt2XSA9ICsrbV9j dXJyZW50X3RpbWU7CiB9CiAKKy8vIE1hcmsgYSBOQU1FIGFzIHN0YWxlIGJ5IG1hcmtpbmcgdGhl IHRpbWVzdGFtcCBhcyBvbGRlc3QsIHVubGVzcyBpdCBpcworLy8gYWxyZWFkeSAiYWx3YXlzIGN1 cnJlbnQiLgorCitpbmxpbmUgdm9pZAordGVtcG9yYWxfY2FjaGU6OnNldF9zdGFsZSAodHJlZSBu YW1lKQoreworICB1bnNpZ25lZCB2ID0gU1NBX05BTUVfVkVSU0lPTiAobmFtZSk7CisgIGlmICh2 ID49IG1fdGltZXN0YW1wLmxlbmd0aCAoKSB8fCBtX3RpbWVzdGFtcFt2XSA9PSAwKQorICAgIHJl dHVybjsKKyAgbV90aW1lc3RhbXBbdl0gPSAxOworfQorCiAvLyBTZXQgdGhlIHRpbWVzdGFtcCB0 byAwLCBtYXJraW5nIGl0IGFzICJhbHdheXMgdXAgdG8gZGF0ZSIuCiAKIGlubGluZSB2b2lkCkBA IC0xNDc1LDYgKzE0ODgsMTUgQEAgcmFuZ2VyX2NhY2hlOjp1cGRhdGVfdG9fbm9ubnVsbCAoYmFz aWNfYmxvY2sgYmIsIHRyZWUgbmFtZSkKIAl7CiAJICByLnNldF9ub256ZXJvICh0eXBlKTsKIAkg IG1fb25fZW50cnkuc2V0X2JiX3JhbmdlIChuYW1lLCBiYiwgcik7CisJICAvLyBNYXJrIGNvbnN1 bWVycyBvZiBuYW1lIHN0YWxlIHNvIHRoZXkgY2FuIGJlIHJlY29tcHV0ZWQuCisJICBpZiAobV9n b3JpLmlzX2ltcG9ydF9wIChuYW1lLCBiYikgfHwgbV9nb3JpLmlzX2V4cG9ydF9wIChuYW1lLCBi YikpCisJICAgIHsKKwkgICAgICB0cmVlIHg7CisJICAgICAgRk9SX0VBQ0hfR09SSV9FWFBPUlRf TkFNRSAobV9nb3JpLCBiYiwgeCkKKwkJaWYgKG1fZ29yaS5pbl9jaGFpbl9wIChuYW1lLCB4KQor CQkgICAgJiYgZ2ltcGxlX2JiIChTU0FfTkFNRV9ERUZfU1RNVCAoeCkpID09IGJiKQorCQkgIG1f dGVtcG9yYWwtPnNldF9zdGFsZSAoeCk7CisJICAgIH0KIAl9CiAgICAgfQogfQpkaWZmIC0tZ2l0 IGEvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDQ1MzAuYyBiL2djYy90ZXN0c3VpdGUvZ2NjLmRn L3ByMTA0NTMwLmMKbmV3IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAuLjlhZGVk YzVlNWY5Ci0tLSAvZGV2L251bGwKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDQ1MzAu YwpAQCAtMCwwICsxLDE3IEBACisvKiB7IGRnLWRvIGNvbXBpbGUgfSAqLworLyogeyBkZy1vcHRp b25zICItTzIgLWZkdW1wLXRyZWUtZXZycCIgfSAqLworCit2b2lkIGZvbyh2b2lkKTsKKworc3Rh dGljIGludCBhLCAqYiA9ICZhLCBjLCBkID0gMTsKKworaW50IG1haW4oKSB7CisgICAgYyA9IDAg PT0gYjsKKyAgICBhID0gKmI7CisgICAgaWYgKGMgJSBkKQorICAgICAgICBmb3IgKDsgZDsgLS1k KQorICAgICAgICAgICAgZm9vKCk7CisgICAgYiA9IDA7Cit9CisKKy8qIHsgZGctZmluYWwgeyBz Y2FuLXRyZWUtZHVtcC1ub3QgImZvbyIgImV2cnAiIH0gfSAqLwotLSAKMi4xNy4yCgo= --------------cB01Zus8wIfvGfWFnc5MMUF7--