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 D6E9F3858425 for ; Fri, 13 Jan 2023 21:23:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D6E9F3858425 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=1673645017; 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=1nxrbwKfDBJDuWERpnGIHE8KcG5RlzDscnoEHUO6zek=; b=G8fdD2Rh86qLLV1Q7i8bn/yM+uxjehiA5nYmvZMPmu+L7aCTfkuveRVbXg9BzDhUBrq+NE F3TG2HJbJpNhqf2zJSi+J7M2tS6PS8kNXmBQlYTc2HdpXHIWyC023yM/2LjDZbLgXBZPFw 8QdLnJqQ+Uwib82thJTPvu0Mw0C7mC0= Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-646-SNwX7bpBNuK5J9sghU2ACw-1; Fri, 13 Jan 2023 16:23:28 -0500 X-MC-Unique: SNwX7bpBNuK5J9sghU2ACw-1 Received: by mail-qk1-f200.google.com with SMTP id bp6-20020a05620a458600b006ffd3762e78so16017458qkb.13 for ; Fri, 13 Jan 2023 13:23:28 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=qvIwjVQ05dDUEN1/plo7Ym3UauOReVSbNwGgPmoq/IQ=; b=5J8p+8/Xrsnf3WMYBXouocNmbCeigqjKzA6DS4EaJQ92xUOXECKouYFoteobT6u7HZ 627wOVcnhVtI3YwAtj85MmikoLJoxdxWAaxeuV/XbF6zKXIyS/PCX/uCEZJoGF7VOkzL /KYqiHK+EUbEqe4IhA5+3Vm3CpP/GEkzUuOQmBvexgiGi/0ou25RRI+ycCVDnlzo48tr B7IxT2fXDfALbZMZ6Qce9bY26zHZNIlBhuIrdz0GI21l2Y1n2gAtS7KGB9eIZRGLHF3m YK0rqGUkWhlII6kTaJ9rGAbKOZcTNlZU1T6siFQHRsbXySyJWKrmCPpOHC3vxjBHskoK jpHQ== X-Gm-Message-State: AFqh2kqxr2CjS5iS1prh+9bWKXn9BM2UFxHdE0rodKpWAsfPj7/LXkvu ZxQLFdgq8QE0y1X2VY8FSLb2rsw2aME9f7Mxbu4VdjDM7ttdvtVevX3c6rLQsvZCCxyDKVmZ7JY HU6wRw5i6LJEA7WJrzfQzXLVHuJKRqAyTDNQ9sI67g1RWfZyhAVSb3waKfVjvjk/16kLKoQ== X-Received: by 2002:a05:622a:124b:b0:3ab:7bb3:4707 with SMTP id z11-20020a05622a124b00b003ab7bb34707mr100252589qtx.64.1673645007917; Fri, 13 Jan 2023 13:23:27 -0800 (PST) X-Google-Smtp-Source: AMrXdXuPuFdBcFmN6K0Nk063Xqm8KQ6ldAE39vGXOz0scPX1ypuSDVc0noK4/pDq7/ur5TYwpUrTFA== X-Received: by 2002:a05:622a:124b:b0:3ab:7bb3:4707 with SMTP id z11-20020a05622a124b00b003ab7bb34707mr100252560qtx.64.1673645007502; Fri, 13 Jan 2023 13:23:27 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::27bf? ([2607:fea8:a263:f600::27bf]) by smtp.gmail.com with ESMTPSA id cr26-20020a05622a429a00b003a68fe872a5sm11007687qtb.96.2023.01.13.13.23.26 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 13 Jan 2023 13:23:26 -0800 (PST) Message-ID: <3815f4c2-7a8d-c662-54d8-eac1ab315fbb@redhat.com> Date: Fri, 13 Jan 2023 16:23:20 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.5.0 To: gcc-patches Cc: "hernandez, aldy" From: Andrew MacLeod Subject: [PATCH] PR tree-optimization/108359 - Utilize op1 == op2 when invoking range-ops folding. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------P3hjAcIbwI7cFDmR3eFGryG0" Content-Language: en-US X-Spam-Status: No, score=-12.3 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. --------------P3hjAcIbwI7cFDmR3eFGryG0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit fold_range() already invokes wi_fold_in_parts to try to get more refined information. If the subranges are quite small, it will do each individual calculation and combine the results. x * y with x = [1,3] and y = [1,3]  is broken down and we calculate each possibility and we end up with [1,4][6,6][9,9] instead of [1,9] We limit this as the time is between quadratic to exponential depending on the number of elements in x and y. If we also check the relation and determine that x == y, we don't need to worry about that growth as this process is linear.  The above case will be broken down to just  1*1, 2*2 and 3*3, resulting in a range of [1, 1][4,4][9,9].  In the testcase, it happens to be the right_shift operation, but this solution is generic and applies to all range-op operations. I added a testcase which checks >>, *, + and %. I also arbitrarily chose 8 elements as the limit for breaking down individual operations.  The overall compile time change for this is negligible. Although this is a regression fix, it will affect all operations where x == y, which is where my initial hesitancy arose. Regardless, bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK for trunk? Andrew --------------P3hjAcIbwI7cFDmR3eFGryG0 Content-Type: text/x-patch; charset=UTF-8; name="0002-Utilize-op1-op2-when-invoking-range-ops-folding.patch" Content-Disposition: attachment; filename*0="0002-Utilize-op1-op2-when-invoking-range-ops-folding.patch" Content-Transfer-Encoding: base64 RnJvbSBmZDUwZGFiYzYyNmNlYTE4ODZlYmI1MTdjYTI0YzhiOGYxOTljM2FhIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBBbmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4K RGF0ZTogV2VkLCAxMSBKYW4gMjAyMyAxODoxMjo1MSAtMDUwMApTdWJqZWN0OiBbUEFUQ0ggMi8z XSBVdGlsaXplIG9wMSA9PSBvcDIgd2hlbiBpbnZva2luZyByYW5nZS1vcHMgZm9sZGluZy4KCklm IHRoZXJlIGV4aXN0cyBhbiBlcXVpdmFsZW5jZSByZWxhdGlvbnNoaXAgYmV0d2VlbiBvcDEgYW5k IG9wMiwKYW55IGJpbmFyeSBvcGVyYXRpb24gY2FuIGJlIGJyb2tlbiBpbnRvIGluZGl2aWR1YWwg b3BlcmF0aW9ucyBhbmQKdW5pb25lZCBpZiB0aGVyZSBhcmUgc3VmZmljZW50bHkgZmV3IGVsZW1l bnRzIGluIHRoZSBzZXQuCgoJUFIgdHJlZS1vcHRpbWl6YXRpb24vMTA4MzU5CglnY2MvCgkqIHJh bmdlLW9wLmNjIChyYW5nZV9vcGVyYXRvcjo6d2lfZm9sZF9pbl9wYXJ0c19lcXVpdik6IE5ldy4K CShyYW5nZV9vcGVyYXRvcjo6Zm9sZF9yYW5nZSk6IElmIG9wMSBpcyBlcXVpdmFsZW50IHRvIG9w MiB0aGVuCglpbnZva2UgbmV3IGZvbGRfaW5fcGFydHNfZXF1aXYgdG8gb3BlcmF0ZSBvbiBzdWIt Y29tcG9uZW50cy4KCSogcmFuZ2Utb3AuaCAod2lfZm9sZF9pbl9wYXJ0c19lcXVpdik6IE5ldyBw cm90b3R5cGUuCgoJZ2NjL3Rlc3RzdWl0ZS8KCSogZ2NjLmRnL3ByMTA4MzU5LmM6IE5ldy4KLS0t CiBnY2MvcmFuZ2Utb3AuY2MgICAgICAgICAgICAgICAgIHwgNTAgKysrKysrKysrKysrKysrKysr KysrKysrKysrKysrKysrCiBnY2MvcmFuZ2Utb3AuaCAgICAgICAgICAgICAgICAgIHwgIDUgKysr KwogZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDgzNTkuYyB8IDUwICsrKysrKysrKysrKysrKysr KysrKysrKysrKysrKysrKwogMyBmaWxlcyBjaGFuZ2VkLCAxMDUgaW5zZXJ0aW9ucygrKQogY3Jl YXRlIG1vZGUgMTAwNjQ0IGdjYy90ZXN0c3VpdGUvZ2NjLmRnL3ByMTA4MzU5LmMKCmRpZmYgLS1n aXQgYS9nY2MvcmFuZ2Utb3AuY2MgYi9nY2MvcmFuZ2Utb3AuY2MKaW5kZXggZWM3NWUwN2JjOGEu LjJjYjJjMTM0NGYxIDEwMDY0NAotLS0gYS9nY2MvcmFuZ2Utb3AuY2MKKysrIGIvZ2NjL3Jhbmdl LW9wLmNjCkBAIC0xNjAsNiArMTYwLDM2IEBAIHJhbmdlX29wZXJhdG9yOjp3aV9mb2xkIChpcmFu Z2UgJnIsIHRyZWUgdHlwZSwKICAgci5zZXRfdmFyeWluZyAodHlwZSk7CiB9CiAKKy8vIENhbGwg d2lfZm9sZCB3aGVuIGJvdGggb3AxIGFuZCBvcDIgYXJlIGVxdWl2YWxlbnQuIEZ1cnRoZXIgc3Bs aXQgc21hbGwKKy8vIHN1YnJhbmdlcyBpbnRvIGNvbnN0YW50cy4gIFRoaXMgY2FuIHByb3ZpZGUg YmV0dGVyIHByZWNpc2lvbi4KKy8vIEZvciB4ICsgeSwgIHdoZW4geCA9PSB5IHdpdGggYSByYW5n ZSBvZiBbMCw0XSBpbnN0ZWFkIG9mIFswLCA4XSBwcm9kdWNlCisvLyBbMCwwXVsyLCAyXVs0LDRd WzYsIDZdWzgsIDhdCisKK3ZvaWQKK3JhbmdlX29wZXJhdG9yOjp3aV9mb2xkX2luX3BhcnRzX2Vx dWl2IChpcmFuZ2UgJnIsIHRyZWUgdHlwZSwKKwkJCQkJY29uc3Qgd2lkZV9pbnQgJmxoX2xiLAor CQkJCQljb25zdCB3aWRlX2ludCAmbGhfdWIpIGNvbnN0Cit7CisgIGludF9yYW5nZV9tYXggdG1w OworICB3aWRlc3RfaW50IGxoX3JhbmdlID0gd2k6OnN1YiAod2lkZXN0X2ludDo6ZnJvbSAobGhf dWIsIFRZUEVfU0lHTiAodHlwZSkpLAorCQkJCSB3aWRlc3RfaW50Ojpmcm9tIChsaF9sYiwgVFlQ RV9TSUdOICh0eXBlKSkpOworICAvLyBpZiB0aGVyZSBhcmUgMSB0byA4IHZhbHVlcyBpbiB0aGUg TEggcmFuZ2UsIHNwbGl0IHRoZW0gdXAuCisgIHIuc2V0X3VuZGVmaW5lZCAoKTsKKyAgaWYgKGxo X3JhbmdlID49IDAgJiYgbGhfcmFuZ2UgPD0gNykKKyAgICB7CisgICAgICB1bnNpZ25lZCB4Owor ICAgICAgZm9yICh4ID0gMDsgeCA8PSBsaF9yYW5nZTsgeCsrKQorCXsKKwkgIHdpZGVfaW50IHZh bCA9IGxoX2xiICsgeDsKKwkgIHdpX2ZvbGQgKHRtcCwgdHlwZSwgdmFsLCB2YWwsIHZhbCwgdmFs KTsKKwkgIHIudW5pb25fICh0bXApOworCX0KKyAgICB9CisgIC8vIE90aGVyd2lzZSBqdXN0IGNh bGwgd2lfZm9sZC4KKyAgZWxzZQorICAgIHdpX2ZvbGQgKHIsIHR5cGUsIGxoX2xiLCBsaF91Yiwg bGhfbGIsIGxoX3ViKTsKK30KKwogLy8gQ2FsbCB3aV9mb2xkLCBleGNlcHQgZnVydGhlciBzcGxp dCBzbWFsbCBzdWJyYW5nZXMgaW50byBjb25zdGFudHMuCiAvLyBUaGlzIGNhbiBwcm92aWRlIGJl dHRlciBwcmVjaXNpb24uIEZvciBzb21ldGhpbmcgICA4ID4+IFswLDFdCiAvLyBJbnN0ZWFkIG9m IFs4LCAxNl0sIHdlIHdpbGwgcHJvZHVjZSBbOCw4XVsxNiwxNl0KQEAgLTIzNCw2ICsyNjQsMjYg QEAgcmFuZ2Vfb3BlcmF0b3I6OmZvbGRfcmFuZ2UgKGlyYW5nZSAmciwgdHJlZSB0eXBlLAogICB1 bnNpZ25lZCBudW1fbGggPSBsaC5udW1fcGFpcnMgKCk7CiAgIHVuc2lnbmVkIG51bV9yaCA9IHJo Lm51bV9wYWlycyAoKTsKIAorICAvLyBJZiBvcDEgYW5kIG9wMiBhcmUgZXF1aXZhbGVuY2VzLCB0 aGVuIHdlIGRvbid0IG5lZWQgYSBjb21wbGV0ZSBjcm9zcworICAvLyBwcm9kdWN0LCBqdXN0IHBh aXJzIG9mIG1hdGNoaW5nIGVsZW1lbnRzLgorICBpZiAocmVsYXRpb25fZXF1aXZfcCAocmVsKSAm JiAobGggPT0gcmgpKQorICAgIHsKKyAgICAgIGludF9yYW5nZV9tYXggdG1wOworICAgICAgci5z ZXRfdW5kZWZpbmVkICgpOworICAgICAgZm9yICh1bnNpZ25lZCB4ID0gMDsgeCA8IG51bV9saDsg Kyt4KQorCXsKKwkgIHdpZGVfaW50IGxoX2xiID0gbGgubG93ZXJfYm91bmQgKHgpOworCSAgd2lk ZV9pbnQgbGhfdWIgPSBsaC51cHBlcl9ib3VuZCAoeCk7CisJICB3aV9mb2xkX2luX3BhcnRzX2Vx dWl2ICh0bXAsIHR5cGUsIGxoX2xiLCBsaF91Yik7CisJICByLnVuaW9uXyAodG1wKTsKKwkgIGlm IChyLnZhcnlpbmdfcCAoKSkKKwkgICAgYnJlYWs7CisJfQorICAgICAgb3AxX29wMl9yZWxhdGlv bl9lZmZlY3QgKHIsIHR5cGUsIGxoLCByaCwgcmVsKTsKKyAgICAgIHVwZGF0ZV9rbm93bl9iaXRt YXNrIChyLCBtX2NvZGUsIGxoLCByaCk7CisgICAgICByZXR1cm4gdHJ1ZTsKKyAgICB9CisKICAg Ly8gSWYgYm90aCByYW5nZXMgYXJlIHNpbmdsZSBwYWlycywgZm9sZCBkaXJlY3RseSBpbnRvIHRo ZSByZXN1bHQgcmFuZ2UuCiAgIC8vIElmIHRoZSBudW1iZXIgb2Ygc3VicmFuZ2VzIGdyb3dzIHRv byBoaWdoLCBwcm9kdWNlIGEgc3VtbWFyeSByZXN1bHQgYXMgdGhlCiAgIC8vIGxvb3AgYmVjb21l cyBleHBvbmVudGlhbCB3aXRoIGxpdHRsZSBiZW5lZml0LiAgU2VlIFBSIDEwMzgyMS4KZGlmZiAt LWdpdCBhL2djYy9yYW5nZS1vcC5oIGIvZ2NjL3JhbmdlLW9wLmgKaW5kZXggYjdiOGEzYjk0NzMu Ljk5OGFlZWRiMGQ5IDEwMDY0NAotLS0gYS9nY2MvcmFuZ2Utb3AuaAorKysgYi9nY2MvcmFuZ2Ut b3AuaApAQCAtMTA5LDYgKzEwOSwxMSBAQCBwcm90ZWN0ZWQ6CiAJCQkgY29uc3Qgd2lkZV9pbnQg JnJoX2xiLAogCQkJIGNvbnN0IHdpZGVfaW50ICZyaF91YikgY29uc3Q7CiAKKyAgLy8gQ2FsbGVk IGJ5IGZvbGQgcmFuZ2UgdG8gc3BsaXQgc21hbGwgc3VicmFuZ2VzIGludG8gcGFydHMgd2hlbiBv cDEgPT0gb3AyCisgIHZvaWQgd2lfZm9sZF9pbl9wYXJ0c19lcXVpdiAoaXJhbmdlICZyLCB0cmVl IHR5cGUsCisJCQkgICAgICAgY29uc3Qgd2lkZV9pbnQgJmxiLAorCQkJICAgICAgIGNvbnN0IHdp ZGVfaW50ICZ1YikgY29uc3Q7CisKICAgLy8gVHJlZSBjb2RlIG9mIHRoZSByYW5nZSBvcGVyYXRv ciBvciBFUlJPUl9NQVJLIGlmIHVua25vd24uCiAgIHRyZWVfY29kZSBtX2NvZGU7CiB9OwpkaWZm IC0tZ2l0IGEvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDgzNTkuYyBiL2djYy90ZXN0c3VpdGUv Z2NjLmRnL3ByMTA4MzU5LmMKbmV3IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAu LjAwZmQyZGU2ZGM3Ci0tLSAvZGV2L251bGwKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIx MDgzNTkuYwpAQCAtMCwwICsxLDUwIEBACisvKiB7IGRnLWRvIGNvbXBpbGUgfSAqLworLyogeyBk Zy1vcHRpb25zICItTzIgLWZkdW1wLXRyZWUtb3B0aW1pemVkIiB9ICovCisKKy8qIFBSIHRlc3Qg Y2FzZS4gICovCitpbnQgYiA9IDEwOworaW50IGM7CitjaGFyIGU7Cit2b2lkIGZvbygpOworc3Rh dGljIGNoYXIoYSkoY2hhciBmLCBjaGFyIGcpIHsgcmV0dXJuIGYgJiYgZyA9PSAxID8gMCA6IGYg JSBnOyB9CitzaG9ydChkKShzaG9ydCBmLCBzaG9ydCBnKSB7IHJldHVybiBmICogZzsgfQoraW50 IG1haW4oKSB7CisgIHNob3J0IGg7CisgIGludCBpOworICB1bnNpZ25lZCBqOworICBoID0gZChi ICYmIGMsIDUpOworICBqID0gaDsKKyAgaSA9IGEoaCwgMjM3KTsKKyAgdW5zaWduZWQgayA9IGk7 CisgIGUgPSBpIDwgMCB8fCBrID49IDMyID8gMCA6IGkgPj4gazsKKyAgaWYgKGUpIHsKKyAgICBj ID0gMDsKKyAgICBmb28oKTsKKyAgfQorfQorCisKKy8qIEFsc28gQ2hlY2sgdGhhdCBzbWFsbCBy YW5nZXMgYXJlIGJyb2tlbiBkb3duIGFuZCBvcHRpbWl6ZWQgcHJvcGVybHkKKyAgIGluIHRoZSBl Z25lcmljIGNhc2UuIFRoaXMgZnVuY3Rpb24gc2hvdWxkIGFsd2F5cyByZXR1cm4gMC4gICovCisK K2ludCBvdGhlcmZ1bmMgKGludCB4LCBpbnQgeikgeworICBpZiAoeCA8IDAgfHwgeCA+IDYgKQor ICAgIHJldHVybiAwOworCisgIGlmICh4ID09IHopCisgICAgeworICAgIGlmICh4ID4+IHogPiAw KQorICAgICAgcmV0dXJuIDE7CisgICAgaWYgKHggKiB6ID4gMjYgJiYgeCAqIHogPCAzNSkKKyAg ICAgIHJldHVybiAxOworICAgIGlmICh4ICsgeiA9PSA1KQorICAgICAgcmV0dXJuIDE7CisgICAg aWYgKCh4ICsgeikgJSAyID09IDEpCisgICAgICByZXR1cm4gMTsKKyAgICB9CisgIHJldHVybiAw OworfQorCisKKy8qIHsgZGctZmluYWwgeyBzY2FuLXRyZWUtZHVtcC1ub3QgImZvbyIgIm9wdGlt aXplZCIgfSB9ICovCisvKiB7IGRnLWZpbmFsIHsgc2Nhbi10cmVlLWR1bXAtbm90ICJyZXR1cm4g MSIgIm9wdGltaXplZCIgfSB9ICovCi0tIAoyLjM4LjEKCg== --------------P3hjAcIbwI7cFDmR3eFGryG0--