From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id EF8433835778; Wed, 22 Jun 2022 06:19:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EF8433835778 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: Wed, 22 Jun 2022 06:19:21 +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: Wed, 22 Jun 2022 06:19:22 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D105740 --- Comment #8 from luoxhu at gcc dot gnu.org --- (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 have = better > > range information later which allows (unfortunately switch-conversion d= oesn't > > use that yet, there is a PR about it) to ignore some never reachable va= lues > > 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 per= form it > > only in analysis mode and record somewhere what kind of lowering would = be done > > and how much it would cost. > > With multiple if-to-switch, don't we risk that we turn some ifs into sw= itch, > > then > > switch-conversion lowers it back to ifs and then another if-to-switch m= atches > > it again and again lowers it? >=20 > Yeah, I think ideally switch conversion would be done as part of switch > 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. 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 */); Tried this to add the second if_to_switch before lower_switch, but switch lowering doesn't work same as switch_conversion: ;; Function test2 (test2, funcdef_no=3D0, decl_uid=3D1982, cgraph_uid=3D1, symbol_order=3D0) beginning to process the following SWITCH statement ((null):0) : ------- switch (_2) [INV], case 1: [INV], case 2: [INV], case 3: [INV], case 4: [INV], case 5: [INV], case 6: [INV]> ;; GIMPLE switch case clusters: JT(values:6 comparisons:6 range:6 density: 100.00%):1-6 Removing basic block 11 ;; basic block 11, loop depth 0 ;; pred: switch (_2) [INV], case 1: [INV], case 2: [INV], case 3: [INV], case 4: [INV], case 5: [INV], case 6: [INV]> ;; succ: 4 ;; 5 ;; 6 ;; 7 ;; 8 ;; 9 ;; 10 Updating SSA: Registering new PHI nodes in block #0 Registering new PHI nodes in block #2 Updating SSA information for statement _1 =3D f_10(D)->len; Registering new PHI nodes in block #3 Updating SSA information for statement _2 =3D f_10(D)->arr[3]; ... int test2 (struct fs * f) { int _1; int _2; int _8; [local count: 1073741824]: _1 =3D f_10(D)->len; if (_1 > 3) goto ; [50.00%] else goto ; [50.00%] [local count: 536870913]: _2 =3D f_10(D)->arr[3]; switch (_2) [0.00%], case 1: [16.67%], case 2: [16.67%], case 3: [16.67%], case 4: [16.67%], case 5: [16.67%], case 6: [16.67%]> [local count: 67108864]: : goto ; [100.00%] [local count: 62914560]: : goto ; [100.00%] [local count: 58982400]: : goto ; [100.00%] [local count: 55296000]: : goto ; [100.00%] [local count: 51840000]: : goto ; [100.00%] [local count: 48600000]: : [local count: 1073741824]:=20 # _8 =3D PHI <12(4), 27(5), 38(6), 18(7), 58(8), 68(9), 0(3), 0(2)> : return _8; } ASM still contains indirect jump table like -fno-switch-conversion: test2: .LFB0: .cfi_startproc xorl %eax, %eax cmpl $3, (%rdi) jle .L1 cmpl $6, 16(%rdi) ja .L3 movl 16(%rdi), %eax jmp *.L5(,%rax,8) .section .rodata .align 8 .align 4 .L5: .quad .L3 .quad .L11 .quad .L9 .quad .L8 .quad .L7 .quad .L6 .quad .L4 .text .p2align 4,,10 .p2align 3 .L11: movl $12, %eax .L1: ret .p2align 4,,10 .p2align 3 .L9: movl $27, %eax ret .p2align 4,,10 .p2align 3 .L8: movl $38, %eax ret .p2align 4,,10 .p2align 3 .L7: movl $18, %eax ret .p2align 4,,10 .p2align 3 .L6: movl $58, %eax ret .p2align 4,,10 .p2align 3 .L4: movl $68, %eax ret .L3: xorl %eax, %eax ret .cfi_endproc .LFE0: .size test2, .-test2 Is this bug of lower_switch or expected? From the code, they have different purpose as switch_conversion turns switch to single if-else while lower_swi= tch expand CLUSTERS as a decision tree.=