3 ms·

Do you also, for example, look up the magic multiplication number in Hacker's Delight every time you want to divide by a constant?

kazinator 8y ago
That silliness is not comparable to effective use of local variables to both streamline the source code and get better output from the compiler. By the way, the magic multiplication number can be worked out, because it's just fixed point math. We take the 32:32 fixed point representation of 1 and divide by 17 to get an approximation of 1/17 in 32:32 fixed: 0x100000000 / 17 = 0xF0F0F0F. That's our magic number for dividing 32 bits by 17 by doing a 64 bit multiplication. For instance 90/17 is 90 * 0xF0F0F0F = 0x54B4B4B46. The integer part of this 32:32 fixed point value is in the upper 32 bits which is 5. There are some subtleties there, plus considerations of whether we want signed or unsigned division. Better let the compiler deal with it. Arithmetic reductions are safe optimizations. It's hard to imagine what you could do wrong so that an arithmetic reduction breaks your code, given that it produces the same result and doesn't interact with some some memory aliasing where the compiler isn't informed about what you're doing. And by the way, given this code: #include <stdio.h> struct node { struct node *next, *prev; }; void ins_after_a(struct node *prev, struct node *node) { node->prev = prev; node->next = prev->next; prev->next->prev = node; prev->next = node; } void ins_after_b(struct node *prev, struct node *node) { struct node *next = prev->next; node->prev = prev; node->next = next; prev->next = node; next->prev = node; } gcc 7.2.0 on Ubuntu 17 generates better code for the cleaner, streamlined second one with the local variable, for exactly the reason I gave. ins_after_a yields 6 movq instructions; in_after_b yields 5. Better source that is easier to reason about; better machine code: all round win. ins_after_a: .LFB23: .cfi_startproc movq (%rdi), %rax movq %rdi, 8(%rsi) movq %rax, (%rsi) movq (%rdi), %rax <-- wasteful re-load of (%rdi) due to aliasing suspicion movq %rsi, 8(%rax) movq %rsi, (%rdi) ret .cfi_endproc .LFE23: .size ins_after_a, .-ins_after_a .p2align 4,,15 .globl ins_after_b .type ins_after_b, @function ins_after_b: .LFB24: .cfi_startproc movq (%rdi), %rax movq %rdi, 8(%rsi) movq %rax, (%rsi) movq %rsi, (%rdi) movq %rsi, 8(%rax) ret .cfi_endproc The language could be specified that way (accesses to structs are memory loads) for all I care and that could be helpful.
- comex 8y ago
  In other words, TBAA is fundamentally limited in its ability to capture the programmer's expectations about aliasing, because it must assume that any two pointers that happen to have the same type could alias – even if a person reading the code would consider that obviously unreasonable. In this case, you could avoid the wasteful re-load by marking the function arguments as `restrict`. One of the reasons Rust's memory model is interesting is that the language statically prevents mutable aliasing in most cases, so "restrict" comes for free… well, kind of. (It's actually rather difficult to nail down the precise guarantees, especially when your compiler's backend was originally designed for C.)
  - kazinator 8y ago
    Ah, but by using restrict I'm saying, "please screw my C program with C99 stuff that potentially introduces undefined behavior". That's what restrict does: it makes some behaviors undefined and otherwise doesn't change the semantics of the program. It's completely against the grain of moving to a safer language. Why would I do that, if I can instead beautify the source and machine code while sticking to what was available in C90. I think restrict is mainly intended as a way of competing against Fortran. If you're processing arrays referenced by pointers, and can get the compiler to believe that they do not overlap, then the compiler can unroll the loops and rearrange the accesses and calculations in the unrolled body. Like it can load four elements from a source arrays, do four calculations, and then store four elements into a target, rather than interleaving. That can be done by vectorized instructions. Here is where our technique falls short: if we write the loop body with our load-calculate-store style, it cannot be unrolled and vectorized. We have pinned down an exact behavior for all possible cases of aliasing, like self-overlap with a displacement. Vectorizing unrolls do not preserve that behavior. Manual unrolling isn't attractive because it's a guessing game. A good amount of unrolling on one machine may give the instruction cache indigestion on another machine.
