Less Gas, More Fun: Optimising Smart Contracts through Yul by Christian Reitwiessner (Devcon4)

Yeah, this talk is about the new Yul optimizer and I want to start in in a good tradition. I want to start with a definition. What is an optimizer? Um, an optimizer is a piece of software that takes another piece of software, a program as input, and transforms it into a new piece of software that hopefully requires fewer resources or at least not more and is semantically equivalent. So, it means it it does exactly the same thing.

And both of these components of the definition allow for some kind of slack. So, both the resources and the semantic equivalence, but we'll touch on that later. Let's see an example. So, this is Solidity code um, that computes the square of the input number. And it uses the exponentiation operation, which is quite expensive on the EVM, and the same thing can be achieved with just a multiplication multiplication of X by itself.

And so, such a transformation on Solidity would be yeah, a valid optimization optimizer transformation because it does the same thing and it's cheaper. Okay, but we don't want to optimize Solidity directly. We want to optimize the low-level language that we'll see later. Um, this thing has two problems. So, the first one touches on the resources part.

So, what are actually the resources we want to optimize? On the EVM, this might be trivial. Of course, you want to optimize for gas. But, if you take a closer look, then you see that yeah, gas is not yeah, there's no not a unique thing you can call gas or gas usage of a smart contract because there are at least two. The first is the the that is required to deploy the smart contract, and the second thing is the gas that is required later if you call individual functions.

And this is a Yeah, this is a trade-off that actually matters later because some routines, if you um transform them to something that is more compact but does the same thing, then this reduces deploy time cost, but most of the time it increases run time costs. So, and uh the current optimizer also has a flag where you can set exactly this trade-off. It's called the runs parameter. This is often misinterpreted as just the number of runs you want to the amount of effort you want to put into the optimizer, but it's actually exactly this trade-off. And this trade-off problem gets even more complicated when you have loops because then you might want to um you So, for the code that is inside the loop that is executed executed more often than the code outside of the loop.

So, uh there it's even more important that the run time costs are lower, and you might uh be fine with a little bit more uh deploy time costs in such cases. But Yeah, these are tough decisions for the optimizer, and it will not always get it right. And the second problem is that even if you have a clearly defined mathematically defined metric for resource consumption, uh it is theoretically impossible to create a perfect optimizer. And perfect optimizer means it takes a program as input, and the output program is the best possible program that does the same thing with the least amount of resource usage. And the reason for that is uh yeah, not not the problem that that finding this optimal program is too difficult because the search space is too large or something like that, but uh it's the semantic equivalence.

And more specifically, you probably heard about the halting problem that gets cited all the way in Turing complete for Turing complete um blockchain smart contract execution environments. And um you can show via the halting problem that a perfect optimizer is impossible. And um yeah, the halting problem is that it's a result from theoretical computer science and it says that there is no program that decides on a given uh input program whether it halts on all inputs or not. And uh because we're on on the EVM here, we replace halt by revert and this is still true. And um so we now assume that we have a perfect optimizer and use that perfect optimizer to solve the halting problem and because of that perfect optimizer is impossible.

And um yeah, the way we do it is so if a program reverts on all inputs and it's the shortest program, then it has to look something like this empty contract here. Because that's the short shortest program that reverts on all inputs. And so to decide the halting problem, we take the perfect optimizer, run it on the input and if it outputs this uh empty smart contract, then the input halts on all inputs and otherwise not. Okay, that's a nice theoretical result, but uh yeah, completely useless for practice. I mean, it's nice to know the lower bounds and where we cannot go, but if we relax this uh optimal thing, we can get uh quite far.

So um Now, next question you might ask is why do we want an optimizer? And there is probably an obvious answer and that is we want cheaper smart contracts. But if you take a closer look, then this is not the main reason to have an optimizer. Instead, um an optimizer allows you to write your code in a more modular and more understandable way. So, um, if you do not use an optimizer and your you care about resource consumption, then you always have to uh consider, "Oh, is this is this cheap enough what I'm writing here or not?

Uh can I change it in a way so that it's it's a little bit cheaper and still does the same thing?" And but if you know that the optimizer will just do that for yourself, then uh you can write it so that it's readable, it's auditable, you are uh 100% sure that it works, and uh you don't have to care about resource consumption all the time. And an example of that is this smart contract here. Um, it's a simple fragment of a voting contract. We have a vote function which takes an output that an an outcome we want to vote.

And it checks that the user has not voted yet. Um, and it if the user has not voted yet, it assigns the weight of the user to the votes. And you see that this weight of is another function that just returns 10 for the owner and one for everyone else. And um, without an optimizer, this would perform a function call which is costly, so uh a cheaper way would be to just take this uh this this statement that is inside the function and put it at the point of the function call. But that will, yeah, that will reduce readability.

It will not tell you what this weird expression 10 one actually is now in in the way it's written now, we see, yeah, it's the weight of the vote. And uh also, if we use this weight if it's like that, we can use the function from other places and then modify the weights without having to modify it everywhere in the code. Okay, um, in the rest of the talk, um, I will quickly describe how the current Solidity optimizer works and then uh explain what we plan to do on Yul. Um, the current Optimizer is wholly based on opcode stream, so it's extremely low-level. Um, yeah, it has several stages.

