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 7595C385C41D for ; Thu, 18 Nov 2021 19:28:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7595C385C41D Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-294-F_TJTRsyNayfe0MmTSdniQ-1; Thu, 18 Nov 2021 14:28:14 -0500 X-MC-Unique: F_TJTRsyNayfe0MmTSdniQ-1 Received: by mail-qk1-f197.google.com with SMTP id bq9-20020a05620a468900b004681cdb3483so5780038qkb.23 for ; Thu, 18 Nov 2021 11:28:13 -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:from:subject:cc; bh=oyqGtjb/V5VxhjtWbbaskON2nWbABpZv/RVa0XTD05Y=; b=GaWEXsFY5Ly8ipn15iSIre0cVODhcOVAKGhz3pcyQtpSMConXNrD7MB1za5Crb7Np7 PJbS9NG8lhV6tAnaPf5f/JbMxbWmCnX0577weMHP0jkVx2NYipVfHt0tZsUG+WwVx32k 7gGa+wA+zSB4lRZgQMO3bJu0EoBwvuQdM8etwDYsPS8jw44PDfA++uoIeP6vtRPdL9YY itCoMmuVpS9XyM/ueREn3z/KlTWPhFs5hKroMc14La6aDzklJ28bpbR8aR7ouSp9bo1/ v494gyYRCv08fUVL3eNHPhWiMcfm74BtH3h4gaMdHk+cUpwhfnjskLV4wFySggpm1ABN NKvg== X-Gm-Message-State: AOAM532cLD3gl95P68kdr7eo2MKH/tZvU+0iOAllosW/g4tPbYLvxH6B BTLXOcWGfpSvGJLLYT50ExuJd6Dv9PLLKXoWz9aJrmmuBftCLq3lKPhLwnVXN/9H9n9SkJfHP5/ V+aI/MQmiJiQj4rA0fWui5+oefFak1o/8idFLPmqYltmefwMgXrgKYgF1u4R+zwhtVdcOKw== X-Received: by 2002:ac8:5a90:: with SMTP id c16mr28639943qtc.199.1637263692907; Thu, 18 Nov 2021 11:28:12 -0800 (PST) X-Google-Smtp-Source: ABdhPJwdrQ/jrpSeuqRfn19CO1iGwY9D1VxyBOu9P63mVXysHyZTx/DDO/KzihZnwa6EcAPWODt48A== X-Received: by 2002:ac8:5a90:: with SMTP id c16mr28639913qtc.199.1637263692653; Thu, 18 Nov 2021 11:28:12 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id x125sm387044qkd.8.2021.11.18.11.28.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 18 Nov 2021 11:28:12 -0800 (PST) Message-ID: Date: Thu, 18 Nov 2021 14:28:10 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.1 To: gcc-patches From: Andrew MacLeod Subject: [PATCH] PR tree-optimization/103254 - Limit depth for all GORI expressions. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------FqcdAR1O2umwdv76PLigQJcG" Content-Language: en-CA X-Spam-Status: No, score=-12.8 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_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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: Thu, 18 Nov 2021 19:28:17 -0000 This is a multi-part message in MIME format. --------------FqcdAR1O2umwdv76PLigQJcG Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit At issue here is the dynamic approach we currently use for outgoing edge calculations.  It isn't normally a problem, but once you get a very large number of possible outgoing values (ie very long unrolled blocks) with pairs of values on a statement, and individual queries for each one, it becomes exponential if they relate to each other. So.  We previously introduced a param for PR 100081 which limited the depth of logical expressions GORI would pursue because we always make 2 or 4 queries for each logical expression, which accelerated the exponential behaviour much quicker. This patch reuses that to apply to any statement which has 2 ssa-names, as the potential for 2 queries can happen then as well..  leading to exponential behaviour.  Each statement we step back through with multiple ssa-names decreases the odds of calculating a useful outgoing range anyway.  This will remove ridiculous behaviour like this PR demonstrates. Next release I plan to revamp GORI to cache outgoing values, which will eliminate all this sort of behaviour, and we can remove all such restrictions. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK for trunk? Andrew PS. This also points out something we are investigating with the threader.  There are no uses of _14 outside the block, so asking for its range is problematic and contributing to excess work and cache filling that we don't need to be doing.  The VRP passes do not demonstrate this behaviour unless, as observed, we ask for details output which queries *all* the names. --------------FqcdAR1O2umwdv76PLigQJcG Content-Type: text/x-patch; charset=UTF-8; name="254-2.diff" Content-Disposition: attachment; filename="254-2.diff" Content-Transfer-Encoding: base64 Y29tbWl0IGJmZWNmNTEyZmI3MTlkY2IwNzJlNTRkODQyYjFlN2E2MmZlMDNkMmQKQXV0aG9yOiBB bmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4KRGF0ZTogICBXZWQgTm92IDE3IDE0 OjE0OjA2IDIwMjEgLTA1MDAKCiAgICBMaW1pdCBkZXB0aCBmb3IgYWxsIEdPUkkgZXhwcmVzc2lv bnMuCiAgICAKICAgIEFwcGx5IHRoZSBsb2dpY2FsX2RlcHRoIGxpbWl0IHJhbmdlciB1c2VzIHRv IGFsbCBzdG10cyB3aXRoIG11bHRpcGxlIHNzYS1uYW1lcwogICAgdG8gYXZvaWQgZXhjZXNzaXZl IG91dGdvaW5nIGNhbGN1bGF0aW9ucy4KICAgIAogICAgICAgICAgICBnY2MvCiAgICAgICAgICAg IFBSIHRyZWUtb3B0aW1pemF0aW9uLzEwMzI1NAogICAgICAgICAgICAqIGdpbXBsZS1yYW5nZS1n b3JpLmNjIChyYW5nZV9kZWZfY2hhaW46OmdldF9kZWZfY2hhaW4pOiBMaW1pdCB0aGUKICAgICAg ICAgICAgZGVwdGggZm9yIGFsbCBzdGF0ZW1lbnRzIHdpdGggbXVsdHBsZSBzc2EgbmFtZXMuCiAg ICAKICAgICAgICAgICAgZ2NjL3Rlc3RzdWl0ZS8KICAgICAgICAgICAgKiBnY2MuZGcvcHIxMDMy NTQuYzogTmV3LgoKZGlmZiAtLWdpdCBhL2djYy9naW1wbGUtcmFuZ2UtZ29yaS5jYyBiL2djYy9n aW1wbGUtcmFuZ2UtZ29yaS5jYwppbmRleCBmYjJkNTcxZWY0NC4uOTExZDdhYzRlYzggMTAwNjQ0 Ci0tLSBhL2djYy9naW1wbGUtcmFuZ2UtZ29yaS5jYworKysgYi9nY2MvZ2ltcGxlLXJhbmdlLWdv cmkuY2MKQEAgLTMzMSw3ICszMzEsNiBAQCByYW5nZV9kZWZfY2hhaW46OmdldF9kZWZfY2hhaW4g KHRyZWUgbmFtZSkKIHsKICAgdHJlZSBzc2ExLCBzc2EyLCBzc2EzOwogICB1bnNpZ25lZCB2ID0g U1NBX05BTUVfVkVSU0lPTiAobmFtZSk7Ci0gIGJvb2wgaXNfbG9naWNhbCA9IGZhbHNlOwogCiAg IC8vIElmIGl0IGhhcyBhbHJlYWR5IGJlZW4gcHJvY2Vzc2VkLCBqdXN0IHJldHVybiB0aGUgY2Fj aGVkIHZhbHVlLgogICBpZiAoaGFzX2RlZl9jaGFpbiAobmFtZSkpCkBAIC0zNDgsMTUgKzM0Nyw2 IEBAIHJhbmdlX2RlZl9jaGFpbjo6Z2V0X2RlZl9jaGFpbiAodHJlZSBuYW1lKQogICBnaW1wbGUg KnN0bXQgPSBTU0FfTkFNRV9ERUZfU1RNVCAobmFtZSk7CiAgIGlmIChnaW1wbGVfcmFuZ2VfaGFu ZGxlciAoc3RtdCkpCiAgICAgewotICAgICAgaXNfbG9naWNhbCA9IGlzX2dpbXBsZV9sb2dpY2Fs X3AgKHN0bXQpOwotICAgICAgLy8gVGVybWluYXRlIHRoZSBkZWYgY2hhaW5zIGlmIHdlIHNlZSB0 b28gbWFueSBjYXNjYWRpbmcgbG9naWNhbCBzdG10cy4KLSAgICAgIGlmIChpc19sb2dpY2FsKQot CXsKLQkgIGlmIChtX2xvZ2ljYWxfZGVwdGggPT0gcGFyYW1fcmFuZ2VyX2xvZ2ljYWxfZGVwdGgp Ci0JICAgIHJldHVybiBOVUxMOwotCSAgbV9sb2dpY2FsX2RlcHRoKys7Ci0JfQotCiAgICAgICBz c2ExID0gZ2ltcGxlX3JhbmdlX3NzYV9wIChnaW1wbGVfcmFuZ2Vfb3BlcmFuZDEgKHN0bXQpKTsK ICAgICAgIHNzYTIgPSBnaW1wbGVfcmFuZ2Vfc3NhX3AgKGdpbXBsZV9yYW5nZV9vcGVyYW5kMiAo c3RtdCkpOwogICAgICAgc3NhMyA9IE5VTExfVFJFRTsKQEAgLTM3Niw2ICszNjYsMTQgQEAgcmFu Z2VfZGVmX2NoYWluOjpnZXRfZGVmX2NoYWluICh0cmVlIG5hbWUpCiAgICAgICByZXR1cm4gTlVM TDsKICAgICB9CiAKKyAgLy8gVGVybWluYXRlIHRoZSBkZWYgY2hhaW5zIGlmIHdlIHNlZSB0b28g bWFueSBjYXNjYWRpbmcgc3RtdHMuCisgIGlmIChtX2xvZ2ljYWxfZGVwdGggPT0gcGFyYW1fcmFu Z2VyX2xvZ2ljYWxfZGVwdGgpCisgICAgcmV0dXJuIE5VTEw7CisKKyAgLy8gSW5jcmVhc2UgdGhl IGRlcHRoIGlmIHdlIGhhdmUgYSBwYWlyIG9mIHNzYS1uYW1lcy4KKyAgaWYgKHNzYTEgJiYgc3Nh MikKKyAgICBtX2xvZ2ljYWxfZGVwdGgrKzsKKwogICByZWdpc3Rlcl9kZXBlbmRlbmN5IChuYW1l LCBzc2ExLCBnaW1wbGVfYmIgKHN0bXQpKTsKICAgcmVnaXN0ZXJfZGVwZW5kZW5jeSAobmFtZSwg c3NhMiwgZ2ltcGxlX2JiIChzdG10KSk7CiAgIHJlZ2lzdGVyX2RlcGVuZGVuY3kgKG5hbWUsIHNz YTMsIGdpbXBsZV9iYiAoc3RtdCkpOwpAQCAtMzgzLDcgKzM4MSw3IEBAIHJhbmdlX2RlZl9jaGFp bjo6Z2V0X2RlZl9jaGFpbiAodHJlZSBuYW1lKQogICBpZiAoIXNzYTEgJiYgIXNzYTIgJiAhc3Nh MykKICAgICBzZXRfaW1wb3J0IChtX2RlZl9jaGFpblt2XSwgbmFtZSwgTlVMTCk7CiAKLSAgaWYg KGlzX2xvZ2ljYWwpCisgIGlmIChzc2ExICYmIHNzYTIpCiAgICAgbV9sb2dpY2FsX2RlcHRoLS07 CiAKICAgcmV0dXJuIG1fZGVmX2NoYWluW3ZdLmJtOwpkaWZmIC0tZ2l0IGEvZ2NjL3Rlc3RzdWl0 ZS9nY2MuZGcvcHIxMDMyNTQuYyBiL2djYy90ZXN0c3VpdGUvZ2NjLmRnL3ByMTAzMjU0LmMKbmV3 IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAuLjYyZDI0MTVmMjE2Ci0tLSAvZGV2 L251bGwKKysrIGIvZ2NjL3Rlc3RzdWl0ZS9nY2MuZGcvcHIxMDMyNTQuYwpAQCAtMCwwICsxLDI1 IEBACisvKiB7IGRnLWRvIGNvbXBpbGUgfSAqLworLyogeyBkZy1vcHRpb25zICItTzMiIH0gKi8K Ky8qIHsgZGctdGltZW91dCAxMCB9ICovCisKK3Nob3J0IGludCBpOworCit2b2lkCitmb28gKHZv aWQpCit7CisgIGZvciAoaSA9IDE7IGkgPCAyOyBpICs9IDQpCisgICAgeworICAgICAgaW50IGo7 CisKKyAgICAgIGZvciAoaiA9IDA7IGogPCA1OyBqICs9IDQpCisgICAgICAgIHsKKyAgICAgICAg ICBpbnQgazsKKworICAgICAgICAgIGZvciAoayA9IDA7IGsgPCA2ODsgayArPSA0KQorICAgICAg ICAgICAgeworICAgICAgICAgICAgICBpICY9IGo7CisgICAgICAgICAgICAgIGogJj0gaTsKKyAg ICAgICAgICAgIH0KKyAgICAgICAgfQorICAgIH0KK30K --------------FqcdAR1O2umwdv76PLigQJcG--