How to solve stack too deep errors: a Yul to EVM pipeline - Alejandro Cerezo

Transcript

Okay. So, uh hello, my name is Alejandro and I'm going to present today um the project we have been working for for a year which is how to solve stuff to the errors and also present the dualm pipeline in which uh we have been working. So I'm a researcher at the complency university of Madrid and this is a project with other researchers from the Costa group and we are doing it in collaboration with the solidity team. Okay. So the premise of this talk is that in general producing byte code that handles the stack in an efficient way is very challenging because the VN is very

unique in its design. So not so much has been studied on how to operate at that level. So in this talk I'm going to present the pipeline that we have been developing. First uh showing why the AVN is unique and how it is different compared to other stackbased machines and also why the stack to problem affects the from our pipeline. H I'm going to explain uh well Morit has done all the heavy work. So now that you know what the SSA is, I'm going to explain a bit how it helps designing efficient stack layouts and also how can we can generate bite code that uses those layouts in an

efficient way. The key point on the talk is that thanks to working on this SSA representation, we can repair any kind of stack to the problem in any arbitrary situation. And finally we will uh discuss a bit uh the experimental evaluation we are performing and some conclusions. So what makes DVN different from other stackbased machines? Well the fact that other stackbased machines also rely heavily on registers whereas the doesn't have registers. So this means that other stack based machines whenever they have to perform a computation of course they use the stack but if I need to reuse

that value at any other point in the control flow graph then I store it in a register and load it when I need it. In the case of DVN we have no registers. So of course I can use either the stack or the memory regions to pass the values around. And in fact the memory becomes expensive if you use if you use it too much. So in the end you prefer to use the stack. This also leads to very uh different uh designs in their up codes because in the case of web assembly and the Java virtual machine they are very limited in the way they use the stack.

But in the case of the AVM, well, we can basically manage uh the first 16 elements we have, which gives a lot of freedom. But also passing variables through the stack has their own problems. And this is what we call the stack to the problem because in the case of the AVM, if I try to retrieve a value that is beyond def 16, I cannot do it because I have no op code that can retrieve it. And uh this is not a problem of the solidity compiler or any compiler. This is something that happens in the AVM. As an example, if we have a stack in which we have more than 16 elements and we want to use something

that is in the seventh position in the 17th position sorry while keeping all of the other variables it doesn't matter how I organize the stack I cannot access it because I cannot remove the variables in between. So in this case of course the only left option is to use the memory. Good things about uh the solidity memory layout is that it allows us to use some region of the memory as registers. So we have some kind of fix that we can do. In particular they have this free memory pointer that points to the next free position in the memory. And what we can do is uh to determine how many erh

memory positions I need uh for representing for storing the intermediate values and this is going to be my spilling region. Of course uh there are some situations that we uh we don't want to handle which are for instance memory and safe blocks or recursion. Okay. So our uh we have proposed a pipeline that it's quite similar to the new pipeline that uh Morins was discussing. So it's different in the way that we apply the code genen but the general idea is more or less similar. So we initially have this dual control flapraph in SSA form and what we do is a bottom map analysis to obtain this lifess information which is the information we are going to use

to determine how variables are passed through the stack. We also have other information that is going to help us uh designing uh good stack layouts which is this distant to next use uh dictionary but we don't care that much about that. So once I generate the stack layouts which are what Moraurice was saying we have the contents of the stack at the beginning of each block and the contents of the stack at the end of each block. And using this information together with the expressions we have to compute in each block, we can apply a code generation algorithm which in our case differs a bit from the one that that is being proposed into the solidity compiler.

So uh similarly again to Morit's idea what happens here is that in this point I can encounter stack to the problems. So what I'm going to do is to annotate them assume that at some point I have uh stores those variables in some uh region of the memory and then as a last step I'm going to do an extra phase in which I'm going to repair those accesses and also uh I'm going to apply some stack allocation techniques to do it in an efficient way which is going to generate our final bite code.

Okay. So well uh how is the dual control flow graph? Uh we have seen other examples before this is a bit more complex. So you can see that uh we have uh this is a very simple case in which we have a conditional and then we have two nested loops and uh the right uh figure is the one that represents the control flow graph which is a bit simplified but this is the idea. As you can see for instance B1 represents the uh initial uh program point inside the function. Then it jumps either to B2 and B3 and they uh are joined in before in which I have this fif function in which I decide which is the variable of the

original uh limit variable. Okay. So again uh this is uh in SSA because we can see that we have multiple functions that basically represent this uh conditional how to assign a variable in a conditional situation and we have in some of the blocks which are also like the the entries of the of the two loops we have there. So again the first step is to compute uh the lifeness analysis and for this this is some kind of bottom map analysis and the good news is that doing this analysis under SSA form is very efficient. In fact if you do it in a

