[Bug tree-optimization/105740] missed optimization switch transformation for conditions with duplicate conditions

[luoxhu at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105740

--- 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:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105740
> > 
> > --- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> > 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 doesn't
> > use that yet, there is a PR about it) to ignore some never reachable 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 would be done
> > and how much it would cost.
> > With multiple if-to-switch, don't we risk that we turn some ifs into switch,
> > then
> > switch-conversion lowers it back to ifs and then another if-to-switch matches
> > it again and again lowers it?
> 
> 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=0, decl_uid=1982, cgraph_uid=1,
symbol_order=0)

beginning to process the following SWITCH statement ((null):0) : -------
switch (_2) <default: <L27> [INV], case 1: <L20> [INV], case 2: <L21> [INV],
case 3: <L22> [INV], case 4: <L2
3> [INV], case 5: <L24> [INV], case 6: <L25> [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) <default: <L27> [INV], case 1: <L20> [INV], case 2: <L21> [INV],
case 3: <L22> [INV], case 4: <L2
3> [INV], case 5: <L24> [INV], case 6: <L25> [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 = f_10(D)->len;
Registering new PHI nodes in block #3
Updating SSA information for statement _2 = f_10(D)->arr[3];
...
int test2 (struct fs * f)
{
  int _1;
  int _2;
  int _8;

  <bb 2> [local count: 1073741824]:
  _1 = f_10(D)->len;
  if (_1 > 3)
    goto <bb 3>; [50.00%]
  else
    goto <bb 10>; [50.00%]

  <bb 3> [local count: 536870913]:
  _2 = f_10(D)->arr[3];
  switch (_2) <default: <L27> [0.00%], case 1: <L20> [16.67%], case 2: <L21>
[16.67%], case 3: <L22> [16.67%], case 4: <L23> [16.67%], case 5: <L24>
[16.67%], case 6: <L25> [16.67%]>

  <bb 4> [local count: 67108864]:
<L20>:
  goto <bb 10>; [100.00%]

  <bb 5> [local count: 62914560]:
<L21>:
  goto <bb 10>; [100.00%]

  <bb 6> [local count: 58982400]:
<L22>:
  goto <bb 10>; [100.00%]

  <bb 7> [local count: 55296000]:
<L23>:
  goto <bb 10>; [100.00%]

  <bb 8> [local count: 51840000]:
<L24>:
  goto <bb 10>; [100.00%]

  <bb 9> [local count: 48600000]:
<L25>:

  <bb 10> [local count: 1073741824]: 
 # _8 = PHI <12(4), 27(5), 38(6), 18(7), 58(8), 68(9), 0(3), 0(2)>
<L27>:
  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_switch
expand CLUSTERS as a decision tree.