code review 7066055: cmd/6c: Improve peep hole optimization of rotate and sh...

cmd/6c: Improve peep hole optimization of rotate and shift instructions.

Update issue 4629.

$ cat shift2.c
unsigned int
shift(unsigned int x, unsigned int y)
{
        x = (x << 3);
        y = (y << 5);
        x = (x << 7);
        y = (y << 9);
        return x ^ y;
}

## BEFORE
$ go tool 6c -S shift2.c
(shift2.c:2)	TEXT	shift+0(SB),$0-8
(shift2.c:4)	MOVL	x+0(FP),!!AX
(shift2.c:4)	SALL	$3,!!AX
(shift2.c:4)	MOVL	AX,!!DX
(shift2.c:5)	MOVL	y+4(FP),!!AX
(shift2.c:5)	SALL	$5,!!AX
(shift2.c:5)	MOVL	AX,!!CX
(shift2.c:6)	MOVL	DX,!!AX
(shift2.c:6)	SALL	$7,!!AX
(shift2.c:6)	MOVL	AX,!!DX
(shift2.c:7)	MOVL	CX,!!AX
(shift2.c:7)	SALL	$9,!!AX
(shift2.c:7)	MOVL	AX,!!CX
(shift2.c:8)	MOVL	DX,!!AX
(shift2.c:8)	XORL	CX,!!AX
(shift2.c:8)	RET	,!!
(shift2.c:8)	RET	,!!
(shift2.c:8)	END	,!!

## AFTER
$ go tool 6c -S shift2.c
(shift2.c:2)	TEXT	shift+0(SB),$0-8
(shift2.c:4)	MOVL	x+0(FP),!!AX
(shift2.c:4)	SALL	$3,!!AX
(shift2.c:5)	MOVL	y+4(FP),!!CX
(shift2.c:5)	SALL	$5,!!CX
(shift2.c:6)	SALL	$7,!!AX
(shift2.c:7)	SALL	$9,!!CX
(shift2.c:8)	XORL	CX,!!AX
(shift2.c:8)	RET	,!!
(shift2.c:8)	RET	,!!
(shift2.c:8)	END	,!!

[mdempsky, 2013-01-09 21:06:44]

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

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

[mdempsky, 2013-01-09 21:08:09]

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c
File src/cmd/6c/peep.c (right):

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c#newcode333
src/cmd/6c/peep.c:333: 
This matches 6g/peep.c like you asked, but is it intentional that AIMUL[LQW]
instructions now check p->from.type == D_CONST too?

[minux1, 2013-01-09 21:11:02]

any before/after comparisons of '6c -S'?
(please add to the description)

[mdempsky, 2013-01-09 21:16:29]

On 2013/01/09 21:11:02, minux wrote:
> any before/after comparisons of '6c -S'?
> (please add to the description)

6c doesn't currently emit ROTL instructions, so no differences.

However, if combined with https://codereview.appspot.com/7069056:

$ cat rotate2.c
unsigned int
rotate(unsigned int x, unsigned int y)
{
	x = (x << 3) | (x >> (sizeof(x) * 8 - 3));
	y = (y << 5) | (y >> (sizeof(y) * 8 - 5));
	x = (x << 7) | (x >> (sizeof(x) * 8 - 7));
	y = (y << 9) | (y >> (sizeof(y) * 8 - 9));
	return x ^ y;
}


## BEFORE

$ go tool 6c -S rotate2.c
(rotate2.c:2)	TEXT	rotate+0(SB),$0-8
(rotate2.c:4)	MOVL	x+0(FP),!!AX
(rotate2.c:4)	ROLL	$3,!!AX
(rotate2.c:4)	MOVL	AX,!!DX
(rotate2.c:5)	MOVL	y+4(FP),!!AX
(rotate2.c:5)	ROLL	$5,!!AX
(rotate2.c:5)	MOVL	AX,!!CX
(rotate2.c:6)	MOVL	DX,!!AX
(rotate2.c:6)	ROLL	$7,!!AX
(rotate2.c:6)	MOVL	AX,!!DX
(rotate2.c:7)	MOVL	CX,!!AX
(rotate2.c:7)	ROLL	$9,!!AX
(rotate2.c:7)	MOVL	AX,!!CX
(rotate2.c:8)	MOVL	DX,!!AX
(rotate2.c:8)	XORL	CX,!!AX
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	END	,!!


## AFTER

