Amiga.org
Operating System Specific Discussions => Amiga OS => Amiga OS -- Development => Topic started by: Karlos on June 27, 2009, 10:58:40 PM
-
Hi,
I've pulled out my dusty coding hat and started reviewing years old code I was working on. I have a set of functions that perform bitwise rotate operations using various combinations of ROR/ROL/SWAP:
namespace Machine {
// ...
template<const uint32 N> inline uint32 rotRight32(uint32 val)
{
// N is shift size
if (!(N&31)) {
return val;
}
if (N<9) {
asm("ror.l %1, %0" : "=d"(val) : "I"(N), "0"(val) : "cc");
}
else if (N==16) {
asm("swap %0" : "=d"(val) : "0"(val) : "cc");
}
else if (N>23) {
asm("rol.l %1, %0" : "=d"(val) : "I"(32-N), "0"(val) : "cc");
}
else {
asm("ror.l %1, %0" : "=d"(val) : "d"(N), "0"(val) : "cc");
}
return val;
}
// ...
}
Now, without getting too much into it, the above template function is designed to emit optimal rotate code for compile-time known shift values. Despite the seemingly large chain of if/else, the fact the code is inline and N is constant means the basic assembler is emitted fine, for all values of N from 0-32. It goes without saying that the behaviour for N>32 is not well defined (actually it is the last branch of the code but that might not be the expected behaviour for all N), but as N is a compile time constant, that doesn't matter. If you need a variable rotate, there is a different non-template function.
Unfortunately, you do get a lot of warning diagnostics of the form "asm operand 0 probably doesn't match constraints" when compiling with gcc.
Does anybody know what option there is to suppress this particular warning or just warnings emitted from the use of asm() in general?
-
Is the warning thrown for all values of N or just values outside the range (0..31) of the I constraint? Can you use N%32? EDIT: A value outside 0..31 might throw "error: impossible constraint in `asm'" in addition to the warning, depending on your version of GCC.
I don't know if that particular warning can be suppressed. Does it show up when optimizations are disabled?
-
Is the warning thrown for all values of N or just values outside the range (0..31) of the I constraint? Can you use N%32? EDIT: A value outside 0..31 might throw "error: impossible constraint in `asm'" in addition to the warning, depending on your version of GCC.
I don't know if that particular warning can be suppressed. Does it show up when optimizations are disabled?
All legal values of N produce the warning, impossible values (>32) produce an error from the assembler stage. I have tried limiting N in the code by changing all instances to (N&31) (you can't do N &= 31 first since a constant literal isn't a legal lvalue, of course).
Turning off optimisations would somewhat defeat the purpose of this code. Dead code elimination at the very least is required to ensure the inlining only emits the one branch of the code.
-
Turning off optimisations would somewhat defeat the purpose of this code. Dead code elimination at the very least is required to ensure the inlining only emits the one branch of the code.
I was just thinking GCC might have a bug in the parser when optimizations are enabled. It's been noted on x86 and Alpha. What does the preproccesed output look like for each possible branch?
-
Interestingly, at -O0, the template code doesn't compile at all :lol:
-
I was just thinking GCC might have a bug in the parser when optimizations are enabled. It's been noted on x86 and Alpha. What does the preproccesed output look like for each possible branch?
for the following test code
uint32 x = 0xAABBCCDD, y=0;
y = Machine::rotLeft32<0>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<4>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<8>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<12>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<16>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<20>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<24>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<28>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotLeft32<32>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<0>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<4>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<8>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<12>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<16>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<20>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<24>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<28>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
y = Machine::rotRight32<32>(x);
std::printf("%08X -> %08X\n", (unsigned)x, (unsigned)y);
I get (at -O1 - the least level it works at)
movel #-1430532899,d4
[B] movel d4,sp@- <- y = Machine::rotLeft32<0>(x);[/b]
movel d4,sp@-
pea LC5
lea _printf,a2
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotLeft32<4>(x);
#APP
rol.l #4, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotLeft32<8>(x);
#APP
rol.l #8, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] moveq #12,d3 <- y = Machine::rotLeft32<12>(x);
movel d4,d0
#APP
rol.l d3, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotLeft32<16>(x);
#APP
swap d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] moveq #20,d2 <- y = Machine::rotLeft32<20>(x);
movel d4,d0
#APP
rol.l d2, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotLeft32<24>(x);
#APP
ror.l #8, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotLeft32<28>(x);
#APP
ror.l #4, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addqw #8,sp
[B] movel d4,sp@ <- y = Machine::rotLeft32<32>(x);[/b]
movel d4,sp@-
pea LC5
jbsr a2@
addqw #8,sp
[B] movel d4,sp@ <- y = Machine::rotRight32<0>(x); [/b]
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<4>(x);
#APP
ror.l #4, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<8>(x);
#APP
ror.l #8, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<12>(x);
#APP
ror.l d3, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<16>(x);
#APP
swap d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<20>(x);
#APP
ror.l d2, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<24>(x);
#APP
rol.l #8, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
[B] movel d4,d0 <- y = Machine::rotRight32<28>(x);
#APP
rol.l #4, d0
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addqw #8,sp
[B] movel d4,sp@ <- y = Machine::rotRight32<32>(x);[/b]
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
-
I should point out it's always bugged me that C never had operators for integer rotate :lol:
It's pretty obvious that gcc is fretting because the value for N is clearly capable of exceeding the limit for the I (immediate) constraint, though the template code is designed to minimize that. If N is outside the range, this is considered a programming error and I'm happy for it to fail compilation.
-
namespace Machine {
// ...
template<const uint32 N> inline uint32 rotRight32(uint32 val)
{
// N is shift size
if (!(N&31)) {
return val;
}
if (N<9) {
asm("ror.l %1, %0" : "=d"(val) : "I"(N), "0"(val) : "cc");
}
else if (N==16) {
asm("swap %0" : "=d"(val) : "0"(val) : "cc");
}
else if (N>23) {
asm("rol.l %1, %0" : "=d"(val) : "I"(32-N), "0"(val) : "cc");
}
else {
[b]asm("ror.l %1, %0" : "=d"(val) : "d"(N), "0"(val) : "cc");[/b]
}
return val;
}
// ...
}
Shouldn't the bold line be the same as the N<9 branch, or is your intent to use a data register if N<9 || N>23? If so, don't you need to move.l the value first?
-
Shouldn't the bold line be the same as the N<9 branch, or is your intent to use a data register if N<9 || N>23? If so, don't you need to move.l the value first?
Yes, register use is intended for that final operation (which is not for N<9 | N>23 but for the intermediate ranges between 8 and 16 bit either direction) since it's probably faster than a pair of rotates. Moving the value to the register is performed automatically by the compiler thanks to the "d" constraint. See the output asm in my earlier post. The N = 9-15 and N = 17-23 are handled by a ROX.l dX, DY type operation, everything else is done with immediate rotates (or a swap in the N=16 case)
-
I should point out it's always bugged me that C never had operators for integer rotate :lol:
Yeah, I think it's a common gripe. A lot of compilers implement rotation as intrinsic functions.
If N is outside the range, this is considered a programming error and I'm happy for it to fail compilation.
Good call.
-
Yeah, I think it's a common gripe. A lot of compilers implement rotation as intrinsic functions.
Good call.
Anyway, to cut the story short, as a construct it works just fine (save the -O0 case which needs a spot of investigation, not that I ever use -O0, even when debugging):
AABBCCDD -> AABBCCDD
AABBCCDD -> ABBCCDDA
AABBCCDD -> BBCCDDAA
AABBCCDD -> BCCDDAAB
AABBCCDD -> CCDDAABB
AABBCCDD -> CDDAABBC
AABBCCDD -> DDAABBCC
AABBCCDD -> DAABBCCD
AABBCCDD -> AABBCCDD
AABBCCDD -> AABBCCDD
AABBCCDD -> DAABBCCD
AABBCCDD -> DDAABBCC
AABBCCDD -> CDDAABBC
AABBCCDD -> CCDDAABB
AABBCCDD -> BCCDDAAB
AABBCCDD -> BBCCDDAA
AABBCCDD -> ABBCCDDA
AABBCCDD -> AABBCCDD
...but the warnings are a PITA. As the code is in a header and not a translation unit, it isn't as if I can just disable warnings for the one file.
-
Which version of gcc are you using? Native or cross?
You could also specialize your templates a bit to perhaps make things a bit clearer:
template <uint32 N> inline uint32 rotRight32(uint32 val)
{
if (N%32 < 9) {
asm("ror.l %1, %0;" : "=d"(val) : "I"(N%32), "0"(val) : "cc");
}
else if (N%32 > 23) {
asm("rol.l %1, %0;" : "=d"(val) : "I"(32-(N%32)), "0"(val) : "cc");
}
else {
asm("ror.l %1, %0;" : "=d"(val) : "d"(N%32), "0"(val) : "cc");
}
return val;
}
template <> inline uint32 rotRight32<0>(uint32 val)
{
return val;
}
template <> inline uint32 rotRight32<16>(uint32 val)
{
asm("swap %0;" : "=d"(val) : "0"(val) : "cc");
return val;
}
EDIT: For extra credit, let's do , too, i.e. rotRight32(-1) rotates left 1 bit. You could then generalize it as rotate(), where the sign of the operand determines the direction. Anyway....
-
(which is not for N<9 | N>23 but for the intermediate ranges between 8 and 16 bit either direction)
Yeah, I'm not doing so well with the ranges today.
-
Which version of gcc are you using? Native or cross?
Native and pretty ancient (2.95.x)
You could also specialize your templates a bit to perhaps make things a bit clearer
Yeah, that certainly looks better but I wasn't about to push that old version to the point of template specialisations. It just about does template functions as it is ;)
BTW, I did actually try with a modulus applied to N as per your example above but it didn't really make a difference to the warning diagnostic.
-
Yeah, I'm not doing so well with the ranges today.
I'm just happy to have some miggy coding time at all. Perverting C++ (in ANSI mode) with inline assembler always felt good :lol: If you think this is bad, you should see the divide by zero exception trick ;)
All I need now is to find an -fno-worry-about-asm-immediate-sizes option...
-
EDIT: For extra credit, let's do , too, i.e. rotRight32(-1) rotates left 1 bit. You could then generalize it as rotate(), where the sign of the operand determines the direction. Anyway....
LOL, not exactly in keeping with operators <> though, eh?
-
Shouldn't you do something like this ???
__inline static unsigned long SWAP32(unsigned long a )
{
unsigned long b;
__asm__ ("lwbrx %0,0,%1"
:"=r"(b)
:"r"(&a), "m"(a));
return b;
}
x303 :D :D :D
-
Couldn't you do something like this ???
__inline static unsigned long SWAP32(unsigned long a )
{
unsigned long b;
__asm__ ("lwbrx %0,0,%1"
:"=r"(b)
:"r"(&a), "m"(a));
return b;
}
x303 :D :D :D
For PowerPC, yeah, this is for M68K :)
BTW, these aren't byteswap functions, they are bitwise rotate functions. I have inlined asm for byteswapping anyway ;)
-
@x303
On PowerPC, yes, but Karlos is talking 680x0.
-
Try:
__inline static unsigned long SWAP32(unsigned long a)
{
__asm__ ("rol.w #8,%0;swap %0;rol.w #8,%0"
:"=d"(a):"0"(a));
return(a);
}
x303 :D :D :D
-
That's still not a rotation function. ;-) I don't think he's trying to do endian conversions.
-
Try:
__inline static unsigned long SWAP32(unsigned long a)
{
__asm__ ("rol.w #8,%0;swap %0;rol.w #8,%0"
:"=d"(a):"0"(a));
return(a);
}
x303 :D :D :D
Sorry, you're missing the point. It isn't a byteswapping function, it's just a vanilla rotate. My 32-bit byteswap function looks pretty much like yours:
namespace Machine {
// ...
inline uint32 swap32(uint32 val)
{
asm(
"rol.w #8, %0\n\t"
"swap %0\n\t"
"rol.w #8, %0"
: "=d"(val)
: "0"(val)
: "cc"
);
return val;
}
-
Looks like gcc 2.95 falls through to a default warning("asm operand %d probably doesn't match constraints", i) for constraints that it doesn't know how to test.
-
Looks like gcc 2.95 falls through to a default warning("asm operand %d probably doesn't match constraints", i) for constraints that it doesn't know how to test.
Yeah, they were hedging their bets there, eh? I need to install a higher version or use a cross compiler. 2.95 has a whole host of issues I have workarounds for that aren't actually needed on higher versions anyway.
-
And here's the snippet from gcc 2.95.3's recog.c in asm_operand_ok():
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
/* For best results, our caller should have given us the
proper matching constraint, but we can't actually fail
the check if they didn't. Indicate that results are
inconclusive. */
result = -1;
break;
So, it automatically falls through on matching constraints. What happens if you change "0" to "d0" to tell it operand 0 goes into a data register? EDIT: The point being that matched input operands aren't checked against the constraints previously specified for the output operand.
-
And here's the snippet from gcc 2.95.3's recog.c in asm_operand_ok():
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
/* For best results, our caller should have given us the
proper matching constraint, but we can't actually fail
the check if they didn't. Indicate that results are
inconclusive. */
result = -1;
break;
So, it automatically falls through on matching constraints. What happens if you change "0" to "d0" to tell it operand 0 goes into a data register? EDIT: The point being that matched input operands aren't checked against the constraints previously specified for the output operand.
Well. I'll have a look but I was under the impression the "0" was the correct constraint here:
asm("rol.l %1, %0" : "=d"(val) : "I"(N), "0"(val) : "cc");
since you want the compiler to keep the output in the same register as the first input. Compare the above with the dynamic version:
inline uint32 rotRight32(uint32 bits, uint32 val)
{
asm("ror.l %1, %0" : "=d"(val) : "d"(bits), "0"(val) : "cc");
return val;
}
Using "d" rather than "d0" allows the compiler to choose which registers to use whenever the function is inlined. I figured this would be a lot better than forcing the use of any specific data register.
-
As I expected, changing "0" to "d0", breaks, since there's nothing forcing the input into d0 in the first place:
movel #-1430532899,d4 <- 0xAABBCCDD
[B] movel d4,sp@- <- no rotate done for zero bits, this is fine[/B]
movel d4,sp@-
pea LC5
lea _printf,a2
jbsr a2@
addw #12,sp
[B]#APP
rol.l #4, d0 <- where is d0 initialised?
#NO_APP[/B]
movel d0,sp@-
movel d4,sp@-
pea LC5
jbsr a2@
addw #12,sp
Whatever was already in d0 gets shifted and the compiler has to work around ensuring d0 is preserved around my asm() calls, despite the fact it never initialises it with the test data (which it decided to put in d4 here).
-
@trev
Amazingly, I just tried the specialization route for the 0/16 case and it worked. When I originally worked on this I distinctly remember template specializations in general causing problems.
That said, I've gone back to the single function(s) and just made it handle all values of N:
template<const uint32 N> inline uint32 rotRight32(uint32 val)
{
if (N&31) {
// only rotate when modulus 32 > 0
if ((N&31) < 9) {
asm("ror.l %1, %0" : "=d"(val) : "I"(N&31), "0"(val) : "cc");
}
else if ((N&31)==16) {
asm("swap %0" : "=d"(val) : "0"(val) : "cc");
}
else if ((N&31)>23) {
// use opposite rotate for N > 23
asm("rol.l %1, %0" : "=d"(val) : "I"(32-(N&31)), "0"(val) : "cc");
}
else {
// use register rotate for all intermediate sizes
asm("ror.l %1, %0" : "=d"(val) : "d"(N&31), "0"(val) : "cc");
}
}
return val;
}
-
As I expected, changing "0" to "d0", breaks, since there's nothing forcing the input into d0 in the first place:
Hmmm, well the intent wasn't to tell it to use d0, but rather that it should use the data register that matches operand 0. (Incidentally, "r0" works correctly on x86, but there is, of course, no r0 register to work around.) Whitespace should be ignored, so a constraint of "d0" might produce the correct result and get rid of the warning; otherwise, I guess the warning is there to stay.
-
That said, I've gone back to the single function(s) and just made it handle all values of N:
I think your solution is best anyway, as values equivalent to 0 and 16 won't be reduced by the specialized templates, and you won't get the expected result.
I also think your idea of letting N < 0 (if signed inputs are allowed) and N > 31 fail at compile time is a good idea if you're worried about source typos.
For fun, though, I still think a general purpose rotation template is a cool idea. ;-) It's too bad C++ won't let you create custom operators without using macros or some other magic. You could throw in <<<, >>>, ^<<, ^>>, or whatever you want. Actually, would it be that difficult to add those to gcc? I don't know. Nothing wrong with non-standard extensions as long as they're well documented.
-
IIRC, d0-d7 and a0-a7 are understood as register specifications for M68K backend with asm(). I'll see if "d 0" works.
To be fair, I can live with the warning as it always seems to generate the correct code. It was just a bit annoying.
-
I think your solution is best anyway, as values equivalent to 0 and 16 won't be reduced by the specialized templates, and you won't get the expected result.
I also think your idea of letting N < 0 (if signed inputs are allowed) and N > 31 fail at compile time is a good idea if you're worried about source typos.
Actually, the revised version essentially treats everything as modulo . I could remove it :)
For fun, though, I still think a general purpose rotation template is a cool idea. ;-)
Feel free to use the code for inspiration :lol: It wouldn't be difficult to make it take a signed shift. Don't forget to throw in a dynamic version (for variable shifts too), though here checking for the sign of the shift exposes the runtime weakness in the plan. The check would probably take more cycles than the operation performed.
It's too bad C++ won't let you create custom operators without using macros or some other magic. You could throw in <<<, >>>, ^<<, ^>>, or whatever you want. Actually, would it be that difficult to add those to gcc? I don't know. Nothing wrong with non-standard extensions as long as they're well documented.
Well, inventing new operators has a lot of hidden traps. You only have to look at the post/pre increment/decrement operators to see how gnarly that could get.
The thing is, rotate is a commonly supported CPU operation. I can't see why C wouldn't have an operator for it originally.
-
Looking at Microsoft's implementation, 8-bit and 16-bit rotations are intrinsics, and 32-bit and 64-bit rotations are functions. The functions are implemented using the traditional bitwise shift and bitwise or combination.
16-bit rotations are actually implemented using 32-bit registers, but the result is truncated:
x86
volatile unsigned char a = _rotl8(1, 1);
013213DE mov al,1
013213E0 rol al,1
013213E2 mov byte ptr [a],al
volatile unsigned short b = _rotl16(1, 1);
013213E5 mov eax,1
013213EA rol ax,1
013213ED mov word ptr [b],ax
volatile unsigned c = _rotl(1, 1);
013213F1 push 1
013213F3 push 1
013213F5 call @ILT+155(__rotl) (13210A0h)
013213FA add esp,8
013213FD mov dword ptr [c],eax
volatile unsigned long d = _lrotl(1, 1);
01321400 push 1
01321402 push 1
01321404 call @ILT+65(__lrotl) (1321046h)
01321409 add esp,8
0132140C mov dword ptr [d],eax
volatile unsigned __int64 e = _rotl64(1, 1);
0132140F push 1
01321411 push 0
01321413 push 1
01321415 call @ILT+280(__rotl64) (132111Dh)
0132141A add esp,0Ch
0132141D mov dword ptr [e],eax
01321420 mov dword ptr [ebp-38h],edx
x64
volatile unsigned char a = _rotl8(1, 1);
000000013FBF102A mov al,1
000000013FBF102C rol al,1
000000013FBF102E mov byte ptr [a],al
volatile unsigned short b = _rotl16(1, 1);
000000013FBF1032 mov ax,1
000000013FBF1036 rol ax,1
000000013FBF1039 mov word ptr [b],ax
volatile unsigned c = _rotl(1, 1);
000000013FBF103E mov edx,1
000000013FBF1043 mov ecx,1
000000013FBF1048 call _rotl (13FBF10A8h)
000000013FBF104D mov dword ptr [c],eax
volatile unsigned long d = _lrotl(1, 1);
000000013FBF1051 mov edx,1
000000013FBF1056 mov ecx,1
000000013FBF105B call _lrotl (13FBF10A2h)
000000013FBF1060 mov dword ptr [d],eax
volatile unsigned __int64 e = _rotl64(1, 1);
000000013FBF1064 mov edx,1
000000013FBF1069 mov ecx,1
000000013FBF106E call _rotl64 (13FBF109Ch)
000000013FBF1073 mov qword ptr [e],rax
The good news--for Visual C++, anyway--is that the shift-or combination is correctly optimized into a rotate. Microsoft reduces with N&31 as well:
___rotl PROC ; COMDAT
; 8 : shift &= 0x1f;
; 9 : val = (val>>(0x20 - shift)) | (val << shift);
00000 b8 01 00 00 00 mov eax, 1
00005 d1 c0 rol eax, 1
; 10 : return val;
; 11 : }
00007 c3 ret 0
___rotl ENDP
Anyhow, just food for thought. I know GCC's m68k optimizer needs work, even in current versions.
-
Thanks to the power of templated inline assembler, it doesn't matter how bad the m68k optimizer is, you've basically taken matters into your own hands :lol:
The things we do for cycles, eh?
-
Thanks to the power of templated inline assembler, it doesn't matter how bad the m68k optimizer is, you've basically taken matters into your own hands :lol:
The things we do for cycles, eh?
Too true, but our compilers should be smart enough to know a rotation when they see it. I've got a marathon gcc-4.4.0 m68k build going at home. Taking hours--on a Core i7. That's what I get for not limiting newlib and g++ to m680x0 CPUs. (Plus, shouldn't we have schnazzy parallel compilers by now? Even a loopback distcc would be nice.) So, we'll see if newer GCCs are any better at optimizing rotatations.
EDIT: Oh, I guess we have 'make -j n', but it's not very robust.
-
I use make -j=4 on my quad core and never had any problems with it :)
-edit-
So, we'll see if newer GCCs are any better at optimizing rotatations.
You're building gcc 4.4 for an m68k backend just to check this? That's hardcore :D
Blimey, time to hit the sack :-/
-
You're building gcc 4.4 for an m68k backend just to check this? That's hardcore :D
Hardcore boredom, maybe. ;-) gcc 4.4.0 is definitely smarter than gcc 2.95.3:
intput:
static inline unsigned _rotl(unsigned val, int shift)
{
shift &= 0x1f;
val = (val>>(0x20 - shift)) | (val << shift);
return val;
}
int main(void)
{
volatile unsigned val = 1;
volatile unsigned a = _rotl(val, 1);
return 0;
}
output:
00000000 :
0: 4e56 fff8 linkw %fp,#-8
4: 7001 moveq #1,%d0
6: 2d40 fffc movel %d0,%fp@(-4)
a: 202e fffc movel %fp@(-4),%d0
e: 721f moveq #31,%d1
[b]10: e2b8 rorl %d1,%d0[/b]
12: 2d40 fff8 movel %d0,%fp@(-8)
16: 4280 clrl %d0
18: 4e5e unlk %fp
1a: 4e75 rts
It's even decided that a register based rotate right is faster than an immediate rotate left, I guess. Or maybe not. I can't get it to produce a rotate left. I guess gcc isn't an ambiturner.
In this case, at least, the optimizer does OK. I don't know anything about gcc internals, but maybe the optimization occurs at the RTL level based on the capabilities of the underlying architecture. That would mean an optimization should apply regardless of the architecture, as long as the architecture supports it.
But why doesn't it rotate left? The execution times are the same for both. Correction: The execution times are the same if the bit count is the same: 8+2n for register operand, 12+2n for immediate operand. What am I missing?
I compiled with an m68k-elf target, but now the m68k-amigaos gods are calling. I know there are some gcc 4.x.x builds out there somewhere, but I haven't used one. I'd also like to see ixemul and libnix go away and be replaced with newlib or another current library.
If necessary, one could even target specific releases, e.g. m68k-*-amigaos1.2, m68k-*-amigaos2.0, m68k-*-amigaos3.0, et al. It depends on how tightly coupled the tool chain is to the target environment. The main differences from a tool chain perspective, though, should be in the hunks supported. Everything else could be handled as it is today, and newlib, crt0.s, and amiga.lib could be written to run optimally on arbitrary releases. Having that magic at compile time, though, would result in much tighter binaries.
-
It's even decided that a register based rotate right is faster than an immediate rotate left, I guess. Or maybe not. I can't get it to produce a rotate left. I guess gcc isn't an ambiturner.
Hmm, unusual. I'm pretty sure an immediate left shift of 1 place ought to be faster than a register based shift right of 31 since you spare yourself the cost of the additional move.l #31, d1. It also reduces register pressure too, which could make all the difference in real code.
Probably in the test code here there's no need for it to do that.
-edit-
Incidentally, you might want to compile that test code with -fomit-frame-pointer ;)
-
EDIT: Oh, I guess we have 'make -j n', but it's not very robust.
if [ -a /proc/cpuinfo ]; then
export CONCURRENCY_LEVEL=$(($(grep -c processor /proc/cpuinfo) * 2 + 1))
export MAKEOPTS="-j${CONCURRENCY_LEVEL}"
fiWhy wouldn't it be robust?
-
The main differences from a tool chain perspective, though, should be in the hunks supported. Everything else could be handled as it is today, and newlib, crt0.s, and amiga.lib could be written to run optimally on arbitrary releases. Having that magic at compile time, though, would result in much tighter binaries.
Well, some 32bit relocs could be made 16bit, that doesn't account for much in most binaries.
-
if [ -a /proc/cpuinfo ]; then
export CONCURRENCY_LEVEL=$(($(grep -c processor /proc/cpuinfo) * 2 + 1))
export MAKEOPTS="-j${CONCURRENCY_LEVEL}"
fi
Why wouldn't it be robust?
Perhaps the Makefiles are subtly flawed? There could be bits that have to be compiled before others that may not be guaranteed with concurrent jobs?
Just guessing here.
-
Perhaps the Makefiles are subtly flawed? There could be bits that have to be compiled before others that may not be guaranteed with concurrent jobs?
Just guessing here.
Well that's not it. The concurrent jobs are only used for things that can be concurrent. Obviously make cannot change the order of commands being executed, that'd never work.
-
Well that's not it. The concurrent jobs are only used for things that can be concurrent. Obviously make cannot change the order of commands being executed, that'd never work.
You have to trust that your target makefile is essentially thread-safe, i.e. all dependencies are properly documented for synchronization, no race conditions exist in similar commands used by different rules, etc.
-
Hmm, unusual. I'm pretty sure an immediate left shift of 1 place ought to be faster than a register based shift right of 31 since you spare yourself the cost of the additional move.l #31, d1. It also reduces register pressure too, which could make all the difference in real code.
Probably in the test code here there's no need for it to do that.
Yeah, I'm really not sure why, since ror.l #n,Dn and ror.l Dx,Dn execute in the same number of cycles assuming n == Dx. Barring outside influences, the only reason to use a register is for a shift >8 or <24 (>8 in the opposite direction), as you've done in your template. Right?
Incidentally, you might want to compile that test code with -fomit-frame-pointer ;)
Well, sure, but it's not actually going to run anywhere and it doesn't change the output of the test itself. :-P
-
You have to trust that your target makefile is essentially thread-safe, i.e. all dependencies are properly documented for synchronization, no race conditions exist in similar commands used by different rules, etc.
That's basically what I was trying to suggest. I've not built anything as large as gcc and the toolchain with multiple concurrent jobs, but I can imagine concurrency issues can exist.
-edit-
Yeah, I'm really not sure why, since ror.l #n,Dn and ror.l Dx,Dn execute in the same number of cycles assuming n == Dx. Barring outside influences, the only reason to use a register is for a shift >8 or <24 (>8 in the opposite direction), as you've done in your template. Right?
Well, you could probably do it with two successive rotates, but I figured that the register method might be better than a pair of rotates. Having said that, I didn't test the latter. You'd swap a move for a rotate but you'd gain a free register overall.
I'll have to look into that.
-
Well, you could probably do it with two successive rotates, but I figured that the register method might be better than a pair of rotates. Having said that, I didn't test the latter. You'd swap a move for a rotate but you'd gain a free register overall.
I'm leaning towards trusting the compiler. One can always hand optimize code, but writing specializations for all possible cases? Tedium. ;-)
-
I'm leaning towards trusting the compiler. One can always hand optimize code, but writing specializations for all possible cases? Tedium. ;-)
The fact is, I needed rotate operations, so I wrote the functions (in pure C++) for 8/16 and 32-bit rotate.
After analysing the output (from older gcc) it was clear that the emitted code wasn't very good. So, I made the inline assembler implementations you saw one of in this thread. There's no question they produce better code now than when they were using shifts and ors ;)
Of course, if I use a better compiler, there's nothing stopping me turning off the inline assembler versions. It's just a compilation directive to use the asm tuned or normal C ones.
-
After analysing the output (from older gcc) it was clear that the emitted code wasn't very good. So, I made the inline assembler implementations you saw one of in this thread. There's no question they produce better code now than when they were using shifts and ors ;)
Oh, for sure. I was just thinking that for the newer compiler, the optimizer should be much better at dynamically optimizing for all possible scenarios than I would be at hand coding them. I'm no amigaksi, after all.
-
Oh, for sure. I was just thinking that for the newer compiler, the optimizer should be much better at dynamically optimizing for all possible scenarios than I would be at hand coding them. I'm no amigaksi, after all.
ROFL (+1)
Tell you what. Seeing as you've compiled a working 4.4 compiler, we could try some synthetic benchmarks. My template rotate versus a standard implementation based on shifting and or'ing that the compiler is left to optimize.
I'd actually be quite interested in the results :)
-
ROFL (+1)
;-)
Tell you what. Seeing as you've compiled a working 4.4 compiler, we could try some synthetic benchmarks. My template rotate versus a standard implementation based on shifting and or'ing that the compiler is left to optimize.
I'd actually be quite interested in the results :)
Well, it's m68k-elf with no real back end. We could count cycles in a simulator, I suppose. :-)
Also, fun with generic templates. Here's an x86 rotate that reduces positive and negative shift values to a positive shift (assuming +right, -left), and "optimizes" based on the width of the shift:
template <signed N> inline unsigned rotate(unsigned val)
{
if ((32-(-(N%32)))%32 != 0) {
if ((32-(-(N%32)))%32 < 16) {
asm("rorl %1, %0;" : "=r"(val) : "I"((32-(-(N%32)))%32), "0"(val) : "cc");
}
else {
asm("roll %1, %0;" : "=r"(val) : "I"(32-((32-(-(N%32)))%32)), "0"(val) : "cc");
}
}
return val;
}
(I haven't looked at the execution times, so the optimization might not even make sense. But that wasn't point, regardless.)
But guess what! N==0 (or any value that reduces to 0) throws this:
warning: asm operand 1 probably doesn't match constraints
Bugger! It still compiles, still runs, and doesn't leave any dead code. Not sure how to get rid of the warning, though, if it's parsing code it shouldn't be parsing after templatization. Template misuse, maybe?
-
But guess what! N==0 (or any value that reduces to 0) throws this:
warning: asm operand 1 probably doesn't match constraints
Bugger! It still compiles, still runs, and doesn't leave any dead code. Not sure how to get rid of the warning, though, if it's parsing code it shouldn't be parsing after templatization. Template misuse, maybe?
Boo! So you basically get the same warning I started this whole thread in aid of? :roflmao:
It's only taken us 50 posts to come full circle :D
-edit-
Template misuse? Are you suggesting that the use of high level metaprogramming devices like templates to emit conditionally selected hand generated code directly for the assembler stage might be outside the original scope? ;)
It isn't quite as cheeky as the processor trap -> C++ exception throw that I used. Frankly, I'm amazed that bugger worked at all. Inside the (asm) m68k trap handler (which you install into your exec Task structure), you poke the stack frame to change the return address to a function which does nothing other than throw an exception of a type suitably mapped to the nature of the trap. Saves having to check for divide by zero when you can just put a try/catch block around a bit of code and trap ZeroDivide ;)
-
Well, it's m68k-elf with no real back end. We could count cycles in a simulator, I suppose. :-)
Or I could write the function to be benchmarked, you can compile it and post the assembler output of the function and I'll put that source back into a test project?
-
Or I could write the function to be benchmarked, you can compile it and post the assembler output of the function and I'll put that source back into a test project?
Or that. :-P
-
Or that. :-P
It will have to wait though, I have a date with the shower then bed. I'm wiped.
-
Boo! So you basically get the same warning I started this whole thread in aid of? :roflmao:
It's only taken us 50 posts to come full circle :D
I think we're safe as long as no one invokes Sir Elton.
It isn't quite as cheeky as the processor trap -> C++ exception throw that I used. Frankly, I'm amazed that bugger worked at all. Inside the (asm) m68k trap handler (which you install into your exec Task structure), you poke the stack frame to change the return address to a function which does nothing other than throw an exception of a type suitably mapped to the nature of the trap. Saves having to check for divide by zero when you can just put a try/catch block around a bit of code and trap ZeroDivide ;)
Actually, that sounds like a quite valid use. Within the design of the operating system even. (Well, sort of. But manipulating stack frames is kind of at the core of exception handling, isn't it?)
-
Actually, that sounds like a quite valid use. Within the design of the operating system even. (Well, sort of. But manipulating stack frames is kind of at the core of exception handling, isn't it?)
Well, yes, but not quite like this. Normally C++ exceptions operate entirely in userland and unwind the stack of the process they were fired in (well, if you omit threadsafe.lib in old gcc, watch the fun when that assertion fails).
Here, we are actually in the supervisor state, altering the saved stack frame of the thread that performed the illegal op and altering the return address such that when the trap is complete, it returns to a completely different location. Right into our code that throws the exception.
The old thread about that is on here somewhere. Amazingly it really does work very well and I built it into my codebase. I'm currently figuring out how to accomplish the same thing inside a signal handler under posix, but it always seems as if the exception occurred inside main() rather than where it really happened.
-edit-
http://www.amiga.org/forums/showthread.php?t=25181 (http://www.amiga.org/forums/showthread.php?t=25181) here
-
Were you ever able to simulate a null pointer exception, short of wrapping all pointers in a class and overloading the indirection operator?
-
I suspect your template will be faster, but only because the optimizer isn't doing rol's:
template <signed N> static inline unsigned rotate(unsigned val)
{
if ((32-(-(N%32)))%32 != 0) {
if ((32-(-(N%32)))%32 < 9) {
asm("rorl %1, %0;" : "=d"(val) : "I"((32-(-(N%32)))%32), "0"(val) : "cc");
}
else if ((32-(-(N%32)))%32 > 23) {
asm("roll %1, %0;" : "=d"(val) : "I"(32-((32-(-(N%32)))%32)), "0"(val) : "cc");
}
else if ((32-(-(N%32)))%32 == 16) {
asm("swap %0;" : "=d"(val) : "0"(val) : "cc");
}
else {
asm("rorl %1, %0;" : "=d"(val) : "d"((32-(-(N%32)))%32), "0"(val) : "cc");
}
}
return val;
}
static inline unsigned _rotl(unsigned val, int shift)
{
shift &= 0x1f;
val = (val>>(0x20 - shift)) | (val << shift);
return val;
}
static inline unsigned _rotr(unsigned val, int shift)
{
shift &= 0x1f;
val = (val<<(0x20 - shift)) | (val >> shift);
return val;
}
int main(void)
{
volatile unsigned x = 1;
volatile unsigned a = _rotl(x, 1);
volatile unsigned b = _rotr(x, 1);
volatile unsigned c = rotate<-1>(x);
volatile unsigned d = rotate<1>(x);
return 0;
}
/*
00000000 <main>:
0: 4e56 ffec linkw %fp,#-20
volatile unsigned x = 1;
4: 7001 moveq #1,%d0
volatile unsigned a = _rotl(x, 1);
6: 2d40 fffc movel %d0,%fp@(-4)
a: 202e fffc movel %fp@(-4),%d0
e: 721f moveq #31,%d1
10: e2b8 rorl %d1,%d0
12: 2d40 fff8 movel %d0,%fp@(-8)
volatile unsigned b = _rotr(x, 1);
16: 202e fffc movel %fp@(-4),%d0
1a: e298 rorl #1,%d0
1c: 2d40 fff4 movel %d0,%fp@(-12)
volatile unsigned c = rotate<-1>(x);
20: 202e fffc movel %fp@(-4),%d0
24: e398 roll #1,%d0
26: 2d40 fff0 movel %d0,%fp@(-16)
volatile unsigned d = rotate<1>(x);
2a: 202e fffc movel %fp@(-4),%d0
2e: e298 rorl #1,%d0
30: 2d40 ffec movel %d0,%fp@(-20)
return 0;
34: 4280 clrl %d0
36: 4e5e unlk %fp
38: 4e75 rts
*/
I don't know anything about how the optimizer works, really, so I don't know why it's always opting for one solution over another.
-
Were you ever able to simulate a null pointer exception, short of wrapping all pointers in a class and overloading the indirection operator?
No. Well, I didn't try too hard as I was never able to get mmu.library working on my system. Every time I'd install it, it would drop to bits.
-
I suspect your template will be faster, but only because the optimizer isn't doing rol's:
Well, that and the fact it doesn't require an additional register to hold the shift value for many of the sizes. Saving a register gives the optimizer more breathing space in 'real' code.
I don't know anything about how the optimizer works, really, so I don't know why it's always opting for one solution over another.
It could be that the RTL model only supports rotation in one direction? Just a guess.
-
I've been digging into GCC's SSA trees, but it's getting late here. Maybe I'll have a moment of clarity tomorrow and actually understand how they work. :-P
-
Well, that and the fact it doesn't require an additional register to hold the shift value for many of the sizes. Saving a register gives the optimizer more breathing space in 'real' code.
And I suspect that GCC will reduce to constant values anything that isn't defined as or determined to be volatile.
-
Well, the day has just started here and I have to head off for work in 2 minutes :)
-
And I suspect that GCC will reduce to constant values anything that isn't defined as or determined to be volatile.
Not so sure it can do that inside an asm() though.
-
In gcc 3.4.4, the traditional shift-or expressions are reduced to rotates while the SSA tree is being built, during constant folding and arithmetic reduction, before tree optimization and RTL generation occur. gcc 4.4.0 is probably similar. (I'm on a system without gcc 4.4.0 at the moment.) No idea what gcc 2.95.3 does yet.
EDIT: Hope to have an understanding later today of why gcc 4.4.0 m68k reduces to a shifted right rotate instead of a left rotate. None of this helps gcc 2.95.3, of course, but it's fun nonetheless.
EDIT2: Constant folding and arithmetic reduction should be done prior to RTL generation in gcc 2.95.3 as well.
-
gcc 2.95.3 isn't that bad, actually. For the most part, it optimizes in the same way your template would.
static inline unsigned _rotl(unsigned val, int shift)
{
shift &= 0x1f;
val = (val>>(0x20 - shift)) | (val << shift);
return val;
}
static inline unsigned _rotr(unsigned val, int shift)
{
shift &= 0x1f;
val = (val<<(0x20 - shift)) | (val >> shift);
return val;
}
int main()
{
volatile unsigned x = 1;
volatile unsigned c = _rotl(x, 64);
volatile unsigned d = _rotl(x, 48);
volatile unsigned e = _rotl(x, 41);
volatile unsigned f = _rotl(x, 36);
volatile unsigned g = _rotl(x, 32);
volatile unsigned h = _rotl(x, 24);
volatile unsigned i = _rotl(x, 16);
volatile unsigned j = _rotl(x, 9);
volatile unsigned k = _rotl(x, 4);
volatile unsigned l = _rotl(x, 0);
volatile unsigned m = _rotr(x, 0);
volatile unsigned n = _rotr(x, 4);
volatile unsigned o = _rotr(x, 9);
volatile unsigned p = _rotr(x, 16);
volatile unsigned q = _rotr(x, 24);
volatile unsigned r = _rotr(x, 32);
volatile unsigned s = _rotr(x, 36);
volatile unsigned t = _rotr(x, 41);
volatile unsigned u = _rotr(x, 48);
volatile unsigned v = _rotr(x, 64);
return 0;
}
00000000 :
0: 4e56 ffac linkw %fp,#-84
4: 4eb9 0000 0000 jsr 0
volatile unsigned x = 1;
a: 7001 moveq #1,%d0
c: 2d40 fffc movel %d0,%fp@(-4)
volatile unsigned c = _rotl(x, 64);
10: 202e fffc movel %fp@(-4),%d0
14: 2d40 fff8 movel %d0,%fp@(-8)
volatile unsigned d = _rotl(x, 48);
18: 202e fffc movel %fp@(-4),%d0
1c: 4840 swap %d0
1e: 2d40 fff4 movel %d0,%fp@(-12)
volatile unsigned e = _rotl(x, 41);
22: 202e fffc movel %fp@(-4),%d0
26: 7209 moveq #9,%d1
28: e3b8 roll %d1,%d0
2a: 2d40 fff0 movel %d0,%fp@(-16)
volatile unsigned f = _rotl(x, 36);
2e: 202e fffc movel %fp@(-4),%d0
32: e998 roll #4,%d0
34: 2d40 ffec movel %d0,%fp@(-20)
volatile unsigned g = _rotl(x, 32);
38: 202e fffc movel %fp@(-4),%d0
3c: 2d40 ffe8 movel %d0,%fp@(-24)
volatile unsigned h = _rotl(x, 24);
40: 202e fffc movel %fp@(-4),%d0
44: e098 rorl #8,%d0
46: 2d40 ffe4 movel %d0,%fp@(-28)
volatile unsigned i = _rotl(x, 16);
4a: 202e fffc movel %fp@(-4),%d0
4e: 4840 swap %d0
50: 2d40 ffe0 movel %d0,%fp@(-32)
volatile unsigned j = _rotl(x, 9);
54: 202e fffc movel %fp@(-4),%d0
58: e3b8 roll %d1,%d0
5a: 2d40 ffdc movel %d0,%fp@(-36)
volatile unsigned k = _rotl(x, 4);
5e: 202e fffc movel %fp@(-4),%d0
62: e998 roll #4,%d0
64: 2d40 ffd8 movel %d0,%fp@(-40)
volatile unsigned l = _rotl(x, 0);
68: 202e fffc movel %fp@(-4),%d0
6c: 2d40 ffd4 movel %d0,%fp@(-44)
volatile unsigned m = _rotr(x, 0);
70: 202e fffc movel %fp@(-4),%d0
74: 2d40 ffd0 movel %d0,%fp@(-48)
volatile unsigned n = _rotr(x, 4);
78: 202e fffc movel %fp@(-4),%d0
7c: e898 rorl #4,%d0
7e: 2d40 ffcc movel %d0,%fp@(-52)
volatile unsigned o = _rotr(x, 9);
82: 202e fffc movel %fp@(-4),%d0
86: e2b8 rorl %d1,%d0
88: 2d40 ffc8 movel %d0,%fp@(-56)
volatile unsigned p = _rotr(x, 16);
8c: 202e fffc movel %fp@(-4),%d0
90: 7210 moveq #16,%d1
92: e2b8 rorl %d1,%d0
94: 2d40 ffc4 movel %d0,%fp@(-60)
volatile unsigned q = _rotr(x, 24);
98: 202e fffc movel %fp@(-4),%d0
9c: 7218 moveq #24,%d1
9e: e2b8 rorl %d1,%d0
a0: 2d40 ffc0 movel %d0,%fp@(-64)
volatile unsigned r = _rotr(x, 32);
a4: 202e fffc movel %fp@(-4),%d0
a8: 2d40 ffbc movel %d0,%fp@(-68)
volatile unsigned s = _rotr(x, 36);
ac: 202e fffc movel %fp@(-4),%d0
b0: e898 rorl #4,%d0
b2: 2d40 ffb8 movel %d0,%fp@(-72)
volatile unsigned t = _rotr(x, 41);
b6: 202e fffc movel %fp@(-4),%d0
ba: 7209 moveq #9,%d1
bc: e2b8 rorl %d1,%d0
be: 2d40 ffb4 movel %d0,%fp@(-76)
volatile unsigned u = _rotr(x, 48);
c2: 202e fffc movel %fp@(-4),%d0
c6: 7210 moveq #16,%d1
c8: e2b8 rorl %d1,%d0
ca: 2d40 ffb0 movel %d0,%fp@(-80)
volatile unsigned v = _rotr(x, 64);
ce: 202e fffc movel %fp@(-4),%d0
d2: 2d40 ffac movel %d0,%fp@(-84)
return 0;
d6: 4280 clrl %d0
d8: 4e5e unlk %fp
da: 4e75 rts
If I had to choose a compiler based on this alone, I'd go with gcc 2.95.3. Notice, though, how it does a swap on _rotl(x, ) and not _rorl(x, ). The same goes for direction changes for large shifts.
Your template is better in that regard, but as you noted, you might exclude the templated asm from further optimization. I think, though, that the code should be optimized (or at least scheduled) properly as long as you don't use asm volatile (...).
-
I don't use asm volatile in my templates as there's no reason to presuppose the code has to be emitted in every case. If the compiler can see the code is redundant it should be allowed to remove it.
Strange, though, I didn't get the anticipated rotate instructions generated by gcc 2.95.3. I wonder why?
-edit-
How is it with rotation of 8/16-bit types?
2.95.3's behaviour is slightly moot at this point as I'm hoping to use a later version anyway. Still a bit confused by your findings above though. Perhaps this could be down to stormgcc's backend? I was under the impression they hadn't messed about with the m68k compiler part at all.
-
How is it with 8/16-bit rotate?
I'll take a look.
2.95.3's behaviour is slightly moot at this point as I'm hoping to use a later version anyway. Still a bit confused by your findings above though. Perhaps this could be down to stormgcc's backend? I was under the impression they hadn't messed about with the m68k compiler part at all.
I don't know. If the source on Alinea's web site is current, we can take a look.
I'm thinking I'll have a go at amigaos targets. I'm building win32 native, non-Cygwin tools, which I'm sure would be useful to others, particularly people that don't want their Cygwin environment hijacked by a single target a la the current solutions out there.
EDIT: The StormC gcc (m68k-storm) is a bit of a mess. They built a modified m68k-amigaos binutils, added an m68k-storm target to gcc (modified from the Geek Gadgets m68k-amigaos), configured for the target, and then created a bunch of StormC projects to bootstrap the compiler, probably from a vanilla Geek Gadgets install. Funky. Anyhow, I don't have it built yet, but I'm not I'm seeing a benefit to completing it. StormC 4 is based on gcc 2.95.2. It's not difficult to get a new native m68k compiler.
And what I was really interested in is why gcc 4.4.0 doesn't optimize correctly--in fact, worse than gcc 2.95.3 (which still isn't optimal). A shiney new gcc 4.4.0 m68k-*-amigaos* with fixed optimization (for this parituclar issue, anyway) and a native newlib implementation would be, well, shiney.
-
I've started adding m68k*-*-amigaos* target support to gcc 4.4.0, and I have a freestanding compiler built. There's a bug in the adtools gas parser (or in my build of it), however, that causes assembly like 'jsr a6@(-0x228:W)' to be assembled as 'js a6@(-0x228:W)', resulting in an assembler error. 'jsrr a6@(-0x228:W)' assembles as 'jsr a6@(-0x228:W)', so that's a bit funny. Anyway, I think it has something to do with the way the offsets are parsed. If the bit after -0x is longer than two characters, the parser eats the r in jrs.
So, I need to fix that before I can move forward.
-
And what I was really interested in is why gcc 4.4.0 doesn't optimize correctly--in fact, worse than gcc 2.95.3 (which still isn't optimal). A shiney new gcc 4.4.0 m68k-*-amigaos* with fixed optimization (for this parituclar issue, anyway) and a native newlib implementation would be, well, shiney.
Indeed it would :)
Kind of scary that what started out as what I hoped was a simple "is there an -Wno-complain-about-asm" option turned into this :laughing:
-edit-
Do I take it my crazy Machine::rot8/16/32() are still fair game, then?
-
Kind of scary that what started out as what I hoped was a simple "is there an -Wno-complain-about-asm" option turned into this :laughing:
:-) Anything to pass the time.
Do I take it my crazy Machine::rot8/16/32() are still fair game, then?
I think so, yes. A "fixed" gcc should be able to properly reduce and generate optimal code for shift-or operations, however, and after that, the templates will be redundant. There's no reason why you shouldn't/wouldn't continue to use templates, though, if that fits your coding style. You think? I'd still get rid of the direction and width and use a set of overloaded rotate templates, though. ;-) Keep it generic.
-
The reason I didn't go for "signed direction" with the rotate operations was that you don't get that behaviour with <> either, by default.
I should point out that the template versions only exist to optimise "constant" rotates. There are normal inline methods where the number of bits to rotate is a variable.
-
I should probably rename this thread "Trev builds gcc 4.4 for m68k target" ;)
-
I should probably rename this thread "Trev builds gcc 4.4 for m68k target" ;)
Not yet! My track record with finishing hobby projects isn't so great. It might be "Trev got bored porting gcc to m68k-amigaos and watched Red Dwarf and Star Trek instead."
Re: gas, I might be running into a problem with Microsoft's implementation of snprintf, which differs from the ISO C99 definition with regard to when and where to append NULLs. So, 'jsr' is probably being truncated to 'js\0' somewhere, but only if the operands are over a certain length. Maybe there's a buffer that's too small somewhere in code. Anyhow, just guessing, as I ran into a similar problem when cross-compiling vbcc.
-
From what I gather looking at MS, they pretty much want to deprecate the C standard library in favour of their own "safe" versions of everything :)
I have to question the valididy of their safe "strcpy" alternative. All you have to do is give it a bad destination buffer size. How is that any safer?
-
Everything post-C89 in the standard C library is considered Microsoft-specific. Their standards efforts are all centered on C++. Based on press, I gather they're doing a pretty good job, but I don't write much C++ code. There's always the "C++ as a better C" argument to fall back on....
EDIT: And no direct references to *snprintf in gas. So, need to do some debugging.
EDIT2: Well, it's actually operands of a specific length that pose a problem:
jsr a6@(-60 :W) <-- 2 spaces no error
jsr a6@(-60 :W) <-- 3 spaces ERROR 'js a6@(-60:W)'
jsr a6@(-60 :W) <-- 4 spaces no error
Building a Cygwin cross right now to see if there's a difference between the two runtime environments.
EDIT3: Same problem under Cygwin, so it's probably a bug in gas. Yay. I can work around it by using decimal values for library offsets in inlines, but blah, do I really want to modify those by hand? I guess I'll change fd2pragma and generate the headers again.
EDIT4: Or I could just pad the expressions in macros.h with enough spaces to prevent the error from occurring, which is what I've done.
-
I'm struggling with read-only data placement at the moment. As the loader begins execution at the start of the first code hunk, all read-only data needs to be placed after code. GCC (supposedly) does this with a target macro, CONSTANT_POOL_BEFORE_FUNCTION. I've defined that macro as 0, which should tell the output routines to do what I want them to do; however, they're ignoring the value. At least, that's how it appears. Read-only data is still being generated before functions, so my hello.c test starts executing in the string "dos.library". Gotta love it. I could force all read-only data into a data hunk, but that shouldn't be necessary. :-/
-
No answer on '#define CONSTANT_POOL_BEFORE_FUNCTION 0' yet, so I'm forcing everything into a data hunk with '#define READONLY_DATA_SECTION_ASM_OP "\t.data"'. Obviously, that's not a viable long-term solution, but it keeps things moving. I'll have to ping the GCC gods on why CONSTANT_POOL_BEFORE_FUNCTION isn't working.
-
Read-only data is still being generated before functions, so my hello.c test starts executing in the string "dos.library".
Hmm. That's pretty bad. I don't know enough about the internals to be much help. Is CONSTANT_POOL_BEFORE_FUNCTION supposed to suppressed via #define CONSTANT_POOL_BEFORE_FUNCTION 0 or #undef CONSTANT_POOL_BEFORE_FUNCTION ?
Perhaps the switch depends on wether it is #defined at all, rather than what it is #defined as?
-
Hmm. That's pretty bad. I don't know enough about the internals to be much help. Is CONSTANT_POOL_BEFORE_FUNCTION supposed to suppressed via #define CONSTANT_POOL_BEFORE_FUNCTION 0 or #undef CONSTANT_POOL_BEFORE_FUNCTION ?
Perhaps the switch depends on wether it is #defined at all, rather than what it is #defined as?
Defining to 0 should be the way to go. If undefined, the compiler defines it as 1. It's only checked in two locations (before and after writing a compiled function to assembly source), but it's an old option, only used by one mainline target. It's possible the option has been inadvertently deprecated by the current maintainers.
-
Moving right along. I'm using the Geek Gadgets patches as a reference, but I'm not merging them. ixemul and libnix will be gone (to be replaced by newlib), as will simple (but annoying) things like legacy built-in definitions (MCH_AMIGA, AMIGA, et all to be replaced with __amigaos__) and attribute shortcuts (e.g. no __chip for __attribute__((__chip__))). Workarounds for missing definitions can be added to the build process for existing software or bundled into compatibility frameworks like the SDI headers.
Features like stack extension and position-independent / base-relative code will be worked into the standard GCC framework.
I'd also like to differentiate between hardware ISRs and AmigaOS ISRs, i.e. rte v. rts with cc set (?). I'm not sure if the Geek Gadgets port does that.
-
Indeed
-
Moving right along. I'm using the Geek Gadgets patches as a reference, but I'm not merging them. ixemul and libnix will be gone (to be replaced by newlib), as will simple (but annoying) things like legacy built-in definitions (MCH_AMIGA, AMIGA, et all to be replaced with __amigaos__) and attribute shortcuts (e.g. no __chip for __attribute__((__chip__))). Workarounds for missing definitions can be added to the build process for existing software or bundled into compatibility frameworks like the SDI headers.
Surely __chip is supportable via a #define __chip __attribute__((__chip__)) type affair?
-
Yes, and the Geek Gadgets sources define that in the compiler itself to provide source-level compatibility with other compilers. I don't see any reason to do that in the compiler when it can be done just as easily in a Makefile or header.
Also, CONSTANT_POOL_BEFORE_FUNCTION didn't do what I thought it did. I'm on the GCC list, hopefully getting pointed in the right direction.
EDIT: And rather humorously, I hit a race condition when making gcc with 'make -j 5 all-gcc' on my Core i7. Builds were much, much faster, but I can't have the process hanging (well, spinning forever, in this case) on me. GCC builds quickly, though. newlib is going to be a pain.
-
8, 16, and 32 bit rotates in gcc 4.4.0:
static inline unsigned char _rotl8(unsigned char val, unsigned char shift)
{
shift &= 7;
val = (val>>(8 - shift)) | (val << shift);
return val;
}
static inline unsigned char _rotr8(unsigned char val, unsigned char shift)
{
shift &= 7;
val = (val<<(8 - shift)) | (val >> shift);
return val;
}
static inline unsigned short _rotl16(unsigned short val, unsigned char shift)
{
shift &= 15;
val = (val>>(16 - shift)) | (val << shift);
return val;
}
static inline unsigned short _rotr16(unsigned short val, unsigned char shift)
{
shift &= 15;
val = (val<<(16 - shift)) | (val >> shift);
return val;
}
static inline unsigned long _rotl32(unsigned long val, unsigned char shift)
{
shift &= 31;
val = (val>>(32 - shift)) | (val << shift);
return val;
}
static inline unsigned long _rotr32(unsigned long val, unsigned char shift)
{
shift &= 31;
val = (val<<(32 - shift)) | (val >> shift);
return val;
}
volatile unsigned char w = 1;
c: 1f7c 0001 0027 moveb #1,%sp@(39)
volatile unsigned char a = _rotl8(w, 1);
12: 102f 0027 moveb %sp@(39),%d0
16: 0280 0000 00ff andil #255,%d0
1c: 2200 movel %d0,%d1
1e: d281 addl %d1,%d1
20: ee80 asrl #7,%d0
22: 8001 orb %d1,%d0
24: 1f40 0026 moveb %d0,%sp@(38)
volatile unsigned char b = _rotr8(w, 1);
28: 102f 0027 moveb %sp@(39),%d0
2c: 0280 0000 00ff andil #255,%d0
32: 2200 movel %d0,%d1
34: e281 asrl #1,%d1
36: ef88 lsll #7,%d0
38: 8001 orb %d1,%d0
3a: 1f40 0025 moveb %d0,%sp@(37)
volatile unsigned short x = 1;
3e: 3f7c 0001 0022 movew #1,%sp@(34)
volatile unsigned short c = _rotl16(x, 1);
44: 302f 0022 movew %sp@(34),%d0
48: 0280 0000 ffff andil #65535,%d0
4e: 2200 movel %d0,%d1
50: d281 addl %d1,%d1
52: 740f moveq #15,%d2
54: e4a0 asrl %d2,%d0
56: 8041 orw %d1,%d0
58: 3f40 0020 movew %d0,%sp@(32)
volatile unsigned short d = _rotr16(x, 1);
5c: 302f 0022 movew %sp@(34),%d0
60: 0280 0000 ffff andil #65535,%d0
66: 2200 movel %d0,%d1
68: e281 asrl #1,%d1
6a: e5a8 lsll %d2,%d0
6c: 8041 orw %d1,%d0
6e: 3f40 001e movew %d0,%sp@(30)
volatile unsigned long y = 1;
72: 7001 moveq #1,%d0
74: 2f40 001a movel %d0,%sp@(26)
volatile unsigned long e = _rotl32(y, 1);
78: 202f 001a movel %sp@(26),%d0
7c: e398 roll #1,%d0
7e: 2f40 0016 movel %d0,%sp@(22)
volatile unsigned long f = _rotr32(y, 1);
82: 202f 001a movel %sp@(26),%d0
86: e298 rorl #1,%d0
88: 2f40 0012 movel %d0,%sp@(18)
volatile unsigned z = 1;
8c: 7401 moveq #1,%d2
8e: 2f42 000e movel %d2,%sp@(14)
volatile unsigned g = _rotl(z, 1);
92: 202f 000e movel %sp@(14),%d0
96: e398 roll #1,%d0
98: 2f40 000a movel %d0,%sp@(10)
volatile unsigned h = _rotr(z, 1);
9c: 202f 000e movel %sp@(14),%d0
a0: e298 rorl #1,%d0
a2: 2f40 0006 movel %d0,%sp@(6)
In the nonvolatile world (and in the compile-time templates), these examples are all reduced to integer constants.
-
Careful, that's almost on-topic :D
-
Careful, that's almost on-topic :D
You're right. Seen any good movies lately?
(And there really should be a simple way to get rid of the warning. It really does imply that something is syntactically wrong with the inline assembly.)
-
Today I stumbled across a very nice gcc specific builtin:
__builtin_constant_p(x)
This evaluates to 1 if x is known to be a compile time constant. A quick test confirmed that it works on stuff as old 2.95.x. This is great, because it obviates the need for the template versions for constant-sized rotates. For example:
inline uint32 rotLeft32(uint32 bits, uint32 val)
{
if (__builtin_constant_p(bits)) {
// from template version
if (bits&31) {
// only rotate when modulus 32 > 0
if ((bits&31) < 9) {
asm("rol.l %1, %0" : "=d"(val) : "I"(bits&31), "0"(val) : "cc");
}
else if ((bits&31)==16) {
asm("swap %0" : "=d"(val) : "0"(val) : "cc");
}
else if ((bits&31)>23) {
// use opposite rotate for N > 23
asm("ror.l %1, %0" : "=d"(val) : "I"(32-(bits&31)), "0"(val) : "cc");
}
else {
// use register rotate for all intermediate sizes
asm("rol.l %1, %0" : "=d"(val) : "d"(bits&31), "0"(val) : "cc");
}
}
}
else {
asm("rol.l %1, %0" : "=d"(val) : "d"(bits), "0"(val) : "cc");
}
return val;
}
This single inline emits code as efficiently as the template version in all cases where bits evaluates to a constant value at compile time. One thing to note is that __builtin_constant(x) only really works at optimisation levels -O1 and higher.
@Trev
Any progress with the gcc 4 m68k amigaos build?