[9fans] 5l bug

[9fans] 5l bug

[Paul Patience]

Mischief reported a crash with on arm with
winwatch when closing all windows excluding those
ignored through the -e flag. Cinap_lenrek
narrowed the problem down to a bug in the 5l
linker: it generates incorrect code when using
the conditional operator and dividing.
A minimal test case is the following:

term% cat foo.c
#include <u.h>
#include <libc.h>

void
main(void)
{
	int i, j, k;

	i = 1;
	j = 0;
	k = j <= 0 ? 1 : 2/i;
	print("%d\n", k);
	exits(nil);
}

The output of asm(main) in acid is:

acid: asm(main)
main 0x00001020	MOVW.W	R14,#-0x18(R13)
main+0x4 0x00001024	MOVW	$#0x1,R1
main+0x8 0x00001028	MOVW	$#0x0,R2
main+0xc 0x0000102c	CMP.S	$#0x0,R2
main+0x10 0x00001030	MOVW.LE	R1,R3
main+0x14 0x00001034	MOVW.GT	$#0x2,R3
main+0x18 0x00001038	SUB.GT	$#0x8,R13,R13
main+0x1c 0x0000103c	MOVW	R1,#0x4(R13)
main+0x20 0x00001040	MOVW	R3,R11
main+0x24 0x00001044	BL	_div
main+0x28 0x00001048	MOVW	R11,R3
main+0x2c 0x0000104c	ADD	$#0x8,R13,R13
main+0x30 0x00001050	MOVW	$#0x7080,R0
main+0x34 0x00001054	MOVW	R3,#0x8(R13)
main+0x38 0x00001058	BL	print
main+0x3c 0x0000105c	MOVW	$#0x0,R0
main+0x40 0x00001060	BL	exits
main+0x44 0x00001064	RET.P	#0x18(R13)

The problem is that the division at main+0x24
happens regardless of the comparison. The output
from the compiler is correct, however:

term% 5c -S foo.c
	TEXT	main+0(SB),0,$20
	MOVW	$1,R1
	MOVW	$0,R2
	CMP	$0,R2,
	MOVW.LE	R1,R3
	MOVW.GT	$2,R3
	DIV.GT	R1,R3,R3
	MOVW	$.string<>+0(SB),R0
	MOVW	R3,8(R13)
	BL	,print+0(SB)
	MOVW	$0,R0
	BL	,exits+0(SB)
	RET	,
	DATA	.string<>+0(SB)/8,$"%d\n\z\z\z\z\z"
	GLOBL	.string<>+0(SB),$8
	END	,

A (temporary) workaround for this is using an
if-else statement, for which the linker generates
correct code.

--
pap

Re: [9fans] 5l bug

[cinap_lenrek]

following up, theres my naive fix for this. instead of
emiting conditional division instruction by 5c... dont and
keep the branch. does this make any sense?

term% hg diff -r 1777 peep.c
diff -r 5eeb36d3ddd0 sys/src/cmd/5c/peep.c
--- a/sys/src/cmd/5c/peep.c	Mon Jul 30 19:11:16 2012 +0200
+++ b/sys/src/cmd/5c/peep.c	Mon Apr 29 20:51:12 2013 +0200
@@ -1354,6 +1354,15 @@
 			j->end = r->s2;
 			return Branch;
 		}
