Data Fields | |
| HOST_WIDE_INT | hi |
| HOST_WIDE_INT | lo |
| edge | target_edge |
| tree | label |
| int | bits |
Detailed Description
Implement switch statements with bit tests
A GIMPLE switch statement can be expanded to a short sequence of bit-wise comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are integer constants. This is better than a series of compare-and-banch insns in some cases, e.g. we can implement:
if ((x==4) || (x==6) || (x==9) || (x==11))
as a single bit test:
if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
This transformation is only applied if the number of case targets is small, if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are performed in "word_mode".
The following example shows the code the transformation generates:
int bar(int x)
{
switch (x)
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case 'A': case 'B': case 'C': case 'D': case 'E':
case 'F':
return 1;
}
return 0;
}
==>
bar (int x)
{
tmp1 = x - 48;
if (tmp1 > (70 - 48)) goto L2;
tmp2 = 1 << tmp1;
tmp3 = 0b11111100000001111111111;
if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
L1:
return 1;
L2:
return 0;
}
TODO: There are still some improvements to this transformation that could be implemented:
A narrower mode than word_mode could be used if that is cheaper, e.g. for x86_64 where a narrower-mode shift may result in smaller code.
The compounded constant could be shifted rather than the one. The test would be either on the sign bit or on the least significant bit, depending on the direction of the shift. On some machines, the test for the branch would be free if the bit to test is already set by the shift operation.
This transformation was contributed by Roger Sayle, see this e-mail: http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html A case_bit_test represents a set of case nodes that may be selected from using a bit-wise comparison. HI and LO hold the integer to be tested against, TARGET_EDGE contains the edge to the basic block to jump to upon success and BITS counts the number of case nodes handled by this test, typically the number of bits set in HI:LO. The LABEL field is used to quickly identify all cases in this set without looking at label_to_block for every case label.
Field Documentation
| int case_bit_test::bits |
Referenced by expand_switch_using_bit_tests_p().
| HOST_WIDE_INT case_bit_test::hi |
Referenced by expand_switch_using_bit_tests_p().
| tree case_bit_test::label |
Referenced by expand_switch_using_bit_tests_p().
| HOST_WIDE_INT case_bit_test::lo |
Referenced by expand_switch_using_bit_tests_p().
| edge case_bit_test::target_edge |
Referenced by expand_switch_using_bit_tests_p().
The documentation for this struct was generated from the following file:
