Bug 46935

Summary: We should recognize expanded switch statement and convert 2 way switch statements into shift & mask test
Product: gcc Reporter: Jan Hubicka <hubicka>
Component: middle-endAssignee: Martin Liška <marxin>
Status: RESOLVED FIXED    
Severity: enhancement CC: guillaume, jakub, laurent, mjambor, mkuvyrkov, vries
Priority: P3 Keywords: patch
Version: 4.6.0   
Target Milestone: ---   
See Also: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14799
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2019-11-04 00:00:00

Description Jan Hubicka 2010-12-14 10:51:03 UTC 
As observed at http://blog.regehr.org/archives/320 (example 7)
testcase:

int crud (unsigned char c)
{
  return (((((((((((int) c <= 32 || (int) c == 46) || (int) c == 44)
		 || (int) c == 58) || (int) c == 59) || (int) c == 60)
	      || (int) c == 62) || (int) c == 34) || (int) c == 92)
	   || (int) c == 39) != 0);
}

Can be compiled using shift and mask test operation as:
crud:
        movzbl    %dil, %edi
        cmpl      $32, %edi
        jle       ..B1.4
        addl      $-34, %edi
        cmpl      $64, %edi
        jae       ..B1.5
        movl      $1, %eax
        movl      %edi, %ecx
        shlq      %cl, %rax
        movq      $0x400000017001421, %rdx
        testq     %rdx, %rax
        je        ..B1.5
..B1.4:
        movl      $1, %eax
        ret
..B1.5:
        xorl      %eax, %eax
        ret

Probably switch conversion pass could be responsible for this.

Honza
Comment 1 Jan Hubicka 2010-12-14 10:51:51 UTC 
Note that both llvm and ICC support this optimization and it was requested by kernel folks for a while (they do so by hand)
Comment 2 Jakub Jelinek 2010-12-14 11:01:11 UTC 
We probably don't want to do such transformation into GIMPLE_SWITCH always, only if the number of comparisons of the same SSA_NAME is big enough and the range isn't too big.

expand_switch_using_bit_tests_p can be used if we want to limit it just to the bittest cases.
Comment 3 Jan Hubicka 2010-12-14 14:14:18 UTC 
I would do the conversion always when we can turn more than one if into signle switch.  Doing so reduces the amount of IL and makes program easier to analyze&opotimize. We should rely on switch expansion code doing the right thing producing back the ifs when profitable.
Comment 4 Maxim Kuvyrkov 2010-12-20 18:42:45 UTC 
I know Tom de Vries is working on this problem and has a prototype patch.  He'll be posting his work for 4.7.
Comment 5 Tom de Vries 2011-01-14 13:17:09 UTC 
> I know Tom de Vries is working on this problem and has a prototype patch.
> He'll be posting his work for 4.7.

http://gcc.gnu.org/ml/gcc-patches/2011-01/msg00959.html
Comment 6 Tom de Vries 2011-01-14 15:48:03 UTC 
Related bug: PR 14799.
Comment 7 Eric Gallager 2018-08-31 11:38:57 UTC 
(In reply to Tom de Vries from comment #5)
> > I know Tom de Vries is working on this problem and has a prototype patch.
> > He'll be posting his work for 4.7.
> 
> http://gcc.gnu.org/ml/gcc-patches/2011-01/msg00959.html

Does it still apply for gcc 9?
Comment 8 Martin Liška 2019-11-04 13:09:01 UTC 
The test-case is still valid.
Comment 9 Martin Liška 2019-11-04 13:13:23 UTC 
(In reply to Martin Liška from comment #8)
> The test-case is still valid.

Sorry, no, the issue is already solved with GCC 9.2:

crud (unsigned char c)
{
  _Bool _11;
  int iftmp.0_14;
  int _16;
  long unsigned int _24;
  _Bool _26;
  int _30;
  long unsigned int _32;

  <bb 2> [local count: 1073741823]:
  if (c_15(D) > 62)
    goto <bb 4>; [50.00%]
  else
    goto <bb 3>; [50.00%]

  <bb 3> [local count: 536870911]:
  _16 = (int) c_15(D);
  _24 = 6629387187945209855 >> _16;
  _32 = ~_24;
  _26 = (_Bool) _32;
  if (_26 != 0)
    goto <bb 4>; [20.00%]
  else
    goto <bb 5>; [80.00%]

  <bb 4> [local count: 536870911]:
  _11 = c_15(D) == 92;
  _30 = (int) _11;

  <bb 5> [local count: 1073741824]:
  # iftmp.0_14 = PHI <_30(4), 1(3)>
  return iftmp.0_14;

}