The following content is
provided under a Creative Commons license. Your support will help
MIT OpenCourseWare continue to offer high-quality
educational resources for free. To make a donation or to
view additional materials from hundreds of MIT courses,
visit MIT OpenCourseWare at ocw.mit.edu. CHARLES E. LEISERSON: Hi,
it's my great pleasure to introduce, again, TB Schardl. TB is not only a fabulous,
world-class performance engineer, he is a world-class
performance meta engineer. In other words, building the
tools and such to make it so that people can
engineer fast code. And he's the author
of the technology that we're using in
our compiler, the taper technology that's in the open
compiler for parallelism. So he implemented all of that,
and all the optimizations, and so forth, which has
greatly improved the quality of the programming environment. So today, he's going to talk
about something near and dear to his heart,
which is compilers, and what they can and cannot do. TAO B. SCHARDL:
Great, thank you very much for that introduction. Can everyone hear
me in the back? Yes, great. All right, so as
I understand it, last lecture you talked about
multi-threaded algorithms. And you spent the lecture
studying those algorithms, analyzing them in a
theoretical sense, essentially analyzing their
asymptotic running times, work and span complexity. This lecture is not that at all. We're not going to
do that kind of math anywhere in the course
of this lecture. Instead, this lecture is going
to take a look at compilers, as professor mentioned, and what
compilers can and cannot do. So the last time, you
saw me standing up here was back in lecture five. And during that
lecture we talked about LLVM IR and
x8664 assembly, and how C code got translated
into assembly code via LLVM IR. In this lecture,
we're going to talk more about what happens between
the LLVM IR and assembly stages. And, essentially, that's what
happens when the compiler is allowed to edit and optimize the
code in its IR representation, while it's producing
the assembly. So last time, we were
talking about this IR, and the assembly. And this time, they called
the compiler guy back, I suppose, to tell you about
the boxes in the middle. Now, even though you're
predominately dealing with C code within this class, I hope
that some of the lessons from today's lecture you will be able
to take away into any job that you pursue in the future,
because there are a lot of languages today that do end
up being compiled, C and C++, Rust, Swift, even
Haskell, Julia, Halide, the list goes on and on. And those languages
all get compiled for a variety of
different what we call backends, different machine
architectures, not just x86-64. And, in fact, a lot
of those languages get compiled using very
similar compilation technology to what you have in
the Clang LLVM compiler that you're using in this class. In fact, many of
those languages today are optimized by LLVM itself. LLVM is the internal
engine within the compiler that actually does all
of the optimization. So that's my hope, that the
lessons you'll learn here today don't just apply to 172. They'll, in fact,
apply to software that you use and develop
for many years on the road. But let's take a step
back, and ask ourselves, why bother studying the
compiler optimizations at all? Why should we take
a look at what's going on within this, up to this
point, black box of software? Any ideas? Any suggestions? In the back? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: You
can avoid manually trying to optimize things
that the compiler will do for you, great answer. Great, great answer. Any other answers? AUDIENCE: You learn
how to best write your code to take advantages
of the compiler optimizations. TAO B. SCHARDL:
You can learn how to write your code to take
advantage of the compiler optimizations, how to suggest
to the compiler what it should or should not do as
you're constructing your program, great
answer as well. Very good, in the front. AUDIENCE: It might
help for debugging if the compiler has bugs. TAO B. SCHARDL:
It can absolutely help for debugging when the
compiler itself has bugs. The compiler is a big
piece of software. And you may have noticed that a
lot of software contains bugs. The compiler is no exception. And it helps to understand where
the compiler might have made a mistake, or where the
compiler simply just didn't do what you thought
it should be able to do. Understanding more of what
happens in the compiler can demystify some
of those oddities. Good answer. Any other thoughts? AUDIENCE: It's fun. TAO B. SCHARDL: It's fun. Well, OK, so in my
completely biased opinion, I would agree that
it's fun to understand what the compiler does. You may have different opinions. That's OK. I won't judge. So I put together
a list of reasons why, in general, we
may care about what goes on inside the compiler. I highlighted that last
point from this list, my bad. Compilers can have a really
big impact on software. It's kind of like this. Imagine that you're working
on some software project. And you have a
teammate on your team he's pretty quiet
but extremely smart. And what that teammate does
is whenever that teammate gets access to some
code, they jump in and immediately start trying
to make that code work faster. And that's really cool, because
that teammate does good work. And, oftentimes, you see that
what the teammate produces is, indeed, much faster
code than what you wrote. Now, in other industries,
you might just sit back and say, this teammate
does fantastic work. Maybe they don't
talk very often. But that's OK. Teammate, you do you. But in this class, we're
performance engineers. We want to understand what that
teammate did to the software. How did that teammate get
so much performance out of the code? The compiler is kind
of like that teammate. And so understanding
what the compiler does is valuable in that sense. As mentioned before,
compilers can save you performance engineering work. If you understand
that the compiler can do some optimization
for you, then you don't have to do it yourself. And that means that
you can continue writing simple, and readable,
and maintainable code without sacrificing performance. You can also understand the
differences between the source code and whatever you might
see show up in either the LLVM IR or the assembly,
if you have to look at the assembly language
produced for your executable. And compilers can make mistakes. Sometimes, that's because of
a genuine bug in the compiler. And other times, it's
because the compiler just couldn't understand something
about what was going on. And having some insight into how
the compiler reasons about code can help you understand why
those mistakes were made, or figure out ways to work
around those mistakes, or let you write meaningful
bug reports to the compiler developers. And, of course,
understanding computers can help you use them
more effectively. Plus, I think it's fun. So the first thing to
understand about a compiler is a basic anatomy of
how the compiler works. The compiler takes
as input LLVM IR. And up until this
point, we thought of it as just a big black box. That does stuff to the IR,
and out pops more LLVM IR, but it's somehow optimized. In fact, what's going
on within that black box the compiler is
executing a sequence of what we call transformation
passes on the code. Each transformation pass
takes a look at its input, and analyzes that
code, and then tries to edit the code in
an effort to optimize the code's performance. Now, a transformation pass might
end up running multiple times. And those passes
run in some order. That order ends up being
a predetermined order that the compiler
writers found to work pretty well on their tests. That's about the
level of insight that went into picking the order. It seems to work well. Now, some good news,
in terms of trying to understand what
the compiler does, you can actually just ask the
compiler, what did you do? And you've already used
this functionality, as I understand, in some
of your assignments. You've already
asked the compiler to give you a
report specifically about whether or not it
could vectorize some code. But, in fact, LLVM, the
compiler you have access to, can produce reports not
just for factorization, but for a lot of the
different transformation passes that it tries to perform. And there's some
syntax that you have to pass to the compiler,
some compiler flags that you have to specify in
order to get those reports. Those are described
on the slide. I won't walk you
through that text. You can look at the
slides afterwards. At the end of the day, the
string that you're passing is actually a
regular expression. If you know what
regular expressions are, great, then you can
use that to narrow down the search for your report. If you don't, and you just
want to see the whole report, just provide dot star as a
string and you're good to go. That's the good news. You can get the compiler to
tell you exactly what it did. The bad news is that when you
ask the compiler what it did, it will give you a report. And the report looks
something like this. In fact, I've highlighted
most of the report for this particular
piece of code, because the report ends
up being very long. And as you might
have noticed just from reading some of the
texts, there are definitely English words in this text. And there are pointers to pieces
of code that you've compiled. But it is very jargon,
and hard to understand. This isn't the easiest
report to make sense of. OK, so that's some good
news and some bad news about these compiler reports. The good news is, you
can ask the compiler. And it'll happily tell you all
about the things that it did. It can tell you about which
transformation passes were successfully able to
transform the code. It can tell you
conclusions that it drew about its analysis of the code. But the bad news
is, these reports are kind of complicated. They can be long. They use a lot of internal
compiler jargon, which if you're not familiar
with that jargon, it makes it hard to understand. It also turns out that not
all of the transformation passes in the compiler give
you these nice reports. So you don't get to
see the whole picture. And, in general, the
reports don't really tell you the whole story
about what the compiler did or did not do. And we'll see another
example of that later on. So part of the goal
of today's lecture is to get some context for
understanding the reports that you might see if you pass
those flags to the compiler. And the structure
of today's lecture is basically divided
up into two parts. First, I want to give
you some examples of compiler optimizations,
just simple examples so you get a sense as to how a
compiler mechanically reasons about the code it's given, and
tries to optimize that code. We'll take a look at how
the compiler optimizes a single scalar value, how
it can optimize a structure, how it can optimize
function calls, and how it can optimize
loops, just simple examples to give some flavor. And then the second
half of lecture, I have a few case
studies for you which get into diagnosing ways
in which the compiler failed, not due to bugs,
per se, but simply didn't do an optimization you
might have expected it to do. But, to be frank, I
think all those case studies are really cool. But it's not totally
crucial that we get through every single case
study during today's lecture. The slides will be
available afterwards. So when we get to
that part, we'll just see how many case
studies we can cover. Sound good? Any questions so far? All right, let's get to it. Let's start with
a quick overview of compiler optimizations. So here is a summary
of the various-- oh, I forgot that I
just copied this slide from a previous lecture
given in this class. You might recognize this slide
I think from lecture two. Sorry about that. That's OK. We can fix this. We'll just go ahead and
add this slide right now. We need to change the title. So let's cross that out
and put in our new title. OK, so, great, and now we
should double check these lists and make sure that
they're accurate. Data structures, we'll come
back to data structures. Loops, hoisting, yeah, the
compiler can do hoisting. Sentinels, not
really, the compiler is not good at sentinels. Loop unrolling, yeah, it
absolutely does loop unrolling. Loop fusion, yeah,
it can, but there are some restrictions that apply. Your mileage might vary. Eliminate waste iterations,
some restrictions might apply. OK, logic, constant folding
and propagation, yeah, it's good on that. Common subexpression
elimination, yeah, I can find common subexpressions,
you're fin there. It knows algebra, yeah good. Short circuiting,
yes, absolutely. Ordering tests,
depends on the tests-- I'll give it to the compiler. But I'll say,
restrictions apply. Creating a fast path,
compilers aren't that smart about fast paths. They come up with really
boring fast paths. I'm going to take
that off the list. Combining tests, again, it
kind of depends on the tests. Functions, compilers are
pretty good at functions. So inling, it can do that. Tail recursion elimination,
yes, absolutely. Coarsening, not so much. OK, great. Let's come back to
data structures, which we skipped before. Packing, augmentation--
OK, honestly, the compiler does a lot with data
structures but really none of those things. The compiler isn't smart
about data structures in that particular way. Really, the way
that the compiler is smart about data
structures is shown here, if we expand this list to
include even more compiler optimizations. Bottom line with data
structures, the compiler knows a lot about architecture. And it really has
put a lot of effort into figuring out how to use
registers really effectively. Reading and writing and
register is super fast. Touching memory is not so fast. And so the compiler works really
hard to allocate registers, put anything that lives in memory
ordinarily into registers, manipulate aggregate
types to use registers, as we'll see in a couple
of slides, align data that has to live in memory. Compilers are good at that. Compilers are also
good at loops. We already saw some
example optimization on the previous slide. It can vectorize. It does a lot of
other cool stuff. Unswitching is a
cool optimization that I won't cover here. Idiom replacement, it
finds common patterns, and does something
smart with those. Vision, skewing, tiling,
interchange, those all try to process the iterations
of the loop in some clever way to make stuff go fast. And some restrictions apply. Those are really in
development in LLVM. Logic, it does a lot more with
logic than what we saw before. It can eliminate instructions
that aren't necessary. It can do strength reduction,
and other cool optimization. I think we saw that one
in the Bentley slides. It gets rid of dead code. It can do more
idiom replacement. Branch reordering is kind
like reordering tests. Global value numbering,
another cool optimization that we won't talk about today. Functions, it can do
more on switching. It can eliminate arguments
that aren't necessary. So the compiler can do
a lot of stuff for you. And at the end the day,
writing down this whole list is kind of a futile activity
because it changes over time. Compilers are a moving target. Compiler developers,
they're software engineers like you and me. And they're clever. And they're trying to apply
all their clever software engineering practice to
this compiler code base to make it do more stuff. And so they are constantly
adding new optimizations to the compiler, new clever
analyses, all the time. So, really, what we're
going to look at today is just a couple examples
to get a flavor for what the compiler does internally. Now, if you want to follow along
with how the compiler works, the good news is,
by and large, you can take a look at
the LLVM IR to see what happens as the compiler
processes your code. You don't need to
look out the assembly. That's generally true. But there are some exceptions. So, for example, if we have
these three snippets of C code on the left, and we look at what
your LLVM compiler generates, in terms of the IR,
we can see that there are some optimizations
reflected, but not too many interesting ones. The multiply by 8 turns into
a shift left operation by 3, because 8 is a power of 2. That's straightforward. Good, we can see that in the IR. The multiply by 15 still
looks like a multiply by 15. No changes there. The divide by 71 looks
like a divide by 71. Again, no changes there. Now, with arithmetic
ops, the difference between what you
see in the LLVM IR and what you see
in the assembly, this is where it's
most pronounced, at least in my
experience, because if we take a look at these
same snippets of C code, and we look at the corresponding
x86 assembly for it, we get the stuff on the right. And this looks different. Let's pick through
what this assembly code does one line at a time. So the first one in the C
code, takes the argument n, and multiplies it by 8. And then the assembly, we
have this LEA instruction. Anyone remember what the
LEA instruction does? I see one person
shaking their head. That's a perfectly
reasonable response. Yeah, go for it? Load effective address,
what does that mean? Load the address, but don't
actually access memory. Another way to phrase that,
do this address calculation. And give me the result of
the address calculation. Don't read or write
memory at that address. Just do the calculation. That's what loading an effective
address means, essentially. But you're exactly right. The LEA instruction does
an address calculation, and stores the result in
the register on the right. Anyone remember enough about
x86 address calculations to tell me how that LEA in
particular works, the first LEA on the slide? Yeah? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: But before
the first comma, in this case nothing, gets added to the
product of the second two arguments in those parens. You're exactly right. So this LEA takes the value
8, multiplies it by whatever is in register RDI,
which holds the value n. And it stores the
result into AX. So, perfect, it does
a multiply by 8. The address calculator is
only capable of a small range of operations. It can do additions. And it can multiply
by 1, 2, 4, or 8. That's it. So it's a really simple
circuit in the hardware. But it's fast. It's optimized heavily
by modern processors. And so if the
compiler can use it, they tend to try to use
these LEA instructions. So good job. How about the next one? Multiply by 15 turns into
these two LEA instructions. Can anyone tell
me how these work? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: You're
basically multiplying by 5 and multiplying by
3, exactly right. We can step through
this as well. If we look at the
first LEA instruction, we take RDI, which
stores the value n. We multiply that by 4. We add it to the
original value of RDI. And so that computes 4 times n,
plus n, which is five times n. And that result
gets stored into AX. Could, we've effectively
multiplied by 5. The next instruction
takes whatever is in REX, which is now 5n,
multiplies that by 2, adds it to whatever is currently in
REX, which is once again 5n. So that computes 2
times 5n, plus 5n, which is 3 times 5n, which is 15n. So just like that,
we've done our multiply with two LEA instructions. How about the last one? In this last piece of code,
we take the arguments in RDI. We move it into EX. We then move the
value 3,871,519,817, and put that into
ECX, as you do. We multiply those
two values together. And then we shift the
product right by 38. So, obviously,
this divides by 71. Any guesses as to
how this performs the division operation we want? Both of you answered. I might still call on you. give a little more
time for someone else to raise their hand. Go for it. AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: It has a lot to
do with 2 to the 38, very good. Yeah, all right,
any further guesses before I give the answer away? Yeah, in the back? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: Kind of. So this is what's technically
called a magic number. And, yes, it's technically
called a magic number. And this magic
number is equal to 2 to the 38, divided by 71, plus
1 to deal with some rounding effects. What this code does
is it says, let's compute n divided by 71, by
first computing n divided by 71, times 2 to the 38, and
then shifting off the lower 38 bits with that shift
right operation. And by converting the
operation into this, it's able to replace
the division operation with a multiply. And if you remember, hopefully,
from the architecture lecture, multiply operations, they're
not the cheapest things in the world. But they're not too bad. Division is really expensive. If you want fast
code, never divide. Also, never compute
modulus, or access memory. Yeah, question? AUDIENCE: Why did you choose 38? TAO B. SCHARDL: Why
did I choose 38? I think it shows 38
because 38 works. There's actually a formula for-- pretty much it
doesn't want to choose a value that's too large,
or else it'll overflow. And it doesn't want to choose
a value that's too small, or else you lose precision. So it's able to find
a balancing point. If you want to know more
about magic numbers, I recommend checking out this
book called Hackers Delight. For any of you who are
familiar with this book, it is a book full of bit tricks. Seriously, that's
the entire book. It's just a book
full of bit tricks. And there's a whole
section in there describing how you do division by various
constants using multiplication, either signed or unsigned. It's very cool. But magic number to
convert a division into a multiply, that's
the kind of thing that you might see
from the assembly. That's one of these examples
of arithmetic operations that are really optimized
at the very last step. But for the rest of
the optimizations, fortunately we can
focus on the IR. Any questions about that so far? Cool. OK, so for the next
part of the lecture, I want to show you a couple
example optimizations in terms of the LLVM IR. And to show you
these optimizations, we'll have a little bit of
code that we'll work through, a running example, if you will. And this running example
will be some code that I stole from I think it was
a serial program that simulates the behavior of n massive
bodies in 2D space under the law of gravitation. So we've got a whole
bunch of point masses. Those point masses
have varying masses. And we just want
to simulate what happens due to gravity as these
masses interact in the plane. At a high level, the n
body code is pretty simple. We have a top level
simulate routine, which just loops
over all the time steps, during which we want
to perform this simulation. And at each time step, it
calculates the various forces acting on those
different bodies. And then it updates the
position of each body, based on those forces. In order to do that calculation. It has some internal
data structures, one to represent each
body, which contains a couple of vector types. And we define our
own vector type to store to double precision
floating point values. Now, we don't need to see
the entire code in order to look at some
compiler optimizations. The one routine that
we will take a look at is this one to
update the positions. This is a simple loop that
takes each body, one at a time, computes the new
velocity on that body, based on the forces
acting on that body, and uses vector
operations to do that. Then it updates the
position of that body, again using these vector
operations that we've defined. And then it stores the results
into the data structure for that body. So all these methods
with this code make use of these basic routines
on 2D vectors, points in x, y, or points in 2D space. And these routines
are pretty simple. There is one to add two vectors. There's another to scale a
vector by a scalar value. And there's a third to compute
the length, which we won't actually look at too much. Everyone good so far? OK, so let's try
to start simple. Let's take a look at just
one of these one line vector operations, vec scale. All vec scale does is it takes
one of these vector inputs at a scalar value a. And it multiplies x by a, and
y by a, and stores the results into a vector type,
and return to it. Great, couldn't be simpler. If we compile this with no
optimizations whatsoever, and we take a look
at the LLVM IR, we get that, which is a
little more complicated than you might imagine. The good news, though, is that
if you turn on optimizations, and you just turn on the first
level of optimization, just 01, whereas we got this code before,
now we get this, which is far, far simpler, and so simple I
can blow up the font size so you can actually read the
code on the slide. So to see, again, no
optimizations, optimizations. So a lot of stuff happened to
optimize this simple function. We're going to see what those
optimizations actually were. But, first, let's
pick apart what's going on in this function. We have our vec scale
routine in LLVM IR. It takes a structure
as its first argument. And that's represented
using two doubles. It takes a scalar as
the second argument. And what the operation does
is it multiplies those two fields by the third
argument, the double A. It then packs those values
into a struct that'll return. And, finally, it
returns that struct. So that's what the
optimized code does. Let's see actually how we
get to this optimized code. And we'll do this
one step at a time. Let's start by optimizing the
operations on a single scalar value. That's why I picked
this example. So we go back to the 00 code. And we just pick out
the operations that dealt with that scalar value. We our scope down
to just these lines. So the argument double A is
the final argument in the list. And what we see is that
within the vector scale routine, compiler to 0, we
allocate some local storage. We store that double A
into the local storage. And then later on,
we'll load the value out of the local storage
before the multiply. And then we load it again
before the other multiply. OK, any ideas how we could
make this code faster? Don't store in memory,
what a great idea. How do we get around not
storing it in memory? Saving a register. In particular, what property of
LLVM IR makes that really easy? There are infinite registers. And, in fact, the argument
is already in a register. It's already in the register
percent two, if I recall. So we don't need to
move it into a register. It's already there. So how do we go about optimizing
that code in this case? Well, let's find the places
where we're using the value. And we're using the
value loaded from memory. And what we're going to do
is just replace those loads from memory with the
original argument. We know exactly what
operation we're trying to do. We know we're trying
to do a multiply by the original parameter. So we just find those two uses. We cross them out. And we put in the input
parameter in its place. That make sense? Questions so far? Cool. So now, those multipliers
aren't using the values returned by the loads. How further can we
optimize this code? Delete the loads. What else can we delete? So there's no address
calculation here just because the code is so
simple, but good insight. The allocation and
the store, great. So those loads are dead code. The store is dead code. The allocation is dead code. We eliminate all that dead code. We got rid of those loads. We just used the value
living in the register. And we've already eliminated
a bunch of instructions. So the net effect of that was
to turn the code optimizer at 00 that we had in the background
into the code we have in the foreground, which
is slightly shorter, but not that much. So it's a little bit faster,
but not that much faster. How do we optimize
this function further? Do it for every
variable we have. In particular, the only
other variable we have is a structure that
we're passing in. So we want to do this kind of
optimization on the structure. Make sense? So let's see how we
optimize this structure. Now, the problem
is that structures are harder to handle than
individual scalar values, because, in general, you can't
store the whole structure in just a single register. It's more complicated
to juggle all the data within a structure. But, nevertheless,
let's take a look at the code that operates
on the structure, or at least operates
on the structure that we pass in to the function. So when we eliminate
all the other code, we see that we've
got an allocation. See if I animations
here, yeah, I do. We have an allocation. So we can store the
structure onto the stack. Then we have an
address calculation that lets us store the
first part of the structure onto the stack. We have a second
address calculation to store the second
field on the stack. And later on, when
we need those values, we load the first
field out of memory. And we load the second
field out of memory. It's a very similar pattern
to what we had before, except we've got more
going on in this case. So how do we go about
optimizing this structure? Any ideas, high level ideas? Ultimately, we want to get
rid of all of the memory references and all that
storage for the structure. How do we reason through
eliminating all that stuff in a mechanical fashion, based
on what we've seen so far? Go for it. AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: They are passed
in using separate parameters, separate registers if you will,
as a quirk of how LLVM does it. So given that insight,
how would you optimize it? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: Cross out
percent 12, percent 6, and put in the relevant field. Cool. Let me phrase that a
little bit differently. Let's do this one
field at a time. We've got a structure,
which has multiple fields. Let's just take it
one step at a time. All right, so let's
look at the first field. And let's look at the operations
that deal with the first field. We have, in our code, in
our LLVM IR, some address calculations that refer to the
same field of the structure. In this case, I believe
it's the first field, yes. And, ultimately, we end up
loading from this location in local memory. So what value is this
load going to retrieve? How do we know that both
address calculations refer to the same field? Good question. What we do in this case
is very careful analysis of the math that's going on. We know that the alga, the
location in local memory, that's just a fixed location. And from that, we can interpret
what each of the instructions does in terms of an
address calculation. And we can determine that
they're the same value. So we have this location in
memory that we operate on. And before you do a
multiply, we end up loading from that
location in memory. So what value do we know is
going to be loaded by that load instruction? Go for it. AUDIENCE: So what we're doing
right now is taking some value, and then storing it, and
then getting it back out, and putting it back. TAO B. SCHARDL: Not putting
it back, but we don't you worry about putting it back. AUDIENCE: So we don't need
to put it somewhere just to take it back out? TAO B. SCHARDL: Correct. Correct. So what are we multiplying in
that multiply, which value? First element of the struct. It's percent zero. It's the value that
we stored right there. That makes sense? Everyone see that? Any questions about that? All right, so we're storing
the first element of the struct into this location. Later, we load it out
of that same location. Nothing else happened
to that location. So let's go ahead and
optimize it just the same way we optimize the scalar. We see that we use the result
of the load right there. But we know that load is going
to return the first field of our struct input. So we'll just cross it out,
and replace it with that field. So now we're not using
the result of that load. What do we get to
do as the compiler? I can tell you know the answer. Delete the dead code,
delete all of it. Remove the now dead code,
which is all those address calculations, as well as the
load operation, and the store operation. And that's pretty much it. Yeah, good. So we replace that operation. And we got rid of a bunch of
other code from our function. We've now optimized one of
the two fields in our struct. What do we do next? Optimize the next one. That happened similarly. I won't walk you through
that a second time. We find where we're using
the result of that load. We can cross it out, and replace
it with the appropriate input, and then delete all
the relevant dead code. And now, we get to delete
the original allocation because nothing's getting
stored to that memory. That make sense? Any questions about that? Yeah? AUDIENCE: So when we first
compile it to LLVM IR, does it unpack the
struct and just put in separate parameters? TAO B. SCHARDL: When we
first compiled LLVM IR, do we unpack the struct and
pass in the separate parameters? AUDIENCE: Like, how we
have three parameters here that are doubled. Wasn't our original C code
just a struct of vectors in the double? TAO B. SCHARDL: So LLVM IR in
this case, when we compiled it as zero, decided to pass
it as separate parameters, just as it's representation. So in that sense, yes. But it was still
doing the standard, create some local storage,
store the parameters on to local storage, and
then all operations just read out of local storage. It's the standard thing that
the compiler generates when it's asked to compile C code. And with no other optimizations,
that's what you get. That makes sense? Yeah? AUDIENCE: What are
all the align eights? TAO B. SCHARDL: What are all
the aligned eights doing? The align eights
are attributes that specify the alignment of
that location in memory. This is alignment
information that the compiler either determines by
analysis, or implements as part of a standard. So they're specifying how
values are aligned in memory. That matters a lot more for
ultimate code generation, unless we're able to
just delete the memory references altogether. Make sense? Cool. Any other questions? All right, so we
optimized the first field. We optimize the second
field in a similar way. Turns out, there's
additional optimizations that need to happen
in order to return a structure from this function. Those operations can be
optimized in a similar way. They're shown here. We're not going to go through
exactly how that works. But at the end of
the day, after we've optimized all of that
code we end up with this. We end up with our
function compiled at 01. And it's far simpler. I think it's far more intuitive. This is what I would
imagine the code should look like when I wrote the
C code in the first place. Take your input. Do a couple of multiplications. And then it does them operations
to create the return value, and ultimately
return that value. So, in summary,
the compiler works hard to transform data
structures and scalar values to store as
much as it possibly can purely within
registers, and avoid using any local storage, if possible. Everyone good with that so far? Cool. Let's move on to
another optimization. Let's talk about function calls. Let's take a look
at how the compiler can optimize function calls. By and large,
these optimizations will occur if you pass
optimization level 2 or higher, just FYI. So from our original
C code, we had some lines that performed a
bunch of vector operations. We had a vec add that added two
vectors together, one of which was the result of
a vec scale, which scaled the result of a vec
add by some scalar value. So we had this chain
of calls in our code. And if we take a look
at the code compile that was 0, what we end up
with is this snippet shown on the bottom, which performs
some operations on these vector structures, does this
multiply operation, and then calls this
vector scale routine, the vector scale routine that
we decide to focus on first. So any ideas for how we
go about optimizing this? So to give you a little bit of
a hint, what the compiler sees when it looks at that call is
it sees a snippet containing the call instruction. And in our example, it also
sees the code for the vec scale function that we
were just looking at. And we're going to suppose
that it's already optimized vec scale as best as it can. It's produced this code
for the vec scale routine. And so it sees that
call instruction. And it sees this code for the
function that's being called. So what could the
compiler do at this point to try to make the
code above even faster? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL:
You're exactly right. Remove the call, and just put
the body of the vec scale code right there in
place of the call. It takes a little bit of
effort to pull that off. But, roughly
speaking, yeah, we're just going to copy and paste
this code in our function into the place where we're
calling the function. And so if we do that
simple copy paste, we end up with some garbage
code as an intermediate. We had to do a little
bit of renaming to make everything work out. But at this point,
we have the code from our function in
the place of that call. And now, we can observe
that to restore correctness, we don't want to do the call. And we don't want to do
the return that we just pasted in place. So we'll just go
ahead and remove both that call and the return. That is called
function inlining. We identify some function
call, or the compiler identifies some function call. And it takes the
body of the function, and just pastes it right
in place of that call. Sound good? Make sense? Anyone confused? Raise your hand if
you're confused. Now, once you've done some
amount of function inlining, we can actually do some
more optimizations. So here, we have the
code after we got rid of the unnecessary
call and return. And we have a couple multiply
operations sitting in place. That looks fine. But if we expand our
scope just a little bit, what we see, so we
have some operations happening that were
sitting there already after the original call. What the compiler
can do is it can take a look at these instructions. And long story
short, it realizes that all these
instructions do is pack some data into a structure,
and then immediately unpack the structure. So it's like you put a
bunch of stuff into a bag, and then immediately
dump out the bag. That was kind of
a waste of time. That's kind of a waste of code. Let's get rid of it. Those operations are useless. Let's delete them. The compiler has a great
time deleting dead code. It's like it's what
it lives to do. All right, now, in fact,
in the original code, we didn't just have
one function call. We had a whole sequence
of function calls. And if we expand our LLVM IR
snippet even a little further, we can include
those two function calls, the original call to
vec ad, followed by the code that we've now
optimized by inlining, ultimately followed by yet
another call to vec add. Minor spoiler, the vec add
routine, once it's optimized, looks pretty similar to
the vec scalar routine. And, in particular,
it has comparable size to the vector scale routine. So what's the compiler is going
to do to those to call sites? Inline it, do more
inlining, inlining is great. We'll inline these
functions as well, and then remove all of the
additional, now-useless instructions. We'll walk through that process. The result of that process
looks something like this. So in the original C
code, we had this vec add, which called
the vec scale as one of its arguments, which
called the vec add is one of its arguments. And what we end up with
in the optimized IR is just a bunch of straight
line code that performs floating point operations. It's almost as if the compiler
took the original C code, and transformed it into
the equivalency code shown on the bottom, where
it just operates on a whole bunch of doubles, and
just does primitive operations. So function inlining, as well as
the additional transformations it was able to
perform as a result, together those were
able to eliminate all of those function calls. It was able to
completely eliminate any costs associated with the
function call abstraction, at least in this code. Make sense? I think that's pretty cool. You write code that has a
bunch of function calls, because that's how you've
constructed your interfaces. But you're not really paying
for those function calls. Function calls aren't
the cheapest operation in the world,
especially if you think about everything
that goes on in terms of the registers and the stack. But the compiler is able to
avoid all of that overhead, and just perform the floating
point operations we care about. OK, well, if function
inlining is so great, and it enables so many
great optimizations, why doesn't the compiler just
inline every function call? Go for it. Recursion, it's really hard
to inline a recursive call. In general, you can't inline
a function into itself, although it turns out
there are some exceptions. So, yes, recursion
creates problems with function inlining. Any other thoughts? In the back. AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: You're
definitely on to something. So we had to do a bunch
of this renaming stuff when we inlined the
first time, and when we inlined every single time. And even though LLVM IR has an
infinite number of registers, the machine doesn't. And so all of that renaming
does create a problem. But there are other
problems as well of a similar nature when you start
inlining all those functions. For example, you copy
pasted a bunch of code. And that made the original call
site even bigger, and bigger, and bigger, and bigger. And programs, we generally
don't think about the space they take in memory. But they do take
space in memory. And that does have an
impact on performance. So great answer,
any other thoughts? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: If your
function becomes too long, then it may not fit
in instruction cache. And that can increase
the amount of time it takes just to
execute the function. Right, because you're now
not getting hash hits, exactly right. That's one of the problems
with this code size blow up from inlining everything. Any other thoughts? Any final thoughts? So there are three main
reasons why the compiler won't inline every function. I think we touched
on two of them here. For some function calls,
like recursive calls, it's impossible to inline
them, because you can't inline a function into itself. But there are exceptions
to that, namely recursive tail calls. If the last thing in a
function is a function call, then it turns out
you can effectively inline that function
call as an optimization. We're not going to talk too
much about how that works. But there are corner cases. But, in general, you can't
inline a recursive call. The compiler has
another problem. Namely, if the function
that you're calling is in a different castle, if
it's in a different compilation unit, literally in
a different file that's compiled independently,
then the compiler can't very well
inline that function, because it doesn't know
about the function. It doesn't have access
to that function's code. There is a way to get
around that problem with modern compiler technology
that involves whole program optimization. And I think there's some backup
slides that will tell you how to do that with LLVM. But, in general, if it's in
a different compilation unit, it can't be inline. And, finally, as touched
on, function inlining can increase code size,
which can hurt performance. OK, so some functions
are OK to inline. Other functions could create
this performance problem, because you've
increased code size. So how does the compiler
know whether or not inlining any particular
function at a call site could hurt performance? Any guesses? Yeah? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: Yeah. So the compiler has some
cost model, which gives it some information
about, how much will it cost to inline that function? Is the cost model always right? It is not. So the answer, how
does the compiler know, is, really, it doesn't know. It makes a best guess
using that cost model, and other heuristics,
to determine, when does it make sense to
try to inline a function? And because it's
making a best guess, sometimes the compiler
guesses wrong. So to wrap up this
part, here are just a couple of tips for
controlling function inlining in your own programs. If there's a function that you
know must always be inlined, no matter what happens,
you can mark that function with a special attribute, namely
the always inline attribute. For example, if you
have a function that does some complex
address calculation, and it should be inlined
rather than called, you may want to mark that with
an always inline attribute. Similarly, if you have a
function that really should never be inlined, it's
never cost effective to inline that function,
you can mark that function with the no inline attribute. And, finally, if you want to
enable more function inlining in the compiler, you can use
link time optimization, or LTO, to enable whole
program optimization. Won't go into that
during these slides. Let's move on, and talk
about loop optimizations. Any questions so
far, before continue? Yeah? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: Sorry? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL:
Does static inline guarantee you the compiler
will always inline it? It actually doesn't. The inline keyword will
provide a hint to the compiler that it should think about
inlining the function. But it doesn't provide
any guarantees. If you want a strong guarantee,
use the always inline attribute. Good question, though. All right, loop optimizations-- you've already seen
some loop optimizations. You've seen vectorization,
for example. It turns out, the compiler
does a lot of work to try to optimize loops. So first, why is that? Why would the compiler
engineers invest so much effort into optimizing loops? Why loops in particular? They're extremely
common control structure that also has a branch. Both things are true. I think there's a higher
level reason, though, or more fundamental
reason, if you will. Yeah? AUDIENCE: Most of the time, the
loop takes up the most time. TAO B. SCHARDL: Most of
the time the loop takes up the most time. You got it. Loops account for a lot of the
execution time of programs. The way I like to
think about this is with a really simple
thought experiment. Let's imagine that you've got
a machine with a two gigahertz processor. We've chosen these
values to be easier to think about
using mental math. Suppose you've got
a two gigahertz processor with 16 cores. Each core executes one
instruction per cycle. And suppose you've
got a program which contains a trillion instructions
and ample parallelism for those 16 cores. But all of those instructions
are simple, straight line code. There are no branches. There are no loops. There no complicated
operations like IO. It's just a bunch of really
simple straight line code. Each instruction takes
a cycle to execute. The processor executes
one instruction per cycle. How long does it take to
run this code, to execute the entire terabyte binary? 2 to the 40th cycles for
2 to the 40 instructions. But you're using a two gigahertz
processor and 16 cores. And you've got ample
parallelism in the program to keep them all saturated. So how much time? AUDIENCE: 32 seconds. TAO B. SCHARDL: 32
seconds, nice job. This one has mastered power
of 2 arithmetic in one's head. It's a good skill to have,
especially in core six. Yeah, so if you have
just a bunch of simple, straight line code, and
you have a terabyte of it. That's a lot of code. That is a big binary. And, yet, the program,
this processor, this relatively
simple processor, can execute the whole thing
in just about 30 seconds. Now, in your experience
working with software, you might have
noticed that there are some programs that take
longer than 30 seconds to run. And some of those programs don't
have terabyte size binaries. The reason that those
programs take longer to run, by and large, is loops. So loops account for
a lot of the execution time in real programs. Now, you've already seen
some loop optimizations. We're just going to take
a look at one other loop optimization today, namely
code hoisting, also known as loop invariant code motion. To look at that,
we're going to take a look at a different
snippet of code from the end body simulation. This code calculates
the forces going on each of the end bodies. And it does it with
a doubly nested loop. For all the zero to
number of bodies, for all body zero
number bodies, as long as you're not looking
at the same body, call this add force routine,
which calculates to-- calculate the force
between those two bodies. And add that force
to one of the bodies. That's all that's
going on in this code. If we translate this
code into LLVM IR, we end up with,
hopefully unsurprisingly, a doubly nested loop. It looks something like this. The body of the code, the
body of the innermost loop, has been lighted, just so
things can fit on the slide. But we can see the
overall structure. On the outside, we have
some outer loop control. This should look familiar
from lecture five, hopefully. Inside of that outer loop,
we have an inner loop. And at the top and the
bottom of that inner loop, we have the inner loop control. And within that
inner loop, we do have one branch, which
can skip a bunch of code if you're looking at the
same body for i and j. But, otherwise, we have the loop
body of the inner most loop, basic structure. Now, if we just zoom
in on the top part of this doubly-nested loop, just
the topmost three basic blocks, take a look at more of the
code that's going on here, we end up with something
that looks like this. And if you remember
some of the discussion from lecture five about the
loop induction variables, and what that looks like
in LLVM IR, what you find is that for the outer loop
we have an induction variable at the very top. It's that weird fee
instruction, once again. Inside that outer loop,
we have the loop control for the inner loop, which has
its own induction variable. Once again, we have
another fee node. That's how we can spot it. And then we have the body
of the innermost loop. And this is just the start of. It it's just a couple
address calculations. But can anyone tell me
some interesting property about just a couple of
these address calculations that could lead to
an optimization? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: The first
two address calculations only depend on the outermost
loop variable, the iteration variable for the outer
loop, exactly right. So what can we do with
those instructions? Bring them out of
the inner loop. Why should we keep
computing these addresses in the innermost loop when we
could just compute them once in the outer loop? That optimization is called
code hoisting, or loop invariant code motion. Those instructions are
invariant to the code in the innermost loop. So you hoist them out. And once you hoist
them out, you end up with a transformed loop that
looks something like this. What we have is the same outer
loop control at the very top. But now, we're doing some
address calculations there. And we no longer have
those address calculations on the inside. And as a result, those
hoisted calculations are performed just once per
iteration of the outer loop, rather than once per
iteration of the inner loop. And so those instructions
are run far fewer times. You get to save a
lot of running time. So the effect of
this optimization in terms of C code,
because it can be a little tedious
to look at LLVM IR, is essentially like this. We took this
doubly-nested loop in C. We're calling add force of blah,
blah, blah, calculate force, blah, blah, blah. And now, we just move
the address calculation to get the ith body
that we care about. We move that to the outer. Now, this was an example of loop
invariant code motion on just a couple address calculations. In general, the
compiler will try to prove that some calculation
is invariant across all the iterations of a loop. And whenever it
can prove that, it will try to hoist that
code out of the loop. If it can get code out
of the body of a loop, that reduces the running
time of the loop, saves a lot of execution time. Huge bang for the buck. Make sense? Any questions about that so far? All right, so just to
summarize this part, what can the compiler do? The compiler optimizes code
by performing a sequence of transformation passes. All those passes are
pretty mechanical. The compiler goes
through the code. It tries to find some property,
like this address calculation is the same as that
address calculation. And so this load will return
the same value as that store, and so on, and so forth. And based on that
analysis, it tries to get rid of some dead code,
and replace certain register values with other
register values, replace things that live
in memory with things that just live in registers. A lot of the transformations
resemble Bentley-rule work optimizations that you've
seen in lecture two. So as you're studying
for your upcoming quiz, you can kind of get
two for one by looking at those Bentley-rule
optimizations. And one transformation pass, in
particular function inlining, was a good example of this. One transformation can
enable other transformations. And those together can
compound to give you fast code. In general, compilers perform
a lot more transformations than just the ones we saw today. But there are things that
the compiler can't do. Here's one very simple example. In this case, we're
taking another look at this calculate
forces routine. Although the compiler
can optimize the code by moving address
calculations out of loop, one thing that I can't
do is exploit symmetry in the problem. So in this problem,
what's going on is we're computing the
forces on any pair of bodies using the law of gravitation. And it turns out that the force
acting on one body by another is exactly the opposite the
force acting on the other body by the one. So F of 12 is equal
to minus F of 21. The compiler will
not figure that out. The compiler knows algebra. It doesn't know physics. So it won't be
able to figure out that there's symmetry
in this problem, and it can avoid
wasted operations. Make sense? All right, so that
was an overview of some simple
compiler optimizations. We now have some examples
of some case studies to see where the compiler
can get tripped up. And it doesn't matter if we get
through all of these or not. You'll have access to
the slides afterwards. But I think these
are kind of cool. So shall we take a look? Simple question-- does the
compiler vectorize this loop? So just to go over what this
loop does, it's a simple loop. The function takes
two vectors as inputs, or two arrays as
inputs, I should say-- an array called y, of like then,
and an array x of like then, and some scalar value a. And all that this
function does is it loops over each element of
the vector, multiplies x of i by the input scalar, adds
the product into y's of i. So does the loop vectorize? Yes? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: y
and x could overlap. And there is no information
about whether they overlap. So do they vectorize? We have a vote for no. Anyone think that
it does vectorize? You made a very
convincing argument. So everyone believes that
this loop does not vectorize. Is that true? Anyone uncertain? Anyone unwilling to commit
to yes or no right here? All right, a bunch of people
are unwilling to commit to yes or no. All right, let's
resolve this question. Let's first ask for the report. Let's look at the
vectorization report. We compile it. We pass the flags to get
the vectorization report. And the vectorization
report says, yes, it does vectorize this loop,
which is interesting, because we have this
great argument that says, but you don't know how these
addresses fit in memory. You don't know if x and y
overlap with each other. How can you possibly vectorize? Kind of a mystery. Well, if we take a look at the
actual compiled code when we optimize this at 02, turns
out you can pass certain flags to the compiler, and get it to
print out not just the LLVM IR, but the LLVM IR formatted
as a control flow graph. And the control flow graph for
this simple two line function is the thing on the
right, which you obviously can't, read because
it's a little bit small, in terms of its text. And it seems have
a lot going on. So I took the liberty of
redrawing that control flow graph with none of
the code inside, just get a picture of
what the structure looks like for this compiled function. And, structurally speaking,
it looks like this. And with a bit of practice
staring at control flow graphs, which you might get if you
spend way too much time working on compilers, you might look
at this control flow graph, and think, this graph looks
a little too complicated for the two line function
that we gave as input. So what's going on here? Well, we've got three
different loops in this code. And it turns out that
one of those loops is full of vector operations. OK, the other two loops are
not full of vector operations. That's unvectorized code. And then there's this
basic block right at the top that has
a conditional branch at the end of it, branching
to either the vectorized loop or the unvectorized loop. And, yeah, there's a lot of
other control flow going on as well. But we can focus on just these
components for the time being. So what's that
conditional branch doing? Well, we can zoom in on
just this one basic block, and actually show it to
be readable on the slide. And the basic block
looks like this. So let's just study
this LLVM IR code. In this case, we have got the
address y stored in register 0. The address of x is
stored in register 2. And register 3 stores
the value of n. So one instruction
at a time, who can tell me what the first
instruction in this code does? Yes? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: Gets
the address of y. Is that what you said? So it does use the address of y. It's an address calculation that
operates on register 0, which stores the address of y. But it's not just
computing the address of y. AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: It's
getting me the address of the nth element of y. It's adding in whatever is in
register 3, which is the value n, into the address of y. So that computes the
address y plus n. This is testing your memory
of pointer arithmetic in C just a little bit but. Don't worry. It won't be too rough. So that's what the first
address calculation does. What does the next
instruction do? AUDIENCE: It does x plus n. TAO B. SCHARDL: That
computes x plus, very good. How about the next one? AUDIENCE: It compares
whether x plus n and y plus n are the same. TAO B. SCHARDL: It compares
x plus n, versus y plus n. AUDIENCE: [INAUDIBLE] compares
the 33, which is x plus n, and compares it to y. So if x plus n is bigger
than y, there's overlap. TAO B. SCHARDL: Right,
so it does a comparison. We'll take that a
little more slowly. It does a comparison of x
plus n, versus y in checks. Is x plus n greater than y? Perfect. How about the next instruction? Yeah? AUDIENCE: It compares
y plus n versus x. TAO B. SCHARDL: It
compares y plus n, versus x, is y plus n
even greater than x. How would the last
instruction before the branch? Yep, go for it? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: [INAUDIBLE]
one of the results. So this computes the
comparison, is x plus n greater than y, bit-wise? And is y plus n greater than x. Fair enough. So what does the result
of that condition mean? I think we've pretty much
already spoiled the answer. Anyone want to hear
it one last time? We had this whole setup. Go for it. AUDIENCE: They overlap. TAO B. SCHARDL: Checks
if they overlap. So let's look at this
condition in a couple of different situations. If we have x living in
one place in memory, and y living in another
place in memory, then no matter how we
resolve this condition, if we check is both y
plus n greater than x, and x plus n greater than y,
the results will be false. But if we have this
situation, where x and y overlap in memory
some portion of memory, then it turns out that
regardless of whether x or y is first, x plus n will
be greater than y. y plus n will be greater than x. And the condition
will return true. In other words, the
condition returns true, if and only if these portions
of memory pointed by x and y alias. So going back to our
original looping code, we have a situation where
we have a branch based on whether or not they alias. And in one case, it executes
the vectorized loop. And in another case, it
executes a non-vectorized code. So returning to our original
question, in particular is a vectorized loop
if they don't alias. So returning to our
original question, does this code get vectorized? The answer is yes and no. So if you voted yes,
you're actually right. If you voted no, and you were
persuaded, you were right. And if you didn't commit to
an answer, I can't help you. But that's interesting. The compiler actually generated
multiple versions of this loop, due to uncertainty
about memory aliasing. Yeah, question? AUDIENCE: [INAUDIBLE] TAO B. SCHARDL: So the
question is, could the compiler figure out this
condition statically while it's compiling
the function? Because we know the
function is going to get called from somewhere. The answer is, sometimes it can. A lot of times it can't. If it's not capable of
inlining this function, for example, then it probably
doesn't have enough information to tell whether or not these
two pointers will alias. For example, you're
just building a library with a bunch of vector routines. You don't know the code
that's going to call this routine eventually. Now, in general,
memory aliasing, this will be the last point
before we wrap up, in general, memory aliasing can
cause a lot of issues when it comes to
compiler optimization. It can cause the compiler
to act very conservatively. In this example, we have
a simple serial base case for a matrix multiply routine. But we don't know anything
about the pointers to the C, A, or B matrices. And when we try to compile
this and optimize it, the compiler complains that it
can't do loop invariant code motion, because it doesn't know
anything about these pointers. It could be that
the pointer changes within the innermost loop. So it can't move
some calculation out to an outer loop. Compilers try to deal with this
statically using an analysis technique called alias analysis. And they do try very
hard to figure out, when are these pointers
going to alias? Or when are they
guaranteed to not alias? Now, in general, it turns
out that alias analysis isn't just hard. It's undecidable. If only it were hard,
maybe we'd have some hope. But compilers, in
practice, are faced with this undecidable question. And they try a variety of tricks
to get useful alias analysis results in practice. For example, based on
information in the source code, the compiler might
annotate instructions with various metadata to track
this aliasing information. For example, TBAA is aliasing
information based on types. There's some scoping
information for aliasing. There is some
information that says it's guaranteed not to alias
with this other operation, all kinds of metadata. Now, what can you
do as a programmer to avoid these issues
of memory aliasing? Always annotate
your pointers, kids. Always annotate your pointers. The restrict keyword
you've seen before. It tells the compiler,
address calculations based off this pointer won't alias
with address calculations based off other pointers. The const keyword provides
a little more information. It says, these addresses
will only be read from. They won't be written to. And that can enable a lot
more compiler optimizations. Now, that's all the
time that we have. There are a couple of other
cool case studies in the slides. You're welcome to peruse
the slides afterwards. Thanks for listening.
