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 AB43238AAC23 for ; Tue, 11 Jan 2022 14:15:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AB43238AAC23 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-423-1Nbs-aXRPEupcqCyrtushA-1; Tue, 11 Jan 2022 09:15:10 -0500 X-MC-Unique: 1Nbs-aXRPEupcqCyrtushA-1 Received: by mail-qv1-f72.google.com with SMTP id r7-20020a0562140c8700b00413d42bccefso15809270qvr.10 for ; Tue, 11 Jan 2022 06:15:10 -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:subject :content-language:to:cc:references:from:in-reply-to :content-transfer-encoding; bh=OiEwCix9QcBSwTDPUshihdL/6GDgkKfWOz+z+7dku8M=; b=0t+H9UIuh3Oo+JeMrNvCWlK1W+G35fjfMKdDLYowSlh/VfUBbDZj22vcpdCCimqSGH UIiima3Ti9opqiDiIdjtpWgjbmWgdCEoDdQKdmWlfP78GCSY7EtpAkMt3GO1vzQbUl7Z wGhn+VMfmdgB6WUOYpq8b++8Sk9fBxSX7VJsjw5pFE9LDdvSAba0vvG56fZMkfUhSIKV JzcOYLlZtsaDXIDLYayLeMdkPOCdPYBzABR98aLNB2At01V80yx9t9pJy5V2HL/dJ87j fbHSPRklMIICXoSMWYgeQcDu/AS7h5PT/7omXDZLAjftzEZkBrucxPoi1b9ZdbN1cHwc VY8w== X-Gm-Message-State: AOAM5306ob+bPiIX/BVyvfX6DEhbMZAPcFVuHsJ+wBNDdgzymiaexeqh hrjucJ8r7VTnq2p2oe4MvdBl+M51rIw+RclF36iSdOY2pdZ3GpQ1repBAxAeU+5vT+xL5W6J//G 5I9xGp4LwzM8ThzuH9w== X-Received: by 2002:a05:622a:1485:: with SMTP id t5mr3813776qtx.610.1641910509298; Tue, 11 Jan 2022 06:15:09 -0800 (PST) X-Google-Smtp-Source: ABdhPJyNPYUU5zULFG7g2njAqVYLaK6AJRz3ZM8hZZ0IcxW2S6/28pGgQDiRC1Bd8iyaNfKOnSsvbQ== X-Received: by 2002:a05:622a:1485:: with SMTP id t5mr3813748qtx.610.1641910509026; Tue, 11 Jan 2022 06:15:09 -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 h9sm3767897qkn.60.2022.01.11.06.15.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 11 Jan 2022 06:15:08 -0800 (PST) Message-ID: Date: Tue, 11 Jan 2022 09:15:06 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.1 Subject: Re: [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations. To: Richard Biener Cc: gcc-patches , Aldy Hernandez References: <65928812-1ff1-7e69-3b1e-7ca62e09cc79@redhat.com> From: Andrew MacLeod In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, 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: Tue, 11 Jan 2022 14:15:13 -0000 On 1/11/22 02:01, Richard Biener wrote: > On Tue, Jan 11, 2022 at 12:28 AM Andrew MacLeod via Gcc-patches > wrote: >> 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. > I'm not sure we can do smarter in a good way other than maybe having > a range helper that reduces a N component range to M components > with maintaining as much precision as possible? Like for [1, 1] u [3, 3] > u [100, 100] and requesting at most 2 elements merge [1, 1] and [3, 3] > and not [100, 100]. That should eventually be doable in O(n log n). Yeah, similar to my line of thought.  It may also be worth considering something similar after we have calculated a range sometimes.  if the resulting range has more than N sub-ranges, look to see if it is worthwhile trying to compress it at that point too maybe.  Something for the next stage-1 to consider. Andrew