From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id C37BB385771A; Thu, 4 May 2023 16:22:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C37BB385771A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1683217336; bh=2/Rjlj/FkqRlcJ/csjeT0Y5hAPXFPOufTTexsIo1aMk=; h=From:To:Subject:Date:In-Reply-To:References:From; b=AEyyMA+SBSwlUGTPqR8cbGSNnec+doUXie6WQXuJBetAXhYIFIbN3lNiMIgp763K1 Pu1svGugSldFq7USgdN0w94TDT0Is5/b0DQL1+/ZCsQ8ToaORzkNWaLYD3kCMaUPi9 OcVGLOwa+yS0TnCVb4UVn80NgxizyKkIl8T0rj2g= From: "amacleod at redhat dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/109695] [14 Regression] crash in gimple_ranger::range_of_expr since r14-377-gc92b8be9b52b7e Date: Thu, 04 May 2023 16:22:15 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: tree-optimization X-Bugzilla-Version: 14.0 X-Bugzilla-Keywords: ice-on-valid-code X-Bugzilla-Severity: normal X-Bugzilla-Who: amacleod at redhat dot com X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P1 X-Bugzilla-Assigned-To: aldyh at gcc dot gnu.org X-Bugzilla-Target-Milestone: 14.0 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D109695 --- Comment #22 from Andrew Macleod --- OK, I've finished with my analysis. There are multiple vectors of attack h= ere, and we should do them all. Some where already on my radar for this release anyway, but this gives a nice tidy place to track them all. First, the increased size of int_range_max needs to be addressed. Short = term we could resolve this simply by making int_range<25> instead of int_range<2= 55>. That of course papers over the real problem, but still needs addressing. = Aldy and I are discussing. Next, prefill_stmt_dependencies exists to short-cut long chains of calls to range_of_stmt by managing it on a stack. It uses a *lot* less stack calls, = but it is still subject to re-evaluating statements whose dependencies are upda= ted. ssa-names that have not been calculated have no entry in rangers global cac= he.=20 As soon as they get an entry, they are also given a monotonically increasing timestamp. This allows us to quickly see if a dependence has been updated since a value was last calculated.=20 prefill_stmt_dependencies pushes un-evaluated names from statements onto a stack as they are seen, and evaluating those first, then finally evaluating= the stmt.=20 _1012 =3D PHI <_1947(2), _1011(1016)> we push _1012, then _1947 and _1011 on the stack to evaluate. _1011 and _1= 947 will be evaluated before _1012, thus allowing for a decent calculation of _1012. We avoid cycles by providing an initial value for a name when it is first registered. When we provide this initial value, we also set the timestamp to "always current" so we don't end up with flip flopping dependencies in cycl= es causing each other to be recalculated. When we store the newly calculated value, we set a proper timestamp. So, on to the issues that need to be addressed. 1) We unconditionally write the new value calculated to the global cache on= ce the dependencies are resolved. This gives it a new timestamp, and thus mak= es any other values which used it out of date when they really aren't. This causes a lot of extra churn. TODO: This should be changed to only update it when it actually changes.=20 Client code shouldn't have to do this, it shoud be handled right int the cache's set_global_value (). 2) The initial value we choose is simply VARYING. This is why 1) alone won't solve this problem. when we push _1947 on the stack, we set it to VARYING.= .=20 then proceed down along chain of other dependencies Driven by _1011 which a= re resolved first. When we get back to _1947 finally, we see:=20 _1947 =3D 77; which evaluated to [77, 77], and is this different than VARYING, and thus w= ould cause a new timestamp to be created even if (1) were implemented. TODO: When setting the initial value in the cache, rather than being lazy a= nd using varying, we should invoke fold_stmt using get_global_range_query ().= =20=20 This will fold the stmt and produce a result which resolved any ssa-names j= ust using known global values. THis should not be expensive, and gives us a reasonable first approximation. And for cases like _1947, the final result= as well. 3) When we first set the intial value for _1947 and give it the ALWAYS_CURR= ENT timestamp, we lose the context of when the initial value was set. So even = with 1) & 2) implemented, we are *still* need to set a timestamp for it when its finally calculated, even though it is the same as the original. This will cause any names already evaluated using its range to become stale because we can't leave it as ALWAYS_CURRENT. (There are other places where we do ne= ed to be able to re-evaluate.. there are 2 testsuite failures caused by this i= f we just leave it as always_current) TODO: Alter the implementation of ALWAYS_CURRENT such that a name is also g= iven a timestamp at the time of setting the initial value. Then set_global_ran= ge() will clear the ALWAYS_CURRENT tag unconditionally, but leave the original timestamp if the value hasn't changed. This will then provide an accurate timestamp for the initial_value. 4) Finally, There are multiple ssa-names that are dependent on _1947. Given= the stack oriented mechanism, the first such case will push the value on the st= ack to be resolved, and all the other names that depend on it will use the init= ial value. When we finally get back to evaluating it, if it DID come out different, then all those names would again be stale, and potentially get recalculated down the road.=20=20 TODO: This impact could be reduced by increasing the priority of its evaluation. Instead of waiting for evaluation all the way back to the botto= m of the stack for _1947, when a new stmt is dependent on it, we could instead m= ove it to the top of the stack for consideration. We'll still be resolving dependencies, but it will be properly evaluated sooner than later. Cycles will have to be avoided by not re prioritizing any dependencies on statement which have been "bumped" like this. You have to put a stake in the ground= at some point and use what you have. Summary: These 4 changes should fix the algorithmic issues exposed, and combined with fixing the memory footprint of int_range-max, we should see a= big different in cases like this. The overhead of doing the extra work is like= ly to be offset by saving in not redoing work. we shall see. I will get to these when I return from vacation=