I won't go into detail for all of them. The most extensive stage is the last one here, the common subexpression eliminator, which does much more than what the name suggests. And yeah, let's dive into that a little. So, what it does is first it chops code, so it gets a stream of opcodes and chops that into blocks, blocks that don't contain jumps, don't contain external calls, and some other restrictions. Um, then these blocks are fed opcode by opcode to the component.

The common component builds symbolic expression trees, so analyzes the stack usage and creates symbolic expressions out of them. Then these expression trees are simplified to I think 40 or 50 simple transformation rules like uh yeah, constant plus variable plus constant is variable plus the sum of the constants. Um, and so on. Uh, these rules will be reused by the Yul Optimizer, so that's not something we have to rewrite. And after the expression trees are simplified, the component records all changes to memory and storage in an abstract way.

So, both the value that is written and the point where it's written to are these abstract expressions. Um, yeah, the problem with that is that it kind of looks like this. So, on the left you have the stream of opcodes and on the right you have some kind of explanation of what the component has to store internally. Um, in the end we can't be yeah, there's no real way to output the internal symbolic representation. Even if there was such a way, it would be very hard to read.

Um, and yeah, so yeah, the takeaway from the old CSE optimizer is that it builds a gigantic internal data structure. Yeah, it it uh yeah. And after it has built this uh data structure, it regenerates the code from scratch. So, it starts from the bottom up and um takes a look what the desired stack elements at the end of this uh chopped up block would be, then recreates the stack elements, and also recreates changes to storage and memory um in a more efficient way um because it will eliminate multiple stores to the same storage location and multiple memory stores to the same memory location. And also, if you have if you have two expressions uh in the code that do the same thing, then it's only computed once.

Um and yeah, as I said, the main drawback of this uh component is very opaque um also, it does only very local uh optimizations, only inside these uh blocks. It has no notion of functions, so it cannot perform inlining, and it also cannot do any loop optimizations. There are some uh stages in the old optimizer that look beyond these blocks, but they also do not do inlining. Okay, now let's take a look at at Yul and what the new optimizer uh can do with it. Uh I there has been a talk, I think, yesterday by Alex about Yul here at Devcon 4 and also another one at Devcon 3 last year.

Um we are already using Yul in the new ABI coder and the plan is to use Yul for everything else uh starting next week. So, the plan is to rewrite the code generator of Solidity using Yul so that it can uh target both EVM and WebAssembly. And uh we will also be able to use the optimizer for all of the the code that Solidity generates, not only for the ABI coder. Um yeah, Yul has a simple syntax, uh has structured components, and I think it's uh quite intuitive to read. But yeah, uh I'm already spending too much time on that.

So, let's take a look what at the optimizer itself. Um instead of uh building a component that looks at the code and assembles tons of information, we decided to instead replace it by a component that performs uh many tiny uh local transformations uh to the code. So, uh every single step of the component does only one So, every single step of every single component of the optimizer does only one single thing, only one small transformation on the uh Yul code, and the output of each of the steps is always again Yul code. So, it always um it is always readable, it is still text, there are no internal big internal data structures. And um at every time you can look at it and see whether the transformation was correct or not.

And uh the optimizer also keeps the structure of the code, so it keeps functions and loops. It does not introduce go-tos, and this helps us for the translation to WebAssembly because WebAssembly does not have go-tos, it only has uh functions, loops, and conditions. Um the tricky part of uh building the optimizer is when is not designing the components, but coming up with a good strategy on when to call each component. Um but the good news here is that uh even if this uh this strategy turns out to be suboptimal, it will never result in invalid code, because as long as we uh check that every of these small tiny transformations does its job correctly, then any combination of these steps will always result will also result in correct code. It might be uh less efficient, but it will always be correct.

Okay, now uh let's take an example. Then let's take a look at an example. This is UEL code that computes the sum of an array. So, we have the first function that uh yeah has a for loop over the array elements. Uh this first function calls the second function.

And the second function uh retrieves a single array element. So, X is the array, and I is the position in the array. Uh the interesting thing here is that array load performs bounds checking. So, um uh array load checks whether I is less than the length of the array. And um this in the in the in the form here, it's inefficient, because it's done in every single loop iteration.

But uh uh it is very safe, because we do it every single loop iteration. And the cool thing now is that we will see that the optimizer is able to uh remove these bounds checks with equivalent transformations. So, the first thing that happens is that we explode this uh large expression into an intermediate assignment. And now we have the the function call isolated. And since it's only called the since the function is only called once, uh we can inline it.

So, we can replace the function call by the body of the function. So, that's a more drastic change to the code, but it's simple enough. And now, the next thing that happens is remove this useless additional indented block, and we also rename one of the variables. Okay, now it's already a little bit clearer. Now, we change the formatting a little.

Okay. So, this was already one of the two tricky parts. Now, what happens next is that we take a look at all the statements inside the loop body and see if some of the statements don't actually depend on the iteration at all. So, um the only variable that is reassigned inside the loop is sum and I. So, everything that does not depend on sum or I or anything that depends on sum or I can be pulled out of the loop and thus not executed for every single loop iteration, but only once uh before the loop starts.

