Hacker News Reader

Comment by brucedawson | Hacker News Reader

The webrtc fix was thematically similar in that the programmer declared what registers were trashed and then the compiler knows which registers need to be saved. I'm not sure why the compiler doesn't notice when registers are used without being declared as being trashed - I'm really not an expert at _writing_ assembly language.

View on HN

It's literally undecidable in principle whether some assembler correctly restores some register R. That's a non-trivial semantic property, Rice's theorem applies. So the compiler's only practical option if it worked this way would be a conservative option - any time it's unclear whether register R is clobbered, treat it as clobbered.

As a trivial example of why a register might not be clobbered even though my code touched it and it seems like I didn't restore it...

Suppose if R is divisible by 12 I branch, in the other branch I don't change R, but in that branch I do change R, XORing it with a value which is difficult to explain but has a value between 1 and 3 inclusive, sometimes more than once. At the end of the branch I also clear the bottom two bits of R.

R is actually not clobbered by this function! If the bottom two bits weren't zero before, R isn't divisible by 12, so we didn't change R, and if they were zero, we restore that, the other bits are never changed.

Having the human programmer promise they they wrote a correct clobber list means if their assembler does somehow restore/ preserve register R, the human can just say so, and needn't prove to the compiler somehow that this works. This sort of code is mostly in performance critical components, e.g. video decoding, where we are already trading reliance on fallible humans for better performance, so adding one extra promise feels OK.

> It's literally undecidable in principle whether some assembler correctly restores some register R.

No, it's literally undecidable in principle whether every bit of assembler correctly restores some register R. For any given bit of inline assembler, it's quite likely to be trivial.

In any case, we can have a useful safety feature without requiring the compiler to decide. The compiler can easily work out all the registers which get written to (right?), just not which get restored. So in addition to the clobber list, we could have a list of registers which the programmer asserts that the code restores. A register which is written to has to be on either the clobber list or the restore list (or be an output). This certainly isn't foolproof, but it would catch accidental clobbers.

> No, it's literally undecidable in principle whether every bit of assembler correctly restores some register R. For any given bit of inline assembler, it's quite likely to be trivial.

Exactly. And if it's non-trivial to decide something that basic, you're doing it wrong. Saving and restoring all the registers is always an option. Only saving and restoring some of them is an optimization which must be shown to be sound.

> every bit of assembler correctly restores some register R.

Thanks, I was trying to think about the correct way to express this but clearly I didn't do the best job.

It would be easy to have an "auto" clobber list option. The inline assembler would note which registers were touched (mostly trivial, a few instructions have implicit destinations) and would add them all to the clobber list. In about 99% of cases this would be sufficient. I am not aware of any code that conditionally uses a register _and_ conditionally preserves it.

So, 1% of assembly code would use the manual clobber list, but the other 99% would be guaranteed (barring bugs in the compiler) to not have this bug. It seems like the right tradeoff.

Or, instead of an "auto" clobber list the compiler could have a warning if a register is used without being in the clobber list. The programmer could silence that warning in the rare cases where they need to optimize register preservation, and the bugs would be greatly reduced.

If your numbers are roughly correct then I agree it's worth trying to do this. My guess was that the assembly we actually use tends to be aggressively hand-optimised to solve very nice problems in the most optimal way and therefore would be more rather than less likely to trip up analysis, but I haven't experimented.

My experience is that most non-trivial assembly language is doing processing of large chunks of data (high-precision math, encrypting blocks of data, FFTs, etc.) and therefore the startup cost of the function is not significant, so a tiny bit of inefficiency in that area is not something people care about.

Or, put another way, writing tiny little assembly language functions is probably not worth it because the mere fact that you are using assembly language instead of (say) C/C++ means that you have missed many opportunities (code reordering, inlining, etc.) so assembly language functions _should_ be doing enough work to justify their calling cost.

But, I'm not working on an assembler or even using one so I don't think I'll even file a feature request.

Traditionally, an assembler neither knows nor cares about such information, it just turns lines of assembly into bytes and does some address fixup for you.

Reply on news.ycombinator.com