From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com [IPv6:2a00:1450:4864:20::52f]) by sourceware.org (Postfix) with ESMTPS id 1AF343858C3A for ; Tue, 11 Jan 2022 07:01:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1AF343858C3A Received: by mail-ed1-x52f.google.com with SMTP id 30so61609813edv.3 for ; Mon, 10 Jan 2022 23:01: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:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=dEG6D6SjmMDYG3PBrqGWiAejCBuZCSxDHkEluyz4/Kc=; b=hhWYAVTeRISsmSoh0G5rxJ1KR4PmByc0HaIceRIKyJv+S1q3GHEQGCN12NR+2z4gUx 6SUeoux8+a591Gp+3hJFviL1HxuaE3+8Nj7TqFuUcPoaXHUSTjk/+faluRP/BvnQbTNQ WwA3HC3xXi5FkwSlCFACUCzxrLu+0nU1QiJsW8GHHAylaWNoxHCEggip8nOSclOOyDRe ikjt73Z4vaLOJ5EXlS8CnZCQPO8g+usHHQ2ZZ/qyMC5aJfG6+WxW5zS/qEegrQCGNyaP qwGQqzprNw7ZlwuKwlJS44GsFxc/KlOt/FyHOL8j7tK2Fc/PLTHVLE9AvBXv8FWaY9kt 1IFg== X-Gm-Message-State: AOAM530jFSYagfk/8Fhdey03/clB8r7QXp/ruZKhhmFLJHtMA0EQYmLh IUhO7KI+Fy/5bkJ6in28KTxOkCGzZcMOFjlkcRQ= X-Google-Smtp-Source: ABdhPJwCf5lXTZw1+D1FEpJ0kF4pG3m/QFTyNpHafKqnikxP4DTQ/MOOGHPwjjOUdh+AXUtlZK3anQNI1+FwBKJjSg8= X-Received: by 2002:a05:6402:1d50:: with SMTP id dz16mr3083412edb.348.1641884479003; Mon, 10 Jan 2022 23:01:19 -0800 (PST) MIME-Version: 1.0 References: <65928812-1ff1-7e69-3b1e-7ca62e09cc79@redhat.com> In-Reply-To: <65928812-1ff1-7e69-3b1e-7ca62e09cc79@redhat.com> From: Richard Biener Date: Tue, 11 Jan 2022 08:01:08 +0100 Message-ID: Subject: Re: [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations. To: Andrew MacLeod Cc: gcc-patches Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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 07:01:21 -0000 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). > 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? OK. Thanks, Richard. > > Andrew