non-nessa form it is a fixed point analysis which you can iterate a lot but here you can do it into passes over the control flow graph. We also compute other information that is going to be helpful but again this is like more uh technical part. What is important is that the liveness analysis is going to give us the way to decide how to propagate information using the stacks. So for instance in block one we know that the liveness analysis says that x and y are life at the beginning and at the end and this means that my stack has to contain both x and y. Okay.

So the next step is this stack layout generation phase and the good thing is that as we have the liveness analysis in the end generating a stack layout means that I have to give an order in which they appear in the stack so that later the code generation phase can assume that the variables are propagated in a certain way. In our case uh we do it in a top- down way and the reason why is that well Moritz couldn't discuss it much much but the thing is that uh there are many times in which we don't want to remove variables that are no longer used because if I remove every variable that

is no longer used this means that I have to introduce a pop instruction for each of them which would make my code really inefficient. So that's why we introduced this concept of garbage which is a way of saying okay uh there is an element that is no longer live but I can just leave it at the bottom of the stack and I can forget about it. And you can see it for instance in block six which is the block that returns the the the solution of the function. And you see that in the end I have many things in the stack but only B6 is relevant. But I don't care about the context of the stack in this situation. So I just use it and keep it everything as it is.

Okay. So just uh give you an intuition why doing it uh top down and again how this essay uh is helping us to design this stack layouts. uh initially we know that uh either the stack is empty if it's at the beginning of the program or if it is a function then I know that uh in which order the function arguments are passed. So I know initially which is the inner stack of the first block in this case B1. So what I do in our stack layout generation algorithm is that at each point I propagate the information so that I can u I assume I I can compute the inner stack of the successor blocks and we see that in the middle control

flow graph in which you say okay uh I propagate uh the the out stack of B1 and then B3 and B2 must have the same stack because in the they are joined uh together. One goes after the other. So if I have those contents of the stack at the at the end of V1, then I have them also at the beginning of B2 and B3. The trick here or the the point on using SSA is that SSA makes it easier to decide how to propagate these stacks and we see it when we want to generate the outst of a tree. In this case, uh I have two blocks that jump into the same one

before. So I have to ensure that before uh their inner stack is compatible with the other two because they are joined together. So the way I do it is first decide uh how the stack of before is propagated which in this case is like this and then the thanks to the fif functions we can uh propagate it to their predecessors and just fix the out stack of those blocks so that they are joined together. Okay and the good thing is again that using SSA makes it easier to decide how to do this unification.

Okay. So the next step is the back code generation. So now we know how uh the contents of the stack at the beginning of the block at the end of the block and also I know which expressions I have to compute. Okay. So what I have to do is try to use the stack efficiently to generate bite code that produces uh well that computes everything that needs to be computed. So in this case uh we propose a greedy algorithm that it's again top down but not only uh we have to do this thing of uh fixing the layouts in between but we also choose in which order we want to perform the computations because this is beneficial in the way that we can build the code.

When we encounter a situation in which an element is too deep to be accessed, what we do is introduce an annotation which is called the virtual get that just says okay at this point I have to retrieve it from memory. I'll solve it in a later step. In our previous example, if we assume that uh the maximum stack def I can access is four, then I would have these two big represent that those ones must go through the memory. Okay, so how the grid algorithm works is that it is an iterative algorithm that chooses an action at each point that transforms the inner stack into the outer stack and these actions can be either popping the topmost element if it

it is not used elsewhere. We can place a variable in their corresponding position in the final stack and this is done in terms of the bottom of the stack because one place in that position it does not need to be moved elsewhere or the most common one is just choosing the next computation to perform. Okay. And when there are no computations chosen I have computed everything. So the stack I have is a permutation of the one I want to achieve. So if I have to do some other changes I do it at that stage. Okay, so now we go into the more technical part which is how I repair these arachable accesses. So the idea here as I said is that in the previous

phase uh we have marked uh with virtual gets all the places in which I need to retrieve a variable from the memory. And in fact what I want to do is to replace this virtual get with a push to the memory uh address in which I have that uh variable and then do an load to just load it. Okay. So the key idea on doing it in a general efficient way is that everything we have done so far is preserving this SSA form. So this means that we have access to existing techniques that use the SS form for propagating the variables using registers. In our case it's the memory but in practice we are using it

