LCC Bug: Guard bits should be updated before right shifts

[victor]

Code: Select all

#define USE_STDOUT

#include <stdlib.h>
#include <stdio.h>
#include <vstypes.h>

s_int32 a = 0x80000000;
s_int32 b = 0x00000001;

main(void) {
	s_int32 c = a - b; // c = 0x7fffffff
	printf("(a - b) >> 16 = %08lx\n", c >> 16);
	return 0;
}

Output (code generated by LCC v1.47 (Dec 11 2013 14:49:00)):

(a - b) >> 16 = ffff7fff


Expected result:

(a - b) >> 16 = 00007fff


Since variable a and b are interpreted as 40-bit registers in VSDSP, a - b does not cause a overflow (0xff7ffffff); but as a and b are defined as signed 32 bit numbers, the result should be 0x7fffffff. After a right shift, one can observe the extra guard bits instead of zeros. Guard bits should be updated by emitting a "MV A1,A1" (or similar) instruction before the ASHL instruction.

The bug (probably a feature?) makes porting a working program to VSDSP even harder and error-prone, since a bug like this is very hard to discover... Currently my work around is to define a simple function

Code: Select all

	.sect code,___builtin_clr_guard
	.export ___builtin_clr_guard
___builtin_clr_guard:
	jr
	mv A1,A1

And call this function __builtin_clr_guard() every time before doing a right shift on a 32-bit variable.

[Henrik]

Hello!

I'll forward also this to Lasse. Thanks for this report, too; I hope we can get this fixed for the very next VSIDE release.

Kind regards,
- Henrik

[victor]

Any updates on this issue?

[Henrik]

Any updates on this issue?

Lasse is working with this issue, and he knows where the issue is, but solving it is a bit tricky. I still think the correction will be available for the next VSIDE release which I hope will be soon.

Kind regards,
- Henrik

[Panu]

That's right. The main thing is that some thought is needed in deciding what kind of fix should be applied. It would be rather expensive to always add the code to clear (sign-extend) the guard bits. Also it just might be that we have some code that benefits from the implicit extra precision a symbol might have (if not spilled). Lasse thinks that one possibility is to add a command line switch to set the clearing on a file-by-file basis. The best would be to add a #pragma to switch it on and off, but this would be the most difficult fix.

Your input is appreciated!

-Panu

[Henrik]

Hello Victor,

all right, after long and lively discussions on the subject, here's what we've gathered so far. Sorry for the long message, but I thought you might be interested into getting into the nitty gritty.

The problem stems from the fact that if s_int32 a = 0x80000000 and s_int32 b = 0x00000001, then the expression a-b causes an integer overflow. The ANSI C/90 standard says that in such a situation behaviour is unspecified. I'm throwing a few quotes straight out of the standard:

3.17 unspecified behavior: Behavior, for a correct program construct and correct data, for which this International Standard explicitly imposes no requirements.
Examples
[...]
2. An example of undefined behavior is the behavior of integer overflow.
3. An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.
[...]

6.1.2.5 Types
[...]
A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.
[...]

6.3 Expressions
[...]
If an exception occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behevior is undefined.
[...]

On these grounds, I'd say that our compiler is complying to the standard in this regard.

Having said that, and having thrown the (standard) book at you, I very much understand that this is a real problem in porting real programs.

