News for hackers. Stuff that matters.
Re:Compilers are hard by cperciva on Thursday January 21, 2021 @12:21AM (#25855746)
On the topic of compilers being hard: In my repositories I'm carrying around a 5 year old workaround (https://github.com/Tarsnap/libcperciva/commit/92e666e59503de...) for a 6 year old bug (https://bugs.llvm.org/show_bug.cgi?id=21183) in clang/LLVM.

You might think that "incorrect code gets generated" would be a maximum-priority must-fix-before-the-next-release bug in a compiler, but apparently not.

Re:Compilers are hard by _slyo on Thursday January 21, 2021 @01:45AM (#25856212)
Wow, this is the first time I've seen the computed goto extension. Delightfully gross!

https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

Re:Compilers are hard by KMag on Thursday January 21, 2021 @02:43AM (#25856507)
Computed gotos are commonly used in main loops of bytecode interpreters to get a separate dispatch (indirect jump) at the end of handling each bytecode, so the CPU's branch target buffer has a better chance of predicting the indirect jump target for the next bytecode based on the previous bytecode. For instance, CPython's dispatch loop uses computed goto on supported platforms, and Erlang's BEAM VM (in non-JIT mode) uses computed branch labels to convert bytecodes into branch addresses at bytecode load time.

I suppose, for twice the latency, CPU designers could implement (a hash of) the previous branch address from the source instruction pointer as part of the BTB tag, similar to using the global branch history as part of the state in the branch predictor. Presumably, the global branch history could also be used in the BTB tag to give some hint as to which bytecode we've just finished executing.

Though, where it really counts, interpreter writers are already often using computed gotos, reducing the reward to cost ratio for implementing such specialized BTB improvements.

On the other hand,

   while (1) {
       switch (...) {
           ...
       }
  }
is probably rare enough (and almost certainly in a hot loop) that a very specific optimization flag might be better than a syntactic extension. Granted, an optimization flag doesn't work for Erlang's threaded code use case.
Re:Compilers are hard by __s on Thursday January 21, 2021 @07:58AM (#25858344)
You'll also find them used in CPython's ceval.c

I use them in both my C befunge implementations:

https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60...

https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60...

Re:Compilers are hard by thegrandpoobah on Thursday January 21, 2021 @12:31AM (#25855795)
Actually shocked to hear this considering the number of people and companies currently working on LLVM.
Re:Compilers are hard by jcranmer on Thursday January 21, 2021 @01:40AM (#25856188)
The code in question is related to setjmp/longjmp. As a general rule of thumb, this is something where the gut reaction to any bug report is going to be "you're doing it wrong"--the C standard actually provides a lot less guarantees here than most people believe it does. I haven't read the verbiage and the bug report in question in enough detail to ascertain if this is true or not, but it isn't in the least bit surprising that most people see setjmp/longjmp and immediately table the issue as being low-priority.
Re:Compilers are hard by usefulcat on Thursday January 21, 2021 @10:52AM (#25860141)
Having read the comments in the llvm bug report, it seems pretty clear that it is a real bug and that they have at least an idea of where the bug is.
Re:Compilers are hard by drivebycomment on Thursday January 21, 2021 @12:40AM (#25855845)
Not that surprising given that it seems specific to asan mode and only in the presence of setjmp/longjmp. I.e. this cant be that important unless the same bug shows also in non-asan Setjmp/longjmp case. Setjmp/longjmp are often a source of trouble for the register allocator or related optimization due to its unique properties. Often the optimizing compilers treat set/longjmp as "give up almost everything around those functions" but maybe llvm is trying hard to model it precisely and failing. But I haven't personally looked at the relevant code in llvm so this is mostly a speculation.
Re:Compilers are hard by cperciva on Thursday January 21, 2021 @12:46AM (#25855900)
The bug shows up without asan. We literally tripped over it in production with code compiled with "clang -O2".
Re:Compilers are hard by drivebycomment on Thursday January 21, 2021 @12:53AM (#25855939)
Then I agree that this is surprising. That means clang/llvm is not modeling set/longjmp correctly in general and that is not acceptable as a C compiler.
Re:Compilers are hard by scatters on Thursday January 21, 2021 @03:51AM (#25856861)
That's apparent from your ticket (which is marked as a duplicate) but on the one you linked to, all the offending compiler lines contain asan. Is there a chance this is impacting prioritization?
Re:Compilers are hard by cperciva on Thursday January 21, 2021 @11:27AM (#25860641)
Could be. I'm not an LLVM developer so I don't know how they prioritize issues.
Re:Compilers are hard by h_anna_h on Thursday January 21, 2021 @12:44AM (#25855880)
Regarding asan bugs, if you do not free all of your memory before exiting main it will complain about stuff and end up calling _exit I think which does not flush the buffers.
Re:Compilers are hard by titzer on Thursday January 21, 2021 @01:25AM (#25856106)
No, performance is maximum priority.
Re:Compilers are hard by naikrovek on Thursday January 21, 2021 @01:52AM (#25856256)
That's a "great on the surface, bad when you think about it" thing if I've ever seen one.

Who cares how fast the code is, if it isn't the correct code?

Re:Compilers are hard by xmprt on Thursday January 21, 2021 @01:56AM (#25856276)
I have solved the halting problem. Every program you write compiles and executes as HALT; and therefore it's possible to determine if a program halts! It might not be correct but it sure is fast!
Re:Compilers are hard by mrybczyn on Thursday January 21, 2021 @03:08PM (#25863544)
https://en.wikipedia.org/wiki/Full_employment_theorem

You've broken the full employment theorem for compiler writers.

Re:Compilers are hard by jcranmer on Thursday January 21, 2021 @12:12PM (#25861270)
The practical effect isn't what you think it is.

Many compiler writers are employed by hardware companies, and these companies are employing them to sell their hardware chips. For these companies, even a 1% boost in performance on $BENCHMARK can drive measurable impact on sales. Even if you're not worried about driving hardware sales, performance tends to be the major benchmark that gets mentioned in comparisons--note how the "Benchmarks Game" (what used to be called the Programming Language Shootout) compares languages solely on the basis of performance.

In other words, if you look at actual customer behavior, performance tends to be one of the most dominant factors in choosing one compiler over another (language compliance is probably more dominant, however). Surety of correctness is not a major factor at all.

Now, in order to actually report benchmarks correctly, you have to implement them correctly, so to some degree you have a basic guarantee that the compiler will usually work. But someone pointing out a soundness issue using a hypothetical example (as opposed to real code) is going to end up low priority because the evidence is that it doesn't matter in practice for the real, large applications that customers care about (as no one else has complained about it for the past several years).

In summary, practical performance will win out over theoretical correctness, but not practical correctness.

Re:Compilers are hard by igouy on Thursday January 21, 2021 @01:49PM (#25862467)
> …"Benchmarks Game" … compares languages solely on the basis of performance.

Not true.

1) source code size is compared

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

2) correctness is checked

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

3) time "to complete and log all make actions" (build the program) is also logged

Re:Compilers are hard by jcranmer on Thursday January 21, 2021 @02:11PM (#25862752)
> 1) source code size is compared

This is new to me (the Benchmarks Game has been around for well over a decade).

> 2) correctness is checked

This is par for the course of benchmarks. A benchmark that is incorrectly compiled provides no useful information whatsoever about performance. It's not really what people mean when they complain about correctness issues in the compiler (which is generally referred to as soundness in literature).

> 3) time "to complete and log all make actions" (build the program) is also logged

Performance in a compiler is usually taken to be a combination of runtime, code size, and compile time, although all three components are not weighted equally.

Re:Compilers are hard by igouy on Thursday January 21, 2021 @02:26PM (#25862996)
Back on May 23 2006, a sortable column of GZip source code size measurements:

https://web.archive.org/web/20060523195137/http://shootout.a...

https://web.archive.org/web/20060519213743/http://shootout.a...

> Performance in a compiler is usually taken to be a combination of runtime, code size, and compile time

The benchmarks game shows source code size, not compiled code size.

Re:Compilers are hard by qznc on Thursday January 21, 2021 @02:30AM (#25856449)
If people cared about correctness, they would use CompCert instead of GCC or Clang.
Re:Compilers are hard by pjmlp on Thursday January 21, 2021 @05:07AM (#25857308)
Or create OSes where applications are all written in managed languages, and the use of GCC and clang is gate keeped to the OS vendor and native libraries, just an idea.
Re:Compilers are hard by MaxBarraclough on Thursday January 21, 2021 @07:15AM (#25858096)
Bit of a nitpick, but the real value is in safe languages, rather than managed languages, no? The distinction is a little blurry, admittedly, but as an example, I figure that verified SPARK counts as safe but unmanaged.
Re:Compilers are hard by pjmlp on Thursday January 21, 2021 @07:19AM (#25858122)
Because as you might have guessed, I was speaking of iOS, Android and ChromeOS, while SPARK as much as I like it, is a very niche technology.
Re:Compilers are hard by MaxBarraclough on Thursday January 21, 2021 @07:30AM (#25858180)
I should have gone with a less niche example: the safe subset of Rust. D also has a safe subset.
Re:Compilers are hard by pjmlp on Thursday January 21, 2021 @08:55AM (#25858772)
Still niche, Rust is not up to the stuff that app developers expect in terms of tooling and D still has quite a few @safe bugs to sort out, among its current adoption issues.

Unfortunely regardless of their own reports regarding CVEs, Microsoft, Apple and Google keep turning to C and C++ for their bottom layers + managed languages, instead of going full speed in some of those alternatives.

So it appears to be the long term solution to mitigate security issues, while keeping compatibility with existing code and tooling.

Re:Compilers are hard by eru on Thursday January 21, 2021 @07:15AM (#25858102)
Why use managed languages when you can prove your code correct?
Re:Compilers are hard by pjmlp on Thursday January 21, 2021 @07:20AM (#25858131)
With what, Frama-C? Good luck getting it adopted outside domains that enforce its use for code certification.
Re:Compilers are hard by eru on Wednesday January 27, 2021 @12:56AM (#25924801)
Frama-C is a specific compiler. It has not much to do with proving your own code. (And C ain't a good language for writing code you want to prove correct in.)

You are right that after having proven your code correct, you might want to use an implementation (compiler or interpreter), that is also proven correct. But those are still two different things.

Re:Compilers are hard by dhekir on Thursday January 28, 2021 @02:54AM (#25939332)
Frama-C is a framework for code analysis. It can help proving code with the aid of ACSL (JML-like notation for C contracts).

But I agree that C is not the best language for writing critical code.

Re:Compilers are hard by tobylane on Thursday January 21, 2021 @03:06AM (#25856619)
CompCert doesn’t guarantee these two functions will work. Thanks, didn’t know about that project.
Re:Compilers are hard by Cthulhu_ on Thursday January 21, 2021 @05:10AM (#25857329)
I do; low level, OS and library code should be both. It's not an either or; you start with the correct code (and code to verify), then if needs be you optimize.
Re:Compilers are hard by wongarsu on Thursday January 21, 2021 @07:42AM (#25858258)
So you're saying maximum priority is correctness, and performance second place? Because if you don't have correctness you can't "start with correct code"
Re:Compilers are hard by 0xTJ on Thursday January 21, 2021 @08:20AM (#25858508)
If you have a broken compiler, you can have broken generated code, and not even know it. This isn't about whether or not your C code is correct, this is about whether the assembly that's generated matches the behavior in your code.
Re:Compilers are hard by ndr on Thursday January 21, 2021 @06:15AM (#25857718)
How is this not confirming the point you're replying to?
Re:Compilers are hard by lmm on Thursday January 21, 2021 @03:47AM (#25856839)
Anyone who's decided to use C has already made that choice, so it makes sense that C compiler writers would follow their priorities.
Re:Compilers are hard by 0xTJ on Thursday January 21, 2021 @08:19AM (#25858500)
In my opinion, a program that is wrong is always worse than a slow program that is correct. Full stop, no exceptions.
Re:Compilers are hard by dkarl on Thursday January 21, 2021 @10:44AM (#25860037)
Almost every commercially successful product I've worked on has been known to be wrong at every point in its useful life. I've worked on a lot of microservices that had no known bugs for most of their deployed life, but they were simple parts of more complex systems that did have known bugs. The computing world is built top to bottom mostly out of programs that are broken.

If this had not been possible, the industry would have gone the way Dijkstra advocated, with mathematical rigor applied to all programming.

Re:Compilers are hard by JoeAltmaier on Thursday January 21, 2021 @08:27AM (#25858559)
Queue pedantic counterexamples.

Anyway, in this day of just-in-time software we're not going in that direction any more.

Re:Compilers are hard by auggierose on Thursday January 21, 2021 @09:11AM (#25858946)
What direction is that? The direction of correct software?
Re:Compilers are hard by JoeAltmaier on Thursday January 21, 2021 @09:43AM (#25859296)
Right. Mostly-correct and on-time is all we're getting paid for. That's what agile is all about.
Re:Compilers are hard by mook on Thursday January 21, 2021 @12:30PM (#25861485)
Hmm, so no floating point math ever, only use arbitrary precision? As far as I know most 3D games do correct-enough math because it'll be replaced in a couple frames anyway.
Re:Compilers are hard by 0xTJ on Friday January 22, 2021 @10:12PM (#25879222)
Of course not. Correctness doesn't mean that everything has to be perfect. It means that things work as defined. A C program should operate as specified.
Re:Compilers are hard by bregma on Thursday January 21, 2021 @06:34AM (#25857836)
Performance of the compiler, that is.
Re:Compilers are hard by vintagedave on Friday January 22, 2021 @12:40PM (#25873980)
Are you sure it's not fixed? https://reviews.llvm.org/D11495 was fixed on 29/7/2015.
Re:Compilers are hard by cperciva on Friday January 22, 2021 @01:38PM (#25874605)
That's marked as being Asan-specific, and the bug isn't. So... I don't think so?