Okay. So, that was data and len. Now, we realize that length and len, they are assigned the same value. Um since since it's a memory load, it's it might not be the same value in the end. Uh but if the memory does not change between these two memory load operations, then of course it has to be the same value, and this is the case here.

So, we do not modify memory. Um So, len and length are actually the same thing, which means we can remove len and replace every len by length. Okay. And now, we see that inside this if statement inside the loop, yeah, that's that's the point where I could use a laser pointer, but So, there is an less than I length. So, if is zero less than I length, revert.

That is the bounce check we had in the in the function. And uh we realized that uh less than I length is also the loop condition. So the for loop has a condition and it runs as long as this is true. So as long as I is less than length the for loop runs. And this means that inside the loop inside the body of the for loop less than I length would always be true.

Otherwise the body would not execute. So this means inside this bounce check we can replace less than I length by true or one. Um Okay, and now we see we have a constant there and applying an operation on that is zero is zero is the is EVM speak for um logical negation. So is zero of one so is zero is basically not true which is false which is zero. So we can replace if is zero of one by if zero.

And now we see so you see these are really tiny um modifications. Uh we could have removed the if all together for a long time already but uh want to keep every step uh as small as possible. So we see if zero and of course yeah, it's a condition that is always false so the whole if statement can be removed. Cool. That's so and that was Did you see the magic happening?

This is where the bounce check uh was removed. And now we can do some more things. Uh we again explode this complex expression into multiple assignments to new variables. And okay, this is this I think the most tricky transformation. Um if you take a look at underscore two it is I multiplied by hex 20 or by hex 20.

And I is the loop iteration counter. Uh so this means underscore two is always 0x20 times the number of iterations. And we know that multiplication is more expensive than addition. But as the code is here now, we multiply in every loop iteration anyway, so we would like to replace it by an addition. And um So what we can So and we know underscore two is 0x20 times number of iterations.

So we can write in a different way where we just add up in every iteration. And it will It's a bit tricky to find the correct start. So we pull out this underscore underscore two outside of the loop and start We have to start with minus 0x20. And uh then we can replace the multiplication by an addition. So two is two plus 0x20.

Okay. Um Yeah, we If you look at underscore three, that's just underscore two plus data. So this is kind of a similar variable um or in other words, these are all additions, so they are all associative, which means we can pull out the data to the very beginning. Um Yeah. So underscore two is So we Now the data is added to two at the very beginning and not anymore inside the loop.

Okay? And I think that's almost it already. Yeah, okay. Another thing we can do is if you look at the definition of underscore two now, um and if you insert data into that, then you see this is X plus 0x20 minus 0x20. Yeah?

So we can replace underscore two by data. Uh I know by X of course, yeah. So it was X plus 0x20 minus 0x20, so it's X. And we also see that X is unused in the rest of the program. So, we can replace underscore two by X.

Oh, that was the next step. Um we see that data is fully unused in the rest of the program, so we can remove it all together. Yeah? Uh and X is not used anymore, so there's no need to redefine it as underscore two, so we can replace underscore two by X. Okay, that's almost it, I think.

Um yeah, underscore one is only used once, so we can inline it back into the expression. And yeah, I would claim that this is the optimal program. The only thing is that the one already mentioned, we might um replace the loop iteration variable by X and add 0x20 instead of one for each iteration. But yeah, uh if you do that, then we would have to modify length. We would have to compare against length * 0x20.

And I think that can create problems with overflow. Yeah. Okay, uh that was an example of how the optimizer operates. You see that the resulting program is really short and all the intermediate steps were quite small. Um another thing we plan to do is uh memory optimizations.

Um currently Solidity does not have any memory management because in the EVM memory is usually short-lived, so it doesn't make sense to have to add the huge overhead of memory management. And this currently results in some wasted memory, especially if you for example if you allocate a memory array inside a function and do not return it, so you basically don't really use it, then it would make sense to free the memory again after the end of the function. And uh this is something we believe that the Yul optimizer can do when we introduce memory objects as um yeah first class citizens. Uh there is a version of Yul that has types and this would fit nicely into the type Yul uh dialect. Um yeah, so as a summary, I hope that the new optimizer will be safer, more transparent, and more powerful.

The main challenge here is finding good heuristics, but uh but as I explained this will not impact uh correctness and um code size is always an important uh measure whether or not to apply some transformation, but sometimes it makes sense to create larger code larger code uh in intermediate steps that can be reduced to even shorter code later. Um Yeah, uh just some quick words on the road map. We currently implemented um most of the steps we've seen here apart from the two or three loop transformations uh we've seen. And now the the uh next step is to implement these loop transformations too and uh check that all the transformations are correct. Uh and then we will apply that to the ABI coder, take the ABI coder out of experimental, and then yeah, make the rewrite of the Solidity compiler and at that point also other steps might make sense that do not make sense in the ABI coder, so we will continually improve the optimizer there.

Thanks for your attention. Mhm.