[Bug tree-optimization/101301] New: Improving sparse switch statement

[tkoenig at gcc dot gnu.org]

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

            Bug ID: 101301
           Summary: Improving sparse switch statement
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

The following two functions do the same thing:

int foo(int x)
{
     switch (x) {
      case 11111: return 1;
      case 22222: return 2;
      case 33333: return 3;
      case 44444: return 4;
      case 55555: return 5;
      case 66666: return 6;
      case 77777: return 7;
      case 88888: return 8;
      case 99999: return 9;
      default: return 0;
     }
}

int foo2(int n)
{
  if (n >= 55555)
    {
      if (n >= 77777)
        {
          if (n == 77777)
            return 7;
          if (n == 88888)
            return 8;
          if (n == 99999)
            return 9;

          return 0;
        }
      else
        {
          if (n == 55555)
            return 5;
          if (n == 66666)
            return 6;

          return 0;
        }
    }
  else
    {
      if (n >= 33333)
        {
          if (n == 33333)
            return 3;
          if (n == 44444)
            return 4;

          return 0;
        }
      else
        {
          if (n == 11111)
            return 1;
          if (n == 22222)
            return 2;

          return 0;
        }
    }
}

but foo2 is translated into code with fewer conditional branches
on average.  Considering how expensive a mispredicted branch
can be, translating foo like foo2 could be an improvement.