SSA CFG Yul A new viaIR backend - Moritz Hoffmann

Transcript

Hi guys, glad you can make it in such great numbers. Um, I want to take you on a small journey into the depths of SOC and how we try to improve them because right now we have a couple problems with them. And part of that is what I like to call Ssacule. And the title is kind of kind of a bit of a double title, at least the subtitle, a new VIR back end, as in we take the VIR pipeline and slap on a new stage after it. But in reality, it is also a new IR back end. And I will I will tell you what that means really in a in a second. [snorts] um to give you a

bit of motivation and background uh I first want to have a look at the performance of via VIR right now and with performance I don't mean bite code performance because you could talk about you know deployment gas you could talk about runtime gas but what I mean really is the how long does it take to invoke the compiler performance and that's not ideal at the moment with via AR and we we're going to look into that. Um, [clears throat] so a little bit of history.

Yeah, this is probably very small, but uh at the bottom left of that graph there is the version 0818 that was beginning of 2023 [snorts] and uh back then we compiled for instance layer which now compiles at 4.4 4 minutes on my home machine at about half an hour. So we already came quite away. So that's a reduction by 80%. But still 4.4 minutes is 4 minutes, right? You don't want to wait 4.4 minutes until your project compiles. So we have to do something about that. This is just a selection of projects. So we have layer

open zeppelin and I think I even squeezed in unis swap there into the graph. But uh we can also make use of our friends on Sourcify, right? Sourcify has this really nice database that you can download to your little home machine and then play with it. And that's precisely what I did. I uh took the Sourcified database, wrote a little SQL query down there, um pulled out about 6,000 contracts, compiled them, and just just checked out how long does this thing take, how how much time do I need?

And it turns out many contracts are quite fast to compile. Um some of them are relatively slow. So you can see like it's a it's a logarithmic x scale. So this goes up to 10^ the 2 seconds. So we are in the minutes regime at the tail end. But it's also not the whole story because for the the projects that take really a long time to compile are the ones that also have a lot of testing and ideally you would want to have a lot of testing and compiling these tests into source is then another aspect of it that is very time inensive.

Still this is only a outside view. Yeah, we we we want to dig deep and to dig deep we have to look at what does SOC do actually [snorts] and if you invoke SOC and let's ignore the standard JSON stuff for a second but just use the ordinary uh CLI then we can do soc-ir so we will take solidity code transform it to u and then d- optimize so there's going to be an ule optimizer and then we have maybe a couple more arguments which I just uh denoted as star arcs and then [snorts] what happens with these sources is it goes into what we call the compiler stack. It will produce ule go

into the ule stack. U is our IR right now and this u stack will then just pass and analyze the generated u optimize it assemble it. Then we have another optimization stage after the code transform. So the code transform is what transforms the stack layout. So the stackified code to EVM bite code and on top of that we have another optimization stage just purely on the assembly which is assembly optimize. And then in the end we have the resulting bite code. If you if you look at a couple of these steps you can see the ASM optimizer ASM short for assembly is relatively quick.

So is the code transform. So whenever I say code transform now I mean the stage that transforms stack layouts so stackified code to EVM bite code that is also relatively quick and what takes a majority of the time is the U optimizer so we certainly have a lot of work to do and how do you want to read this graph right um this is over the 6,000 contracts we pulled out of Sourceify and um each of these contracts is then sorted into bins. So is kind of the the time distribution over these 6,000 contracts.

So let's look at the U optimizer. What can we learn? And um what I did is I looked at layer because it takes a long time to compile and I wanted to figure out why does it take so long, right? Where are we stuck? And uh turns out it really depends on the structure of the input. And if you take an project like IGEN layer that is not really just one contract, right? But it's a it's a collection of contracts. It's I don't know, correct me if I'm wrong, but it's probably something like 120, a little bit less, I think. And um each of [clears throat] these 120 contracts has a different structure, has a different a so abstract syntax tree,

that's kind of the data representation of the code. And based on that you get different results. So here I cherrypicked something and this shows that a lot of time is spent for instance in common subp expression elimination. That's like the the topmost bar. Um, [clears throat] common subp expression elimination is something that strongly depends on data flow analysis because you have to kind of track which variable has for how long which value and then if you want to substitute something I mean Nick already mentioned how that works earlier then you have to make use of that sort of information which is kind of tough to compute. So here we have an

