Optimize the loops away? How?

Ajouté : 2026-05-12

[00:00:00]Hello internet. So, as I've been thinking about ways to add optimizations to my uh C compiler that fits in one JavaScript file, uh I came across this this this classic optimization that I don't know. It Every time I see it, it still kind of kind of blows my mind a little bit. So, you see you have this simple loop, uh but you see that when you when you compile it with clang, you get this.

[00:00:24]Like, you don't have to be uh an expert in assembly to see that Wait a second, there's no loop here. This is it. This this this freaking loop compiles down to this, which is just like a number, right? It basically looks like clang pre-calculated the number, and then just just shoved it in there as a return value.

[00:00:44]It's wild, right?

[00:00:46]And then so, if you think like, "Okay, well, it maybe it's just something to do with like constants, and then the compiler kind of knew what to do." Uh you could you could substitute uh uh an argument here, right? Th- Then, what is clang going to do after that?

[00:01:00]It actually still gets rid of the loop.

[00:01:02]Um again, like there's no loop here. This is just a set of of uh you know, computation uh computation instructions.

[00:01:10]And essentially boils down to to this formula down here, right? Which is like actually the formula for how to get uh uh you know, add numbers up from from, you know, two to to what whatever uh n minus one or whatever, right?

[00:01:25]But like, how did how did clang come up with that formula, right? Like, why? Why why is this optimization here, right?

[00:01:31]Like, this essentially what happened here was we we went from here, this code, and then clang looked at it and decided that "Nah, I'll just I'll just emit this instead."

[00:01:43]Right? Like, much. Where did Where did this optimization come from?

[00:01:48]Um well, well, my first thought, right, was like, "Okay, the way they it must have like the my first thought on how they must have implemented was like they must have looked for certain patterns in the compiler. Maybe certain patterns like X plus equals uh some formula based on the the the iteration variable. And then okay, well like you can happen to solve the formula uh uh you know, if if you see this pattern and then and then convert it down to this.

[00:02:15]In spirit in in a way it kind of is what happens, but but in practice it isn't.

[00:02:21]Clang actually doesn't do it exactly this way. Right? So okay, like My second thought was okay, maybe it's loop unrolling, right? I know that compiler sometimes when it when it knows uh uh the loop uh is bounded, it'll create like it'll actually write it out to avoid uh doing branching and then loops and so it'll just just compute everything uh unrolled. And when you see the formulas unrolled, maybe you know, you could also imagine a a a fathomable world where like okay, well I know the initial values and I happen to see the formulas for for how these values evolve. So you can keep track of it kind of kind of like this here, right?

[00:03:01]It turns out this isn't this is also not what Clang does because first of all, if in the first case when you have when you're going all the way up to a million, unrolling a loop of a million is a little bit crazy. It wouldn't do that.

[00:03:13]And secondly, uh in the second case, you it's not um you also don't have a constant number.

[00:03:21]You actually don't know how many times you have to unroll.

[00:03:24]So this this idea doesn't quite work.

[00:03:27]So basically a a lot of these compilers when they do optimizations, they they store the program in what's called single static assignment. Single as in once, static as in not changing, and assignment as in setting the value of a variable. So in the static single assignment, uh single static assignment single static single assignment. Uh in SSA, uh you're you're only ever allowed to store uh, a value to a variable once.

[00:03:58]But then you might think, wait a second, like my program has mutations everywhere. Like I have value of X changing, I have value of I changing.

[00:04:04]What do you do? Well, every time you assign to it, in SSA, you create a new variable.

[00:04:10]Essentially, you have, uh, you know, the initially you have I = 0, X = 0. And then whenever you have a situation where the value could have come from two different places, you represent it with phi, and then you you store the two things it could have been. So in this case, for example, uh, the assignment in I++ here, I1, well, it could have come either from uh, the the value the value of I before starting the loop, or it could have come from the value of I after incrementing in the previous iteration of the loop.

[00:04:45]Right? Same for X. X starts out as zero.

[00:04:49]And then X also gets updated later in the loop. So when you're assigning X1, you could either have gotten this value from X coming from outside of the loop, or you could have gotten X from the value X2, which is the value of X you got from incrementing uh, updating the value of X in the previous iteration of the loop.

[00:05:10]Right? It feels a little bit roundabout, but, um, this is quite standard compiler fair, uh, from what I understand.

[00:05:21]And once you store it in in this this format, it is a little bit easier to identify certain kind of patterns like, uh, when when you notice that a formula evolves as like like a variable is essentially uh, evolves as a recurrence relation.