$ go tool 6c -S rotate2.c
(rotate2.c:2)	TEXT	rotate+0(SB),$0-8
(rotate2.c:4)	MOVL	x+0(FP),!!AX
(rotate2.c:4)	ROLL	$3,!!AX
(rotate2.c:5)	MOVL	y+4(FP),!!CX
(rotate2.c:5)	ROLL	$5,!!CX
(rotate2.c:6)	ROLL	$7,!!AX
(rotate2.c:7)	ROLL	$9,!!CX
(rotate2.c:8)	XORL	CX,!!AX
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	END	,!!

[mdempsky, 2013-01-09 21:18:29]

Er, I should point out the "BEFORE" there is with 7069056 applied.  The status
quo is:

## UNPATCHED

$ go tool 6c -S rotate2.c
(rotate2.c:2)	TEXT	rotate+0(SB),$0-8
(rotate2.c:2)	MOVL	x+0(FP),!!AX
(rotate2.c:2)	MOVL	y+4(FP),!!DX
(rotate2.c:4)	MOVL	AX,!!BX
(rotate2.c:4)	SALL	$3,!!AX
(rotate2.c:4)	MOVL	BX,!!CX
(rotate2.c:4)	SHRL	$29,!!CX
(rotate2.c:4)	ORL	CX,!!AX
(rotate2.c:4)	MOVL	AX,!!BX
(rotate2.c:5)	MOVL	DX,!!AX
(rotate2.c:5)	SALL	$5,!!AX
(rotate2.c:5)	MOVL	DX,!!CX
(rotate2.c:5)	SHRL	$27,!!CX
(rotate2.c:5)	ORL	CX,!!AX
(rotate2.c:5)	MOVL	AX,!!DX
(rotate2.c:6)	MOVL	BX,!!AX
(rotate2.c:6)	SALL	$7,!!AX
(rotate2.c:6)	MOVL	BX,!!CX
(rotate2.c:6)	SHRL	$25,!!CX
(rotate2.c:6)	ORL	CX,!!AX
(rotate2.c:6)	MOVL	AX,!!BX
(rotate2.c:7)	MOVL	DX,!!AX
(rotate2.c:7)	SALL	$9,!!AX
(rotate2.c:7)	MOVL	DX,!!CX
(rotate2.c:7)	SHRL	$23,!!CX
(rotate2.c:7)	ORL	CX,!!AX
(rotate2.c:7)	MOVL	AX,!!CX
(rotate2.c:8)	MOVL	BX,!!AX
(rotate2.c:8)	XORL	CX,!!AX
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	RET	,!!
(rotate2.c:8)	END	,!!

[mdempsky, 2013-01-09 21:24:17]

Oh right, it helps shifts too. :) Updated the description to provide an example.

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c
File src/cmd/6c/peep.c (right):

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c#newcode333
src/cmd/6c/peep.c:333: 
On 2013/01/09 21:08:09, mdempsky wrote:
> This matches 6g/peep.c like you asked, but is it intentional that AIMUL[LQW]
> instructions now check p->from.type == D_CONST too?

Actually, this seems fine.  IMUL with "to" set to D_NONE means the output will
be written to EDX:EAX, and that format instruction can't multiply by a constant
anyway.

[rsc, 2013-01-09 21:57:49]

LGTM

Could you add an explicit return 0; to the IMULW case in both 6c and 6g?
Thanks.

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c
File src/cmd/6c/peep.c (right):

https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c#newcode333
src/cmd/6c/peep.c:333: 
On 2013/01/09 21:24:17, mdempsky wrote:
> On 2013/01/09 21:08:09, mdempsky wrote:
> > This matches 6g/peep.c like you asked, but is it intentional that AIMUL[LQW]
> > instructions now check p->from.type == D_CONST too?
> 
> Actually, this seems fine.  IMUL with "to" set to D_NONE means the output will
> be written to EDX:EAX, and that format instruction can't multiply by a
constant
> anyway.

I don't think I intended that when I fixed 6g, but yes it does work. :-)

[dave_cheney.net, 2013-01-09 22:00:54]

Thoughts about doing this for 8c (if affected) ?

On Thu, Jan 10, 2013 at 8:57 AM,  <rsc@golang.org> wrote:
> LGTM
>
> Could you add an explicit return 0; to the IMULW case in both 6c and 6g?
> Thanks.
>
>
>
>
> https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c
> File src/cmd/6c/peep.c (right):
>
> https://codereview.appspot.com/7066055/diff/1003/src/cmd/6c/peep.c#newcode333
> src/cmd/6c/peep.c:333:
> On 2013/01/09 21:24:17, mdempsky wrote:
>>
>> On 2013/01/09 21:08:09, mdempsky wrote:
>> > This matches 6g/peep.c like you asked, but is it intentional that
>
> AIMUL[LQW]
>>
>> > instructions now check p->from.type == D_CONST too?
>
>
>> Actually, this seems fine.  IMUL with "to" set to D_NONE means the
>
> output will
>>
>> be written to EDX:EAX, and that format instruction can't multiply by a
>
> constant
>>
>> anyway.
>
>
> I don't think I intended that when I fixed 6g, but yes it does work. :-)
>
> https://codereview.appspot.com/7066055/