algorithmical problem. But if we look deeper over all of these 120 let's say contracts, we see DFA standing for data flow analysis. So DFA dependent steps cumulatively take actually less time than steps in the optimizer that are not dependent on the data flow analysis part. So we kind of have two orthogonal problems here. One is we have an algorithmic thing to solve. We want to get better at data flow analysis and the other thing is we just have a slow implementation and we need to get better at that and get better data structures think more about the algorithms how we implement them do profiling that kind of stuff. So you can

compile your projects more quickly. Um [clears throat and cough] so summing up layer takes about 5 minutes to compile a little bit less on my machine and um the the bottleneck inside the optimizer strongly depends on what kind of a we're looking at. So that that's kind of kind of the gist of it. What can we do? We can look at the SSA form. SSA stands for static signal assignment and uh I will introduce that in a second.

And this SSA form will enable us to alleviate these algorithmic problems and essentially make the data flow dependent steps of one. So kind of immediate. At the same time going to this new IR back end, we have the opportunity to rework and carefully profile a lot of the existing optimizer steps and reframe them in this new IR. So we plan to slowly bring over the current year optimizer into the SSA CFG form and then based on that really get performance boosts and what is also nice it enables us to have better algorithms for code

generation which are easily easier to maintain and fix which is good for everybody and we can also tackle stack too deep which is something that Alejandro will talk about in the next talk. So I won't go into too much detail here. [snorts] Okay. So what is S SACFG? Um the SSA CFG is comprised of one part SSA. So here we have on the left hand side something that is not SSA. We have a variable Y which is reassigned from one to two and then assigned to X.

So SSA means each variable once it is assigned is constant. Which means here we have to introduce more variables. So we we only get that at the expense of more variables. But we can make v_sub_1 equal to 1, v2 equal to two and then v3 corresponding to x on the left hand side equal to v2. And in that setting everything is constant which means if I query my uh control flow graph or my program my my program when is something set to a certain value then the answer is trivial right because once it is set it is constant it doesn't change this kind of approach is used in many

state-of-the-art compilers among them LLVM GCC gslang [snorts] and yeah I already said that data flow based optimizations are going to be more efficient which is one of the pieces and then the cfg is kind of a graph representation of the control flow. So cfg actually does stand for control flow graph. If you look at the left hand side we have an if statement. A might be the the head of the if statement where you kind of encode the um condition and then B is the conditional block. C is where the control flow then merges back together. Or you can also have for loops. So this is not just a a deck but it is something that has cycles. Yeah.

So A and B has a cycle but that could be a for loop where B is the loop body and then when you go out you move to C or on the right hand side um you would have something that is like a for loop with a break in the middle. No that's kind of a CFG representation of that. Now we can mesh the two together and we get something like this. So if we take this u snippet where we have a variable x, we mload it and then I mean this is kind of stupid code, right? But just for illustration purposes, we then check if x then we set x to mload 42 and afterwards store it. And on the on the bottom half, you can see what the ssac cfg representation of that looks like.

So we only assign variables once. And one thing that I wanted to highlight here which is kind of special for SSA CFGs is file v fi variables. That's what you can see here in block two. In block two you uh have something that depends on the graph itself. So f0 will take the value v 0 if the control flow stems from block zero and v1 if the control flow stems from block one. This is kind of how you can work around this problem of I want to assign something and then it is constant which otherwise doesn't really work. Right? If you have something that you set conditionally, you have to do something special. And that is that special trick to make the concept still work.

Okay. Um, we can also have loops, right? Then you get these back edges. I'm not going to go into that too much in the interest of time. And uh then we are pretty much ready to tackle codegen, right? How do we do codegen? So how do we take these SSA graphs and then transform them into EVM by bite code? Um this is the the current pipeline of it. So we take a U dialect which kind of is the internal representation of SOC saying I have this and that EVM version. I'm in the context of Ule objects or I'm in the context of inline assembly and it takes a dual a which could be optimized beforehand which is something that we do right now or it could also be

unoptimized which is you know fast and then later on once we have spent enough time on it we can have optimizer passes in this SSCGR and hopefully get away with a much better runtime um [clears throat] based Bas on that we construct the SSA CFG. We make a livveness analysis which is pretty much textbook. Um so that's kind of an a priori thing where you statically determine which variable is live when and for how long. I'll give you an example in a second. We also find bridges. Uh I might actually skip over that a little bit. And then we have a stack layout generation pass which

