this talk is about the new you'll
optimizer and I want to start in a good
tradition I want to start with a
definition what is an optimizer 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 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 cement
equivalents but we will touch on that
later let's see an example so this is
solidity code 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 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
this thing has two problems 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 we want to optimize
for gas but if you take a closer look
then you see that yeah gas is not
yeahthere's knows not a unique thing you
can call a gas or gas usage of a smart
contract because there are at least two
the first is the gas 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 if that
actually matters later because some
routines if you 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 runtime costs
so and 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 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 you
so for the code that is inside the loop
that is executed executed more often
than the code outside of the loop so
there it's even more important that the
runtime costs are lower and you might be
fine with a little bit more 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 it is
theoretically impossible to create a
perfect optimizer and perfect optimizer
means it takes a program is 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 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 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 blockchain
smart contract execution environments
and you can show via the halting problem
that a perfect optimizer is impossible
and 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 input
program whether it halts on all inputs
or not
and because we're in on the EVM here we
replace halt by revert and this is still
true and 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 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 shorter
program that revolts 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 empty smart
contract then the input halts on all
inputs and otherwise not okay that's a
nice theoretical result but 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
optimal thing we can get quite far so
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 an optimizer allows you to write
your code in a more modular and more
understandable way so if you do not use
an optimizer and you're you care about
resource consumption and you always have
to consider oh is this is this cheap
enough what I'm writing here or not can
I change it in a way so that it's it's a
little bit cheaper and still that's the
same thing and but if you know that the
optimizer will just do that for yourself
then you can write it so that it's
readable it's auditable you are 100%
sure that it works and you don't have to
care about the resource consumption all
the time and an example of that is this
smart contract here it's a simple
fragment of a voting contract we have a
vote function which takes an output
and an outcome we want to vote and it
checks that the user has not voted yet
and it if the user hasn't voted yet it
assigns the weight of the user to the
votes and you see that this weight off
is another function that just returns
ten for the owner and one for everyone
else and without an optimizer this would
perform a function call which is costly
so a cheaper way would be to just take
this 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:1
actually is now in the way it's written
now we see yes the weight of the vote
and 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 in the rest of the talk
I will quickly describe how the current
solidity optimizer works and then
explain what we plan to do on you'll the
current optimizer is wholly based on up
code stream so it's extremely low-level
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 sub-expression 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 op codes and
chops that into blocks blocks that don't
contain jumps don't contain external
calls and some other restrictions then
these blocks are fed up code the OP code
to the component the comment 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 yeah
constant plus variable plus constant is
variable plus the sum of the constants
and so on these rules will be reused by
the you'll optimize so that's not
something we have to rewrite and after
the expression fees 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 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 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 and yeah so yeah the
takeaway from the old CC optimizer is
that it builds a gigantic internal data
structure yeah yeah and after it has
built this data structure it regenerates
the code from scratch so it starts from
the bottom up and takes a look what the
desired stack elements at the end of
this chopped up block would be then
recreates the stack elements and also
recreates changes to storage and memory
in a more efficient way because it will
really mean a limit eliminate multiple
stores to the same storage location and
multiple memory stores to the same
memory location and also if you have if
we have two expressions in the code that
do the same thing then it's only
computed once and yeah as I said the
main drawback of this component is very
opaque also it is only very local
optimizations only inside these blocks
it has no notion of functions so it
cannot
inlining and also cannot do any loop
optimizations there are some stages in
the old optimizer that look beyond these
blocks but they also do not do in lining
ok now let's take a look at at Yule and
what the new optimizer can do with it
there has been a talk I think yesterday
by Alex about Yule here at DEFCON 4 and
also another one that I've confirmed
last year we are already using Yule in
the new ABI coder and the plan is to use
Yule for everything else starting next
week so the plan is to rewrite the code
generator of solidity using Yule so that
it can target both EVM and web assembly
and we will also be able to use the
optimizer for all of the the code that
solidity generates not only for the ABI
coder yeah you'll has a simple syntax
has structural components and I think
it's quite intuitive to read but yeah
I'm already spending too much time on
that so let's take a look what the
optimizer itself instead of building a
component that looks at the code and
assembles tons of information we decided
to instead replace it by a component
that performs many tiny local
transformations to the code so every
single step of the component there's
only one so every single step of every
single component of the optimizer
there's only one single thing only one
small transformation on the yule code
and the output of each of the steps is
always again Google code so it always it
is always readable it is still text
there are no internal big internal data
structures and at every time you can
look at it and see whether the
transformation was curved
not and the optimizer also keeps the
structure of the code so it keeps
functions and loops it does not
introduce go tools and this helps us for
the translation to webassembly because
whoever simply does not have go to us it
only has functions loops and conditions
the tricky part of building the
optimizer is when it's not designing the
components but coming up with a good
strategy on when to call each component
but the good news here is that even if
this this strategy turns out to be
suboptimal it will never result in
invalid code because as long as we check
that every of these small time
transformations does its job correctly
then any combination of these steps will
always result it will also result in
correct code it might be less efficient
but it will always be correct okay now
let's take an example let's take a look
at example this is your code that
computes the sum of an array so we have
the first function that has a for loop
over the array elements and this first
function calls the second function and
the second function retrieves a single
array element so access the array and I
is the position in the array the
interesting thing here is that a ray
load performs bounds checking so array
load checks whether I is less than the
length of the array and this in the form
here it's inefficient because it's done
in every single loop iteration but 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 remove these bounds checks with
equivalent transformations so the first
thing that happens is that we explode
this 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 we can inline it so
we can replace the function call by the
body of the function so that's any more
drastic change to the
but it's simple enough and now the next
thing that happens is we 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 buddy and see
if some of the statements don't actually
depend on the iteration at all so the
only variable that is reassigned inside
the loop is some and I so everything
that is not depend on some or I or
anything that depends on somewhere I can
be pulled out of the loop and that's not
executed for every single loop iteration
but only once before the loop starts
okay so there was data and Len now we
realized that length and length they are
assigned the same value sits since it's
a memory load it's it might not be the
same value in the end 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 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 the
point where I could use a laser pointer
but so there is a less than eye length
so if is 0 less than I length revert
that is the bounce check we had in the
in the function and we realize that less
than eye 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 Len 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 bounced check
we can replace less than eye length by
true or 1 okay and now we see we have a
constant there and apply an operation on
that is zero is zero is the is EVM speak
for logical negation so is zero of one
so it's zero it's basically not true
which is false which is zero so we can
replace if it's zero of 1 by if zero and
now we see so you see these are really
tiny modifications we could have removed
the if altogether or for a long time
already but we want to keep every step
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 so
and that was did you see the magic
happening this is where the balance
check was removed and now we can do some
more things we again explode this
complex expression into multiple
assignments two new variables and ok
this is this is I think the most tricky
transformation if you take a look at
underscore 2 it is I multiplied by hex
20 or by x2 0 and I is the loop
iteration counter so this means
underscore 2 is always 0 X 20 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 the vinyl
edition and so what we can so and we
know underscore 2 is 0 X 20 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 under code underscore 2
outside of the loop and store we have to
start with minus 0 X 20
and then we can replace the
multiplication by an addition so 2 is 2
plus 0 X 20 ok yeah if you look at
underscore 3 that's just underscore 2
plus data so this is kind of a similar
variable 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 yeah so underscore 2
is so we know the data is added to 2 at
the very beginning and not anymore
inside the loop ok and I think that's
almost it already yeah ok another thing
we can do is if you look at the
definition of underscore 2 now and if
you insert data into that then you see
this is x + 0 x 20 - 0 x 20 so we can
replace underscore 2 by data I know by X
of course yeah so it was x + 0 X 2 0 - 3
X - 0 so it's X and we also see that X
is unused in the rest of the program so
we can replace underscore 2 by X now
that was the next step we see that data
is fully unused in the rest of the
program so we can remove it altogether
yeah
and X is not used anymore so there's no
need to redefine it as underscore 2 so
we can replace underscore 2 by X ok
that's almost it I think yeah underscore
one is only used one 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 one
already mentioned we might replace the
loop iteration variable by X and add 0 X
20 instead of 1 for each iteration but
yeah if you do that then we would have
to modify length we would have to
compare against length x 0 X 20
and I think that can create problems
with overflow okay 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
another thing we plan to do is memory
optimizations 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 these 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 this is something we
believe that the yule optimizer can do
when we introduce yes memory objects as
yeah first-class citizens there is a
version of you that has types and this
would fit nicely into the type Kuehl
dialect 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 per step as I explained this
will not impact correctness and yeah
code size is always an important measure
whether or not to apply some
transformation but sometimes it makes
sense to create larger court larger code
in intermediate steps that can be
reduced to even shorter code later yeah
just some quick words on the roadmap we
currently implemented most of the steps
we've seen here apart from the two or
three loop transformations we've seen
and now the next step is to implement
these loop transformations too and
check that all the transformations are
correct and then we will apply that to
the a bi coder take the ABI KOTOR out of
experimental and then ya 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
[Applause]
you