6 ms·

I'm not an expert, but I don't think the optimization phase should be really considered here: the same kind of pattern matching used by (e.g.) LLVM to find opti

by pera 9y ago

I'm not an expert, but I don't think the optimization phase should be really considered here: the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler. NASM for instance offer some level of optimizations, so I think optimization should only be considered when it's part of the language specification itself, like in Scheme. IMO C is close to low-level because it's relatively easy to imagine the resulting unoptimized assembly given some piece of code (which is why some people jokes about C being a macro assembly). Maybe this old debate should get an slight update... and this could be the starting point: Is modern x86 assembly still "low-level"? :)

munificent 9y ago
> the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler. Some of the simpler optimizations, sure. But modern backends do many incredibly sophisticated optimizations that are way beyond any kind of simple pattern-matching-and-substitution model. Even fundamental "optimizations" like register allocation use quite sophisticated algorithms. Optimal register allocation is NP-complete, so compilers use heuristics on top of graph coloring algorithms to do their best. Most other optimizations rely on type analysis, data flow analysis, liveness analysis, etc.
- vvanders 9y ago
  It would be interesting to revisit a world where languages/compilers were built explicitly with common memory access semantics/out of order op/etc in mind. One of the things that really excites me about Rust is that it's single mutable reference enforcement means you can run run `restrict` 100% of the time if you wanted which is a non-trivial performance boost. I think it's not enabled today but from previous discussions it sounds like that's just a matter of plumbing through the right things to LLVM. Every time I've seen that rolled out in a C/C++ codebase someone invariably forgets about pointer aliasing and you spend a week tracking down some non-deterministic behavior.
- pera 9y ago
  My point was that since optimization is also possible in assembly, and since assembly is considered low-level, then optimization per se shouldn't be used as something that characterize high-level languages exclusively. But it is true that some abstractions used by high-level languages enable quite complex optimization techniques, so there is a clear correlation between the level of a language and the ability of its compiler to analyze and optimize programs.
- verall 9y ago
  The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where to optimally place spills and fills around loops and calls. https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pdf https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pd...
  - andrewflnr 9y ago
    Yeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.
nickpsecurity 9y ago
"the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler" Transmeta's x86 CPU's were even doing translations and optimizations dynamically between x86 and their internal representations.
- still_grokking 9y ago
  > Transmeta's x86 CPU's were even doing translations and optimizations dynamically between x86 and their internal representations. I think every modern x86 CPU is doing exactly that.
posterboy 9y ago
C cannot read the overflow bit after an ADD, because of it's abstractions ... so I would say modern ASM is still lower in some aspects because it has less constrains and more importantly, it is less expressive, which is the whole idea of this hierarchy. The compiler should offer a macro for that. Then the question is whether to take the specification or the implementation at which point it's an absurd question to begin with. You could compare -O0 binaries, bypassing the optimization question, too. High/low is not fine grained enough. IIRC, prolog for example would be dubbed a fifth generation language, after assembler, goto hell macro compilers, structured functional programming, and DSLs. Now coq and the like seem to be of yet a higher order (pun intended, sorry).
- jburgess777 9y ago
  > C cannot read the overflow bit after an ADD ... The compiler should offer a macro for that. If you use GCC then __builtin_add_overflow() is what you are looking for: "The compiler will attempt to use hardware instructions to implement these built-in functions where possible, like conditional jump on overflow after addition, conditional jump on carry etc." https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
  - posterboy 9y ago
    Yes, I know that. Y ou could add macros implementing a complete asm language to become a subset of C and C would still be more expressive

by pera 9y ago

munificent 9y ago

> the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler. Some of the simpler optimizations, sure. But modern backends do many incredibly sophisticated optimizations that are way beyond any kind of simple pattern-matching-and-substitution model. Even fundamental "optimizations" like register allocation use quite sophisticated algorithms. Optimal register allocation is NP-complete, so compilers use heuristics on top of graph coloring algorithms to do their best. Most other optimizations rely on type analysis, data flow analysis, liveness analysis, etc.

vvanders 9y ago
It would be interesting to revisit a world where languages/compilers were built explicitly with common memory access semantics/out of order op/etc in mind. One of the things that really excites me about Rust is that it's single mutable reference enforcement means you can run run `restrict` 100% of the time if you wanted which is a non-trivial performance boost. I think it's not enabled today but from previous discussions it sounds like that's just a matter of plumbing through the right things to LLVM. Every time I've seen that rolled out in a C/C++ codebase someone invariably forgets about pointer aliasing and you spend a week tracking down some non-deterministic behavior.
pera 9y ago
My point was that since optimization is also possible in assembly, and since assembly is considered low-level, then optimization per se shouldn't be used as something that characterize high-level languages exclusively. But it is true that some abstractions used by high-level languages enable quite complex optimization techniques, so there is a clear correlation between the level of a language and the ability of its compiler to analyze and optimize programs.
verall 9y ago
The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where to optimally place spills and fills around loops and calls. https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pdf https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pd...
- andrewflnr 9y ago
  Yeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.

nickpsecurity 9y ago

"the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler" Transmeta's x86 CPU's were even doing translations and optimizations dynamically between x86 and their internal representations.

still_grokking 9y ago
> Transmeta's x86 CPU's were even doing translations and optimizations dynamically between x86 and their internal representations. I think every modern x86 CPU is doing exactly that.

posterboy 9y ago

C cannot read the overflow bit after an ADD, because of it's abstractions ... so I would say modern ASM is still lower in some aspects because it has less constrains and more importantly, it is less expressive, which is the whole idea of this hierarchy. The compiler should offer a macro for that. Then the question is whether to take the specification or the implementation at which point it's an absurd question to begin with. You could compare -O0 binaries, bypassing the optimization question, too. High/low is not fine grained enough. IIRC, prolog for example would be dubbed a fifth generation language, after assembler, goto hell macro compilers, structured functional programming, and DSLs. Now coq and the like seem to be of yet a higher order (pun intended, sorry).

jburgess777 9y ago
> C cannot read the overflow bit after an ADD ... The compiler should offer a macro for that. If you use GCC then __builtin_add_overflow() is what you are looking for: "The compiler will attempt to use hardware instructions to implement these built-in functions where possible, like conditional jump on overflow after addition, conditional jump on carry etc." https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
- posterboy 9y ago
  Yes, I know that. Y ou could add macros implementing a complete asm language to become a subset of C and C would still be more expressive