From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id AD5253858415; Fri, 1 Jul 2022 02:06:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AD5253858415 From: "luoxhu at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/105740] missed optimization switch transformation for conditions with duplicate conditions Date: Fri, 01 Jul 2022 02:06:22 +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: 12.1.0 X-Bugzilla-Keywords: missed-optimization X-Bugzilla-Severity: normal X-Bugzilla-Who: luoxhu at gcc dot gnu.org X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- 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 X-BeenThere: gcc-bugs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-bugs mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Jul 2022 02:06:22 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D105740 --- Comment #10 from luoxhu at gcc dot gnu.org --- (In reply to Martin Li=C5=A1ka from comment #9) > (In reply to luoxhu from comment #8) > > (In reply to rguenther@suse.de from comment #6) > > > On Tue, 21 Jun 2022, jakub at gcc dot gnu.org wrote: > > >=20 > > > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D105740 > > > >=20 > > > > --- Comment #5 from Jakub Jelinek --- > > > > The problem with switch-conversion done multiple times is that when= it is done > > > > early, it can do worse job than when it is done late, e.g. we can h= ave better > > > > range information later which allows (unfortunately switch-conversi= on doesn't > > > > use that yet, there is a PR about it) to ignore some never reachabl= e values > > > > etc. > > > > So ideally we either need to be able to undo switch-conversion and = redo it if > > > > things have changed, or do it only late and for e.g. inlining costs= perform it > > > > only in analysis mode and record somewhere what kind of lowering wo= uld be done > > > > and how much it would cost. > > > > With multiple if-to-switch, don't we risk that we turn some ifs int= o switch, > > > > then > > > > switch-conversion lowers it back to ifs and then another if-to-swit= ch matches > > > > it again and again lowers it? > > >=20 > > > Yeah, I think ideally switch conversion would be done as part of swit= ch > > > lowering (plus maybe an extra if-to-switch). The issue might be what > > > I said - some passes don't like switches, but they probably need to be > > > taught. As of inline cost yes, doing likely-switch-converted analysis > > > would probably work. > >=20 > > git diff > > diff --git a/gcc/passes.def b/gcc/passes.def > > index b257307e085..1376e7cb28d 100644 > > --- a/gcc/passes.def > > +++ b/gcc/passes.def > > @@ -243,8 +243,6 @@ along with GCC; see the file COPYING3. If not see > > Clean them up. Failure to do so well can lead to false > > positives from warnings for erroneous code. */ > > NEXT_PASS (pass_copy_prop); > > /* Identify paths that should never be executed in a conforming > > program and isolate those paths. */ > > NEXT_PASS (pass_isolate_erroneous_paths); > > @@ -329,6 +327,7 @@ along with GCC; see the file COPYING3. If not see > > POP_INSERT_PASSES () > > NEXT_PASS (pass_simduid_cleanup); > > NEXT_PASS (pass_lower_vector_ssa); > > + NEXT_PASS (pass_if_to_switch); > > NEXT_PASS (pass_lower_switch); > > NEXT_PASS (pass_cse_reciprocals); > > NEXT_PASS (pass_reassoc, false /* early_p */); > >=20 > > Tried this to add the second if_to_switch before lower_switch, but swit= ch > > lowering doesn't work same as switch_conversion: >=20 > Note the lowering expand to a decision tree where node of such tree can be > jump-tables, > bit-tests or simple comparisons. >=20 > >=20 > > ;; Function test2 (test2, funcdef_no=3D0, decl_uid=3D1982, cgraph_uid= =3D1, > > symbol_order=3D0) > >=20 > > beginning to process the following SWITCH statement ((null):0) : ------- > > switch (_2) [INV], case 1: [INV], case 2: [= INV], > > case 3: [INV], case 4: > 3> [INV], case 5: [INV], case 6: [INV]> > >=20 > > ;; GIMPLE switch case clusters: JT(values:6 comparisons:6 range:6 densi= ty: > > 100.00%):1-6 >=20 > So jump-table is selected. Where do you see this GIMPLE representation? This is dumped by the second run of iftoswitch after fre5. >=20 > ... >=20 > >=20 > > ASM still contains indirect jump table like -fno-switch-conversion: >=20 > >=20 > > Is this bug of lower_switch or expected? >=20 > What bug do you mean?=20 Sorry, it not a bug, got to know that switch lower and switch conversion are doing two different things, different with "pass_lower_switch also performs the transforms switch-conversion does" in c#4? >=20 > > From the code, they have different > > purpose as switch_conversion turns switch to single if-else while >=20 > No switch_conversion expands a switch statement to a series of assignment > based on CSWITCH[index] arrays. >=20 > > lower_switch expand CLUSTERS as a decision tree. Yes, rerun pass_convert_switch after the second if_to_switch could generate= the CSWITCH[index].=20 pr105740.c.195t.switchconv2: [local count: 1073741824]: if (x_4(D) > 3) goto ; [50.00%] else goto ; [50.00%] [local count: 536870913]: _1 =3D f_6(D)->arr[3]; _10 =3D (unsigned int) _1; _2 =3D _10 + 4294967295; if (_2 <=3D 5) goto ; [INV] else goto ; [INV] [local count: 1073741822]: : _8 =3D 0; goto ; [100.00%] [local count: 1073741822]: : _9 =3D CSWTCH.4[_2]; [local count: 2147483644]: # _3 =3D PHI <_8(4), 0(2), _9(5)> : : return _3;=