transforms the um SS ACFG based on the livveness and the bridges that I will skip uh to ST layouts. And then we have codegen. Okay. So what is livveness and um this is kind of the example that we had before just a bit more complicated. And uh in these graphs you know let's look at block six. Right? That's like the second from the right we have something that says live in and then fi3 and in in what are these brackets angled brackets I guess two that means there is a variable 53 that is going into block

six. It is used either in block six or in one of its successes and it is used at most twice. This is how to read this and the live out. Similarly says 53 is going out of the block so it has to stay live as we would say after uh finishing with this control flow block and it only has a one now. So we know in difference 53 must have been used exactly once in block six and I mean it is because that's the block where it is defined.

Um [clears throat] okay and then we can do stack layout generation and stack layout generation has kind of two phases. The first phase is inside of a block of code. Um here it's a function block. You ask yourself how does the EVM stack right the EVM is a stack machine. How does the EVM stack has to look symbolically at each step of the way so that I can execute whatever operations were implemented by the programmer that used solidity or ule right and the stack layout generation's job is to make that as efficient as possible. So here we have a function

with two arguments v_sub_1 v 0 and so we know a priori for that function if we call into that context the top of the stack must look like v1 v 0 otherwise we couldn't have called into it [snorts] and then we have an m load. Yeah and here you can see kind of on the left hand side operations that are for preparing the stack for the next operation and on the right hand side we have the operations themselves. So for the first M load, we don't need to prepare anything because we're just going to consume V 0 and emitter V2. And then for the next operation, which is an M load of 42, we have to push the 42 onto stack. So the stack changes from V1, V 0 to V1, and then V2, which is the

result of the M load before, and then the 42 and then we can execute the next M load, which will give us V3. And then we have a add function. We need to swap it around. And then in the end we want to uh emit the v4 variable or the the value of the v4 variable. [snorts] And for that we have to reduce the stack back to solely containing the v4. That means after the second to last line we have to swap one which exchanges the stack top with the element beneath it and remove that. That's the pop instruction. And this is then actually precisely what you would see in the EVM bite code in the assembly. Yeah, that's

that's how that is created. And [clears throat] now we also have funny things like if statements and loops and so on. And then we have to ask ourselves the question what do what else do we need in order to properly stackify our code? And we also have to think about you know if I have these function arguments I might have code blocks scoping and then at these boundaries of blocks I uh have to define what is the stack in and stack out. That's how we call it internally.

That means it is the stack layout that I want to achieve when calling into a specific block of code or when I am leaving a specific block of code. This is kind of a a global optimization problem then like how do I define these um these points at these interfaces of the blocks so that I get the most efficient bite code out. Yeah. And [clears throat] by using an SSCG IIR, we can do that top down, which means we can just look at operations and we have a certain input stack S, which is SN to S1. And I probably should have mentioned that, but for me, uh, mentally

the stack top is always on the right hand side. That might be confusing for some. I'm sorry, I should have said that earlier. Um [clears throat] and then in order to prepare something for a target operation what we have to take into account is first of all what are the operation arguments right and then what is life out after the operation. So what has to still be retained after the arguments of that operation have been consumed and I also want to know what is the size of the target stack and then based off that I can devise very funny and complicated algorithms which are greedy and fast and are built on a bunch of huristics like down below. I'm not

going to go into that because I just have three and a half minutes now. But uh yeah, there's a lot of fun to be had with that. Um doing it this top down meta also enables us to attack stack too deep. Yeah. So stack too deep is the situation when I need to grab too deep into the stack to produce something up top that I otherwise couldn't reach. And in this operation forward shuffling as I would call it uh we can be sure that if we need to reach into the stack then it is always due to one of the arguments and this is where the SSA property rescues us really because the SSA property tells us all right I have this

argument of the operation and now I just have to trace worst case where it was defined and I know at the point where it was defined I can just put it into memory. memory and then you know m load it and there we go and this is like one way of of dealing with it it's a bit more nuanced but I also don't want to take away too much from the next talk um [clears throat] so we're working on that in comparison right I already mentioned we're going top down so we start with for instance the function head and then top down do the stification in the current via IR pipeline the approach is bottom because there we don't have the SSA property and we don't

