Bug 46935 - We should recognize expanded switch statement and convert 2 way switch statements into shift & mask test
Summary: We should recognize expanded switch statement and convert 2 way switch statem...
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 4.6.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-12-14 10:51 UTC by Jan Hubicka
Modified: 2011-01-14 15:48 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2010-12-14 14:14:18


Attachments

Note You need to log in before you can comment on or make changes to this bug.
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.