From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) by sourceware.org (Postfix) with ESMTPS id 3DA3A3889826 for ; Thu, 25 May 2023 07:06:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3DA3A3889826 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lj1-x236.google.com with SMTP id 38308e7fff4ca-2af2602848aso2317921fa.2 for ; Thu, 25 May 2023 00:06:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1684998362; x=1687590362; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=98OYo7tr17mOVZlDSw/NzeivOCLME4F9jT1x4WPn6KI=; b=itS2EBJJKIBrbF0zzlhpNado256y8ynrIjFB0ZWZhyIDkfcw0jSqS/PZWLt3WkhizL aZh6+U+b2xMZQ4g7f77SlqNFmIGXmrnNTKY6n71VxcaLvj1OBDSA9WHLFYvxD6qP5FQ0 ciwN1HdyGd0eXPd+opYvZY/LFjrhd3G3EfPcY+EDrJjrkHtc/NMkyagaukHpJpkBnHHl iNF1HsuYu46kj2/XyT+5N6HKys95pCma3JzShAiZhmSvFRE7VmGYwC0LCTl3gE7MDqp5 wRQmMGZGZqnvEWyMdg6TGHKxvCjE90Db8ZQaw6dCXcpt00TORv25bl/kY+U/93/5hnK0 oMBw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684998362; x=1687590362; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=98OYo7tr17mOVZlDSw/NzeivOCLME4F9jT1x4WPn6KI=; b=Rhhm69upk1yKEFDCGXFpJcKXwMN0EXbRycLcVeSylKXrxs/ZPPcxL4PRF6jOApcD3V Iwf8/vnaesirT4+coqlGsSVHdy+RM/1ruQ2fZq1EQBdPALukWnLtLnpMsyc69eyVLBin 1oyAPC/ZCpS/XnL1MHcJ8tj5bBbGvart/NIShjnsH3mfEcFXVkg3lBwa5dhBUv5bnZ0m QmoXx7hkr8FtRLcQ2mP1nzozrtV7CX4GwS1huO5JyDWi1jGZNiuAYOxhTncgq/sKUBSC zK4QXlRnt7ic+M3EFlj1Zv0Yoir2v4VF9a8nklw7tsN2uR/47smF/gjNW0fffEIP4624 nZRQ== X-Gm-Message-State: AC+VfDx+jROFR5KlgdlM3/1yQS2+2rAVdP2SSfRlO694j89kKxOYXqtc TSySwVP42u3DKxG30ulIF1quSgyIReFys3dlEjzPOpOU X-Google-Smtp-Source: ACHHUZ7a9tnVRbg8t2sCdtWxa80D1VKGZIPcnbRpADyDUao0wTbBeqJEFZXh2LG0boEfRDjI8biMydd+XQrk+t+cK1c= X-Received: by 2002:a2e:9217:0:b0:2a8:aec9:b0ba with SMTP id k23-20020a2e9217000000b002a8aec9b0bamr784235ljg.11.1684998362395; Thu, 25 May 2023 00:06:02 -0700 (PDT) MIME-Version: 1.0 References: <6a24c0bf-aa0d-5e13-6852-705605db15ec@redhat.com> In-Reply-To: <6a24c0bf-aa0d-5e13-6852-705605db15ec@redhat.com> From: Richard Biener Date: Thu, 25 May 2023 09:03:55 +0200 Message-ID: Subject: Re: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases To: Andrew MacLeod Cc: gcc-patches , "hernandez, aldy" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.4 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,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 Wed, May 24, 2023 at 11:21=E2=80=AFPM Andrew MacLeod via Gcc-patches wrote: > > This patch provide the framework for a gimple-range phi analyzer. > > Currently, the primary purpose is to give better initial values for > members of a "phi group" > > a PHI group is defined as a a group of PHI nodes whose arguments are all > either members of the same PHI group, or one of 2 other values: > - An initializer, (typically a constant), but not necessarily, > - A modifier, which is always of the form: member_ssa =3D member_ssa > OP op2 > > When the analyzer finds a group which matches this pattern, it tries to > evaluate the modifier using the initial value and project a range for > the entire group. > > This initial version is fairly simplistic. It looks for 2 things: > > 1) if there is a relation between LHS and the other ssa_name in the > modifier, then we can project a range. ie, > a_3 =3D a_2 + 1 > if there is a relation generated by the stmt which say a_3 > a_2, and > the initial value is 0, we can project a range of [0, +INF] as the > moifier will cause the value to always increase, and not wrap. > > Likewise, for a_3 =3D a_2 - 1, we can project a range of [-INF, 0] based > on the "<" relationship between a_3 and a_2. > > 2) If there is no relationship, then we use the initial range and > "simulate" the modifier statement a set number of times looking to see > if the value converges. > Currently I have arbitrarily hard coded 10 attempts, but intend to > change this down the road with a --param, as well as to perhaps > influence it with any known values from SCEV regarding known iterations > of the loop and possibly change it based on optimization levels. > > I also suspect something like one more than the number of bits in the > type might help with any bitmasking tricks. > > Theres a lot of additinal things we can do to enhance this, but this > framework provides a start. These 2 initial evaluations fix 107822, and > part of 107986. > > 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 =3D=3D 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. Richard. > Andrew > > > >