C Is Not a Low-Level Language

Re:C Is Not a Low-Level Language by pera on Tuesday May 01, 2018 @12:27PM (#16968545)

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"? :)

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by munificent on Tuesday May 01, 2018 @03:44PM (#16970725)

> 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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by verall on Tuesday May 01, 2018 @04:52PM (#16971482)

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.pd...

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by andrewflnr on Tuesday May 01, 2018 @06:42PM (#16972416)

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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by vvanders on Tuesday May 01, 2018 @04:22PM (#16971140)

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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by pera on Tuesday May 01, 2018 @04:34PM (#16971271)

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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by nickpsecurity on Tuesday May 01, 2018 @04:26PM (#16971184)

"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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by still_grokking on Wednesday May 02, 2018 @02:29AM (#16974596)

> 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.

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by posterboy on Tuesday May 01, 2018 @04:45PM (#16971400)

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).

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by jburgess777 on Tuesday May 01, 2018 @05:23PM (#16971808)

> 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...

[ Parent | on HN ]

Re:C Is Not a Low-Level Language by posterboy on Wednesday May 02, 2018 @05:43AM (#16975383)

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

[ Parent | on HN ]