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.129.124]) by sourceware.org (Postfix) with ESMTPS id 4BEF13858400 for ; Mon, 10 Jan 2022 23:27:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4BEF13858400 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-605-XZ6Nekd3NruDqenH53iK1g-1; Mon, 10 Jan 2022 18:27:33 -0500 X-MC-Unique: XZ6Nekd3NruDqenH53iK1g-1 Received: by mail-qk1-f199.google.com with SMTP id v3-20020a376103000000b004782a1ed001so781553qkb.0 for ; Mon, 10 Jan 2022 15:27:33 -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; bh=bs00DjrgvZro51hj9CLV0AMaYdU2lBrOpgxZ7DAmGI8=; b=15glcN19AoGys2wKpifrdfjr9Lt5aUTP2FnV5icSKJxkzGFhhwEYkIwllzGiP3RxvI 3hliFZbaKSX331a6aK98DwbzwuFGt6Tt2dUEgc6xutbiH5nFgwuZG9WDPdee/FYPXiNV YjYWLOWHwv2rtb6hURGxfrqWXOxHAzfODy1GraeggGoSH9u2GrR8y58oE6Ehsqloos8R jCzZyZQTxMDCeZOLVQss/y1VAB1u+WWqLEUZA60beO7GFiQP18XjwSMJfQsK7tS8mM0g smDyOCR+iG2S7u19RinXiIa7jpxD1TjjBRb86rA8F94+RxgMKf/VIGkICd1B09yrhS44 CWmA== X-Gm-Message-State: AOAM533OI3sRL6x0BAByW2MhnkBvUhDLoAZbmu5rf3s79WdQF6ynNcgB rqhXYs5oF9Ton1Aux7zWURSEcqCOHrvae4grbZUjB8mrF7B/HwD6IjmXToOejtdKqGNztqRDQAF 258M/bjrIv73r5+dC7V6C8bi7H5WqiACNcDcsngpshJxYvku4N4GugI/m+D+b0TD36hsA1g== X-Received: by 2002:ac8:7d8d:: with SMTP id c13mr1817220qtd.609.1641857252856; Mon, 10 Jan 2022 15:27:32 -0800 (PST) X-Google-Smtp-Source: ABdhPJwLs4BcLZHJS9eQvkmSyIWZ9nYN2yRf6u+v3Zl/8Ix3J3HO98ey+WnbLc7OjlHwl3q+pzRSkA== X-Received: by 2002:ac8:7d8d:: with SMTP id c13mr1817204qtd.609.1641857252518; Mon, 10 Jan 2022 15:27:32 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00:e36d:32da:80f:d4e1? ([2607:fea8:a262:5f00:e36d:32da:80f:d4e1]) by smtp.gmail.com with ESMTPSA id u7sm5882007qta.32.2022.01.10.15.27.31 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 10 Jan 2022 15:27:31 -0800 (PST) Message-ID: <65928812-1ff1-7e69-3b1e-7ca62e09cc79@redhat.com> Date: Mon, 10 Jan 2022 18:27:30 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.1 To: gcc-patches From: Andrew MacLeod Subject: [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------5tye0YbwixjInmtUN1tR524I" Content-Language: en-CA 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_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, 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: Mon, 10 Jan 2022 23:27:36 -0000 This is a multi-part message in MIME format. --------------5tye0YbwixjInmtUN1tR524I Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit This test case demonstrates an unnoticed exponential situation in range-ops. We end up unrolling the  loop, and the pattern of code creates a set of cascading multiplies for which we can precisely evaluate them with sub-ranges. For instance, we calculated : _38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344] so _38 has 4 sub-ranges, and then we calculate: _39 = _38 * _38; we do 16 sub-range multiplications and end up with:  int [67108864, 67108864][201326592, 201326592][335544320, 335544320][469762048, 469762048][603979776, 603979776][1006632960, 1006632960][1409286144, 1409286144][1677721600, 1677721600][+INF, +INF] This feeds other multiplies (_39 * _39)  and progresses rapidly to blow up the number of sub-ranges in subsequent operations. Folding of sub-ranges is an O(n*m) process. We perform the operation on each pair of sub-ranges and union them.   Values like _38 * _38 that continue feeding each other quickly become exponential. Then combining that with union (an inherently linear operation over the number of sub-ranges) at each step of the way adds an additional quadratic operation on top of the exponential factor. This patch adjusts the wi_fold routine to recognize when the calculation is moving in an exponential direction, simply produce a summary result instead of a precise one.  The attached patch does this if (#LH sub-ranges * #RH sub-ranges > 12)... then it just performs the operation with the lower and upper bound instead.    We could choose a different number, but that one seems to keep things under control, and allows us to process up to a 3x4 operation for precision (there is a testcase in the testsuite for this combination gcc.dg/tree-ssa/pr61839_2.c).    Longer term, we might want adjust this routine to be slightly smarter than that, but this is a virtually zero-risk solution this late in the release cycle. This also a generalize ~1% speedup in the VRP2 pass across 380 gcc source files, but I'm sure has much more dramatic results at -O3 that this testcase exposes. Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk? Andrew --------------5tye0YbwixjInmtUN1tR524I Content-Type: text/x-patch; charset=UTF-8; name="821.diff" Content-Disposition: attachment; filename="821.diff" Content-Transfer-Encoding: base64 Y29tbWl0IGQ4YzVjMzdkNTM2MmJkODc2MTE4OTQ5ZGU3NjA4NmRhYmE3NTZhY2UKQXV0aG9yOiBB bmRyZXcgTWFjTGVvZCA8YW1hY2xlb2RAcmVkaGF0LmNvbT4KRGF0ZTogICBNb24gSmFuIDEwIDEz OjMzOjQ0IDIwMjIgLTA1MDAKCiAgICBQcmV2ZW50IGV4cG9uZW50aWFsIHJhbmdlIGNhbGN1bGF0 aW9ucy4KICAgIAogICAgUHJvZHVjZSBhIHN1bW1hcnkgcmVzdWx0IGZvciBhbnkgb3BlcmF0aW9u IGludm9sdmluZyB0b28gbWFueSBzdWJyYW5nZXMuCiAgICAKICAgICAgICAgICAgUFIgdHJlZS1v cHRpbWl6YXRpb24vMTAzODIxCiAgICAgICAgICAgICogcmFuZ2Utb3AuY2MgKHJhbmdlX29wZXJh dG9yOjpmb2xkX3JhbmdlKTogT25seSBkbyBwcmVjaXNlIHJhbmdlcwogICAgICAgICAgICB3aGVu IHRoZXJlIGFyZSBub3QgdG9vIG1hbnkgc3VicmFuZ2VzLgogICAgCiAgICByYW5nZV9vcGVyYXRv cjo6Zm9sZF9yYW5nZQoKZGlmZiAtLWdpdCBhL2djYy9yYW5nZS1vcC5jYyBiL2djYy9yYW5nZS1v cC5jYwppbmRleCAxYWY0MmViYzM3Ni4uYTRmNmU5ZWJhMjkgMTAwNjQ0Ci0tLSBhL2djYy9yYW5n ZS1vcC5jYworKysgYi9nY2MvcmFuZ2Utb3AuY2MKQEAgLTIwOSwxMCArMjA5LDEyIEBAIHJhbmdl X29wZXJhdG9yOjpmb2xkX3JhbmdlIChpcmFuZ2UgJnIsIHRyZWUgdHlwZSwKICAgdW5zaWduZWQg bnVtX3JoID0gcmgubnVtX3BhaXJzICgpOwogCiAgIC8vIElmIGJvdGggcmFuZ2VzIGFyZSBzaW5n bGUgcGFpcnMsIGZvbGQgZGlyZWN0bHkgaW50byB0aGUgcmVzdWx0IHJhbmdlLgotICBpZiAobnVt X2xoID09IDEgJiYgbnVtX3JoID09IDEpCisgIC8vIElmIHRoZSBudW1iZXIgb2Ygc3VicmFuZ2Vz IGdyb3dzIHRvbyBoaWdoLCBwcm9kdWNlIGEgc3VtbWFyeSByZXN1bHQgYXMgdGhlCisgIC8vIGxv b3AgYmVjb21lcyBleHBvbmVudGlhbCB3aXRoIGxpdHRsZSBiZW5lZml0LiAgU2VlIFBSIDEwMzgy MS4KKyAgaWYgKChudW1fbGggPT0gMSAmJiBudW1fcmggPT0gMSkgfHwgbnVtX2xoICogbnVtX3Jo ID4gMTIpCiAgICAgewotICAgICAgd2lfZm9sZF9pbl9wYXJ0cyAociwgdHlwZSwgbGgubG93ZXJf Ym91bmQgKDApLCBsaC51cHBlcl9ib3VuZCAoMCksCi0JCQlyaC5sb3dlcl9ib3VuZCAoMCksIHJo LnVwcGVyX2JvdW5kICgwKSk7CisgICAgICB3aV9mb2xkX2luX3BhcnRzIChyLCB0eXBlLCBsaC5s b3dlcl9ib3VuZCAoKSwgbGgudXBwZXJfYm91bmQgKCksCisJCQlyaC5sb3dlcl9ib3VuZCAoKSwg cmgudXBwZXJfYm91bmQgKCkpOwogICAgICAgb3AxX29wMl9yZWxhdGlvbl9lZmZlY3QgKHIsIHR5 cGUsIGxoLCByaCwgcmVsKTsKICAgICAgIHJldHVybiB0cnVlOwogICAgIH0K --------------5tye0YbwixjInmtUN1tR524I--