Profile-Guided Optimization in the LDC D compiler
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Nacke, Kai
Profile-Guided Optimization (PGO) is an optimization technique which usesinformation about the runtime profile of an application. PGO is an area ofactive development in LLVM. In this talk I discuss how PGO was implemented inLDC, the LLVM-based D compiler, and which speedup the use of PGO can give. Profile-Guided Optimization (PGO) is an optimization technique which usesinformation about the runtime profile of an application. The binary of anapplication is instrumented to collect data like number of times a function iscalled. This additional information is used to apply advanced optimizations tothe application. PGO is an area of active development in LLVM. A recent updateof LDC, the LLVM-based D compiler, is able to use PGO. In this talk I discusswhich additonal IR code must be generated for PGO and how it was implementedin LDC. I also show the effect of PGO on a test application and the compileritself.
 Hello, as Renato said, my name is Kai. I'm one of the maintainers of the LDCD compiler. And today I'm talking about the profile guided optimization, which was recently added to the compiler. OK, there's a lot of specific words in there. Let's explain what it is all is. So what is profile guided optimization? It's recently added to LLVM. It's based on a simple idea. I can have better optimizations if I have more informations. And what is the source for more informations I can use for optimization? Well, I can do a lot of static analysis. And there's a theory about it that's a lot of stuff. It's hard work. And you always can't determine everything just from looking at the source. So another way to get information for optimization is to just look at the running application and get information from the application itself. And to do this, there are two approaches. One approach is I can sample the application. I just stop the application in certain amounts of time, look where is the application and store this data. That's one way to do it. I'm going not to cover this in this talk. I'm just covering instrumentation of the source. So that's a LLVM. This is a common approach. We have, for example, the sanitizers, which also add some instrumentation and do certain stuff. So for optimization, what information do I want to know? For example, I want to know how often is a function called? Or if I have a branch, and if how often is the positive, or how often is the branch taken, or how often is it not taken. I simply can count this. Or for example, I can count how often calls the function A, the function B, to know the dependency for this. So I have to add a lot of counters to the source and collect all these data. I run my application. I collect this data. I dump this to the hard disk. And then I have something which we call a profile of the application. Yes. This is also the main drawback. We run the application to create the information. So the quality of the information we derive depends on the run we do. If we run the application with an average input, I can expect to get some good result. If I run it with an exceptional input, so I look just for specific cases, then I get a profile which does not cover everything. And this can also result in, well, not an optimization, but in the performance loss, because I'm pointing the optimizer to the wrong places to optimize. So it's a good way to get information about to use in optimization, but you have to be careful. So the very, very important point with every optimization, by the way, is you have to measure. Just to say, this is a proven optimization. I just use it blindly and think everything will be good. This does not work. So be sure to measure your result. OK. So this first was about what is profile guided optimization. The next thing is what is this D language? Everybody heard of D? OK. So by the way, there's David, the other maintainer of the LDC, so we have very competent support for it. OK. You're the maintainer now, though. OK. Yes. So what is D for the people who did not heard about it? D was created as a system programming language. It was about 99 or 2000 when it appeared the first time. And it was really meant to be what the name implies, a better C++. But today, we are proud of having our own language. But yeah, we're using C like syntax, so you can immediately read it if you are known to C or C++. We also use static typing. That's also the same like C++. What's better, we have a good module support. So this will come in C++, I think, in the next standard. Also, we already had it, and it's very good. And one of the good points of the language is we support many paradigms. So we have polymorphism. You can do some object-oriented programming. We also support the functional style if you prefer that. We have generics and a lot of other style. And it's all well integrated. So you don't have to switch to this style or this style. You can mix it up, and it works all good together. From templates, I also know from C++. But with D, it's going to be a step further. We have really template meta-programming with a nice edit if. So then you can choose which template is selected based on some conditions. Let's make it very easy to use template meta-programming, and it's not the hard stuff in C++. That's very nice. Yeah, we use a garbage collector. This is always a point of discussion. Is this good or is this not good? The language uses this, but there's also work on it to replace it with or to make it, let's say, a plug-in and to use memory management by hand, for example. It has some drawbacks, maybe. But let's see, a garbage collector is always a safety guard. You don't have certain memory problems with it. And also nice, a unique feature, I think. It's called compile-time function execution. You can say that certain functions are executed by the compiler, not at runtime, but at compile-time, so that you don't have to run it at runtime just to insert the result into the binary, and that's it. That can make things very fast. For example, if you have regular expressions, and you know the expressions at compile-time, then you can compile this regular expression into decode. And this gets all the optimization done by LLVM, and that's very, very fast. So there are certain use cases for it, and that makes it very nice. Yes, LDC is one of the decompilers available. And it's, let's say, a combined afford. We have a reference compiler. It's the dDMD compiler. And the first d comes from the fact that the front end is now written in d itself. And LDC uses this front end and adds some C++ glue code to it to generate the LLVM ER, and then uses the LLVM backends. So we support a lot of the backends LLVM support, but we are just copying the reference front. And so we say we are really compatible with our compiler, but we generate a really industrial style machine code. That's very good. If someone is more interested about the compiler, I think in 2014 I had at this place a talk about the inner working of LDC. So you can download the slides on the first name page. If you want to know more about it. OK, so we have now the part profile guided optimization, which is provided by LLVM. We have the LDC compiler. And now we need it to plug this all together. And yes, this is the latest release. It's already there. So if you go to our GitHub page and download the binaries for Linux, you get it for free. But of course, the implementation was not for free. And one guy, Johann, made the effort to really implement this. And this was, let's say, a lot of work. What was needed to be done? The first, you have to add the source code instrumentation, which boils down to we have to insert the codes to LLVM in Trenzig at the right places. And if you look at the pull request, then you see a typical pattern to it. We have a PGO, profile guided optimization class that's more or less copied from the same class from Clang. And this class tracks the state of the current function. And so what you always see is I have to get a reference to this tracker class. I inform this class about the current statement where I'm currently in. And at the right place, you have to do something with the count. For example, I'm entering the function I have to increment the counter corresponding to this function. This is the common pattern. There are also code to count how is the branch taken or not taken. And this must all be added. So we have a big visitor more or less, which goes through the abstract syntax tree. And this needs to do all this stuff. This was really added. And that's a lot of work because D is a full feature language, not a toy language. So parts of the compiler, the front, and I said, is written in D. So that's really a lot of work to do. But there's no automatic way to add it. Yeah, another point is now that we have the instrumentation, we also need to add the profiling path to the path manager. And one of the things we do with LEC is that we support different versions of the LLVM back end. And this leads always to some kind of ugly code because the instruction profiling path is a bit new. It was added in LLVM 3.7, I think. And with LLVM 3.9, the name was changed. It was renamed. So just after a year, we had to use this if to say, OK, if you use a newer version of LLVM, then stick to this legacy name, and otherwise use the old name. So that's also a common pattern in the glue code of LEC. We always have to check for the version of LLVM and then use this name or that name or different order of parameters also. That's sometimes a bit annoying to support. OK, what else needed to be done? What else needed to be added? We have the profile data. So we collect all these counters, the counter data, and the counter data is attached to the function or some basic blocks, for example, for loops or ifs. And this must be after the end of the program written to disk. And this requires a bit of fiddling how to identify where I am in the source code and put it to disk. So you have to add some function for reading and writing this profile data. And when I'm say reading, this also means we have them, the data, and we must bring it to LLVM. And if this is done, we have the metadata of LLVM. So reading also implies that we go through the data and attach it again to the LLVM IR. So it's a bit of work to do this. Yeah, and not everything is just lowered to machine instructions by LLVM. There's also small runtime library. And the small library we have to link to. So at first, our driver needs to know if we switch on profile-guided optimizations, we have to link to an additional library. That's one part. That's easy. The other part is we need the library. So we take the easy approach and edit the profile-rt library to our repository. And we did this for each supported LLVM version. So this is a big directory which contains the profile-rt from, I think, 3.7 to LLVM5 now. Because that's the easiest way to do it. Otherwise, we would have another external dependency which would be annoying. OK, but that's the whole stuff. And with this done, we are ready to use profile-guided optimization with our LDC compiler. OK, I said the latest release contains it, at least for Linux, because as far as I know, not available for Windows, for example. But with Linux, you can go to our GitHub page, download the compiler, and everything works as described here. So what you do, you have a test program or whatever application you have. I call it the pgotest.d. And the first is we have to add the instrumentation during the compile process. So you use this LengthlySwitch profile instra-generate. I think it's the same name used by Klang. And this just not only compiles the module, but also adds the instrumentation. One good hint here is just give it a different name. So you know you're having this binary with the instrumentation. The reason is simple. Adding all these counters. It's a lot of stuff. And if you're out of luck, you're having a counter for every basic block. And this is also a great performance impact. You do not want to distribute this instrumented version to any user. So just use a different name, and everything is right. OK. So you now have the instrumented binary. Just run it. When you run it, it will write the profile data at the end to the hard disk. And two things here. The default name is default.proffraw. And you can change this name. And you want to do this because of two reasons. Maybe default is a very generic name. And if you do it a lot, this file will always overwritten. And the second thing is you will do many runs of it. And for every run, you would like to collect the data and just merge it into one profile. So you really need several of these profile files. And for this, you can either give it here a name after with the equal sign and then the name. Or you can use an environment variable. And in this name, you can also use some parameters which can be replaced, for example, with the process ID. So you can really say I have here a script file and I run my test application with 10 different inputs. And you can get 10 different profile data files. And what you do, if you have these profile data files, you need to convert it. Therefore, we have the LEC Prof Data Tool. There's no magic in it. It's just a renamed LLVM Prof Data. But it's renamed because we are tied to a specific LLVM version. And again, there can be many LLVM versions installed on the, for example, in Linux. And with this, we make sure that we are using the right one for our tool. And so this tool has just two basic options, merge and show. For the run, you use the merge option. And the merge option, there you give all the prof raw files you have generated. And it creates the final profile data file. And with the output parameter, just give it a name. There's some format conversion in it. But basically, it merges all the profiles together and create a format which is, again, readable by the compiler. And then you're done. You can take the second compile one. In this case, you see use command switch. You get the profile data with it. And then LLVM, hopefully, gives you a better optimized version of your program. OK. And again, the hint measures the result. Because it's only runtime that's really looking at the runtime behavior of the application. And it can go wrong. It might not, but it can go wrong. So measure the result. OK. What kind of optimization is done with this? With LLVM 3.9, there's a new optimization introduced which uses exclusively the information derived from a profile-guided optimization. And this is called the indirect call promotion. And I think it's a very important optimization. Because indirect calls, so I'm calling a function through a function pointer, that's very often used in, for example, object-oriented languages. But also, for example, in C, it's coming to have a pointer to some function and do the call about this pointer. So the optimization we can do here is when we know which function is called through the pointer, then I don't use the pointer. I call the function directly. And OK, that's the pointer. The pointer can point to many functions. So we want to know what is the, let's say, the most likely called function. Or the most likely too called functions. And so how do we get this information? We simply count how often is this function called and from where is it called. And that's exactly the information we can collect with the profile-guided optimization in our profile data. So this is a nice optimization. And the benefit of this is if we know what is the most likely called function, and replace it with a direct call, then we enable other LLVM optimizations. For example, function inlining, which can say that for the most common function, it's a very, very fast path because we have eliminated all the branches in it. Yeah, let's look first at the high level and then at the low level. So this is decode, and I think it should be readable for everyone. OK, I have a simple function, which is really simple. It just returns one value. And there's also a function pointer to it. And to make the things more interesting, we're going to have a loop and call this function in a loop. So there's no sense behind it from this function doing really something useful. It only demonstrates we're calling the function indirectly through a pointer. OK, and what does the indirect function call promotion do? It's quite simple. It checks if the pointer is the most likely called function. OK, we have only one function. So that's quite easy. And if it's the case, then we call this function directly. And for sure, this is only a heuristic method. So the compiler does not know what happened with the variable maybe in other places. So we also have the forebake and say, OK, if it's not this function, then just do the call by the function pointer. So this is a very simple approach. And for sure, you can do it yourself. You don't need compiler support for it. That's with other optimizations, that is not that easy. But if you have a good knowledge about which function gets called, then you can do it yourself. And yeah, you can really do it in D with the need syntax. So you can define a template which hides the check for the most likely function and then call the likely function or use the function pointer. And then we have this nice syntax, which is a very special feature of the language. But it's readable for, I think, because we say we have the function pointer and we apply this likely template. And this template has the most likely function as a parameter and everything else is hidden another template. So we could do all this stuff by ourselves and we don't need the compiler support. So if you know it, you can do it this way. But that's not really a very good approach because you have the problem you don't know, which is the most likely called function. Look at LLVM. It has millions of lines of code. And at a specific place, what is the most likely called functions? Don't know. So let's do the compiler's work. Let's go down to the ER level. So just how is the indirect call represented at the ER level? It's quite simple. We load the value of the pointer. So we have here this pointer and load it into the virtual register one. And then we just call the function. It's a very simple load value and jump. OK. So what is the next? We have the instrumented version. The instrumented version is the step. It's an immediate step. We have to add the counter for the loop. If you remember, I had a loop. And we need to count how often is the loop used at this point. We also need to record which target we do call with this pointer. And of course, the loading and calling, the function is also present. But there's a lot of stuff around it. When we run the instrumented application, it generates the profile data. You can also use the show argument to the LDC Prof Data tool and look at the generated profile. And for example, you see the ICP function. It has one counter instrumented in it. And it's called 1,000 times. That's what I would expect from my source. And there's also the main function. There are two counters in it, one for the function and one for the loop body. And the function is called 1 time. So there you can get an overview of your profile. And now we use the profile data to optimize the function. And this is with the O3 switch. We really optimize. And in this case, well, you see the load, the pointer. We have a compare with the most likely function, the ICT function, and then the branch. And the branch is, if it's not equal, we go to the original indirect call. That's the C4 back. And in the other case, we jump over it. And this function was very simple. So the result was inline by LLVM. And so in the phi instruction, we see, OK, if you come from the forebody, then use the value 42. So in the most likely case, there's no jump at all. And that's what we're going to have. And also, you see this profile data is attached in the metadata by LLVM. Yeah. What's the result of all this? Johann, who did the pull request for it, he tested it also. And if you only look at the D part of LBC, then the compiler becomes faster by about 7%. This was done on a test case from an industrial project. And so it's not some simplistic benchmark, but it's a real test case from application. So that's a very good result in my eyes. And he had also some more ideas. And these more ideas are, therefore, only a sample implementation. He called it the virtual call promotion, which is the same as the indirect call promotion, but applies to classes which uses a file table structure to do the virtual call. And with this, there's also ways with the same, this is a similar approach to replace these virtual calls with direct calls. And that's a very interesting approach, but not yet committed. Yeah. So my summary is, it's really worth to have this profile guided optimization in our toolbox now, because if you're done it right, you can get a better speed margin. And I think just having 7% faster application with only running the application several times, that's a very good result, I think. OK. So I'm done now. Are there any questions? Yes? I might have used it, but could you mention how much overhead is the information that is feasible with the application running in reduction of the information? So I did not really mention it. The question was how much overhead there is. And the overhead is really noticeable. You don't want to distribute an instrumented binary. I think it was about factor 2 or so. It's really slow. So you do not want to really distribute this. More questions? So what makes it the funded-based instrumentation also IR-based instrumentation or it's unauthorized? Excuse me. Could you repeat? OK. So what makes it the funded-based instrumentation or the IR-based instrumentation? I don't get it. Back then. The agency instead of the MIR? Yeah. So the question was why we choose this approach with the source code instrumentation. That's the generic way to do it. It's work with all backends. So we simply added one and we have it there. There's another implementation that is inside of the end of the error. This is like when you did this. And there are some arguments to be made that virtual code promotion is easier or harder in some scenarios. Basically, we had it around. And we might actually, if it turns out to be terrible, we might just ditch it and we'll be able to respond. OK. Thanks. Yeah. Thanks for the talk. It was interesting. So I think that you were wondering whether you could profile memory accesses or memory allocations and then choose the GC triggers, the garbage collection triggering to put the simulation. Yes. Yes. So far, the idea is pretty cool because you can optimize all this function code and stuff like that. Can you also play or do you think of playing with the garbage collector? OK. So the question is if the instrumentation could also be used for other kind of stuff, for example, memory allocations. And at this point, no. So it's also only this optimization for the indirect code promotion. But for sure, that's the profile-guided optimization. It's an array of active development in LLVM. So yes, it should be possible. But there's no work for it yet. But yes, it should work. Is there a way to, my understanding is that it's worked very well if the actual function can be enlightened at the end. If it has to be called eventually, then you're not much better than what the ECU would do anyway. Yeah. So the question is if the function is not enlightened, then there's no big benefit with using this optimization. And yeah, it really depends. And it depends on the way the CPU works because it has a lot to do with the branch prediction in the CPU. So if you're doing an indirect call and the CPU cannot predict the right target, then there might be a lot of stuff the CPU has to do internally. So it really depends on your target if this is a good optimization or if it has no benefit. So no general answer in this case. We really have to measure it. My thought would be is there a way to remove the optimization of the check at the beginning if you see, OK, enlightening doesn't make that specific argument. Yeah, that's a kind of problem here because we use data which is collected from runtime. And from there you don't have the absolute knowledge about all the possible inputs and all the possible branches which can be used. You would do to have some kind of, let's say, global program analysis to really deduce to say that's the only target for this pointer. And that's not possible now. So if you had an LTO, if you run this, imagine that the setting, the pointer is not a global setting. So I mean, the LTO doesn't know without LTO what the target is. But with PGO it says this is the most likely, then you would have to point the whole thing out of the loop and say return 42,000. If the pointer is this, return 42,000, otherwise go through the loop. And that would be a big saving. So LTO is also supported with LDC. So this could be combined. OK, more questions? If not, then thank you very much. Thank you.
 Hello, as Renato said, my name is Kai.  I'm one of the maintainers of the LDCD compiler.  And today I'm talking about the profile guided  optimization, which was recently added to the compiler.  OK, there's a lot of specific words in there.  Let's explain what it is all is.  So what is profile guided optimization?  It's recently added to LLVM.  It's based on a simple idea.  I can have better optimizations if I have more  informations.  And what is the source for more informations I can use  for optimization?  Well, I can do a lot of static analysis.  And there's a theory about it that's a lot of stuff.  It's hard work.  And you always can't determine everything just from  looking at the source.  So another way to get information for optimization is  to just look at the running application and get  information from the application itself.  And to do this, there are two approaches.  One approach is I can sample the application.  I just stop the application in certain amounts of time, look  where is the application and store this data.  That's one way to do it.  I'm going not to cover this in this talk.  I'm just covering instrumentation of the source.  So that's a LLVM.  This is a common approach.  We have, for example, the sanitizers, which also add  some instrumentation and do certain stuff.  So for optimization, what information do I want to know?  For example, I want to know how often is a function called?  Or if I have a branch, and if how often is the positive, or  how often is the branch taken, or how often is it not taken.  I simply can count this.  Or for example, I can count how often calls the function A,  the function B, to know the dependency for this.  So I have to add a lot of counters to the source and  collect all these data.  I run my application.  I collect this data.  I dump this to the hard disk.  And then I have something which we call a profile of the  application.  Yes.  This is also the main drawback.  We run the application to create the information.  So the quality of the information we derive depends on  the run we do.  If we run the application with an average input, I can expect  to get some good result.  If I run it with an exceptional input, so I look just for  specific cases, then I get a profile which does not cover  everything.  And this can also result in, well, not an optimization, but  in the performance loss, because I'm pointing the  optimizer to the wrong places to optimize.  So it's a good way to get information about to use in  optimization, but you have to be careful.  So the very, very important point with every optimization,  by the way, is you have to measure.  Just to say, this is a proven optimization.  I just use it blindly and think everything will be good.  This does not work.  So be sure to measure your result.  OK.  So this first was about what is profile  guided optimization.  The next thing is what is this D language?  Everybody heard of D?  OK.  So by the way, there's David, the other maintainer of the  LDC, so we have very competent support for it.  OK.  You're the maintainer now, though.  OK.  Yes.  So what is D for the people who did not heard about it?  D was created as a system programming language.  It was about 99 or 2000 when it appeared the first time.  And it was really meant to be what the name implies, a  better C++.  But today, we are proud of having our own language.  But yeah, we're using C like syntax, so you can immediately  read it if you are known to C or C++.  We also use static typing.  That's also the same like C++.  What's better, we have a good module support.  So this will come in C++, I think, in the next standard.  Also, we already had it, and it's very good.  And one of the good points of the language is we support  many paradigms.  So we have polymorphism.  You can do some object-oriented programming.  We also support the functional style if you prefer that.  We have generics and a lot of other style.  And it's all well integrated.  So you don't have to switch to this style or this style.  You can mix it up, and it works all good together.  From templates, I also know from C++.  But with D, it's going to be a step further.  We have really template meta-programming with a nice  edit if.  So then you can choose which template is selected based on  some conditions.  Let's make it very easy to use template meta-programming,  and it's not the hard stuff in C++.  That's very nice.  Yeah, we use a garbage collector.  This is always a point of discussion.  Is this good or is this not good?  The language uses this, but there's also work on it to  replace it with or to make it, let's say, a plug-in and to  use memory management by hand, for example.  It has some drawbacks, maybe.  But let's see, a garbage collector is always a safety  guard.  You don't have certain memory problems with it.  And also nice, a unique feature, I think.  It's called compile-time function execution.  You can say that certain functions are executed by  the compiler, not at runtime, but at compile-time, so that  you don't have to run it at runtime just to insert the  result into the binary, and that's it.  That can make things very fast.  For example, if you have regular expressions, and you  know the expressions at compile-time, then you can  compile this regular expression into decode.  And this gets all the optimization done by LLVM, and  that's very, very fast.  So there are certain use cases for it, and that makes it  very nice.  Yes, LDC is one of the decompilers available.  And it's, let's say, a combined afford.  We have a reference compiler.  It's the dDMD compiler.  And the first d comes from the fact that the front end is  now written in d itself.  And LDC uses this front end and adds some C++ glue code to  it to generate the LLVM ER, and then uses the LLVM backends.  So we support a lot of the backends LLVM support, but  we are just copying the reference front.  And so we say we are really compatible with our compiler,  but we generate a really industrial style machine  code.  That's very good.  If someone is more interested about the compiler, I think in  2014 I had at this place a talk about the inner working of  LDC.  So you can download the slides on the first name page.  If you want to know more about it.  OK, so we have now the part profile guided optimization,  which is provided by LLVM.  We have the LDC compiler.  And now we need it to plug this all together.  And yes, this is the latest release.  It's already there.  So if you go to our GitHub page and download the binaries for  Linux, you get it for free.  But of course, the implementation was not for  free.  And one guy, Johann, made the effort to really implement  this.  And this was, let's say, a lot of work.  What was needed to be done?  The first, you have to add the source code  instrumentation, which boils down to we have to insert  the codes to LLVM in Trenzig at the right places.  And if you look at the pull request, then you see a  typical pattern to it.  We have a PGO, profile guided optimization class that's more  or less copied from the same class from Clang.  And this class tracks the state of the current function.  And so what you always see is I have to get a reference to  this tracker class.  I inform this class about the current statement where I'm  currently in.  And at the right place, you have to do something with the  count.  For example, I'm entering the function I have to increment  the counter corresponding to this function.  This is the common pattern.  There are also code to count how is the branch taken or not  taken.  And this must all be added.  So we have a big visitor more or less, which goes through the  abstract syntax tree.  And this needs to do all this stuff.  This was really added.  And that's a lot of work because D is a full feature  language, not a toy language.  So parts of the compiler, the front, and I said, is written  in D. So that's really a lot of work to do.  But there's no automatic way to add it.  Yeah, another point is now that we have the  instrumentation, we also need to add the profiling path to  the path manager.  And one of the things we do with LEC is that we support  different versions of the LLVM back end.  And this leads always to some kind of ugly code because  the instruction profiling path is a bit new.  It was added in LLVM 3.7, I think.  And with LLVM 3.9, the name was changed.  It was renamed.  So just after a year, we had to use this if to say, OK, if  you use a newer version of LLVM, then stick to this  legacy name, and otherwise use the old name.  So that's also a common pattern in the glue code of LEC.  We always have to check for the version of LLVM and then  use this name or that name or different order of  parameters also.  That's sometimes a bit annoying to support.  OK, what else needed to be done?  What else needed to be added?  We have the profile data.  So we collect all these counters, the counter data,  and the counter data is attached to the function or  some basic blocks, for example, for loops or ifs.  And this must be after the end of the program written to  disk.  And this requires a bit of fiddling how to identify  where I am in the source code and put it to disk.  So you have to add some function for reading and  writing this profile data.  And when I'm say reading, this also means we have them, the  data, and we must bring it to LLVM.  And if this is done, we have the metadata of LLVM.  So reading also implies that we go through the data and  attach it again to the LLVM IR.  So it's a bit of work to do this.  Yeah, and not everything is just lowered to machine  instructions by LLVM.  There's also small runtime library.  And the small library we have to link to.  So at first, our driver needs to know if we switch on  profile-guided optimizations, we have to link to an  additional library.  That's one part.  That's easy.  The other part is we need the library.  So we take the easy approach and edit the profile-rt  library to our repository.  And we did this for each supported LLVM version.  So this is a big directory which contains the profile-rt  from, I think, 3.7 to LLVM5 now.  Because that's the easiest way to do it.  Otherwise, we would have another external dependency  which would be annoying.  OK, but that's the whole stuff.  And with this done, we are ready to use profile-guided  optimization with our LDC compiler.  OK, I said the latest release contains it, at least for  Linux, because as far as I know, not available for  Windows, for example.  But with Linux, you can go to our GitHub page, download the  compiler, and everything works as described here.  So what you do, you have a test program or whatever  application you have.  I call it the pgotest.d.  And the first is we have to add the instrumentation during  the compile process.  So you use this LengthlySwitch profile  instra-generate.  I think it's the same name used by Klang.  And this just not only compiles the module, but also adds the  instrumentation.  One good hint here is just give it a different name.  So you know you're having this binary with the  instrumentation.  The reason is simple.  Adding all these counters.  It's a lot of stuff.  And if you're out of luck, you're having a counter for  every basic block.  And this is also a great performance impact.  You do not want to distribute this instrumented  version to any user.  So just use a different name, and everything is right.  OK.  So you now have the instrumented binary.  Just run it.  When you run it, it will write the profile data at the end  to the hard disk.  And two things here.  The default name is default.proffraw.  And you can change this name.  And you want to do this because of two reasons.  Maybe default is a very generic name.  And if you do it a lot, this file will always overwritten.  And the second thing is you will do many runs of it.  And for every run, you would like to collect the data and  just merge it into one profile.  So you really need several of these profile files.  And for this, you can either give it here a name after  with the equal sign and then the name.  Or you can use an environment variable.  And in this name, you can also use some parameters which  can be replaced, for example, with the process ID.  So you can really say I have here a script file and I  run my test application with 10 different inputs.  And you can get 10 different profile data files.  And what you do, if you have these profile data files,  you need to convert it.  Therefore, we have the LEC Prof Data Tool.  There's no magic in it.  It's just a renamed LLVM Prof Data.  But it's renamed because we are tied to a specific LLVM  version.  And again, there can be many LLVM versions installed on the,  for example, in Linux.  And with this, we make sure that we are using the right one  for our tool.  And so this tool has just two basic options, merge and show.  For the run, you use the merge option.  And the merge option, there you give all the prof raw files  you have generated.  And it creates the final profile data file.  And with the output parameter, just give it a name.  There's some format conversion in it.  But basically, it merges all the profiles together  and create a format which is, again, readable by the compiler.  And then you're done.  You can take the second compile one.  In this case, you see use command switch.  You get the profile data with it.  And then LLVM, hopefully, gives you a better optimized  version of your program.  OK.  And again, the hint measures the result.  Because it's only runtime that's really looking at the runtime  behavior of the application.  And it can go wrong.  It might not, but it can go wrong.  So measure the result.  OK.  What kind of optimization is done with this?  With LLVM 3.9, there's a new optimization introduced  which uses exclusively the information derived  from a profile-guided optimization.  And this is called the indirect call promotion.  And I think it's a very important optimization.  Because indirect calls, so I'm calling a function  through a function pointer, that's  very often used in, for example, object-oriented languages.  But also, for example, in C, it's  coming to have a pointer to some function  and do the call about this pointer.  So the optimization we can do here  is when we know which function is called through the pointer,  then I don't use the pointer.  I call the function directly.  And OK, that's the pointer.  The pointer can point to many functions.  So we want to know what is the, let's say,  the most likely called function.  Or the most likely too called functions.  And so how do we get this information?  We simply count how often is this function called  and from where is it called.  And that's exactly the information  we can collect with the profile-guided optimization  in our profile data.  So this is a nice optimization.  And the benefit of this is if we know  what is the most likely called function,  and replace it with a direct call,  then we enable other LLVM optimizations.  For example, function inlining, which  can say that for the most common function,  it's a very, very fast path because we have eliminated  all the branches in it.  Yeah, let's look first at the high level  and then at the low level.  So this is decode, and I think it  should be readable for everyone.  OK, I have a simple function, which is really simple.  It just returns one value.  And there's also a function pointer to it.  And to make the things more interesting,  we're going to have a loop and call this function in a loop.  So there's no sense behind it from this function  doing really something useful.  It only demonstrates we're calling the function  indirectly through a pointer.  OK, and what does the indirect function call promotion do?  It's quite simple.  It checks if the pointer is the most likely called function.  OK, we have only one function.  So that's quite easy.  And if it's the case, then we call this function directly.  And for sure, this is only a heuristic method.  So the compiler does not know what happened with the variable  maybe in other places.  So we also have the forebake and say, OK,  if it's not this function, then just do the call  by the function pointer.  So this is a very simple approach.  And for sure, you can do it yourself.  You don't need compiler support for it.  That's with other optimizations, that is not that easy.  But if you have a good knowledge about which function gets  called, then you can do it yourself.  And yeah, you can really do it in D with the need syntax.  So you can define a template which hides the check for the  most likely function and then call the likely function or  use the function pointer.  And then we have this nice syntax, which is a very  special feature of the language.  But it's readable for, I think, because we say we have the  function pointer and we apply this likely template.  And this template has the most likely function as a  parameter and everything else is hidden another template.  So we could do all this stuff by ourselves and we don't need  the compiler support.  So if you know it, you can do it this way.  But that's not really a very good approach because you have  the problem you don't know, which is the most likely  called function.  Look at LLVM.  It has millions of lines of code.  And at a specific place, what is the most likely  called functions?  Don't know.  So let's do the compiler's work.  Let's go down to the ER level.  So just how is the indirect call represented at the ER level?  It's quite simple.  We load the value of the pointer.  So we have here this pointer and load it into the virtual  register one.  And then we just call the function.  It's a very simple load value and jump.  OK.  So what is the next?  We have the instrumented version.  The instrumented version is the step.  It's an immediate step.  We have to add the counter for the loop.  If you remember, I had a loop.  And we need to count how often is the loop used at this point.  We also need to record which target we do call with this  pointer.  And of course, the loading and calling, the function is  also present.  But there's a lot of stuff around it.  When we run the instrumented application, it generates the  profile data.  You can also use the show argument to the LDC Prof Data  tool and look at the generated profile.  And for example, you see the ICP function.  It has one counter instrumented in it.  And it's called 1,000 times.  That's what I would expect from my source.  And there's also the main function.  There are two counters in it, one for the function and one  for the loop body.  And the function is called 1 time.  So there you can get an overview of your profile.  And now we use the profile data to optimize the function.  And this is with the O3 switch.  We really optimize.  And in this case, well, you see the load, the pointer.  We have a compare with the most likely function, the  ICT function, and then the branch.  And the branch is, if it's not equal, we go to the original  indirect call.  That's the C4 back.  And in the other case, we jump over it.  And this function was very simple.  So the result was inline by LLVM.  And so in the phi instruction, we see, OK, if you come from  the forebody, then use the value 42.  So in the most likely case, there's no jump at all.  And that's what we're going to have.  And also, you see this profile data is attached in the  metadata by LLVM.  Yeah.  What's the result of all this?  Johann, who did the pull request for it, he tested it  also.  And if you only look at the D part of LBC, then the  compiler becomes faster by about 7%.  This was done on a test case from an industrial project.  And so it's not some simplistic benchmark, but it's a real  test case from application.  So that's a very good result in my eyes.  And he had also some more ideas.  And these more ideas are, therefore, only a sample  implementation.  He called it the virtual call promotion, which is the same  as the indirect call promotion, but applies to classes  which uses a file table structure to do the virtual  call.  And with this, there's also ways with the same, this is a  similar approach to replace these virtual calls with  direct calls.  And that's a very interesting approach, but not yet  committed.  Yeah.  So my summary is, it's really worth to have this profile  guided optimization in our toolbox now, because if you're  done it right, you can get a better speed margin.  And I think just having 7% faster application with only  running the application several times, that's a very good  result, I think.  OK.  So I'm done now.  Are there any questions?  Yes?  I might have used it, but could you mention how much  overhead is the information that is feasible with the  application running in reduction of the  information?  So I did not really mention it.  The question was how much overhead there is.  And the overhead is really noticeable.  You don't want to distribute an instrumented binary.  I think it was about factor 2 or so.  It's really slow.  So you do not want to really distribute this.  More questions?  So what makes it the funded-based instrumentation  also IR-based instrumentation or it's unauthorized?  Excuse me.  Could you repeat?  OK.  So what makes it the funded-based instrumentation  or the IR-based instrumentation?  I don't get it.  Back then.  The agency instead of the MIR?  Yeah.  So the question was why we choose this approach with the  source code instrumentation.  That's the generic way to do it.  It's work with all backends.  So we simply added one and we have it there.  There's another implementation that is inside of  the end of the error.  This is like when you did this.  And there are some arguments to be made that virtual code  promotion is easier or harder in some scenarios.  Basically, we had it around.  And we might actually, if it turns out to be terrible, we  might just ditch it and we'll be able to respond.  OK.  Thanks.  Yeah.  Thanks for the talk.  It was interesting.  So I think that you were wondering whether you could  profile memory accesses or memory allocations and then  choose the GC triggers, the garbage collection triggering  to put the simulation.  Yes.  Yes.  So far, the idea is pretty cool because you  can optimize all this function code and stuff like that.  Can you also play or do you think of playing with the  garbage collector?  OK.  So the question is if the instrumentation could also be  used for other kind of stuff, for example, memory allocations.  And at this point, no.  So it's also only this optimization for the indirect  code promotion.  But for sure, that's the profile-guided optimization.  It's an array of active development in LLVM.  So yes, it should be possible.  But there's no work for it yet.  But yes, it should work.  Is there a way to, my understanding is that it's worked  very well if the actual function can be enlightened at the  end.  If it has to be called eventually, then you're not much  better than what the ECU would do anyway.  Yeah.  So the question is if the function is not enlightened, then  there's no big benefit with using this optimization.  And yeah, it really depends.  And it depends on the way the CPU works because it has a  lot to do with the branch prediction in the CPU.  So if you're doing an indirect call and the CPU cannot  predict the right target, then there might be a lot of stuff  the CPU has to do internally.  So it really depends on your target if this is a good  optimization or if it has no benefit.  So no general answer in this case.  We really have to measure it.  My thought would be is there a way to remove the  optimization of the check at the beginning if you see, OK,  enlightening doesn't make that specific argument.  Yeah, that's a kind of problem here because we use data  which is collected from runtime.  And from there you don't have the absolute knowledge about  all the possible inputs and all the possible branches which  can be used.  You would do to have some kind of, let's say, global  program analysis to really deduce to say that's the only  target for this pointer.  And that's not possible now.  So if you had an LTO, if you run this, imagine that the  setting, the pointer is not a global setting.  So I mean, the LTO doesn't know without LTO what the target  is.  But with PGO it says this is the most likely, then you would  have to point the whole thing out of the loop and say  return 42,000.  If the pointer is this, return 42,000, otherwise go through  the loop.  And that would be a big saving.  So LTO is also supported with LDC.  So this could be combined.  OK, more questions?  If not, then thank you very much.  Thank you.
ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_0_131.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_132_635.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_636_6371.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_6372_13871.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_13872_17747.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_17748_23459.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_23460_31283.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_31284_34283.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_34284_37103.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_37104_39107.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_39108_40067.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_40068_41291.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_41292_42323.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_42324_44075.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_44076_44543.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_44544_44687.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_44688_46343.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_46344_46571.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_46572_55079.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_55080_55175.png ProfileGuided_Optimization_in_the_LDC_D_compiler_Implementation_and_Benefi_55176_55219.png