Godbolt: Enter C, get Assembly
godbolt.org
godbolt.org
int square(int num) {
int a = 0;
for (int x = 0; x < num; x+=2) {
if (!(x % 2)) {
a += x;
}
}
return a;
}
All kinds of loop unrolling and vector instructions.
Now remove the "!"Not sure if that's smart or stupid.
(1 * 5 * 9 * 13 * 17 * ...) * (2 * 6 * 10 * 14 * 18 * ...) * (3 * 7 * 11 * 15 * 19 * ...) * (4 * 8 * 12 * 16 * 20 * ...)
(it's not precisely that, but close enough)
It isn't optimal however, optimal code would be pre-computed results (signed integer overflow is undefined, so n <= 12 is defined)
(if signed integer overflow would be defined to be 2's complement overflow, you can still use a table, as n > 33 gives 0)
1. Turned from recursive form into iterative form 2. Unrolled heavily 3. Autovectorized (!)
The throughput will be substantially more than the simple version.
I'd like to know how the recursion to iteration step was done.
vs. what it does with 64-bit ints:
Can anybody explain the 32 bit version?
I would be much more impressed if I hadn't taken a compilers course. I reckon (god alone knows exactly what GCC does) this is just linear induction variable substitution[1] (so `x` gets replace with `i*2`), then associativity of integer multiplication, then some (probably builtin) rule that `n%n` is always 0. From there, it is pretty straightforward.
Don't get me wrong - the devil is in the details and getting optimizations that are both powerful and only applied when they are valid, and at the right time is difficult as hell. That said, I do expect compilers to be at least this smart.
[1]: https://en.wikipedia.org/wiki/Induction_variable#Induction_v...
Does anyone know if, internally, compilers second-guess / double-check themselves ? For instance, when they detect a clever shortcut do they generate and quickly run [1] the optimized bytecode on a sampling of inputs to verify it is functionally-equivalent to what non-optimized bytecode outputs ?
[1] obviously cross-compilers are a thing, so this wouldn't be possible if it were compiling/optimizing for a separate architecture.
There are people who do do more exhaustive checks of the peephole optimizations for correctness--or finding new opportunities (see John Regehr's Souper work). But production compilers are well-known (at least by anyone who works on them) for having lots of bugs in these kinds of optimizations.
No. Optimization transformations are generally expected to result in provably identically-functional code (or sufficiently identical, in case of e.g. floating-point optimizations). Otherwise it is a bug.
Is this quite right? It's not true in general that (a * b) % c = a * (b % c). E.g. it's not true for 2,3,4. The relevant generalization is that (a * b) % b = 0, which has nothing to do with associativity.
magic constants galore... where does 3435973837 come from? ;)
[edit] and playing around with the increment of x it keeps throwing in some magical values which are a repeating pattern in hex, with the LSB off by one usually...
0.CCCCCCCC.... = 4/5 had anything to do with it.
Using hexadecimal we have
5 * 3 = 10 - 1, so
5 * C = 40 - 4 so
5 * (1 + C + C0 + C00 + C000...) = 5 - 4 + 40 - 40 + 400... where the last term is = 0 mod 2^32
-----
D
This relates to 0.CCCCCC.... = 4 / 5
Because in order for that to come out right, multiplying 0.CCCC... with 5 has to have all intermediate terms cancel, leaving only a 4.So why would it take its digit from 4 / 5 and not 1 / 5? Because it takes x=4 to make the 5-x subtraction in 5 - x + x0 - x0 + x00 to come out to 1.
So this gives us a general rule for inversion (for numbers less than 16). Take the hexadecimal expansion of (n-1) / n, truncate to get enough hex chars, add 1 to the least significant hex digit.
I.e. the inversion of 3 would be 0xAAAAAAAB
if (num <= 0) {
return 0;
}
int a = 0;
int loop_n = (unsigned)(num - 1) / 5;
for (int x = 0; x <= loop_n; x++) {
a += x * 5 - 1;
}
return a;
Division by 5 is done by multiplying by the modular inverse, 3435973837.From there you just have a summation, which has two components.
((loop_n + 1) * loop_n / 2) * 5 // 5x
- loop_n - 1 // -1
The assembly between these the manual and automatic methods is slightly different, but the difference is fairly trivial and opaque.http://mathandmultimedia.com/2010/09/15/sum-first-n-positive...
> Now remove the "!"
To be fair 4.6 and clang also do that, and I suspect so do earlier versions if I could be arsed to fix the compilation error.Also as pointed out elsewhere clang turns the "!" version into a simple equation in terms of n, so I'm actually kind of disappointed in GCC here.
Now here's a more efficient algorithm which does produce the currect result:
int square(int num) {
int a = 0;
for (int x = 1, n = num; x <= num; x+=x, n+=n) {
if( num & x) {
a += n;
}
}
return a;
}
It would be nice if this site allowed us to run/step through the code, to see exactly what it is doing. square(int): # @square(int)
xor eax, eax
ret
is required to perform this, what's going on?From this we can see that gcc and clang have figured out that the "if" can never be true, then they elided the loop, then optimized out the variable, ending in the equivalent of "return 0;".
#include <stdint.h>
uint32_t testFunction(uint32_t x)
{
return ((x & 0xff) << 24) | ((x & 0xff00) << 8) | ((x & 0xff0000) >> 8) | ((x & 0xff000000) >> 24);
}
compiles into: testFunction(unsigned int):
mov eax, edi
bswap eax
ret
Another fun one, that only works with clang: #include <stdint.h>
int testFunction(uint64_t x)
{
int count;
for (count = 0; x; count++)
x &= x - 1;
return count;
}
compiles into: testFunction(unsigned long):
popcnt rax, rdi
rethttps://github.com/llvm-mirror/llvm/blob/master/lib/Transfor...
A smart compiler would not use the new SSE version. (perhaps you didn't set the flags right?)
This is why: http://0x80.pl/articles/sse-popcount.html
http://xania.org/201609/how-compiler-explorer-runs-on-amazon
as a pragmatic example (incl. all tools & configs) of how to build an auto scaling & deploying site, without overdosing on kool-aid.
Of course I am only a minor Haskell learner but jhc could do whole-program compilation with readable assembly.
As for gcc, try 'gcc -fdump-tree-all -fdump-rtl-all-slim' and read the 50 files it prints.
I think most people internally optimise readability and thus size, those who don't generally make unmaintainable mush.
(In that issue I am trying to figure out some FMV stuff.)
Yes, but once you did you might see how you might improve it.
Your brain, while slower at code translation than gcc, can think of things that gcc never will, and yet things that can beat your brain[1] are still slower.
The Rust Playground at https://play.rust-lang.org/ has a similar function, letting you check ASM, LLVM IR, and MIR (Rust's mid-level intermediate representation) output for current versions of the Rust compiler.
int retNum(int num, int num2) {
return (num * num2)/num;
}
gives this in clang retNum(int, int): # @retNum(int, int)
mov eax, esi
ret
While icc and gcc give retNum(int, int):
mov eax, esi
imul eax, edi
cdq
idiv edi
ret
retNum(int, int):
imul esi, edi
mov eax, esi
cdq
idiv edi
ret
The clang version at first sight seem right. But then thinking about it this is integer math. 4/3 := 1
1 * 3 := 3
leads to
3 != 4
I believe gcc and icc returning 3 there is correct, while clang returning 4 is not. Maybe someone more C/int versed
can tell us which are acceptable (knowing C both might be ok)One thing that can happen is an integer overflow: if you pass (0x10000, 0x10000), icc's and gcc's versions will calculate 0x10000 * 0x10000 = 0, 0 / 0x10000 = 0, while clang will return 0x10000. But clang's not wrong: signed integer overflow is undefined behavior in C, so compilers are allowed to just assume it never happens when making optimizations.
If it does not work in new GCC it is a bug.
The division cancels out the multiplication. Just like if you were doing arithmetic on paper as you did in school. There's nothing more to it than that is there? What inputs do you think it's incorrect for in clang?
Overflow is of course undefined.
What arguments do you think it will do the wrong thing with?
int retNum(int num, int num2) {
return (num2 * num)/num;
}
now becomes retNum(int, int):
mov eax, esi
ret return (num / num2) * num2;
Where the division happens first.That is what I get for thinking about this before coffee.
I'd love to see Motorola 68000 support.
Also this is actually a repost from one year ago,
The loop was also vectorized, so that each multiply is a 4-element vector multiplication, with the final result being a horizontal reduction.
The rest of the mess is trying to account for all of the cases where the input power is not a multiple of 128.
Cool project regardless.
Instead of finding (or worse, building) a compiler or cross compiler locally and doing all the boring steps to compile properly (harder than it sounds) and disassemble the code, you can just splat some code into this and take a peek.
Less about "assembly projects", more about breadth of info available to a developer writing C/C++.
The closest I've ever come to this back in the day was running (Borland) Turbo Debugger's assembly view after building with Turbo C (w/ or w/out -O...), as either 8086 or 80286 output - "x16". Yeah, that was a while back :-)
I had a chance to read part of the sources and prepare a patched version with a set of toolchains (m68k, amd64, mips). It's nicely written, it's easy to add toolchains as well as to set default compilation options.
http://xania.org/201609/how-compiler-explorer-runs-on-amazon
After moving back to linux I haven't found a replacement ide that's as nice for doing c++ development.
Most of the optimizing magic happens in the JITs, not javac.
square(int):
mul r0, r0, r0
bx lr
Mips is damn awesome.If Agner Fog has no problem calling it 'assembly'[0], then neither do I.
Because they've written more applications in assembler than anyone else in the history of computing. Look at Aminet, and csdb.dk, and that's just Amiga and C=64, I haven't even included the Spectrum, Amstrad CPC, Atari ST and PC.
Absolute unbridled nonsense.
They've been using that name since 1992, and if those guys aren't "scene coders" then I've never seen one.
I never went back in the day, but pretty sure I didn't primarily interpret it as "ooh, a congregation of people".
Source: I started writing assembly code in 1968, over the years coding for Sigma 5/7, PDP-10, TI 9900, 6502, 8080, Z80, 8086, 68000, x86, and ARM. I occasionally saw it called assembler language, but less often than assembly language.
Update: As I think about it, there is a bit more nuance to the terminology that I remembered at first. While I do recall "assembler language" and "assembler code" as being infrequently used, "assembler" by itself has often been a common usage:
"I'm writing this in assembly code."
"I'm writing this in assembler."
Those were used fairly interchangeably, even by someone like me to whom "assembler code" sounded a bit off.
So you're definitely not wrong to call it "assembler". Where you're going wrong is claiming that "assembly code" is incorrect.
6502:
https://www.amazon.com/Assembly-Language-Programming-Lance-L...
ftp://ftp.apple.asimov.net/pub/apple_II/documentation/programming/6502assembly/6502%20Assembly%20Language%20Programming.pdf
Z80:
http://maben.homeip.net/static/S100/zilog/z80/Z80%20Assembly...
https://archive.org/details/Zilog_Z80_assembly_language_prog...
68000:
http://dev-docs.atariforge.org/files/Asm_Lang_Prog_68K_Famil...
https://www.amazon.com/68000-Family-Assembly-Language-Progra...
Assembly is also the result of something that was assembled.
(which is why the tool to handle them is called objdump)
> What happens when you assemble a group of people? You have an assembly. The same can be said for other objects.
Although assembly is machine code represented with mnemonics, they're not the same: assemblers take assembly and produce machine code.