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 8BBBD3857702 for ; Thu, 25 May 2023 14:01:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8BBBD3857702 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1685023281; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=PJsMzyBtXfWFqUGWruVyLTwQU/Ch4MXoDN4qfvjCDh0=; b=BPDd0qVDyR2eqOx5Hh0UWKn9kNGcRr41PyC2XRWwmJBqFv/zaf5mMEX7ZZbaEzrtsDPLkC kT5NQqS7SzvmdIqcDL3KBI4P8nJAF0JW9nI6J9Qf3eoSTPOiwog6iLerJXeHjkA9nUg7zy oIYz7WRaJQDjl20cp7ZRp98ArXe4C30= Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-612-CF-EPSNTPE6CG_yOeDqsNQ-1; Thu, 25 May 2023 10:01:17 -0400 X-MC-Unique: CF-EPSNTPE6CG_yOeDqsNQ-1 Received: by mail-qt1-f200.google.com with SMTP id d75a77b69052e-3f6c1baafa5so9894181cf.2 for ; Thu, 25 May 2023 07:01:17 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685023276; x=1687615276; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=PJsMzyBtXfWFqUGWruVyLTwQU/Ch4MXoDN4qfvjCDh0=; b=k39ap58zrWv6AoNPkLTsfhMGhw9OHW2CDnSujY3gerOTbcxDWaw6Uf9oQfFo+YGg4B EZgXj6NtK1NmTwHUl4yGDqDQzwaF8/JTW9FmyPY9LyFXoxNoCPIifsIb/9zpPKaDKnCB EPuYz5Xf13RDnGTcZXJ0dEs161/2u0+AIaoOkbSCmR9goJWtCJ1IjXzigUU5K1DA9yvn 8W2enG0eGBcYEWJFnVMVNLja/vQXeIFK7+0kwklJpUoLtjBHQE2fFTCSH/B9L6BbnNCK 6tjZHbGdeMQAjI5OusBCMqLIvHUjaOAirJoEInEcIFfBHStj9E9iCJarE6T/5xRccLit gITA== X-Gm-Message-State: AC+VfDxeMTNs+GAqS7xT9w3XuBM4Sbo30AykXR8BfudW/FZq6AShW6TH nQhH9fuYPTTU9hl6cFOpUtPE3XGAEt9XyjtrxyeLkdG27qXSJmi9imxGUaBFY+uIkTBHAcmeYKj zoPFXm8t9b6MZVn/ZSzHxenysgQ== X-Received: by 2002:a05:622a:1349:b0:3f4:e1e3:5ba with SMTP id w9-20020a05622a134900b003f4e1e305bamr30738423qtk.68.1685023276163; Thu, 25 May 2023 07:01:16 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7ryP2K/jGHx7cu4lIadxPuCxCfXdsaz56df8F/VskQbd6LGbSdYCcS4JVpu2ZHyWjL38Q4Zw== X-Received: by 2002:a05:622a:1349:b0:3f4:e1e3:5ba with SMTP id w9-20020a05622a134900b003f4e1e305bamr30738378qtk.68.1685023275784; Thu, 25 May 2023 07:01:15 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id fc22-20020a05622a489600b003e0945575dasm431832qtb.1.2023.05.25.07.01.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 25 May 2023 07:01:15 -0700 (PDT) Message-ID: Date: Thu, 25 May 2023 10:01:14 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases To: Richard Biener Cc: gcc-patches , "hernandez, aldy" References: <6a24c0bf-aa0d-5e13-6852-705605db15ec@redhat.com> From: Andrew MacLeod In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.2 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_NONE,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 5/25/23 03:03, Richard Biener wrote: > On Wed, May 24, 2023 at 11:21 PM Andrew MacLeod via Gcc-patches > > > There is about a 1.5% slowdown to VRP to invoke and utilize the > analyzer in all 3 passes of VRP. overall compile time is 0.06% slower. > > Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed. > Hm. What I've noticed the last time looking at how ranger deals > with PHIs is that it diverts to SCEV analysis for all of them but > it could restrict itself to analyze PHIs in loop headers > (bb->loop_father->header == bb). That only handles natural > loops of course but that was good enough for the old VRP implementation. > That might also help to keep the PHI anlyzer leaner by less entires. > > I've only quickly looked at the PHI analyzer and I failed to understand > how you discover cycles. I'm pointing you to the SCC value-numbering > cycle finding which you can find for example on the GCC 7 branch > (it's gone for quite some time) in tree-ssa-sccvn.c:DFS - that collects > strongly connected SSA components (it walks all uses, you probably > want to ignore virtuals). SCEV also has its own cycle finding > (well, sort of) with the scev_dfs class and it restricts itself to > operations it handles (so it's more close to what you do). > > I fear you're developing sth very ad-hoc here. > Not something Ad-hoc in this compiler! This is primarily an initial value estimator.  There is no attempt to do any loop analysis or anything like that. It doesn't look for cycles per se, merely PHI nodes which feed each other and are modified in a straight forward way.. ie initialized on one edge and modified via one statement that we can then look at to decide how it affects the range of all the PHI nodes. This can eventually be changed to a sequence of a few statements, but one gets us started with the simple cases. All the rest of the PHI arguments come from PHI nodes and share the same value.  This can allow us to project a range which is better than VARYING.  SCEV doesnt seem to help much in these cases.  It's pretty straightforward which is why it isn't much code. all handled in  phi_analyzer::process_phi().   Add phi node to worklist, examine each argument, if it iis a PHI def, add it to the worklist  if it hasnt been processed, otherwise, its an external input to the group, and bail if we get more than 2 of these. Andrew Andrew