code review 7069056: cmd/6c: Optimize rotate expressions to use rotate instr...

cmd/6c: Optimize rotate expressions to use rotate instructions.

For simplicity, only recognizes expressions of the exact form
"(x << a) | (x >> b)" where x is a variable and a and b are
integer constant expressions that add to x's bit width.

Fixes issue 4629.

$ cat rotate.c
unsigned int
rotate(unsigned int x)
{
        x = (x << 3) | (x >> (sizeof(x) * 8 - 3));
        return x;
}

## BEFORE
$ go tool 6c -S rotate.c
(rotate.c:2)	TEXT	rotate+0(SB),$0-8
(rotate.c:2)	MOVL	x+0(FP),!!DX
(rotate.c:4)	MOVL	DX,!!AX
(rotate.c:4)	SALL	$3,!!AX
(rotate.c:4)	MOVL	DX,!!CX
(rotate.c:4)	SHRL	$29,!!CX
(rotate.c:4)	ORL	CX,!!AX
(rotate.c:5)	RET	,!!
(rotate.c:5)	RET	,!!
(rotate.c:5)	END	,!!

## AFTER
$ go tool 6c -S rotate.c
(rotate.c:2)	TEXT	rotate+0(SB),$0-8
(rotate.c:4)	MOVL	x+0(FP),!!AX
(rotate.c:4)	ROLL	$3,!!AX
(rotate.c:5)	RET	,!!
(rotate.c:5)	RET	,!!
(rotate.c:5)	END	,!!

[mdempsky, 2013-01-10 01:58:47]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go

[rsc, 2013-01-18 21:46:49]

Please add 8c too. It should be mostly copy and paste.

[mdempsky, 2013-01-18 22:18:00]

On 2013/01/18 21:46:49, rsc wrote:
> Please add 8c too. It should be mostly copy and paste.

Done.  Also verified that 8c similarly optimizes rotations for uint32
expressions but doesn't modify uint64 expressions.

As an aside, I notice now that neither 6c nor 8c optimizes rotations of uint8 or
uint16 expressions.  I think this is actually correct though, since otherwise

  uint16 x = 0x1000;
  uint32 y = (x << 8) | (x >> 8);

might set y to 0x10 (wrong) instead of 0x100010 (correct).

[minux1, 2013-01-18 22:27:38]

I guess I will need to port these changes to cmd/5c.

https://codereview.appspot.com/7069056/diff/18001/src/cmd/6c/cgen.c
File src/cmd/6c/cgen.c (right):

https://codereview.appspot.com/7069056/diff/18001/src/cmd/6c/cgen.c#newcode268
src/cmd/6c/cgen.c:268: if(n->op == OOR && l->op == OASHL && r->op == OLSHR
also check for ^?
because (x << 3) ^ (x >> (sizeof(x)*8-3)) is also a rotate.

[rsc, 2013-01-18 22:28:19]

On Fri, Jan 18, 2013 at 5:27 PM,  <minux.ma@gmail.com> wrote:
> I guess I will need to port these changes to cmd/5c.

That'd be great, thanks. While you're there please check that I did a
good enough job in 5g.
It looks like I couldn't find an actual rotate instruction, which
seems a little surprising.

Russ

[rsc, 2013-01-18 22:29:11]

FWIW, I am not too worried about XOR, nor am I worried about >> | <<.
6g etc handle these cases, since they are used by all our Go users. In
comparison, 6c is a much more specialized thing - basically only we
use it.

Russ

[rsc, 2013-01-18 22:29:58]

*** Submitted as https://code.google.com/p/go/source/detail?r=3a0b341a95de ***

cmd/6c: Optimize rotate expressions to use rotate instructions.

For simplicity, only recognizes expressions of the exact form
"(x << a) | (x >> b)" where x is a variable and a and b are
integer constant expressions that add to x's bit width.

Fixes issue 4629.

$ cat rotate.c
unsigned int
rotate(unsigned int x)
{
        x = (x << 3) | (x >> (sizeof(x) * 8 - 3));
        return x;
}

## BEFORE
$ go tool 6c -S rotate.c
(rotate.c:2)	TEXT	rotate+0(SB),$0-8
(rotate.c:2)	MOVL	x+0(FP),!!DX
(rotate.c:4)	MOVL	DX,!!AX
(rotate.c:4)	SALL	$3,!!AX
(rotate.c:4)	MOVL	DX,!!CX
(rotate.c:4)	SHRL	$29,!!CX
(rotate.c:4)	ORL	CX,!!AX
(rotate.c:5)	RET	,!!
(rotate.c:5)	RET	,!!
(rotate.c:5)	END	,!!

## AFTER
$ go tool 6c -S rotate.c
(rotate.c:2)	TEXT	rotate+0(SB),$0-8
(rotate.c:4)	MOVL	x+0(FP),!!AX
(rotate.c:4)	ROLL	$3,!!AX
(rotate.c:5)	RET	,!!
(rotate.c:5)	RET	,!!
(rotate.c:5)	END	,!!

R=rsc, minux.ma
CC=golang-dev
https://codereview.appspot.com/7069056

Committer: Russ Cox <rsc@golang.org>