[minux1, 2013-01-09 22:08:17]

On Thu, Jan 10, 2013 at 6:00 AM, Dave Cheney <dave@cheney.net> wrote:

> Thoughts about doing this for 8c (if affected) ?

I've been experimenting with a similar change to cmd/8c, and i confirm it's
affected.
however, go tool 8c -S x.c shows this:
(x.c:2) TEXT    shift+0(SB),(gok(79))   //  why gok(79) here???
(x.c:4) MOVL    x+0(FP),AX
(x.c:4) SALL    $3,AX
(x.c:5) MOVL    y+4(FP),CX
(x.c:5) SALL    $5,CX
(x.c:6) SALL    $7,AX
(x.c:7) SALL    $9,CX
(x.c:8) XORL    CX,AX
(x.c:8) RET     ,
(x.c:8) RET     ,
(x.c:8) END     ,

[mdempsky, 2013-01-09 22:45:49]

Hello rsc@golang.org, minux.ma@gmail.com, dave@cheney.net (cc:
golang-dev@googlegroups.com),

Please take another look.

[mdempsky, 2013-01-09 22:48:35]

On 2013/01/09 21:57:49, rsc wrote:
> Could you add an explicit return 0; to the IMULW case in both 6c and 6g?

I added a "giveup:" label and "goto giveup;" to the end of the imul and
shift/rotate blocks.  This way the fall through is explicit, and in the case of
6g, the debug prints don't need to be duplicated.

Let me know if you think "return 0;" would be better still.

[nigeltao, 2013-01-10 00:58:44]

In the CL description, s/Related to issue 4629./Update issue 4629./ and leave a
blank line after it.

http://code.google.com/p/support/wiki/IssueTracker#Integration_with_version_c...

[mdempsky, 2013-01-10 01:00:40]

On 2013/01/10 00:58:44, nigeltao wrote:
> In the CL description, s/Related to issue 4629./Update issue 4629./ and leave
a
> blank line after it.

Done.

>
http://code.google.com/p/support/wiki/IssueTracker#Integration_with_version_c...

Hadn't seen that, thanks!

[mdempsky, 2013-01-18 20:32:34]

Ping?

[rsc, 2013-01-18 21:32:42]

LGTM

[rsc, 2013-01-18 21:33:35]

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

cmd/6c: Improve peep hole optimization of rotate and shift instructions.

Update issue 4629.

$ cat shift2.c
unsigned int
shift(unsigned int x, unsigned int y)
{
        x = (x << 3);
        y = (y << 5);
        x = (x << 7);
        y = (y << 9);
        return x ^ y;
}

## BEFORE
$ go tool 6c -S shift2.c
(shift2.c:2)	TEXT	shift+0(SB),$0-8
(shift2.c:4)	MOVL	x+0(FP),!!AX
(shift2.c:4)	SALL	$3,!!AX
(shift2.c:4)	MOVL	AX,!!DX
(shift2.c:5)	MOVL	y+4(FP),!!AX
(shift2.c:5)	SALL	$5,!!AX
(shift2.c:5)	MOVL	AX,!!CX
(shift2.c:6)	MOVL	DX,!!AX
(shift2.c:6)	SALL	$7,!!AX
(shift2.c:6)	MOVL	AX,!!DX
(shift2.c:7)	MOVL	CX,!!AX
(shift2.c:7)	SALL	$9,!!AX
(shift2.c:7)	MOVL	AX,!!CX
(shift2.c:8)	MOVL	DX,!!AX
(shift2.c:8)	XORL	CX,!!AX
(shift2.c:8)	RET	,!!
(shift2.c:8)	RET	,!!
(shift2.c:8)	END	,!!

## AFTER
$ go tool 6c -S shift2.c
(shift2.c:2)	TEXT	shift+0(SB),$0-8
(shift2.c:4)	MOVL	x+0(FP),!!AX
(shift2.c:4)	SALL	$3,!!AX
(shift2.c:5)	MOVL	y+4(FP),!!CX
(shift2.c:5)	SALL	$5,!!CX
(shift2.c:6)	SALL	$7,!!AX
(shift2.c:7)	SALL	$9,!!CX
(shift2.c:8)	XORL	CX,!!AX
(shift2.c:8)	RET	,!!
(shift2.c:8)	RET	,!!
(shift2.c:8)	END	,!!

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

Committer: Russ Cox <rsc@golang.org>