From patchwork Fri Feb 10 02:38:06 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 55190 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp709882wrn; Thu, 9 Feb 2023 18:39:01 -0800 (PST) X-Google-Smtp-Source: AK7set9PorNs8mll/upzjgdREpLxLlnnSqIlshQCYTJNS+lE2GD1LnWt69seaeqHjBSEQxqe9Owo X-Received: by 2002:a17:906:8284:b0:87b:bbd4:1bd2 with SMTP id h4-20020a170906828400b0087bbbd41bd2mr14280295ejx.52.1675996741812; Thu, 09 Feb 2023 18:39:01 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1675996741; cv=none; d=google.com; s=arc-20160816; b=hW0NPUI1RL0JZ6BteFyzuhlRm7Lweeu1RRpMMZ8sDgixHrLl1mbt40hnq1Jc2a8TCq dWS32K/fUCFZq0dB6CmnKcC8c/xOfhPg+mE1H2Y7LWivW/USwgU877IrpyU4DfdBnHNh 0WrRpsTegdhtVnUdm4FWkcdqvc1nIborn7hZvp7tk9DKXaCivktR4IZoiwawfSz9hbNu /vOiveMHz2iQAYHWm39MOBebtcQheUos6zf/q18nwC27xwnoQ+aED7kJRinAmHqH5oBh VpQYwWww/ROhoK05SROGkxe4y9S1MkqaAhdfyyToc/P15Te/EEsYNLxDvtLpFdHF1x51 i85w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:cc:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=0BYafEs3tXXlRppyZTE6TaJWu82l9WZMKfKtSFeZdts=; b=UdwxzMBOIpaKXEFtTkXNTYxXKGGnlxDlvmglFPw06f105CnZ8w8KRGP+q8G5d9fwYj qgoW7T4AFSihTMZop7M7f2ZqhgbFhvbUk7orFu5mHxlugMIVfyXBoFFZXXbRoPp0WDPy WIysH0sVyUGBIJ82WO9+H/uRnLLqpTunYTJAfwfVZomwAeHr/HiXJqGVvrMbMGLEYPF9 lCnXJGvjiKLwcEJCynLm+91mc5aWVMekkloIrVAPBRXejxZcChk0Dd35l1eTiGHbOqSP nXnXDQnYR/urnhWOPyJrSIWbiiEloCt5nNQyaKSe1jbPXXIjPmS5RiGM7pXk6qxhnvl9 1PAg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=FLjmJcVw; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id eu9-20020a170907298900b008af3df2c2c8si3389339ejc.214.2023.02.09.18.39.01 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 09 Feb 2023 18:39:01 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=FLjmJcVw; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 799553857838 for ; Fri, 10 Feb 2023 02:39:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 799553857838 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1675996740; bh=0BYafEs3tXXlRppyZTE6TaJWu82l9WZMKfKtSFeZdts=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=FLjmJcVwNwi+JacWWrGtQtCoXoGTBUZefulhBVmnEJ93YvlLz6xkV24O4s7h5jBEQ dGAdhUSt0OiIDO73zR/buqTNRqm2Dt8slE9v2FoeyeWmBXISMzfxFi2V3h1tydUdMU 3yOAuoVbUnszbLmIuX2M70nV6HZB9pR+eGjriX78= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 36D833858C50 for ; Fri, 10 Feb 2023 02:38:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 36D833858C50 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-82-OXDcOWRUNQWd9aP9PTnbbg-1; Thu, 09 Feb 2023 21:38:09 -0500 X-MC-Unique: OXDcOWRUNQWd9aP9PTnbbg-1 Received: by mail-qt1-f199.google.com with SMTP id cr22-20020a05622a429600b003b694a9f291so2292496qtb.1 for ; Thu, 09 Feb 2023 18:38:09 -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=Wh90OKjC8q8ESrGgyxQvs47wLyy2wrPftNwILW2HmlM=; b=71bJbf8LFizxEkZAs4byUtA4QPmtE50rVDXJUCGk8KkD0+FLLkI1CiAL/IRb/JeyYC MMWQ577wg7JhudpPRbHhYuFvaVBYBCFOweHA+1Sxa+ePRyN3bY5BbZiDdTykXJsMFcbW g3dYvvFP5gU4VtqWtkHiedUJZFJrlfIGuh0FQI28BHYE3CAojNEJxpGjJMfnVF16dlKo rqjUgLxGMLBuHtC7qtR2MFCmdo6D3+WlgeaUkjC2BFjc88SLrFWeAeN3VIMcbpynqiOe m10IudrfBimFruEGP410jDPZhY9MF3df/E9o+GrfaXIbs2+6fKvMZiUwy2JSGCDTBlIm Nhpw== X-Gm-Message-State: AO0yUKWvlorgz7fz7BaOFadSwcWEpBGsBNkfLD9sIQtd+lcEXLm+Cr7c a4biYFwVwZxPjWvc58kl3ZeV0NNB7Rp8+dtAOBRqBkVXEUpLlecCPrfkTOMBBrY1r1q474pXZSV BI6/uKzLcEUSrVRGsxx+3Ju7WDP3xsSumi+oXBkisd0t2VbZAKwewdXB5Fabf6DzbAkb53g5UH/ s= X-Received: by 2002:ac8:5913:0:b0:3b9:bd05:bde1 with SMTP id 19-20020ac85913000000b003b9bd05bde1mr21489587qty.8.1675996688503; Thu, 09 Feb 2023 18:38:08 -0800 (PST) X-Received: by 2002:ac8:5913:0:b0:3b9:bd05:bde1 with SMTP id 19-20020ac85913000000b003b9bd05bde1mr21489570qty.8.1675996688202; Thu, 09 Feb 2023 18:38:08 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::de2a? ([2607:fea8:a263:f600::de2a]) by smtp.gmail.com with ESMTPSA id ew12-20020a05622a514c00b003b86a6449b8sm2502575qtb.85.2023.02.09.18.38.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 09 Feb 2023 18:38:07 -0800 (PST) Message-ID: <11e4d748-a5e7-8931-ccad-911f3591da3b@redhat.com> Date: Thu, 9 Feb 2023 21:38:06 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.0 To: gcc-patches Cc: "hernandez, aldy" , Richard Biener Subject: [PATCH] PR tree-optimization/108687 - Query rangers cache in readonly mode only internally X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.4 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 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1757409959448920122?= X-GMAIL-MSGID: =?utf-8?q?1757409959448920122?= The change for 108356 allowed the cache to scan the dominator trees when it was attempting a lookup rather than using the local value.  I inadvertantly changed the external interface to also do this, so all the GORI queries via range_on_edge of the cache could also do lookups in this mode. This triggered a quadratic, possible exponential time increase when the right conditions were presented. That being a cascading series of recomputations on outgoing edge calculations that at then searched the dom tree instead of being a simple calculation using whats easily available. The fix is to use the internal API within the cache rather than the extrenal one that GORI uses.   This leaves GORI computations to be resolved in linear time.  GORI is designed to only use what immediately available and should never trigger new lookups of its own.  Doh. This may possibly fix a a few other new large time growth issues in DOM and friends,  such as 108705. bootstrapped on x86_64-pc-linux-gnu, regtesting ongoing.. assuming no issues, OK for trunk? Andrew From 39f573402e92ab07fbe8a2ced513d8de63881135 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 9 Feb 2023 17:50:07 -0500 Subject: [PATCH 2/4] Query rangers cache in readonly mode only from within The change for 108356 allowed the cache to scan the dominator trees when it was attempting a lookup rather than using the local value. I inadvertantly changed the externbal interface to also do this, so all the GORI queries via range_on_edge of the cache could also do lookups. This triggered a quadratic, possible expoential time increase when the right conditions were presented. That being a cascading series of recomputaions on outgoing edge calucaltions that at then searched the dom tree instead of being a simple calcualtion using whats easily available. The fix is to use the internal API within the cache rather than the extrenal one that GORI uses. This leaves GORI computations to be resovled in linear time. PR tree-optimization/108687 gcc/ * gimple-range-cache.cc (ranger_cache::range_on_edge): Revert back to RFD_NONE mode for calculations. (ranger_cache::propagate_cache): Call the internal edge range API with RFD_READ_ONLY instead of changing the external routine. --- gcc/gimple-range-cache.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 20c444bc4f4..546262c4794 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -998,7 +998,7 @@ bool ranger_cache::range_on_edge (vrange &r, edge e, tree expr) { if (gimple_range_ssa_p (expr)) - return edge_range (r, e, expr, RFD_READ_ONLY); + return edge_range (r, e, expr, RFD_NONE); return get_tree_range (r, expr, NULL); } @@ -1081,7 +1081,7 @@ ranger_cache::propagate_cache (tree name) new_range.set_undefined (); FOR_EACH_EDGE (e, ei, bb->preds) { - range_on_edge (e_range, e, name); + edge_range (e_range, e, name, RFD_READ_ONLY); if (DEBUG_RANGE_CACHE) { fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index); -- 2.39.0