similarly to registers. Okay. But uh to apply these techniques there are two things that we have to do. The first one is to identify which fe functions are involved and I'll give you an intuition on why f functions in particular are relevant in this context and then I have to decide where I introduce them store. So if I for instance before had the big get for variable B2 then I also have to do at some point in store that stores it in the corresponding memory region.

Okay. So the first part uh is identifying few functions. So here the idea is that for every computation that we do usually we know that it appears at the top of the stack. So I know that there is a point in which I can duplicate it and store it in memory. This strategy preserves uh all the layouts I had so far. So I'm not breaking anything but also uh yeah this is the way to go for very simple cases. It works. The burles are f functions. And what happens with the functions is that as they are like basically saying okay combine these variables they might not appear at the top of the stack and they must be even very deep to be

accessed. So I cannot just duplicate it and store in memory. So uh this is another example in which we have uh two virtual gets two variables defined buffy functions and in this case uh what I'm going to show you later is that uh solving this v5 and v6 also triggers other variables to be passed uh through the registers. Okay. Then uh once I know everything that must go into registers uh I have to decide when or where in which program point they are stored. So of course I could uh just store them when they are computed but again uh as we are we have the stack layouts that preserve all the

information that we had so far. It is better to do it in a lower point because this allows us to reuse more registers and not to use so much memory. Okay. Again this is very technical but just to give you an intuition. So we decide where things are stored and uh again we can do this in an efficient way thanks to the SSA in a nonssa setting. This is not that easy because I have to perform decide where to store all variables in well you would like to have it in just one pass and this is thanks to the SSA.

So this would be uh the code that would be generated. As you can see uh handling f functions can affect different blocks and different variables. In fact uh variables b1, b2 and b4 must be duplicated and stored. Whereas in the initial setting we don't have this. But again uh the idea here I want to emphasize is does this work for any situation. So because we are working with f functions it doesn't matter how complex our control for graph is we can do this trick and we can solve it in just linear passes so this is basically the whole pipeline that we have developed. Okay going back to the initial example uh how do we

replace this virtual get annotations by actual code. So as I said before we can use uh memory address 80 which is the first one that is available to use in the in the solidity layout and I just load the variable from that region and in block four what I do is to store v2 in memory using store okay and this is the two extra passes that I have explained before okay so now I'm going to discuss a bit about the implementation and the experimental evaluation so this This this has been implemented as an independent tool from the sal compiler because the um code generation algorithm was already part of another

implementation and that's also why we have it in Python but it is available online. So I'm going to present the results for two evaluation data sets. The one the first one is the solidity benchmark set which explores uh different situations and of course we are passing it with our pipeline and the second one are a very well they are 16 contracts that we have downloaded from source file that are producing a stack to deep errors in the latest sie version as you may imagine uh people doesn't publish u contracts with a stack to deep so it is very difficult to find the situations in which we can apply our our our pipeline.

So for benchmar uh we are achieving savings in number of instructions uh the number of bytes and uh an estimation on the total gas and this is because we are doing uh moving things in a better way. So that's why we are showing like all the different parameters for a fair comparison in the case of benchmark uh we are repairing all the stack to the cases. Okay. But uh as they were at some point um they could uh the soulc compiler at some point could generate code. They are mild stack to the errors.

They are not so complex. So what we said was like okay let's take again the first benchmark and we're going to say that instead of being able to access position 16 now we can only access till position 8. And suddenly of course we have a lot of stack to deep errors. So we tried with again with a benchmar and we solve all this stack 2D. Of course the code is worse in this case but because we don't have that much freedom to manage the stack in an efficient way.

Uh a bit of the experimental evaluation again uh consider that we are working in Python. So our tool of course is uh is going to be a bit slower but not that much. And what is interesting is the graph on the right in which we saw the times uh for the different uh phases in our layout generation. And what we see is that right now what is taking the longest is the control for graph generation done by the solidity compiler which seems to indicate that yeah uh the analysis we are doing and the layout generation that we repair in the end are uh linear passes there are multiple of them but they are linear so they behave quite well when the code grows

okay so in this just to conclude in this talk I have presented the pipeline of the great tool in which we are generating even bite code from the dual control floors representation it is quite similar to the ideas mor has said but uh like we are using a different code gen that is like more flexible for some themes and the good thing is that uh we are addressing this stack to problem in an efficient way for uh general cases so this project has been on going ongoing for uh a bit more than a year. So we have been discussing on the best way to do the to exchange format between uh the dual control for representation from the

sol compiler and also we have done a lot of debugging together with them because in the end uh having a stable version that works that passes all the test shows a lot of uh bugs to fix and uh one of the main limitations that we are having so far is that this dual control for that is generated from the compiler is missing some optimization passes because these optimization passes are being done at the level of the EV by bite code in the compiler. So we don't have access to them and the ones that are more relevant than the functioning lining and also some redundant C elimination that make it quite difficult to compare hto block with their um with their pipeline. So this hopefully at

