[Bug middle-end/37710] When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[Bug middle-end/37710] When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note we almost optimize out the testcase now to just:
  <bb 2> [local count: 1073741819]:
  typenum.0_1 = (unsigned int) typenum_4(D);
  _2 = typenum.0_1 + 34;
  if (_2 > 33)
    goto <bb 6>; [34.00%]
  else
    goto <bb 3>; [66.00%]

  <bb 3> [local count: 708669597]:
  _10 = (unsigned int) typenum_4(D);
  _5 = 4294967294 - _10;
  if (_5 <= 1)
    goto <bb 5>; [33.33%]
  else
    goto <bb 4>; [66.67%]

  <bb 4> [local count: 472446402]:

  <bb 5> [local count: 708669603]:
  # prephitmp_8 = PHI <105(4), 115(3)>

  <bb 6> [local count: 1073741824]:
  # _3 = PHI <0(2), prephitmp_8(5)>
  return _3;

Not the problem described here is fixed, just the testcase does not hit it any
more.
Note we currently produce much better code than even LLVM which still does:
        movl    $.L.str, %ecx
        cmpl    $32, %eax
        ja      .LBB0_3
# %bb.2:
        cltq
        movq    .Lswitch.table.main(,%rax,8), %rcx
.LBB0_3:
        movsbl  (%rcx), %eax

[Bug middle-end/37710] When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is a new testcase:
extern void abort (void);

extern char *name1;
extern char *name2;

int stab_xcoff_builtin_type (int typenum) __attribute__((noclone,noinline));
int stab_xcoff_builtin_type (int typenum)
{
  const char *name;
  if (typenum >= 0 || typenum < -34)
    {
      return 0;
    }
  switch (-typenum)
    {
    case 1:
      name = name1;"int";
      break;
    case 2:
      name = "char";
    case 3:
      name = name2;"short";
      break;
    case 4:
      name = "long";
      break;
    case 5:
      name = "unsigned char";
      break;
    case 6:
      name = "signed char";
      break;
    case 7:
      name = "unsigned short";
      break;
    case 8:
      name = "unsigned int";
      break;
    case 9:
      name = "unsigned";
      break;
    case 10:
      name = "unsigned long";
      break;
    case 11:
      name = "void";
      break;
    case 12:
      name = "float";
      break;
    case 13:
      name = "double";
      break;
    case 14:
      name = "long double";
      break;
    case 15:
      name = "integer";
      break;
    case 16:
      name = "boolean";
      break;
    case 17:
      name = "short real";
      break;
    case 18:
      name = "real";
      break;
    case 19:
      name = "stringptr";
      break;
    case 20:
      name = "character";
      break;
    case 21:
      name = "logical*1";
      break;
    case 22:
      name = "logical*2";
      break;
    case 23:
      name = "logical*4";
      break;
    case 24:
      name = "logical";
      break;
    case 25:
      name = "complex";
      break;
    case 26:
      name = "double complex";
      break;
    case 27:
      name = "integer*1";
      break;
    case 28:
      name = "integer*2";
      break;
    case 29:
      name = "integer*4";
      break;
    case 30:
      name = "wchar";
    case 31:
      name = "long long";
      break;
    case 32:
      name = "unsigned long long";
      break;
    case 33:
      name = "logical*8";
      break;
    case 34:
      name = "integer*8";
      break;
    }
  return name[0];
}

int main()
{
  int i;
  if (stab_xcoff_builtin_type(0) != 0)
    abort ();
  if (stab_xcoff_builtin_type(-1) != 'i')
    abort ();
  if (stab_xcoff_builtin_type(-2) != 's')
    abort ();
  if (stab_xcoff_builtin_type(-3) != 's')
    abort ();
  for (i = -4; i >= -34; --i)
    if (stab_xcoff_builtin_type(i) != 'i')
      abort ();
  if (stab_xcoff_builtin_type(-35) != 0)
    abort ();
  return 0;
}

[Bug middle-end/37710] When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
and yes we get code that looks like:
        xorl    %eax, %eax
        cmpl    $-34, %edi
        jb      .L1
        negl    %edi
        cmpl    $34, %edi
        ja      .L3
        jmp     *.L5(,%rdi,8)
        .section        .rodata
        .align 8
        .align 4
.L5:
        .quad   .L3
        .quad   .L3

Even though we should something like:
        xorl    %eax, %eax
        cmpl    $-34, %edi
        jb      .L1
        negl    %edi
        jmp     *.L5(,%rdi,8)
        .section        .rodata
        .align 8
        .align 4
.L5:
        .quad   .L3

[Bug middle-end/37710] New: When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[hp at gcc dot gnu dot org]

See PR 35809, comment #3
<http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35809#c3>:
Looking at assembly-code for
gcc.c-torture/execute/pr35800.c at r140821 reveals that the first case is still
arbitrarily taken as the default, where the last one would have been better as
it's repeated 32 times.

So, when a new default-label is to be picked, use the end with identical
labels, and peel all of them off.  If there are no identical labels, use the
end which results in the smallest lower end of the case range. (Usually the
beginning needs to be added or subtracted in the back-end, so a smaller
constant (hopefully zero) usually means a lower cost.


-- 
           Summary: When peeling an ordinary label off a case-table and
                    making it a default label, strip from the end with
                    identical labels.
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: hp at gcc dot gnu dot org
GCC target triplet: cris-*-*


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37710

[Bug middle-end/37710] When peeling an ordinary label off a case-table and making it a default label, strip from the end with identical labels.

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-10-02 11:08 -------
This basically boils down to moving optimizing case labels earlier (we do
so after going out-of-ssa).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-10-02 11:08:25
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37710