Alignment bug in your codegen

[bztsrc]

Hi,

First I'd like to say thanks for this great repo! Is is possible to buy your book in e-book (or any other computer readable format, eg. not on paper)?

I've found a bug in your code generation though (at line 53):

// Round up `n` to the nearest multiple of `align`. For instance,
// align_to(5, 8) returns 8 and align_to(11, 8) returns 16.
int align_to(int n, int align) {
  return (n + align - 1) / align * align;
}

As a matter of fact, both align_to(5,8) and align_to(11,8) returns zero when compiled with an optimizer. The correct code would be (assuming align is always power of two):

int align_to(int n, int align) {
  return (n + align - 1) & ~(align - 1);
}

If align could be really any arbitrary value, not just power of two, then:

int align_to(int n, int align) {
  return (int)((n + align - 1) / align) * align;
}

Note that the casting and parenthesis is required only to stop optimizers from making a mistake. As the precedence of * and / is the same, this is actually an UB with a side-effect (round down), therefore some optimizers would result in a code that incorrectly removes the operations entirely or calculates the multiplication first (I believe that is what's happening and why I get zero results with -O3). Granted, this could very well be an optimizer bug, but non the less the resulting chibicc executable isn't working correctly. An itherwise unnecessary casting and parenthesis solves the issue.

Again, really cool project, I like that you prefer readability over anything else, I'll recommend this tutorial to my students for sure! So far I was using Small C which although works, but a bit outdated (and TCC is totally unreadable for students). So chibicc is perfect for them!

Cheers,
bzt

[rui314]

I don't think this is a bug because * and / are defined to be left-associative. Compilers are allowed to reorder operators as long as it produces the same result, but as you pointed out, reordered computation can produce a different result, so it's not a sound optimization.

[bztsrc]

I don't think this is a bug

It definitely is, because chibicc executable produces incorrect alignments. It is not necessarily a bug in chibicc's source as I've said this can be an optimizer bug.

it's not a sound optimization.

But unfortunately it is happening. And chibicc could workaround this issue easily. Adding that parenthesis and cast has no downsides, won't hurt anything, wouldn't affect properly written optimizers, but would fix buggy ones (I've tested it, it works). I believe it would also increase the code readability by making the intention more clear.

Anyway, it is up to you, just a suggestion. I'd use the bitmask if I were you.

Cheers,
bzt

ps: thanks again for chibicc, I really like its style, perfect for my students!

[rui314]

What compiler are you using and what option are you passing?