some point is going to be uh improved so that we can apply our pipeline like a as a last step in the in the generation phase. So uh for the future uh we have several ideas we want to so our fix now preserves all the stack layouts but we would also would like to remove uh variables from the stack layout so that we can solve uh some stack collateral stack to dips and this is something that we are working on that having this kind of stack pressure and deciding to just from the beginning move it to the to the memory we don't want to use it in the stack We also want to improve the heristics for handling garbage because uh

this is I think one of the most crucial parts on doing on generating good bite code. A good way to handle this garbage. And finally uh we also are exploring better ways to do the greedy algorithm and in particular we want to find better ways to choose the order in which we perform these computations. So that would be all. Thank you. So now the the the tool is available online. Uh we have to document it because so far like we have been working on having it stable but just if if you want to see it. Thank you.

[applause] >> Thank you so much Alejandra. We have quite a few questions already. So I will be delivering the questions to you. Um the first one is why don't we make use of transient variables instead of memory to solve the stack to deep problem. >> Why don't we sorry >> why don't we make use of transient variables >> instead of memory. >> I so memory I refer the the normal memory that it's like the the cheapest one. So I think the the trans storage doesn't make sense to use because it's uh more expensive to use. So we prefer to use it just the memory. we don't need to do more complex things.

>> Okay. And someone also asked um that shouldn't this memory dduplication strategy make the code more expensive? >> So >> why are we seeing gas saving in the benchmark? >> So the thing is that uh the stack lay layout generation thing uh preserves the variables in the same order. So we don't have to be swapping things around. So most of these savings can because uh we are trying to do it. So maybe I haven't uh given much emphasis there but what we try to do with the stack layout uh generation phase as an isolated phase is to have uh stack layouts that don't move things around. So we are achieving savings because we are not moving things

around. Even if the stack too deep errors occur, we are being very careful to avoid them as much as possible. And this is why we are having some gains compared to the to now to the VI pipeline. Now >> awesome. Um, another question. Can you expand on what optimization metric is used to select which variable will be moved to the memory? >> So far, uh, well that is part of the of the so far the only variables that we are moving to memory are those ones that uh, produce some kind of stack to errors. So if I understand it, this means a part of the related work we want to do and for that uh probably we'll

have so in in SSA in already existing techniques for SSA in registers there is this notion of pressure and there are metrics based on on how many st on how many registers I I'm using them too much and we would have something similar to that idea. Okay, but we still have to to explore it in more details. So the idea would be like to choose those variables that uh if I just pass it only through memory then their variables are freed as a result. So they don't have to they don't have a stack to the problems.

>> Okay. Um could we make variables share stack slots? >> Sorry. >> Could we make the variables share stack slots? >> Yes. stack >> share the stack slots like two UN 188 128 or four Uint 64 variables can we make them share the slots >> uh to share slots for what sorry I I don't understand the >> anyone who asked the question do you want to elaborate on the question any takers for this question please if not then we can also ah Okay,

>> it's not my question, but I can explain the idea that in storage we usually put multiple values to the same slot because slots are so expensive >> and given that SL slack slots are just words of 32 bytes. I'm guessing the question is whether it would make sense to put multiple variables that are smaller than 32 bytes together in the same location. I think it could make sense but it's uh different thing or well it's a difficult thing to do in a good way but the good thing is that when you do the stack allocation techniques you have like all the freedom to choose the way in which you store uh things together. So if you detected some kind of situation in which that would be viable, you could do it. But for now, we haven't explored it because we understand that's quite difficult now to

to manage. We assume like every variable has their own uh is stored independently in their own address and that's all. But of course that would be a nice thing to to consider. Yeah, thank you. >> Okay, one last question. Would it not be preferable to duplicate or swap a value before it gets too deep instead of using memory? >> The thing with uh yeah in general uh you would like to do that but the thing that we are the thing we are doing in the stack layout generation phase is that uh we try to avoid these situations directly because we construct the stack layouts in a way that everything that is going to be used uh soon appears on the

top. So we can do some kind of tricks to address uh this part and in fact we are doing them but uh this is done like at the level of the stack layout generation phase not at the level of the bode generation. So in the end uh the stack layout generation phase there are very uh specific properties that your layouts have to verify so you can work following that idea. Yeah. So we are doing some tricks there to to to make things appear again at the top or uh by designing uh in a top down way this stack layouts.

>> Thank you so much Alejandro. That will be your time. Thank you.