From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x12c.google.com (mail-lf1-x12c.google.com [IPv6:2a00:1450:4864:20::12c]) by sourceware.org (Postfix) with ESMTPS id A21253858D39 for ; Tue, 19 Sep 2023 12:56:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A21253858D39 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-lf1-x12c.google.com with SMTP id 2adb3069b0e04-500913779f5so9433526e87.2 for ; Tue, 19 Sep 2023 05:56:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1695128174; x=1695732974; darn=gcc.gnu.org; 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=C/aHGmHpyeo7/LRYz9dDE/djr0qoLFxw4tHK4Yz45zs=; b=InlXq1gFVze+mCy8QggPVc07xbTsFleVmc07AEs7kR/zazUSkznYYTZdas/5SirpEu BMemozQob1JKTFp0pbEwu35gStXfbYTWpvyfjVfzR6owq+FvYLHeDUD4Y7N4aY/Go6fi M2RSNfyzBq72qpK9yd09Nh5mz9JCxkqhnPCr1ciT/bhk79EgVFTMKexI2yP50TmagEEQ tUbTeUr+xgnDtKEmhj8TsK+llO4XA+eVfsZgKCwH9q11JR7ooczULYan1fA3cPdB+rMU FsnVVZ8k2QeBt0pxw7NyEc6nmE+kV9M8LpDUMbSTqPkc5hyTXHKt75sIgpyNd/RS1Rii 4h4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695128174; x=1695732974; 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=C/aHGmHpyeo7/LRYz9dDE/djr0qoLFxw4tHK4Yz45zs=; b=mREONR/A8S+u3qzRemFvj+5+OPs8NTDYhSMtBYV2VMmP21h96JRLDNE0Ar7jPl6koW SlvtLnfW+Js0BGyyLJF49NGpqrtBlVVYEGDC2koxFZyGZidjSW3BsT0yS0CHWV4tcv8p kgfZOIc40Rv12gRxWUnNUaWXiASo9u0UHuMVgvq2Igg5XBE3BWv69VtztZo2shecS6so Y3Yo3ZuS/aIDAD96+NX3/bwZjwI0tD3Ka2IQvk8il9OEwyzFmtjaCaLqogONb4koGgXa 6jvkrxg0/wQlNhu61hhmEVCdFyGKpLc4cMuyy8wR6caKoL1udiyvVd2sQaom1Dw88y48 408g== X-Gm-Message-State: AOJu0YzjzUOgAfhigLN4ZWh1CwQapx7k5zvPmEBpuIeBSdlhAlze7GtK YW2JBcp3HLv43IFDNezfUyedv6bQysojNwvYHG/gkqCV X-Google-Smtp-Source: AGHT+IFbnrV6tBspjNlLol5ry+FskWK276ziR+Mx2cgbbSgu2J9ynpUiBojuXThKNXBpXQjfCnATsumhhgpJPKKwTgc= X-Received: by 2002:ac2:5f46:0:b0:4fe:af1:c3ae with SMTP id 6-20020ac25f46000000b004fe0af1c3aemr8982684lfz.15.1695128173526; Tue, 19 Sep 2023 05:56:13 -0700 (PDT) MIME-Version: 1.0 References: <703c843e-1743-f2d4-4e38-0a52a048725b@redhat.com> In-Reply-To: <703c843e-1743-f2d4-4e38-0a52a048725b@redhat.com> From: Richard Biener Date: Tue, 19 Sep 2023 14:56:01 +0200 Message-ID: Subject: Re: [PATCH] [RFC] New early __builtin_unreachable processing. 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 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 Mon, Sep 18, 2023 at 3:48=E2=80=AFPM Andrew MacLeod wrote: > > > On 9/18/23 02:53, Richard Biener wrote: > > On Fri, Sep 15, 2023 at 4:45=E2=80=AFPM Andrew MacLeod wrote: > >> Ive been looking at __builtin_unreachable () regressions. The > >> fundamental problem seems to be a lack of consistent expectation for > >> when we remove it earlier than the final pass of VRP. After looking > >> through them, I think this provides a sensible approach. > >> > >> Ranger is pretty good at providing ranges in blocks dominated by the > >> __builtin_unreachable branch, so removing it isn't quite a critical a= s > >> it once was. Its also pretty good at identifying what in the block ca= n > >> be affected by the branch. > >> > >> This patch provide an alternate removal algorithm for earlier passes. > >> it looks at *all* the exports from the block, and if the branch > >> dominates every use of all the exports, AND none of those values acces= s > >> memory, VRP will remove the unreachable call, rewrite the branch, upda= te > >> all the values globally, and finally perform the simple DCE on the > >> branch's ssa-name. This is kind of what it did before, but it wasn't > >> as stringent on the requirements. > >> > >> The memory access check is required because there are a couple of test > >> cases for PRE in which there is a series of instruction leading to an > >> unreachable call, and none of those ssa names are ever used in the IL > >> again. The whole chunk is dead, and we update globals, however > >> pointlessly. However, one of ssa_names loads from memory, and a later > >> passes commons this value with a later load, and then the unreachable > >> call provides additional information about the later load. This is > >> evident in tree-ssa/ssa-pre-34.c. The only way I see to avoid this > >> situation is to not remove the unreachable if there is a load feeding = it. > >> > >> What this does is a more sophisticated version of what DOM does in > >> all_uses_feed_or_dominated_by_stmt. THe feeding instructions dont hav= e > >> to be single use, but they do have to be dominated by the branch or be > >> single use within the branches block.. > >> > >> If there are multiple uses in the same block as the branch, this does > >> not remove the unreachable call. If we could be sure there are no > >> intervening calls or side effects, it would be allowable, but this a > >> more expensive checking operation. Ranger gets the ranges right anywa= y, > >> so with more passes using ranger, Im not sure we'd see much benefit fr= om > >> the additional analysis. It could always be added later. > >> > >> This fixes at least 110249 and 110080 (and probably others). The only > >> regression is 93917 for which I changed the testcase to adjust > >> expectations: > >> > >> // PR 93917 > >> void f1(int n) > >> { > >> if(n<0) > >> __builtin_unreachable(); > >> f3(n); > >> } > >> > >> void f2(int*n) > >> { > >> if(*n<0) > >> __builtin_unreachable(); > >> f3 (*n); > >> } > >> > >> We were removing both unreachable calls in VRP1, but only updating the > >> global values in the first case, meaning we lose information. With t= he > >> change in semantics, we only update the global in the first case, but = we > >> leave the unreachable call in the second case now (due to the load fro= m > >> memory). Ranger still calculates the contextual range correctly as [0= , > >> +INF] in the second case, it just doesn't set the global value until > >> VRP2 when it is removed. > >> > >> Does this seem reasonable? > > I wonder how this addresses the fundamental issue we always faced > > in that when we apply the range this range info in itself allows the > > branch to the __builtin_unreachable () to be statically determined, > > so when the first VRP pass sets the range the next pass evaluating > > the condition will remove it (and the guarded __builtin_unreachable ())= . > > > > In principle there's nothing wrong with that if we don't lose the range > > info during optimizations, but that unfortunately happens more often > > than wanted and with the __builtin_unreachable () gone we've lost > > the ability to re-compute them. > > > > I think it's good to explicitly remove the branch at the point we want > > rather than relying on the "next" visitor to pick up the global range. > > > > As I read the patch we now remove __builtin_unreachable () explicitly > > as soon as possible but don't really address the fundamental issue > > in any way? > > > I think it pretty much addresses the issue completely. No globals are > updated by the unreachable branch unless it is removed. We remove the > unreachable early ONLY if every use of all the exports is dominated by > the branch... with the exception of a single use in the block used to > define a different export. and those have to all have no other uses > which are not dominated. ie > > [local count: 1073741824]: > y_2 =3D x_1(D) >> 1; > t_3 =3D y_2 + 1; > if (t_3 > 100) > goto ; [0.00%] > else > goto ; [100.00%] > > [count: 0]: > __builtin_unreachable (); > > [local count: 1073741824]: > func (x_1(D), y_2, t_3); > > > In this case we will remove the unreachable call because we can provide > an accurate global range for all values used in the definition chain for > the program. > > Global Exported (via early unreachable): x_1(D) =3D [irange] unsigned int > [0, 199] MASK 0xff VALUE 0x0 > Global Exported (via early unreachable): y_2 =3D [irange] unsigned int [0= , > 99] MASK 0x7fffffff VALUE 0x0 > Global Exported (via early unreachable): t_3 =3D [irange] unsigned int [1= , > 100] > > > If conditions are not satisfied to do this early, we do not et ANY of > the global values, and leave the unreachable alone. ie. if that was fed > from a memory load instead of a parameter: > > > [local count: 1073741824]: > x.0_1 =3D x; > y_3 =3D x.0_1 >> 1; > t_4 =3D y_3 + 1; > if (t_4 > 100) > goto ; [0.00%] > else > goto ; [100.00%] > > [count: 0]: > __builtin_unreachable (); > > > we no longer remove the unreachable call, and do not sety any global > values as a result. that means a following pass is not goign to see > the condition as foldable because we dont know anything about t_4's > range globally. > > We still contextually know via ranger that after the unreachable call we > have those ranges: > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D BB 4 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D > x.0_1 [irange] unsigned int [0, 199] MASK 0xff VALUE 0x0 > y_3 [irange] unsigned int [0, 99] MASK 0x7fffffff VALUE 0x0 > t_4 [irange] unsigned int [1, 100] > [local count: 1073741824]: > func (x.0_1, y_3, t_4); > > but even ranger will not apply those ranges at the branch location. > > The same thing happen if there is any other use of x.0_1, y_3 or t_4 > that isnt dominated by the branch.. we leave it alone. > > So I don't think we lose any information... we just only ever move it to > the global range early IFF we know that range applies to every export, > and there is no chance there will be any commoning opportunities due to > memory loads. OK. > I dont see anything in the early VRP processing now that would allow a > later pass to remove the unreachable unless it does its own analysis > like DOM might do. Isn't it as simple as if (i_2 > 5) __builtin_unreachable (); registering a global range of [6, INF] for i_2 and then the next time we fold if (i_2 > 5) using range info will eliminate it? Yes, historically that required VRP or DOM since nothing else looked at ranges, not sure how it behaves now given more match.pd patterns do look at (global) ranges. In any case, thanks for the explanation and OK for the patch. Thanks, Richard. > Andrew >