deleted 8y ago
[deleted]

kazinator 8y ago

That silliness is not comparable to effective use of local variables to both streamline the source code and get better output from the compiler. By the way, the magic multiplication number can be worked out, because it's just fixed point math. We take the 32:32 fixed point representation of 1 and divide by 17 to get an approximation of 1/17 in 32:32 fixed: 0x100000000 / 17 = 0xF0F0F0F. That's our magic number for dividing 32 bits by 17 by doing a 64 bit multiplication. For instance 90/17 is 90 * 0xF0F0F0F = 0x54B4B4B46. The integer part of this 32:32 fixed point value is in the upper 32 bits which is 5. There are some subtleties there, plus considerations of whether we want signed or unsigned division. Better let the compiler deal with it. Arithmetic reductions are safe optimizations. It's hard to imagine what you could do wrong so that an arithmetic reduction breaks your code, given that it produces the same result and doesn't interact with some some memory aliasing where the compiler isn't informed about what you're doing. And by the way, given this code: #include <stdio.h> struct node { struct node *next, *prev; }; void ins_after_a(struct node *prev, struct node *node) { node->prev = prev; node->next = prev->next; prev->next->prev = node; prev->next = node; } void ins_after_b(struct node *prev, struct node *node) { struct node *next = prev->next; node->prev = prev; node->next = next; prev->next = node; next->prev = node; } gcc 7.2.0 on Ubuntu 17 generates better code for the cleaner, streamlined second one with the local variable, for exactly the reason I gave. ins_after_a yields 6 movq instructions; in_after_b yields 5. Better source that is easier to reason about; better machine code: all round win. ins_after_a: .LFB23: .cfi_startproc movq (%rdi), %rax movq %rdi, 8(%rsi) movq %rax, (%rsi) movq (%rdi), %rax <-- wasteful re-load of (%rdi) due to aliasing suspicion movq %rsi, 8(%rax) movq %rsi, (%rdi) ret .cfi_endproc .LFE23: .size ins_after_a, .-ins_after_a .p2align 4,,15 .globl ins_after_b .type ins_after_b, @function ins_after_b: .LFB24: .cfi_startproc movq (%rdi), %rax movq %rdi, 8(%rsi) movq %rax, (%rsi) movq %rsi, (%rdi) movq %rsi, 8(%rax) ret .cfi_endproc The language could be specified that way (accesses to structs are memory loads) for all I care and that could be helpful.

comex 8y ago
In other words, TBAA is fundamentally limited in its ability to capture the programmer's expectations about aliasing, because it must assume that any two pointers that happen to have the same type could alias – even if a person reading the code would consider that obviously unreasonable. In this case, you could avoid the wasteful re-load by marking the function arguments as `restrict`. One of the reasons Rust's memory model is interesting is that the language statically prevents mutable aliasing in most cases, so "restrict" comes for free… well, kind of. (It's actually rather difficult to nail down the precise guarantees, especially when your compiler's backend was originally designed for C.)
- kazinator 8y ago
  Ah, but by using restrict I'm saying, "please screw my C program with C99 stuff that potentially introduces undefined behavior". That's what restrict does: it makes some behaviors undefined and otherwise doesn't change the semantics of the program. It's completely against the grain of moving to a safer language. Why would I do that, if I can instead beautify the source and machine code while sticking to what was available in C90. I think restrict is mainly intended as a way of competing against Fortran. If you're processing arrays referenced by pointers, and can get the compiler to believe that they do not overlap, then the compiler can unroll the loops and rearrange the accesses and calculations in the unrolled body. Like it can load four elements from a source arrays, do four calculations, and then store four elements into a target, rather than interleaving. That can be done by vectorized instructions. Here is where our technique falls short: if we write the loop body with our load-calculate-store style, it cannot be unrolled and vectorized. We have pinned down an exact behavior for all possible cases of aliasing, like self-overlap with a displacement. Vectorizing unrolls do not preserve that behavior. Manual unrolling isn't attractive because it's a guessing game. A good amount of unrolling on one machine may give the instruction cache indigestion on another machine.

deleted 8y ago

[deleted]