have explicit lightness. So what we do is we look at termination points, we look at function returns and then bottom up from these points kind of propagate the stack layout. Um and that also means that we see variables being used before they were defined which is you know maybe not the best way if you want to deal with ST too deep. Um with the SS ACFG we get a top- down uh approach. We get explicit explicit livveness and we can also handle control flow joins more constructively.

Meaning if I have two blocks and I want to join them. So for instance after an if statement where the conditional block is then um producing something then I can just pick one of the two stack layouts because I know already that all the information that I need is contained in either of them. This is like a very simple and constructive way and something that you can pretty easily bug fix. If you go bottom up you have a information disparity. you don't necessarily have the property that both um stacks or symbolic stacks contain enough information to do the join and then I have to do more complicated algorithms

which are harder to maintain. All right, this is the bridge business which we are going to skip. Then we want to stabilize the implementation and to do that we want to do a lot of fuzzing, right? We can do fuzzing in multiple ways. We can take ule, we can optimize it. We can do codegen on that and see where the compiler crashes. That's maybe not very satisfactory. We can do better than that. We can also look at bite code equivalence for instance. And bite code equivalence can be checked with the tools from our HVM friends, right? Which is pretty nice. Or we can also just fuzz the bite code itself by generating call data and then run the fuzzer on that. So that's kind of differential fuzzing

then. And we can also draw from sourcify of course. All right, I have three seconds. I hope that's enough for the outlook. So status quo, we have a prototypical implementation uh of this new IR plus codeg genen. It's still a bit rough around the edges, but you know does its thing most of the time and uh we are pretty confident we can release that into the wild relatively soon under an experimental flag. Next up would be then the stack to deep handling. So memory spilling um right now we already see in our tests that the bite code performance so gas used to deploy and run is relatively on par with the current VR pipeline which is a good sign and sometimes even beats it. And uh

because we don't really have the optimizer passes implemented yet in the SSFG IR, we can't really say uh how much faster we're going to be in the end. So it's kind of same same at the moment because we have to bring up these optimizer steps into the new IR that's pending. Yeah, that's it. Thanks. [applause] >> Awesome. Thank you so much, Moritz. We've uh briefly mentioned the SSA CFG work in the past. So it's uh it was really cool to see the inner workings of it finally. Um we have a couple of questions. Um the first one we've seen massive improvements from 10 seconds

tens of seconds to sub 1 second by just inlining all contracts into one file. Why do you think that is? >> That might be something I have to benchmark. like I I could actually imagine that it is due to the function inliner where I did see performance deficits in the past but this is like highly specific. I I would have to actually profile and benchmark this and see where it's coming from. So whoever asked this question please let me know.

Send me whatever files you're concerned with and we can see whether we can figure something out. >> Awesome. Um for compilation time why not go towards incremental compilation? >> That is something that we are exploring but it requires some deeper changes to the IR pipeline right now. And this via IR SSA CFG stuff is kind of an addendum right we we can just switch it on or off but it doesn't mess really with the internals yet. For incremental compilation we have to do more changes but it's something that we are actually considering also. Yep.

>> And how does SSA deal with relocation inside reallocation inside ifs? >> With reallocation inside ifs I mean the the reallocation would actually be a function of memory or yeah memory probably and that's not really something that SSA form is concerned with at all. it is rather something that uh has to be respected by optimization passes which do optimization over memory. So the SSA form then only really deals with the variables stack variables which point to memory locations.

>> Um will the SSA layer allow inputs other than ule? Um, right now no later theoretically, sure. I mean, it's it's just going to be some IR that you can target and then generate code with it, right? So, whoever wants to output it can use it and hopefully be happy with it. Yeah. >> Okay. Has the recent increase in call data gas cost in influenced any change on the compiler optimizer? Um, no it hasn't like not not in a in a deep sense. We haven't actually added any uh optimization passes on top of that. But

that's something we can consider. Yeah. >> Okay. And um there are two questions that are quite similar. It's uh they ask is the SSA CFG stuff included in core solidity or classic solidity? >> Both. It's it's actually something that we can do for both because classic solidity targets u which is the IR and core solidity also targets ule. So yeah win-win. >> Okay. And we have just enough time for a last one. Given the SSA is on ule does it mean it does not support memory variable like strrus etc?

uh it doesn't have memory objects at the moment but this is something that we are considering to extend ule for yeah so it's in the pipeline >> amazing thanks for all of the questions that you answered Moritz and thanks also for the talk um give it up for Moritz once again >> thank Yep.