[00:05:39]When that is a case, uh, there are some general formulas for for uh, uh calculating it, and then you can simplify to find that the formula becomes this. And when when when it's identifiable, the compiler will actually just uh substitute the value.

[00:05:54]You don't actually completely have to understand this to apply it.

[00:05:57]Essentially, uh you just the algorithm is something you can follow. I >> [laughter] >> I get I guess this is a thing you could do. Um there there's an algorithm for identifying the the recurrence relations itself, the chain of recurrence relations, like uh I is essentially a recurrence relation of I equals I plus one, right? And then you have X, which is a recurrence relation that contains I.

[00:06:20]But even in those situations, um we have some magical formulas, if you've uh essentially essentially calculus, but for discrete numbers.

[00:06:32]Uh that will give you this formula to to figure out how to compute them in a closed form. Which I I I think it's pretty magical. Like like, you know, when you're doing programming, quite often you're like, "You know, do you really need math in programming?" Well, turns out like math really does help sometimes, you know?

[00:06:49]Well, one of those rare cases you actually see some math while you're doing programming. Like, the loop itself is not something you see quite that all that often. Like, I just don't think I'm going to write a loop like this. I'll probably just write the formula myself, you know? I'll probably just write this if if this is what I actually want.

[00:07:06]But like, it's just kind of a cool optimization to have, right? So like, this begs the question, do I want to add it to my my compiler, compiler.js, right?

[00:07:17]But the thing is, uh the the key aspect of implementing this optimization is the SSA part, the the static single single single static assignment, right? Static single assignment, single static assignment. Uh and currently my compiler follows this pipeline, right? You have You have the C and the head as header files, the lexer and preprocessor tokenizes it, and then the tokens are are parsed into an AST, and then the AST uh has a couple lowering phases, like getting rid of the go-tos uh into a format that's easier for the WASM to to consume, and then we code gen that into the WASM.

[00:08:00]And then we convert the the tree into a a WebAssembly.

[00:08:05]I'm I'm in the process of adding an IR phase uh that is essentially like a tree structure.

[00:08:12]So, the AST re- the AST is a is a tree structure that mirrors the C code.

[00:08:21]The IR is meant to be a tree structure that better resembles the WebAssembly code.

[00:08:27]The IR is is uh tends to be a bit simpler and easier to reason about than the the AST, and so it makes for a good uh tool for optimizing. At least doing this the sort of optimizing that the kind of is like a little bit easier to to to imagine, like uh constant folding, basic constant folding, and like um inlining certain certain function calls, and so on.

[00:08:52]So, I'm in the process of doing that.

[00:08:54]But, in order to be able to implement this specific optimization, I actually need to have an extra phase here, right?

[00:09:00]Essentially, I need to have the IR, and then I need a phase that converts the IR into SSA.

[00:09:06]And then in the SSA, I'm going to do some optimizations on on it.

[00:09:12]Possibly SSA, and then I might need a a control flow graph as well. I'll have to think about that. And then after doing the optimizations, I need to convert it back into IR, and then from IR, I'll I'll do the code uh code gen.

[00:09:25]Um Maybe at some point if like I need those optimizations, maybe I will really have to to do that. But, at this point in time, I feel like uh this is not this is not the direction I want to be going in.

[00:09:40]And like it is hairier, like Uh At least conceptually to me May maybe uh smarter people might disagree with me, but The ASC is pretty close to the C source.

[00:09:55]And then even the IR, even though the intermediate representation is meant to be closer to how web assembly uh raw web assembly views things, I still find the IR to be quite close to the human readable code. Right? But once you're taking stuff down into SSA Uh You you get like you you saw it, right? Like the code is going to look like um Oh.

[00:10:21]This, right? Whatever whatever this is, right? Like yeah, you can kind of see the pattern, okay, like all the variables kind of explode into multiple variables, and then you have all these phis everywhere, and then you have to kind of think about like what What do phis mean?

[00:10:36]Right? Uh so you're going to have what I'm going to need an internal representation that I feel like is going to drift quite a bit from What the original sources up here are like.

[00:10:47]Right?

[00:10:48]Yeah, it it it it can be done. It it is doable, but it but it is also something where uh It adds, in my opinion, quite a bit of complexity that is unnecessary at this moment. So it is a kind of a shame. I I would have loved to have have a demo where it's like, "Oh yeah, look look at my compiler like optim- optimizing away this loop." Uh but alas, um That I Yeah, this is just this is just me complaining.

[00:11:16]Yeah, this is this is just me me uh trying [laughter] to justify uh my compiler not having the coolest optimizations, but who knows? Never never say never, you know? May may maybe maybe at some point it'll be added.

[00:11:28]Yeah.