+		switch(r->prog->as){
+		case ADIV:
+		case ADIVU:
+		case AMOD:
+		case AMODU:
+			/* emulated by 5l, doesnt handle conditionals */
+			j->end = r->s1;
+			return Toolong;
+		}
 		if (modifiescpsr(r->prog)) {
 			j->end = r->s1;
 			return Setcond;

--
cinap

Re: [9fans] 5l bug

[erik quanstrom]

On Mon Apr 29 14:55:02 EDT 2013, cinap_lenrek@gmx.de wrote:
> following up, theres my naive fix for this. instead of
> emiting conditional division instruction by 5c... dont and
> keep the branch. does this make any sense?
>
> term% hg diff -r 1777 peep.c
> diff -r 5eeb36d3ddd0 sys/src/cmd/5c/peep.c
> --- a/sys/src/cmd/5c/peep.c	Mon Jul 30 19:11:16 2012 +0200
> +++ b/sys/src/cmd/5c/peep.c	Mon Apr 29 20:51:12 2013 +0200
> @@ -1354,6 +1354,15 @@
>  			j->end = r->s2;
>  			return Branch;
>  		}
> +		switch(r->prog->as){
> +		case ADIV:
> +		case ADIVU:
> +		case AMOD:
> +		case AMODU:
> +			/* emulated by 5l, doesnt handle conditionals */
> +			j->end = r->s1;
> +			return Toolong;
> +		}
>  		if (modifiescpsr(r->prog)) {
>  			j->end = r->s1;
>  			return Setcond;

it's possible to do in the linker, but without trying this,
it looks reasonable to me.  what does the resulting asm
look like?

- erik

Re: [9fans] 5l bug

[cinap_lenrek]

term% cat foo.c
#include <u.h>
#include <libc.h>

void
main(void)
{
	int i, j, k;

	i = 1;
	j = 0;
	k = j <= 0 ? 1 : 2/i;
	print("%d\n", k);
	exits(nil);
}

term% 5c -S foo.c
	TEXT	main+0(SB),0,$20
	MOVW	$1,R1
	MOVW	$0,R2
	CMP	$0,R2,
	MOVW.LE	R1,R3
	BLE	,3(PC)
	MOVW	$2,R3
	DIV	R1,R3,R3
	MOVW	$.string<>+0(SB),R0
	MOVW	R3,8(R13)
	BL	,print+0(SB)
	MOVW	$0,R0
	BL	,exits+0(SB)
	RET	,
	DATA	.string<>+0(SB)/8,$"%d\n\z\z\z\z\z"
	GLOBL	.string<>+0(SB),$8
	END	,

5.out:arm plan 9 executable
/sys/lib/acid/port
/sys/lib/acid/arm
acid: asm(main)
main 0x00001020	MOVW.W	R14,#-0x18(R13)
main+0x4 0x00001024	MOVW	$#0x1,R1
main+0x8 0x00001028	MOVW	$#0x0,R2
main+0xc 0x0000102c	CMP.S	$#0x0,R2
main+0x10 0x00001030	MOVW.LE	R1,R3
main+0x14 0x00001034	B.LE	main+0x34
main+0x18 0x00001038	MOVW	$#0x2,R3
main+0x1c 0x0000103c	SUB	$#0x8,R13,R13
main+0x20 0x00001040	MOVW	R1,#0x4(R13)
main+0x24 0x00001044	MOVW	R3,R11
main+0x28 0x00001048	BL	_div
main+0x2c 0x0000104c	MOVW	R11,R3
main+0x30 0x00001050	ADD	$#0x8,R13,R13
main+0x34 0x00001054	MOVW	$#0x7084,R0
main+0x38 0x00001058	MOVW	R3,#0x8(R13)
main+0x3c 0x0000105c	BL	print
main+0x40 0x00001060	MOVW	$#0x0,R0
main+0x44 0x00001064	BL	exits
main+0x48 0x00001068	RET.P	#0x18(R13)
_main 0x0000106c	MOVW.W	R14,#-0x54(R13)
acid:

--
cinap

Re: [9fans] 5l bug

[erik quanstrom]

nice.

- erik

Re: [9fans] 5l bug

[Richard Miller]

> following up, theres my naive fix for this. instead of
> emiting conditional division instruction by 5c... dont and
> keep the branch. does this make any sense?

I think it should be corrected in 5l.  Some ARM versions do
have a hardware divide instruction, which could one day be
supported by 5l, so 5c should be kept more generic.

Re: [9fans] 5l bug

[kernel panic]

> Gesendet: Montag, 29. April 2013 um 21:34 Uhr
> Von: "Richard Miller" <9fans@hamnavoe.com>
> An: 9fans@9fans.net
> Betreff: Re: [9fans] 5l bug
>
> > following up, theres my naive fix for this. instead of
> > emiting conditional division instruction by 5c... dont and
> > keep the branch. does this make any sense?
>
> I think it should be corrected in 5l.  Some ARM versions do
> have a hardware divide instruction, which could one day be
> supported by 5l, so 5c should be kept more generic.

The compiler already assumes things that would be not true for
native divide instructions. For example, we assume that divide
modifies the condition flags, which would not be the case for
native SDIV/UDIV, but is the case for the emulated ones because
its implemented as a subroutine:

(from /sys/src/cmd/5c/peep.c)

/*
 * Depends on an analysis of the encodings performed by 5l.
 * These seem to be all of the opcodes that lead to the "S" bit
 * being set in the instruction encodings.
 *
 * C_SBIT may also have been set explicitly in p->scond.
 */
int
modifiescpsr(Prog *p)
{
	return (p->scond&C_SBIT)
		|| p->as == ATST
		|| p->as == ATEQ
		|| p->as == ACMN
		|| p->as == ACMP
		|| p->as == AMULU
		|| p->as == ADIVU
		|| p->as == AMUL
		|| p->as == ADIV
		|| p->as == AMOD
		|| p->as == AMODU
		|| p->as == ABL;
}

the change i made just avoids the branch optimization for these
instructions not executing them conditionally. the whole idea of
this pass is to avoid the branching arround *short* conditional
code sequences (4 instructions at max).

with the emulated instructions the _div call setup already takes
more than 4 instructions and just reintroducing a branch in the
linker counters what the optimization pass tried to archive in the
first place.

but maybe its not really worth thinking about because conditional
divide seems quite rare (?) and emulated divide will be slow in any
case (?) so it wont matter if we readd conditional branch in the linker?

still, the dependency between 5l <-> 5c above remains... otherwise,
one would need to write condition flag preserving version... for
these instructions to make them behave exactly like the native
instructions... perhaps emulate the instructions by traping in the
kernel? seems even slower... how ignorant do we want 5c to be at
what cost?

--
cinap

Re: [9fans] 5l bug

[zephyr.pellerin]

Patching p -> scond = q -> scond in /sys/src/cmd/5l/noop.c fixes this unfortunate linker bug.

On Sunday, April 28, 2013 10:54:18 PM UTC-7, Paul Patience wrote:
> Mischief reported a crash with on arm with
>
> winwatch when closing all windows excluding those
>
> ignored through the -e flag. Cinap_lenrek
>
> narrowed the problem down to a bug in the 5l
>
> linker: it generates incorrect code when using
>
> the conditional operator and dividing.
>
> A minimal test case is the following:
>
>
>
> term% cat foo.c
>
> #include <u.h>
>
> #include <libc.h>
>
>
>
> void
>
> main(void)
>
> {
>
> 	int i, j, k;
>
>
>
> 	i = 1;
>
> 	j = 0;
>
> 	k = j <= 0 ? 1 : 2/i;
>
> 	print("%d\n", k);
>
> 	exits(nil);
>
> }
>
>
>
> The output of asm(main) in acid is:
>
>
>
> acid: asm(main)
>
> main 0x00001020	MOVW.W	R14,#-0x18(R13)
>
> main+0x4 0x00001024	MOVW	$#0x1,R1
>
> main+0x8 0x00001028	MOVW	$#0x0,R2
>
> main+0xc 0x0000102c	CMP.S	$#0x0,R2
>
> main+0x10 0x00001030	MOVW.LE	R1,R3
>
> main+0x14 0x00001034	MOVW.GT	$#0x2,R3
>
> main+0x18 0x00001038	SUB.GT	$#0x8,R13,R13
>
> main+0x1c 0x0000103c	MOVW	R1,#0x4(R13)
>
> main+0x20 0x00001040	MOVW	R3,R11
>
> main+0x24 0x00001044	BL	_div
>
> main+0x28 0x00001048	MOVW	R11,R3
>
> main+0x2c 0x0000104c	ADD	$#0x8,R13,R13
>
> main+0x30 0x00001050	MOVW	$#0x7080,R0
>
> main+0x34 0x00001054	MOVW	R3,#0x8(R13)
>
> main+0x38 0x00001058	BL	print
>
> main+0x3c 0x0000105c	MOVW	$#0x0,R0
>
> main+0x40 0x00001060	BL	exits
>
> main+0x44 0x00001064	RET.P	#0x18(R13)
>
>
>
> The problem is that the division at main+0x24
>
> happens regardless of the comparison. The output
>
> from the compiler is correct, however:
>
>
>
> term% 5c -S foo.c
>
> 	TEXT	main+0(SB),0,$20
>
> 	MOVW	$1,R1
>
> 	MOVW	$0,R2
>
> 	CMP	$0,R2,
>
> 	MOVW.LE	R1,R3
>
> 	MOVW.GT	$2,R3
>
> 	DIV.GT	R1,R3,R3
>
> 	MOVW	$.string<>+0(SB),R0
>
> 	MOVW	R3,8(R13)
>
> 	BL	,print+0(SB)
>
> 	MOVW	$0,R0
>
> 	BL	,exits+0(SB)
>
> 	RET	,
>
> 	DATA	.string<>+0(SB)/8,$"%d\n\z\z\z\z\z"
>
> 	GLOBL	.string<>+0(SB),$8
>
> 	END	,
>
>
>
> A (temporary) workaround for this is using an
>
> if-else statement, for which the linker generates
>
> correct code.
>
>
>
> --
>
> pap

Re: [9fans] 5l bug

[kernel panic]

i is not ovious to me why that would work without adding a conditiona branch.
maybe my assumptions are wrong. can you show the resulting assembly for the
testcase?

> Gesendet: Dienstag, 30. April 2013 um 11:07 Uhr
> Von: zephyr.pellerin@gmail.com
> An: 9fans@9fans.net
> Betreff: Re: [9fans] 5l bug
>
> Patching p -> scond = q -> scond in /sys/src/cmd/5l/noop.c fixes this unfortunate linker bug.
>

--
cinap