So, what we have discussed is adding a command line option to the C compiler that would reset the guard bits each time before performing one of the potentially dangerous operations: shifting to the right, and comparisons. Signed 32-bit division is also a potential problem, but Pasi changed the standard libc function in such a way that it protects against the guard bits (the function didn't even get any longer).

As Panu said, adding these checks woukd make the compiler generate larger and slower code, so we have decided to make this optional, activated by a command line option. Lasse is working on it, and we'll let you know when we are ready.

As an aside: unsigned operations on 32-bit integers should work as expected because we've added guard bit clean-up to them already many years ago.

Kind regards,
- Henrik

[victor]

Adding a command line switch sounds like a good option. I do understand it is rather expensive to always add the code to sign-extend the guard bits. However, I still think this optimization (omitting guard bits extension before shifting/comparison) is unsafe and I would recommend that you disable it by default.

For example, if a s_int32 variable is spilled to memory, guard bits are lost. In this case, we might get strange results if some "irrelevant" code that affects variable spilling is changed slightly. From a user's point of view, there is no easy way to tell if variable spilling is necessary or which variable will be spilled. Consider the following example,

Code: Select all

#define USE_STDOUT

#include <stdlib.h>
#include <stdio.h>
#include <vstypes.h>

s_int32 a = 0x80000000;
s_int32 b = 0x00000001;

main(void) {
	s_int32 c, d, e; // c = 0x7fffffff
	c = a - b;
	printf("(a - b) >> 8 = %08lx\n", c >> 8);
	d = a * b;
	e = a / b;
	printf("d = %08lx, e = %08lx\n", d, e);
	printf("(a - b) >> 16 = %08lx\n", c >> 16);
	return 0;
}

Code: Select all

(a - b) >> 8 = ff7fffff
d = 80000000, e = 80000000
(a - b) >> 16 = 00007fff

First, the discrepancy between (a - b) >> 8 and (a - b) >> 16 is very confusing, since we didn't change c in any ways after is was evaluated; Second, if we remove the second printf statement, (a - b) >> 16 becomes ffff7fff since c is not spilled in this case. It could be very frustrating if your code doesn't work as expected after you simply remove some printf's for debugging. Third, if the algorithm used in the compiler for register spilling changes a little bit in a latter version, it could cause compatibility problems (new compiler cannot produce the same results as the old one does).

IMO, this optimization should be enabled if and only if the user knows what exactly the compiler is doing. GCC has some similar options like -funsafe-math-optimizations and -ffast-math.

In the long run, I would suggest adding a new 40bit integer type __int40 (I do understand it is not easy to implement, though); if a user wants to exploit the full 40-bit datapath, he can use this type explicitly. 32-bit variables should act like what they mean, but an optimization flag (or #pragma, or __attribute__ for a variable) is provided for advanced users to enable potentially unsafe optimizations for better performance.

[Henrik]

God news, Victor!

To our great surprise, Lasse was able to clear the guard bits in such a way that had almost no effect in code size or execution time. For instance our VSOS3 kernel, which is 12 KiW in size, grew only by one single word. Granted, it doesn't use too much of the s_int32 datatype, but still.

Because of this, we decided to not add a command line option, but make the improved arithmetics a default in LCC. Later today Lasse will publish a test version of the new compiler to this thread. It will also have another major bug fix that should help with compiling large functions. Watch this space for more news!

Kind regards,
- Henrik

[Lasse]

Hi,

here's the updated compiler. It seems LCC already handled s_int32 comparisons so I only had to update the bit shift operator. Because we allow shifting by a negative value the compiler needs to update the guard bits even when you write a left shift expression like "a<<b". I'm hoping it won't do too many trivially useless updates such as at "a<<4".

Overall there is a small penalty in terms of resulting code efficiency when the s_int32 type is used. However based on a quick benchmark its not too much so I'm guessing we will keep it this way.

Consider the attached compiler a Beta. I have run the usual regression tests but its possible there are some bugs remaining. Any feedback is of course welcome. Also as Henrik mentioned this build includes a couple of other rather significant fixes that will hopefully improve reliability quite a bit.

[victor]

Thank you for all your hard work!

I just tried the beta compiler to compile my project and no immediate problem is found. My project is about 4KiW in size, and the code only increases by 5 Words. I compared the binary produced by the beta compiler to the old binary, and I found 3 occurrences of guard bits updates that can actually be eliminated:

Code: Select all

0x068d	0x32108024	LDX (I2)+1,B0
0x068e	0x32f0c024	LDX (I2)-1,B1
0x068f	0xf40040c3	MV B1,B1
0x0690	0xad160024	ASHL B,A1,B

Code: Select all

0x06c6	0x30108024	LDX (I0)+1,B0
0x06c7	0x2401b541	LOOP A1,0x6d5    /* section decode_chunk + 0x100c3 */
0x06c8	0x30f0c024	LDX (I0)-1,B1
0x06c9	0xf40040c3	MV B1,B1
0x06ca	0xad460024	ASHL B,C0,B

Code: Select all

0x06cd	0x33108024	LDX (I3)+1,B0
0x06ce	0x33f0c024	LDX (I3)-1,B1
0x06cf	0xf40040c3	MV B1,B1
0x06d0	0xad460024	ASHL B,C0,B

Because MV B1, B1 is immediately after a load to B1, they can actually be optimized away. I think we can omit guard bits updates if the higher half of a register has been written and no change has been done to the full register since last write (please correct me if I am wrong). This optimization should be easy to implement within a basic block, and then overhead can be further reduced ...

Victor