From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 79B8E385840F; Thu, 23 Mar 2023 10:00:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 79B8E385840F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1679565634; bh=SQe+DgD6r2D/ciyJMZGhK1sYDAyZRLSuGlQLiGP0Ntw=; h=From:To:Subject:Date:In-Reply-To:References:From; b=OmSiq7ZwL2qraG1ehnPmt2MGZdj88l5DE/dc948P3DpJ7SkP+JsKbMCvRdJ7XIV2J QJvpgWBV1HzKs3BOFJGy4un4770K/UAvKootdYFA1zKd6l1EtrWJP+GwDxhZS9tPWK Z7mi8w2Mx7TP3wfaoFzhyUtEFjPpD1Y0ys8mvJpQ= From: "rguenth at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: =?UTF-8?B?W0J1ZyBjLzEwOTIzM10gWzEyLzEzIFJlZ3Jlc3Npb25dIHdhcm5p?= =?UTF-8?B?bmc6IGFycmF5IHN1YnNjcmlwdCA1IGlzIGFib3ZlIGFycmF5IGJvdW5kcyBv?= =?UTF-8?B?ZiDigJhzdHJ1Y3QgdGczX25hcGlbNV3igJkgc2luY2UgcjEyLTI1OTE=?= Date: Thu, 23 Mar 2023 10:00:33 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: c X-Bugzilla-Version: 13.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: rguenth at gcc dot gnu.org X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: 12.3 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: cc 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=3D109233 Richard Biener changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |hubicka at gcc dot gnu.org --- Comment #12 from Richard Biener --- (In reply to Andrew Macleod from comment #11) > (In reply to Aldy Hernandez from comment #10) > > (In reply to Jakub Jelinek from comment #8) > >=20 > > > And on the ranger side why we have determined the [0, 5] range rather= than > > > [0, 4], whether it is related to inaccurate number of iterations esti= mation, > > > or ranger using it incorrectly, ... > >=20 > > The [0, 5] is actually coming from SCEV, which ranger is using to refin= e the > > range. Presumably, ranger is doing worse than SCEV, because it doesn't > > improve it. > >=20 > > $ grep 'Loops range fo' a.c.*evrp > > Loops range found for i_3: [irange] int [0, 5] NONZERO 0x7 and calcu= lated > > range :[irange] int [-2147483647, +INF] > > Loops range found for i_3: [irange] int [0, 5] NONZERO 0x7 and calcu= lated > > range :[irange] int [0, 6] NONZERO 0x7 > >=20 > > Perhaps Andrew can pontificate on the recalculations / iterations / etc. >=20 > Im not sure what to add.=20 >=20=20 >=20 > SCEV tells us its [0,5] . >=20 > Statement MEM [(struct S *)t_9(D)].f[i_3].y =3D 1; > is executed at most 4 (bounded by 4) + 1 times in loop 1. > Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM > [(struct S *)t_9(D)].f[i_3].z =3D 2; > in loop 1. > Statement MEM [(struct S *)t_9(D)].f[i_3].z =3D 2; > is executed at most 4 (bounded by 4) + 1 times in loop 1. > Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM > [(struct S *)t_9(D)].f[i_3].x =3D 3; > in loop 1. > Statement MEM [(struct S *)t_9(D)].f[i_3].x =3D 3; > is executed at most 4 (bounded by 4) + 1 times in loop 1. > Induction variable (int) 0 + 1 * iteration does not wrap in statement MEM > [(struct S *)t_9(D)].f[i_3].z =3D 2; > in loop 1. > Statement MEM [(struct S *)t_9(D)].f[i_3].z =3D 2; > is executed at most 4 (bounded by 4) + 1 times in loop 1. > Trying to walk loop body to reduce the bound. > Found better loop bound 5 >=20 >=20 > I see nothing else in the IL to help ranger make any other decision, so it > defers to SCEV, and the transformtion to rewrite the array index to [5] > seems spot on, its the only possible value that can be there... THe bran= ch > condition is: > _1 =3D t_9(D)->h; > i.0_2 =3D (unsigned int) i_3; > if (_1 > i.0_2) > goto ; >=20 > Ranger knows nothing of the value of _1, and with i_3 being [0,5] there is > nothing that I can see that ranger could do >=20 > Why does scev decide 5 is a better bound? It's the first bound it finds, based on the access. The issue is that the accesses are after the exit test and we're doing adjustments to the estimates in discover_iteration_bound_by_body_walk like /* Exit terminates loop at given iteration, while non-exits produce undefined effect on the next iteration. */ if (!elt->is_exit) { bound +=3D 1; but note we're always setting elt->is_exit to false for bounds discovered from array refs (see record_estimate call from record_nonwrapping_iv from idx_infer_loop_bounds). I think there's either some duplicate accounting or confusion as to what is_exit means though. Since we record the number of latch executions the estimate from blocks dominated by the exit test should be directly usable as estimate while those before the exit test would need adjustment in the other direction? is_exit is documented as /* True if, after executing the statement BOUND + 1 times, we will leave the loop; that is, all the statements after it are executed at m= ost BOUND times. */=20 bool is_exit; the "that is, all the statements after it are executed at most BOUND times" really suggests this is about an actual exit statement and not about position relative to the exit. In the function of the above loop we translate the stmt execution bound to a bound on the number of latch executions (so the last time an exit stmt is executed it will exit the loop, so no +1). Note this is a tricky area and we have many related bugreports, but testsuite coverage should be quite good here. Btw, the actual thing is that the IV as analyzed by SCEV can get the value 5, the actual array references will not be executed but we must exit the loop in that case. That's something not covered by niter analysis / SCEV directly but if you use max_stmt_executions () on blocks following the exit test you should be able to determine that i !=3D 5 is always true. So the fix is probably somewhere in ranger determining that on the exit test edge remaining in the loop, the bounds on other IVs can be adjusted by one (but only on that edge).=