case_bit_test Struct Reference

Collaboration diagram for case_bit_test:

Data Fields
HOST_WIDE_INT	hi
HOST_WIDE_INT	lo
edge	target_edge
tree	label
int	bits

---

Detailed Description

@verbatim 

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:

• tree-switch-conversion.c