Bug 14799 - [tree-ssa] convert a sequence of "if"s to a "switch" statement
Summary: [tree-ssa] convert a sequence of "if"s to a "switch" statement
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: tree-ssa
: P2 enhancement
Target Milestone: 11.0
Assignee: Martin Liška
URL:
Keywords: missed-optimization
: 78484 87925 (view as bug list)
Depends on:
Blocks:
 
Reported: 2004-03-31 11:24 UTC by Kazu Hirata
Modified: 2020-12-01 10:52 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-03-05 16:29:10


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Kazu Hirata 2004-03-31 11:24:48 UTC
void bar (void);

void
foo (int a)
{
  if (a == 30)
    bar ();
  else if (a == 31)
    bar ();
  else if (a == 53)
    bar ();
  else if (a == 23)
    bar ();
}

The idea comes from LLVM.
Of course we should do this only if switch statements are expanded in
an (almost?) optimal way.
Comment 1 Andrew Pinski 2004-03-31 12:46:29 UTC
Confirmed.
Comment 2 Kazu Hirata 2004-05-03 08:33:06 UTC
The following example is not strictly a seuqence of "if"s, but
do note that it is a real-world example extracted from function.c of GCC.

<L21>:;
  T.1674_116 = type_1->common.code;
  T.1675_117 = T.1674_116 == 18;
  T.1676_118 = T.1674_116 == 20;
  T.1677_119 = T.1675_117 || T.1676_118;
  if (T.1677_119) goto <L25>; else goto <L22>;

<L22>:;
  if (T.1674_116 == 21) goto <L25>; else goto <L23>;

<L23>:;
  if (T.1674_116 == 22) goto <L25>; else goto <L24>;

<L24>:;
  if (T.1674_116 == 19) goto <L25>; else goto <L26>;

<L25>:;
  return 1;

Here, we could do a simple range check like "if ((t - 18) <= 4)".
Comment 3 Tom de Vries 2011-01-14 15:45:56 UTC
The example from the description field looks like this at tree level (optimized dump with 4.5.1). It takes until late in the rtl untill the duplicate call blocks are collapsed.
...
foo (int a)
{
<bb 2>:
  if (a_1(D) == 30)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  bar (); [tail call]
  goto <bb 10>;

<bb 4>:
  if (a_1(D) == 31)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  bar (); [tail call]
  goto <bb 10>;

<bb 6>:
  if (a_1(D) == 53)
    goto <bb 7>;
  else
    goto <bb 8>;

<bb 7>:
  bar (); [tail call]
  goto <bb 10>;

<bb 8>:
  if (a_1(D) == 23)
    goto <bb 9>;
  else
    goto <bb 10>;

<bb 9>:
  bar (); [tail call]

<bb 10>:
  return;
}
...

If the duplicate blocks would have been collapsed, it would look like this:
...
foo (int a)
{
<bb 2>:
  if (a_1(D) == 30)
    goto <bb 9>;
  else
    goto <bb 4>;

<bb 4>:
  if (a_1(D) == 31)
    goto <bb 9>;
  else
    goto <bb 6>;

<bb 6>:
  if (a_1(D) == 53)
    goto <bb 9>;
  else
    goto <bb 8>;

<bb 8>:
  if (a_1(D) == 23)
    goto <bb 9>;
  else
    goto <bb 10>;

<bb 9>:
  bar (); [tail call]

<bb 10>:
  return;
}
...
for this representation, the patch from PR 46935 comment 5 should work.
Comment 4 Andrew Pinski 2016-11-22 22:01:18 UTC
*** Bug 78484 has been marked as a duplicate of this bug. ***
Comment 5 Andrew Pinski 2018-11-10 07:18:29 UTC
*** Bug 87925 has been marked as a duplicate of this bug. ***
Comment 6 Martin Liška 2019-10-31 09:36:50 UTC
I'm working on the optimization.
Comment 7 CVS Commits 2020-12-01 10:47:32 UTC
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:03eb09292ef228d1d12b5168cdd748583b1f992a

commit r11-5605-g03eb09292ef228d1d12b5168cdd748583b1f992a
Author: Martin Liska <mliska@suse.cz>
Date:   Fri Aug 28 10:26:13 2020 +0200

    Add if-chain to switch conversion pass.
    
    gcc/ChangeLog:
    
            PR tree-optimization/14799
            PR ipa/88702
            * Makefile.in: Add gimple-if-to-switch.o.
            * dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
            * passes.def: Include new pass_if_to_switch pass.
            * timevar.def (TV_TREE_IF_TO_SWITCH): New timevar.
            * tree-pass.h (make_pass_if_to_switch): New.
            * tree-ssa-reassoc.c (struct operand_entry): Move to the header.
            (dump_range_entry): Move to header file.
            (debug_range_entry): Likewise.
            (no_side_effect_bb): Make it global.
            * tree-switch-conversion.h (simple_cluster::simple_cluster):
            Add inline for couple of functions in order to prevent error
            about multiple defined symbols.
            * gimple-if-to-switch.cc: New file.
            * tree-ssa-reassoc.h: New file.
    
    gcc/testsuite/ChangeLog:
    
            PR tree-optimization/14799
            PR ipa/88702
            * gcc.dg/tree-ssa/pr96480.c: Disable if-to-switch conversion.
            * gcc.dg/tree-ssa/reassoc-32.c: Likewise.
            * g++.dg/tree-ssa/if-to-switch-1.C: New test.
            * gcc.dg/tree-ssa/if-to-switch-1.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-2.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-3.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-4.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-5.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-6.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-7.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-8.c: New test.
Comment 8 Martin Liška 2020-12-01 10:52:15 UTC
Implemented in master.