[Bug optimization/14842] New: Another way of expanding a switch statement

[kazu at cs dot umass dot edu]

Convert foo() to baz() (at expand time or very late in tree optimization):

void bar (void);

void
foo (int a)
{
  switch (a)
    {
    case 5:
    case 7:
      bar ();
    }
}

void
baz (int a)
{
  if ((a & ~2) == 5)
    bar ();
}

On i686-pc-linux-gnu with -O2 -fomit-frame-pointer, I get:

	.text
	.p2align 2,,3
.globl foo
	.type	foo, @function
foo:
	movl	4(%esp), %eax	# 3	*movsi_1/1	[length = 4]
	cmpl	$5, %eax	# 9	*cmpsi_1_insn/1	[length = 3]
	je	.L3	# 10	*jcc_1	[length = 2]
	cmpl	$7, %eax	# 11	*cmpsi_1_insn/1	[length = 3]
	je	.L3	# 12	*jcc_1	[length = 2]
	ret	# 35	return_internal	[length = 1]
	.p2align 2,,3
.L3:
	jmp	bar	# 19	*call_0	[length = 5]
	.size	foo, .-foo
	.p2align 2,,3
.globl baz
	.type	baz, @function
baz:
	movl	4(%esp), %eax	# 29	*movsi_1/1	[length = 4]
	andl	$-3, %eax	# 9	*andsi_1/1	[length = 3]
	cmpl	$5, %eax	# 10	*cmpsi_1_insn/1	[length = 3]
	je	.L8	# 11	*jcc_1	[length = 2]
	ret	# 32	return_internal	[length = 1]
	.p2align 2,,3
.L8:
	jmp	bar	# 16	*call_0	[length = 5]
	.size	baz, .-baz

Comparing baz() to foo(), aside from the small size reduction,
notice that we have eliminated one conditional jump.
(If we need to preserve the value of "a", we don't get
the size reduction anymore because we need to make a copy of "a", but
we can still eliminate one conditional jump.)

Depending on a situation, we can either entirely replace the binary tree
expansion of the switch statement (like this case) or replace a part of
the binary tree.

If we think of this problem as minimizing a circuit recognizing 5 and 7,
we can use Quine-McCluskey minimization to make (a & ~2) == 5,
but a sequential program is different from a circuit, so the result of 
Quine-McCluskey minimization is not always optimal on a sequential machine.
It may not be a bad idea to just specialize for a small case involving only two
cases like this one.

-- 
           Summary: Another way of expanding a switch statement
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Keywords: pessimizes-code
          Severity: enhancement
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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