3 ms·

If every source-language load must result in a memory load, then you at the very least killed scalar replacement of aggregates (a critical optimization), and, d

If every source-language load must result in a memory load, then you at the very least killed scalar replacement of aggregates (a critical optimization), and, depending on how you define it, you might have killed register allocation too.

eddyb 8y ago
You get register allocation back if you deny taking the address of variables declared with the `register` keyword - and we've gone full circle!
- kazinator 8y ago
  Taking the addresses of variables defined register is denied; that's the only modern meaning of the specifier.
kazinator 8y ago
Give me the rule "every source language load of a structure member, array or global variable, or anything loaded indirectly through a pointer results in an actual load" and I will still crank out fast code, by explicitly using local variables for caching the values coming from those places.
- pcwalton 8y ago
  You'll also write unmaintainable code. To a large degree, optimizations exist to allow programmers to write maintainable code without sacrificing performance.
  - kazinator 8y ago
    I will write absolutely clear code this way. I use that style anyway, quite often. Optimization can work backwards in this regard. For instance, let's consider CSE (common subexpression elimination). That allows some repetitive code to produce the same results as code that adheres to DRY. E.g. stupid way to insert into a circular list: node->prev = prev; node->next = prev->next; prev->next->prev = node; prev->next = node; The compiler has no idea whether node and prev are aliased or not. The assignment to node->next might be the same as prev->next, and so prev->next has to be reloaded even though it was just loaded in the previous line. smart way: get a local variable for prev->next! node *next = prev->next; node->prev = prev; node->next = next; next->prev = node; prev->next = node; Bonus: much more readable, lining up in neat columns. Just one arrow in each line. If this doesn't generate at most one load and four stores, the compiler is garbage. Also note that we can reorder these four assignments in any of the 4! permutations and they produce the same result (unless there is aliasing, which would be unintentional and wrong regardless of the order). Not the case in the original. For instance, it's important that prev->next is stored in node->next before the assignment to prev->next. You can shoot yourself in the foot with local variables though. Caching is susceptible to staleness. You have to know when it is legitimate to keep using the cached value and when it must be reloaded or disused. After our assignment prev->next = node, the next variable no longer represents the value of prev->next. In this case, since we are done, we don't care. If more code followed which still assumed that next is the original successor of prev (now the successor of node), that would be wrong.
    - pcwalton 8y ago
      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.

eddyb 8y ago

You get register allocation back if you deny taking the address of variables declared with the `register` keyword - and we've gone full circle!

kazinator 8y ago
Taking the addresses of variables defined register is denied; that's the only modern meaning of the specifier.

kazinator 8y ago

Give me the rule "every source language load of a structure member, array or global variable, or anything loaded indirectly through a pointer results in an actual load" and I will still crank out fast code, by explicitly using local variables for caching the values coming from those places.

pcwalton 8y ago
You'll also write unmaintainable code. To a large degree, optimizations exist to allow programmers to write maintainable code without sacrificing performance.
- kazinator 8y ago
  I will write absolutely clear code this way. I use that style anyway, quite often. Optimization can work backwards in this regard. For instance, let's consider CSE (common subexpression elimination). That allows some repetitive code to produce the same results as code that adheres to DRY. E.g. stupid way to insert into a circular list: node->prev = prev; node->next = prev->next; prev->next->prev = node; prev->next = node; The compiler has no idea whether node and prev are aliased or not. The assignment to node->next might be the same as prev->next, and so prev->next has to be reloaded even though it was just loaded in the previous line. smart way: get a local variable for prev->next! node *next = prev->next; node->prev = prev; node->next = next; next->prev = node; prev->next = node; Bonus: much more readable, lining up in neat columns. Just one arrow in each line. If this doesn't generate at most one load and four stores, the compiler is garbage. Also note that we can reorder these four assignments in any of the 4! permutations and they produce the same result (unless there is aliasing, which would be unintentional and wrong regardless of the order). Not the case in the original. For instance, it's important that prev->next is stored in node->next before the assignment to prev->next. You can shoot yourself in the foot with local variables though. Caching is susceptible to staleness. You have to know when it is legitimate to keep using the cached value and when it must be reloaded or disused. After our assignment prev->next = node, the next variable no longer represents the value of prev->next. In this case, since we are done, we don't care. If more code followed which still assumed that next is the original successor of prev (now the successor of node), that would be wrong.
  - pcwalton 8y ago
    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.