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

["luoxhu at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

--- Comment #10 from luoxhu at gcc dot gnu.org ---
(In reply to Martin Liška 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:
> > > 
> > > > 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:
> 
> Note the lowering expand to a decision tree where node of such tree can be
> jump-tables,
> bit-tests or simple comparisons.
> 
> > 
> > ;; 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
> 
> So jump-table is selected. Where do you see this GIMPLE representation?

This is dumped by the second run of iftoswitch after fre5.

> 
> ...
> 
> > 
> > ASM still contains indirect jump table like -fno-switch-conversion:
> 
> > 
> > Is this bug of lower_switch or expected?
> 
> What bug do you mean? 

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?

> 
> > From the code, they have different
> > purpose as switch_conversion turns switch to single if-else while
> 
> No switch_conversion expands a switch statement to a series of assignment
> based on CSWITCH[index] arrays.
> 
> > lower_switch expand CLUSTERS as a decision tree.

Yes, rerun pass_convert_switch after the second if_to_switch could generate the
CSWITCH[index]. 

pr105740.c.195t.switchconv2:

  <bb 2> [local count: 1073741824]:
  if (x_4(D) > 3)
    goto <bb 3>; [50.00%]
  else
    goto <bb 6>; [50.00%]

  <bb 3> [local count: 536870913]:
  _1 = f_6(D)->arr[3];
  _10 = (unsigned int) _1;
  _2 = _10 + 4294967295;
  if (_2 <= 5)
    goto <bb 5>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 4> [local count: 1073741822]:
<L28>:
  _8 = 0;
  goto <bb 6>; [100.00%]

  <bb 5> [local count: 1073741822]:
<L29>:
  _9 = CSWTCH.4[_2];

  <bb 6> [local count: 2147483644]:
  # _3 = PHI <_8(4), 0(2), _9(5)>
<L30>:
<L27>:
  return _3;