From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x835.google.com (mail-qt1-x835.google.com [IPv6:2607:f8b0:4864:20::835]) by sourceware.org (Postfix) with ESMTPS id 8BDFD38356A9 for ; Wed, 1 Jun 2022 09:42:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8BDFD38356A9 Received: by mail-qt1-x835.google.com with SMTP id k12so741219qtx.13 for ; Wed, 01 Jun 2022 02:42:37 -0700 (PDT) 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=Mqp/tKRKGdDsQUeUKHwD/0ahDeTuXxte+NqBsoGzabY=; b=NUJRhi8UXTBAM/vzECVztUymwyWafPGf+xa7N2J2FiwJbo2fTezBT7Gp+qYeFrsIh4 F/kT0wJJjHmlyCuDaKRtOHi8dpFbqNZJYxFwbysk9LK3X0C9c4qVwmgwpR7/GR7gYdM6 Dirl/ZvHpsye/CikYgy+vmV6m2cQ9CAHkncY66zbtYsHBMiC6YiyByG4FCF5gFgULiBD 2yYbVG+Ec82cDHUA8sgc0cA5rAVy25mjTzwUbhgHxmv2uXyTlv5Tv5bYf20ioy04hoep gIa1cgBB14/vKqqnk8fni+t88adAIvjWiFd/KhcZ2+moaHEtOjrYROdVTNlB9J1V/pPh hBTA== X-Gm-Message-State: AOAM531VigHgrMsScxtucPKBv+5VnCTB58QbuxQjBJfDbf8Cw7K9JEYN gNzDrByVL6ApO2BNuO03JvhgCAqr+tP3Dvzot/mIMv0hVo550WXr X-Google-Smtp-Source: ABdhPJzI85ttnbecpNxuaDYnVwpQ6ZQlfQIi8XiQX+5rwqXo+mnSMJnmB4F8L2DpiVh240hEqQo54ZlPgRVKDOFdamM= X-Received: by 2002:ac8:57cc:0:b0:304:b904:a2e8 with SMTP id w12-20020ac857cc000000b00304b904a2e8mr6920223qta.472.1654076556842; Wed, 01 Jun 2022 02:42:36 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Wed, 1 Jun 2022 11:42:25 +0200 Message-ID: Subject: Re: [PATCH] [PR105665] ivopts: check defs of names in base for undefs To: Alexandre Oliva Cc: GCC Patches , Bin Cheng Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.5 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 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: Wed, 01 Jun 2022 09:42:39 -0000 On Tue, May 31, 2022 at 3:27 PM Alexandre Oliva wrote: > > On May 30, 2022, Richard Biener wrote: > > > I don't think you can rely on TREE_VISITED not set at the start of the > > pass (and you don't clear it either). > > I don't clear it, but I loop over all SSA names and set TREE_VISITED to > either true or false, so that's covered. > > I even had a test patch that checked that TREE_VISITED remains unchanged > and still matched the expected value, with a recursive verification. > > I could switch to an sbitmap if that's preferred, though. > > > I also wonder how you decide that tracking PHIs with (one) uninit arg > > is "enough"? > > It's a conservative assumption, granted. One could imagine cases in > which an uninit def is never actually used, say because of conditionals > forced by external circumstances the compiler cannot possibly know > about. But then, just as this sort of bug shows, sometimes even when an > uninit is not actually used, the fact that it is uninit and thus > undefined may end up percolating onto stuff that is actually used, so I > figured we'd be better off leaving alone whatever is potentially derived > from an uninit value. > > > Is it important which edge of the PHI the undef appears in? > > At some point, I added recursion to find_ssa_undef, at PHI nodes and > assignments, and pondered whether to recurse at PHI nodes only for defs > that were "earlier" ones, rather than coming from back edges. I ended > up reasoning that back edges would affect step and rule out an IV > candidate even sooner. But the forward propagation of maybe-undef > obviated that reasoning. Now, almost tautologically, if circumstances > are such that the compiler could only tell that an ssa name is defined > with external knowledge, then, since such external knowledge is not > available to the compiler, it has to assume that the ssa name may be > undefined. > > > I presume the testcase might have it on the loop entry edge? > > The original testcase did. The modified one (the added increment) shows > it can be an earlier edge that has the maybe-undef name. > > > I presume only PHIs in loop headers are to be considered? > > As in the modified testcase, earlier PHIs that are entirely outside the > loop can still trigger the bug. Adding more increments of g guarded by > conditionals involving other global variables pushes the undef ssa name > further and further away from the inner loop, while still rendering g an > unsuitable IV. So for example void foo (int flag, int init, int n, int *p) { int i; if (flag) i = init; for (; i < n; ++i) *(p++) = 1; } will now not consider 'i - i-on-entry' as an IV to express *(p++) = 1. But void foo (int flag, int init, int n, int *p) { int i; if (flag) i = init; i++; for (; i < n; ++i) *(p++) = 1; } still would (the propagation stops at i++). That said - I wonder if we want to compute a conservative set of 'must-initialized' here or to say, do we understand the failure mode good enough to say that a must-def (even if from an SSA name without a definition) is good enough to avoid the issues we are seeing? One would argue that my example above invokes undefined behavior if (!flag), but IIRC the cases in the PRs we talk about are not but IVOPTs with its IV choice exposes undefined behavior - orignially by relying on undef - undef being zero. That said, the contains-undef thing tries to avoid rewriting expressions with terms that possibly contain undefs which means if we want to strenthen it then we look for must-defined (currently it's must-undefined)? Richard. > >> +int a, b, c[1], d[2], *e = c; > >> +int main() { > >> + int f = 0; > >> + for (; b < 2; b++) { > >> + int g; > >> + if (f) > >> + g++, b = 40; > >> + a = d[b * b]; > >> + for (f = 0; f < 3; f++) { > >> + if (e) > >> + break; > >> + g--; > >> + if (a) > >> + a = g; > >> + } > >> + } > >> + return 0; > >> +} > > -- > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about