9 ms·

PartialExecuter: Reducing WebAssembly size by exploring all executions in LLVM

295 points by apignotti 5y ago

WebAssembly is commonly used as part of web applications, and minimizing its size is especially important. As part of the latest release of Cheerp, our C++ to WebAssembly/JavaScript compiler, we have introduced a powerful new LLVM optimization that aggressively reduce WebAssembly output size at compile time. We have named this optimization 'PartialExecuter', the key idea behind it being taking advantage of known function parameters to find inner code blocks that cannot ever be possibly executed. Such blocks can then be completely removed from the compiled output, significantly reducing its size. What makes this pass more powerful than typical Dead Code Elimination is the ability of reasoning over all the possible executions that the code can take, while being robust to memory stores and side-effects. Moreover, PartialExecuter can even reason over loads as far as they refer to read-only memory. This latter capability is especially useful to drop code from complex functions whose behavior depend on input strings (i.e. printf). We think this work may be of interest for the HN community, and we welcome feedback and questions. In-depth blog post: https://leaningtech.com/reducing-webassembly-size-by-exploring-all-executions-in-llvm/ https://leaningtech.com/reducing-webassembly-size-by-explori...

rowanG077 5y ago
Have you guys looked the literature of supercompilation? This seems to be a special case of it.
- carlopi 5y ago
  Hi, author of the post here, I am not familiar with this concept, do you have any pointers?
  - rowanG077 5y ago
    The idea is to evaluate the program at compile time and obtain a trace of the program that allows you to reconstruct a semantically equivalent program which has some desirable properties. In your case (and most cases in literature) it's done for optimization. Partial evaluation, which is a subset of supercompilation, is similar to what you are doing. See the wiki page: https://en.wikipedia.org/wiki/Partial_evaluation https://en.wikipedia.org/wiki/Partial_evaluation Some literature: https://dl.acm.org/doi/10.1145/5956.5957 https://dl.acm.org/doi/10.1145/5956.5957 https://ndmitchell.com/downloads/paper-rethinking_supercompilation-29_sep_2010.pdf https://ndmitchell.com/downloads/paper-rethinking_supercompi...
- moralestapia 5y ago
  Supercompilation came to my mind as well! Wasm + SC would be a killer deal.
- fulafel 5y ago
  All analytical solutions to optimization problems can be seen as special cases of the brute force search I guess. But SC is impractically slow for anything except a few instructions long sequences. edit: actually I was thinking of superoptimizers, I guess it's a different concept.
  - rowanG077 5y ago
    Supercompilation is not brute force search.
  - titzer 5y ago
    Superoptimizers have gotten a lot better in the past few years. E.g. have a look at [1]. [1] https://arxiv.org/abs/1211.0557 https://arxiv.org/abs/1211.0557
    - fulafel 5y ago
      Thanks, cool stuff. This paper from the same project was also cool: https://raw.githubusercontent.com/StanfordPL/stoke/develop/docs/papers/oopsla15a.pdf https://raw.githubusercontent.com/StanfordPL/stoke/develop/d... Quote from abstract: " For many applications, the best possible code is conditionally correct: the optimized kernel is equal to the code that it replaces only under certain preconditions on the kernel’s inputs. The main technical challenge in producing conditionally correct opti- mizations is in obtaining non-trivial and useful conditions and proving conditional equivalence formally in the pres- ence of loops. We combine abstract interpretation, decision procedures, and testing to yield a verification strategy that can address both of these problems. This approach yields a superoptimizer for x86 that in our experiments produces binaries that are often multiple times faster than those pro- duced by production compilers"
andrewbarba 5y ago
Is this something that could be exposed as a generic CLI tool to replace something like wasm-opt from Binaryen?
- carlopi 5y ago
  A subset of this could possibly be applied at the wasm-opt level, but consider that at the LLVM's IR level there is more information to be leveraged (in particular PartialExecuter uses information on what memory ranges are read-only). In general the whole concept behind Cheerp (C++ to WebAssembly + JavaScript compiler) is doing as much as possible at the LLVM IR level, JavaScript concept included, since it's easier and more powerful to do code transformation there.
- kateinoigakukun 5y ago
  Binaryen implemented partial evaluation at the beginning of this year https://github.com/WebAssembly/binaryen/pull/4438 https://github.com/WebAssembly/binaryen/pull/4438
turminal 5y ago
Are the these new techniques only applicable to WebAssembly? If so, why?
- carlopi 5y ago
  WebAssembly implies static linking (malloc / printf & all are part of the shipped module) and code size matters since it directly influence users (since there might be delays in downloading big payloads). Both factors plays a role in deciding to plan putting work in optimizations like this. There are some general gains to be had with this optimization, and probably the same ideas were already around for a while, but putting together in this way was helped by thinking about WebAssembly specific constraints.
  - sroussey 5y ago
    Code size always matters, and while wasm may be an extreme case, hopefully this kind of benefit can contribute to shrinking other kinds of code targets.
  - pjmlp 5y ago
    Not necessarily, shared libraries are on the WebAssembly roadmap.
    - carlopi 5y ago
      Yes, I wanted to be more nuanced but oversimplified. Thanks for mentioning this!
- eklitzke 5y ago
  GCC and Clang aren't super aggressive with DCE (dead code elimination) because most of the time the complex cases for DCE have essentially no impact on run time performance, and may be expensive to implement (i.e. significantly increase compile times). For example, suppose you have a library that is configured with some options struct that contains a bunch of flags/settings. The behavior of the library changes based on these flags. The compiler will see a bunch of branches like "if (opts.foo) { ... }" and will generate code for all of these branches of. Now let's say you statically compile this library, and in practice in your code you only ever has one set of options enabled. In principle the compiler could figure out which branches can be eliminated based on the single instantiation of the opts struct in your code, and eliminate dead branches. But in practice neither Clang nor GCC will actually do this kind of DCE even at -O3 because it's simply not worth it. By the way, this kind of example is exactly the kind of DCE that the blog post is talking about and could be removed by the new DCE pass implemented by the author. How big of an impact would this kind of DCE make on performance? Well the compiled binary size will be a bit smaller, which is kind of nice. But in practice this will have almost no impact on performance. Loading and mapping an ELF file is practically instantaneous even on huge executables. The branch predictor will predict all of the options branches that are hit repeatedly at close to 100%. Eliminating the branch entirely is in theory better than having a branch with a 100% hit rate, but hard to demonstrate in real world benchmarks for all but the most critical code paths. If there are large pieces of code in the executable that are unused they'll be mapped but won't even be page faulted during program execution. There are some kind of hand wavy arguments you can make about the extra code wasting space in the icache but again it would probably be difficult to actually demonstrate the impact even in microbenchmarks. This isn't to say that there are no benefits to more expensive DCE passes. But they're generally extremely meager, so it's not worth increasing compile times for most applications. Wasm is an exception because compiled assets need to be transferred over the network and apparently it takes longer to load wasm code than it does to map an ELF executable. It's also worth noting that Clang and GCC do a lot of other types of simpler DCE, and these simpler DCE passes can be critical for performance, so I'm not trying to suggest that DCE entirely is worthless; just that the type of DCE presented here is less useful for traditional compilation.
JoshTriplett 5y ago
This looks great! Please consider upstreaming this into LLVM; it would benefit many other users of LLVM. I'd love to see this used in Rust, for instance. What kind of compilation performance do you see for how long this pass takes? Do you apply this to all functions, or to all functions with certain properties, or to functions tagged some particular way?
- masklinn 5y ago
  > This looks great! Please consider upstreaming this into LLVM; it would benefit many other users of LLVM. I'd love to see this used in Rust, for instance. Or in straight C++ for that matter. Though possibly the optimisation passes relies on specific properties of the target which don't exist for non-wasm? I didn't see anything in the writeup but that doesn't mean they don't exist.
  - carlopi 5y ago
    PartialExecuter happens at the LLVM's IR level, and in theory it's fully generic. Then has been only partially tested outside the Cheerp-pipeline, so I would expect it to rely on some implicit assumptions on the kind of legalizations or lowering that are done before-hand. Target-wise, all information is kept encoded in the IR, so that part is easier (the only strange thing that might happens is bumping some alignment to 8, but I expect every target to be able to handle the prescribed IR alignemtn)
- syrusakbary 5y ago
  I'd love if the is pass submitted upstream as well if possible. I think a lot of ecosystems could benefit from the awesome work you did!
- carlopi 5y ago
  Thanks a lot! I also believe it would be cool to upstream this, we will have to sit down and do some planning. Compilation time could improve (I was actually working on this today), but it's already in line with other optimizations, taking < 10% of the time spent doing optimizations on a big codebase we use as benchmark. Currently it's applied to all functions, since runtime it's anyhow somehow linear in the number of Instructions a Function has, but possibly in more costly versions of this (that we have on paper but yet to implement) some logic to filter functions in advance could be used.
deleted 5y ago
[deleted]
jjice 5y ago
Optimizations like this are incredible to me. In my compiler class in college, I was smitten by how different optimizations were performed, and we only ever worked with pretty basic constant propagation and dead code elimination. The work here is incredible. My respect to the entire team.
- carlopi 5y ago
  > My respect to the entire team. Same!
gavinray 5y ago
This company has an x86-to-WASM compiler that lets you execute arbitrary binaries in the browser. Also a JVM to WASM transpiler. There's a fantastic Meetup presentation given by one of them where they show running a C++ multiplayer game with both client AND server running in a browser, using WebRTC as a networking polyfill. Really mindblowing: https://youtu.be/7JUs4c99-mo?t=167 https://youtu.be/7JUs4c99-mo?t=167
- mysterydip 5y ago
  > running a C++ multiplayer game with both client AND server running in a browser, using WebRTC as a networking polyfill Ok, now you have my attention. Been waiting for that possibility for a while!
  - yuri91 5y ago
    If you are interested, here is the article I wrote about that particular project: https://medium.com/leaningtech/porting-a-c-multiplayer-game-to-the-web-with-cheerp-webrtc-and-firebase-29fbbc62c5ca https://medium.com/leaningtech/porting-a-c-multiplayer-game-...
- apignotti 5y ago
  > This company has an x86-to-WASM compiler that lets you execute arbitrary binaries in the browser. Direct link to our latest demo in case anybody would like to see this tech in action: https://webvm.io https://webvm.io
- zeusk 5y ago
  At what point does the browser become an "os", what's next? Chrome hypervisor?
  - dmitrygr 5y ago
    It happened about a decade ago.
  - tentacleuno 5y ago
    Not sure what you mean by hypervisor, but Microsoft does have... Microsoft Defender Application Guard, I believe it's called. It's a totally sandboxed version of Edge.
richdougherty 5y ago
I love all these techniques where you can find static info about a program by 'running' it at compile time. Normally you run a program at runtime (obviously) at which point you have the full environment and inputs, so you can run the program fully. However... you can also kind of "run" a program at compile time. You can do this using some known and some unknown values in the source code, so you can "partially" run it. https://en.wikipedia.org/wiki/Partial_evaluation https://en.wikipedia.org/wiki/Partial_evaluation Or you can use abstract/pretend values instead of real values, so you can "abstractly" interpret it. https://en.wikipedia.org/wiki/Abstract_interpretation https://en.wikipedia.org/wiki/Abstract_interpretation Running at compile time lets you learn things about the program at compile time, allowing advanced optimisations and error checking. You might realise that some code can never execute, so you can remove it (as in the project above). Or you can learn that some code is incorrect and give an error at compile time...
api 5y ago
Please mainstream this in general. It would save a decent amount of RAM if it became a standard part of LLVM and would probably improve overall performance due to cache effects. Dead code sitting in RAM would be bad for cache locality.
- mhh__ 5y ago
  It could save ram but presumably if applied wrong you could waste ram by having multiple copies of the code. So you'd probably want to profile guide this.
  - api 5y ago
    Dead code removal and deduplication are orthogonal aren't they? You can already turn off verbosity increasing things with -Os etc.
- astrange 5y ago
  PGO already solves that if you can do hot/cold splitting, though I don't think that pass in LLVM is very maintained.
landr0id 5y ago
This is sweet! This is actually a very similar approach to how I deobfuscate Python bytecode: https://github.com/landaire/unfuck/blob/bfa164b4e261deffeb37270de486fd2fbb877535/src/partial_execution.rs#L47 https://github.com/landaire/unfuck/blob/bfa164b4e261deffeb37... My code is pretty messy, but I take the same exact approach of taking known function parameters, interpreting the instructions, and removing any condition and the instructions which built its arguments if it evaluates to a constant value. Even called it partial execution as well :p
- carlopi 5y ago
  Congrats, later will check & take inspiration!
titzer 5y ago
Nice work. I love simple and "conservative brute force" techniques like this--brute force in that you run all the example call sites in the interpreter, conservative in that it bails out when things get hard (e.g. bail out if a single basic block is executed too many times). I am wondering if this technique could be hybridized with abstract interpretation or partial evaluation, which are known techniques in compilers. In essence, this would become a type of concolic execution.
- carlopi 5y ago
  The step forward that I believe worked well here is that given some actual paths (and since they are simply a sequence of Instruction, they can be fed to an interpreter) they are merged or forked while entering or exiting SCCs, this allows to keep a low count of actual visit but exploring a big enough set of path to prove that it covers all possible executions. On the second part, I have to do some thinking and coming back, thanks!
deleted 5y ago
[deleted]
densh 5y ago
Thanks for sharing, we ended up designing something very similar in Scala Native [1]. The use case we had was to explore all possible code paths was to reduce the overhead of virtual call dispatch (since very often virtual calls have very few targets in practice), which is extremely dominant and prohibitive in JVM languages unless optimized away. I hope to see your work upstream in LLVM. [1]: https://scala-native.readthedocs.io/en/latest/blog/interflow.html https://scala-native.readthedocs.io/en/latest/blog/interflow...
- carlopi 5y ago
  Devirtualization is always plenty of fun + has lots of potential. Added to the list of article to read.
jhgb 5y ago
> We have named this optimization 'PartialExecuter', the key idea behind it being taking advantage of known function parameters to find inner code blocks that cannot ever be possibly executed. I'm wondering, what exactly are the differences of this approach from "classical" partial evaluation? This seems to be a special case of it, unless I missed something.
- carlopi 5y ago
  I am not completely sure of what "classical" partial evaluation is, but probably yes, this is somehow a special case of it. I have now quite some material to read (see other links about partial evaluation or super-compilation).
sabr 5y ago
Annotated article: https://smort.io/5e621c00-3c95-4807-b0be-488947a34d8a https://smort.io/5e621c00-3c95-4807-b0be-488947a34d8a For the first image to render correctly, please change the theme to light mode
- mkl 5y ago
  So you highlighted a few sentences? What's the point, other than advertising your project?
  - sabr 5y ago
    I made highlights as well as formatting changes that I found insightful. Sharing it so that others can benefit from it too :)
hackcasual 5y ago
How does this differ from existing LLVM interprocedural optimizations? Particularly value propagation sounds like it would handle a lot of these cases. > You might have heard of dead-code elimination, an LLVM optimization pass that removes code proven as unreachable. I was actually interested in less-obvious situations. In particular blocks that are reachable on the control flow graph, but not when consider wider execution invariants. I've got a trivial example here: https://gcc.godbolt.org/z/7EnPG5WM6 https://gcc.godbolt.org/z/7EnPG5WM6 noinline is added to foo to demonstrate Clang is actually changing the number of arguments foo takes, and its inlined the arguments from bar and baz. > Can we use information on the call-sites and the corresponding format strings to prove that some code paths, for example formatting for floating point numbers, are actually never taken? Seems to already have that effect in Clang. Using Emscripten 3.1.3, compiling 2 different main's with just printf("Hello world %d\n", argc); And printf("Hello world %d %f\n", argc, volatileFloatArg); For the single int arg, the top 3 symbols by size are 47.7% 2.65Ki -NAN(IND)% 0 printf_core 7.4% 421 -NAN(IND)% 0 [section Data] 6.6% 375 -NAN(IND)% 0 main And for the one that added a float arg, 34.5% 3.04Ki -NAN(IND)% 0 fmt_fp 28.8% 2.54Ki -NAN(IND)% 0 printf_core 5.1% 464 -NAN(IND)% 0 [section Data] So when a float argument wasn't passed into printf, it did not include fmt_fp, a delegate that handles floating point for printf One issue that can complicate this analysis is linking multiple libraries that reference standard library (or functions in other libraries). If you're linking together object code, without more IR context, LLVM is going to have to be more conservative. So I think if you link in a WASM object code file that references printf, it won't be able to perform all the IPO that will allow it to trim the CFG.
- carlopi 5y ago
  Take this other example: https://gcc.godbolt.org/z/nebP68Tx8 https://gcc.godbolt.org/z/nebP68Tx8 Here by playing HumanCompiler it should be possible to prove that the if condition never evaluates to true, so removing the if is safe. This is an example of optimization that PartialExecuter is able to do. Note that some combinations of other optimizations might also be potentially able to get to this result (say adding a tag "is always power of 2", but doing this in a general way it's what PartialExecuter does well). Somehow similarly, clang might be instructed to enable a check to avoid including printf_float and somehow detect it and exclude it (this is what happens here), but this is hardly generalizable.
Hercuros 5y ago
How much does this optimization save in terms of executable size on realistic examples (i.e. a full-sized code base)? I would naively expect that for most functions you know too little about their arguments or the state in which they will be executed to be able to tell that certain branches will definitely not be taken. Especially since any function that has some mildly interesting side-effects (like loading and storing from a pointer or a class/struct field, or even _calling into any function that does that_) would seem to foil the analysis and turn large chunks of code into "unknown reachability". Rephrasing, I would expect the set of basic blocks that can be removed just by essentially repeated constant propagation of statically-known function arguments to be pretty small. But I would be happy to be proved wrong if that intuition is not right. Printf is somewhat of an exception, since the format strings are usually known at compile time, meaning that a lot of the control flow can indeed be deduced by compile-time evaluation, but for most functions I would not expect that.
cafxx 5y ago
Sounds somewhat similar to the closed-world assumption that graalvm makes (https://www.graalvm.org/22.0/reference-manual/native-image/ https://www.graalvm.org/22.0/reference-manual/native-image/), and the optimizations that assumption enables.
sriram_malhar 5y ago
I don't see any benchmark of this approach ... how much code does it eliminate, what's the performance improvement attributable to PartialExecutor alone?
kateinoigakukun 5y ago
I really hope this will be upstreamed :)

295 points by apignotti 5y ago

rowanG077 5y ago

Have you guys looked the literature of supercompilation? This seems to be a special case of it.

carlopi 5y ago
Hi, author of the post here, I am not familiar with this concept, do you have any pointers?
- rowanG077 5y ago
  The idea is to evaluate the program at compile time and obtain a trace of the program that allows you to reconstruct a semantically equivalent program which has some desirable properties. In your case (and most cases in literature) it's done for optimization. Partial evaluation, which is a subset of supercompilation, is similar to what you are doing. See the wiki page: https://en.wikipedia.org/wiki/Partial_evaluation https://en.wikipedia.org/wiki/Partial_evaluation Some literature: https://dl.acm.org/doi/10.1145/5956.5957 https://dl.acm.org/doi/10.1145/5956.5957 https://ndmitchell.com/downloads/paper-rethinking_supercompilation-29_sep_2010.pdf https://ndmitchell.com/downloads/paper-rethinking_supercompi...
moralestapia 5y ago
Supercompilation came to my mind as well! Wasm + SC would be a killer deal.
fulafel 5y ago
All analytical solutions to optimization problems can be seen as special cases of the brute force search I guess. But SC is impractically slow for anything except a few instructions long sequences. edit: actually I was thinking of superoptimizers, I guess it's a different concept.
- rowanG077 5y ago
  Supercompilation is not brute force search.
- titzer 5y ago
  Superoptimizers have gotten a lot better in the past few years. E.g. have a look at [1]. [1] https://arxiv.org/abs/1211.0557 https://arxiv.org/abs/1211.0557
  - fulafel 5y ago
    Thanks, cool stuff. This paper from the same project was also cool: https://raw.githubusercontent.com/StanfordPL/stoke/develop/docs/papers/oopsla15a.pdf https://raw.githubusercontent.com/StanfordPL/stoke/develop/d... Quote from abstract: " For many applications, the best possible code is conditionally correct: the optimized kernel is equal to the code that it replaces only under certain preconditions on the kernel’s inputs. The main technical challenge in producing conditionally correct opti- mizations is in obtaining non-trivial and useful conditions and proving conditional equivalence formally in the pres- ence of loops. We combine abstract interpretation, decision procedures, and testing to yield a verification strategy that can address both of these problems. This approach yields a superoptimizer for x86 that in our experiments produces binaries that are often multiple times faster than those pro- duced by production compilers"

andrewbarba 5y ago

Is this something that could be exposed as a generic CLI tool to replace something like wasm-opt from Binaryen?

carlopi 5y ago
A subset of this could possibly be applied at the wasm-opt level, but consider that at the LLVM's IR level there is more information to be leveraged (in particular PartialExecuter uses information on what memory ranges are read-only). In general the whole concept behind Cheerp (C++ to WebAssembly + JavaScript compiler) is doing as much as possible at the LLVM IR level, JavaScript concept included, since it's easier and more powerful to do code transformation there.
kateinoigakukun 5y ago
Binaryen implemented partial evaluation at the beginning of this year https://github.com/WebAssembly/binaryen/pull/4438 https://github.com/WebAssembly/binaryen/pull/4438

turminal 5y ago

Are the these new techniques only applicable to WebAssembly? If so, why?

carlopi 5y ago
WebAssembly implies static linking (malloc / printf & all are part of the shipped module) and code size matters since it directly influence users (since there might be delays in downloading big payloads). Both factors plays a role in deciding to plan putting work in optimizations like this. There are some general gains to be had with this optimization, and probably the same ideas were already around for a while, but putting together in this way was helped by thinking about WebAssembly specific constraints.
- sroussey 5y ago
  Code size always matters, and while wasm may be an extreme case, hopefully this kind of benefit can contribute to shrinking other kinds of code targets.
- pjmlp 5y ago
  Not necessarily, shared libraries are on the WebAssembly roadmap.
  - carlopi 5y ago
    Yes, I wanted to be more nuanced but oversimplified. Thanks for mentioning this!
eklitzke 5y ago
GCC and Clang aren't super aggressive with DCE (dead code elimination) because most of the time the complex cases for DCE have essentially no impact on run time performance, and may be expensive to implement (i.e. significantly increase compile times). For example, suppose you have a library that is configured with some options struct that contains a bunch of flags/settings. The behavior of the library changes based on these flags. The compiler will see a bunch of branches like "if (opts.foo) { ... }" and will generate code for all of these branches of. Now let's say you statically compile this library, and in practice in your code you only ever has one set of options enabled. In principle the compiler could figure out which branches can be eliminated based on the single instantiation of the opts struct in your code, and eliminate dead branches. But in practice neither Clang nor GCC will actually do this kind of DCE even at -O3 because it's simply not worth it. By the way, this kind of example is exactly the kind of DCE that the blog post is talking about and could be removed by the new DCE pass implemented by the author. How big of an impact would this kind of DCE make on performance? Well the compiled binary size will be a bit smaller, which is kind of nice. But in practice this will have almost no impact on performance. Loading and mapping an ELF file is practically instantaneous even on huge executables. The branch predictor will predict all of the options branches that are hit repeatedly at close to 100%. Eliminating the branch entirely is in theory better than having a branch with a 100% hit rate, but hard to demonstrate in real world benchmarks for all but the most critical code paths. If there are large pieces of code in the executable that are unused they'll be mapped but won't even be page faulted during program execution. There are some kind of hand wavy arguments you can make about the extra code wasting space in the icache but again it would probably be difficult to actually demonstrate the impact even in microbenchmarks. This isn't to say that there are no benefits to more expensive DCE passes. But they're generally extremely meager, so it's not worth increasing compile times for most applications. Wasm is an exception because compiled assets need to be transferred over the network and apparently it takes longer to load wasm code than it does to map an ELF executable. It's also worth noting that Clang and GCC do a lot of other types of simpler DCE, and these simpler DCE passes can be critical for performance, so I'm not trying to suggest that DCE entirely is worthless; just that the type of DCE presented here is less useful for traditional compilation.

JoshTriplett 5y ago

This looks great! Please consider upstreaming this into LLVM; it would benefit many other users of LLVM. I'd love to see this used in Rust, for instance. What kind of compilation performance do you see for how long this pass takes? Do you apply this to all functions, or to all functions with certain properties, or to functions tagged some particular way?

masklinn 5y ago
> This looks great! Please consider upstreaming this into LLVM; it would benefit many other users of LLVM. I'd love to see this used in Rust, for instance. Or in straight C++ for that matter. Though possibly the optimisation passes relies on specific properties of the target which don't exist for non-wasm? I didn't see anything in the writeup but that doesn't mean they don't exist.
- carlopi 5y ago
  PartialExecuter happens at the LLVM's IR level, and in theory it's fully generic. Then has been only partially tested outside the Cheerp-pipeline, so I would expect it to rely on some implicit assumptions on the kind of legalizations or lowering that are done before-hand. Target-wise, all information is kept encoded in the IR, so that part is easier (the only strange thing that might happens is bumping some alignment to 8, but I expect every target to be able to handle the prescribed IR alignemtn)
syrusakbary 5y ago
I'd love if the is pass submitted upstream as well if possible. I think a lot of ecosystems could benefit from the awesome work you did!
carlopi 5y ago
Thanks a lot! I also believe it would be cool to upstream this, we will have to sit down and do some planning. Compilation time could improve (I was actually working on this today), but it's already in line with other optimizations, taking < 10% of the time spent doing optimizations on a big codebase we use as benchmark. Currently it's applied to all functions, since runtime it's anyhow somehow linear in the number of Instructions a Function has, but possibly in more costly versions of this (that we have on paper but yet to implement) some logic to filter functions in advance could be used.

deleted 5y ago

[deleted]

jjice 5y ago

Optimizations like this are incredible to me. In my compiler class in college, I was smitten by how different optimizations were performed, and we only ever worked with pretty basic constant propagation and dead code elimination. The work here is incredible. My respect to the entire team.

carlopi 5y ago
> My respect to the entire team. Same!

gavinray 5y ago

This company has an x86-to-WASM compiler that lets you execute arbitrary binaries in the browser. Also a JVM to WASM transpiler. There's a fantastic Meetup presentation given by one of them where they show running a C++ multiplayer game with both client AND server running in a browser, using WebRTC as a networking polyfill. Really mindblowing: https://youtu.be/7JUs4c99-mo?t=167 https://youtu.be/7JUs4c99-mo?t=167

mysterydip 5y ago
> running a C++ multiplayer game with both client AND server running in a browser, using WebRTC as a networking polyfill Ok, now you have my attention. Been waiting for that possibility for a while!
- yuri91 5y ago
  If you are interested, here is the article I wrote about that particular project: https://medium.com/leaningtech/porting-a-c-multiplayer-game-to-the-web-with-cheerp-webrtc-and-firebase-29fbbc62c5ca https://medium.com/leaningtech/porting-a-c-multiplayer-game-...
apignotti 5y ago
> This company has an x86-to-WASM compiler that lets you execute arbitrary binaries in the browser. Direct link to our latest demo in case anybody would like to see this tech in action: https://webvm.io https://webvm.io
zeusk 5y ago
At what point does the browser become an "os", what's next? Chrome hypervisor?
- dmitrygr 5y ago
  It happened about a decade ago.
- tentacleuno 5y ago
  Not sure what you mean by hypervisor, but Microsoft does have... Microsoft Defender Application Guard, I believe it's called. It's a totally sandboxed version of Edge.

richdougherty 5y ago

I love all these techniques where you can find static info about a program by 'running' it at compile time. Normally you run a program at runtime (obviously) at which point you have the full environment and inputs, so you can run the program fully. However... you can also kind of "run" a program at compile time. You can do this using some known and some unknown values in the source code, so you can "partially" run it. https://en.wikipedia.org/wiki/Partial_evaluation https://en.wikipedia.org/wiki/Partial_evaluation Or you can use abstract/pretend values instead of real values, so you can "abstractly" interpret it. https://en.wikipedia.org/wiki/Abstract_interpretation https://en.wikipedia.org/wiki/Abstract_interpretation Running at compile time lets you learn things about the program at compile time, allowing advanced optimisations and error checking. You might realise that some code can never execute, so you can remove it (as in the project above). Or you can learn that some code is incorrect and give an error at compile time...

api 5y ago

Please mainstream this in general. It would save a decent amount of RAM if it became a standard part of LLVM and would probably improve overall performance due to cache effects. Dead code sitting in RAM would be bad for cache locality.

mhh__ 5y ago
It could save ram but presumably if applied wrong you could waste ram by having multiple copies of the code. So you'd probably want to profile guide this.
- api 5y ago
  Dead code removal and deduplication are orthogonal aren't they? You can already turn off verbosity increasing things with -Os etc.
astrange 5y ago
PGO already solves that if you can do hot/cold splitting, though I don't think that pass in LLVM is very maintained.

landr0id 5y ago

This is sweet! This is actually a very similar approach to how I deobfuscate Python bytecode: https://github.com/landaire/unfuck/blob/bfa164b4e261deffeb37270de486fd2fbb877535/src/partial_execution.rs#L47 https://github.com/landaire/unfuck/blob/bfa164b4e261deffeb37... My code is pretty messy, but I take the same exact approach of taking known function parameters, interpreting the instructions, and removing any condition and the instructions which built its arguments if it evaluates to a constant value. Even called it partial execution as well :p

carlopi 5y ago
Congrats, later will check & take inspiration!

titzer 5y ago

Nice work. I love simple and "conservative brute force" techniques like this--brute force in that you run all the example call sites in the interpreter, conservative in that it bails out when things get hard (e.g. bail out if a single basic block is executed too many times). I am wondering if this technique could be hybridized with abstract interpretation or partial evaluation, which are known techniques in compilers. In essence, this would become a type of concolic execution.

carlopi 5y ago
The step forward that I believe worked well here is that given some actual paths (and since they are simply a sequence of Instruction, they can be fed to an interpreter) they are merged or forked while entering or exiting SCCs, this allows to keep a low count of actual visit but exploring a big enough set of path to prove that it covers all possible executions. On the second part, I have to do some thinking and coming back, thanks!

deleted 5y ago

[deleted]

densh 5y ago

Thanks for sharing, we ended up designing something very similar in Scala Native [1]. The use case we had was to explore all possible code paths was to reduce the overhead of virtual call dispatch (since very often virtual calls have very few targets in practice), which is extremely dominant and prohibitive in JVM languages unless optimized away. I hope to see your work upstream in LLVM. [1]: https://scala-native.readthedocs.io/en/latest/blog/interflow.html https://scala-native.readthedocs.io/en/latest/blog/interflow...

carlopi 5y ago
Devirtualization is always plenty of fun + has lots of potential. Added to the list of article to read.

jhgb 5y ago

> We have named this optimization 'PartialExecuter', the key idea behind it being taking advantage of known function parameters to find inner code blocks that cannot ever be possibly executed. I'm wondering, what exactly are the differences of this approach from "classical" partial evaluation? This seems to be a special case of it, unless I missed something.

carlopi 5y ago
I am not completely sure of what "classical" partial evaluation is, but probably yes, this is somehow a special case of it. I have now quite some material to read (see other links about partial evaluation or super-compilation).

sabr 5y ago

Annotated article: https://smort.io/5e621c00-3c95-4807-b0be-488947a34d8a https://smort.io/5e621c00-3c95-4807-b0be-488947a34d8a For the first image to render correctly, please change the theme to light mode

mkl 5y ago
So you highlighted a few sentences? What's the point, other than advertising your project?
- sabr 5y ago
  I made highlights as well as formatting changes that I found insightful. Sharing it so that others can benefit from it too :)

hackcasual 5y ago

How does this differ from existing LLVM interprocedural optimizations? Particularly value propagation sounds like it would handle a lot of these cases. > You might have heard of dead-code elimination, an LLVM optimization pass that removes code proven as unreachable. I was actually interested in less-obvious situations. In particular blocks that are reachable on the control flow graph, but not when consider wider execution invariants. I've got a trivial example here: https://gcc.godbolt.org/z/7EnPG5WM6 https://gcc.godbolt.org/z/7EnPG5WM6 noinline is added to foo to demonstrate Clang is actually changing the number of arguments foo takes, and its inlined the arguments from bar and baz. > Can we use information on the call-sites and the corresponding format strings to prove that some code paths, for example formatting for floating point numbers, are actually never taken? Seems to already have that effect in Clang. Using Emscripten 3.1.3, compiling 2 different main's with just printf("Hello world %d\n", argc); And printf("Hello world %d %f\n", argc, volatileFloatArg); For the single int arg, the top 3 symbols by size are 47.7% 2.65Ki -NAN(IND)% 0 printf_core 7.4% 421 -NAN(IND)% 0 [section Data] 6.6% 375 -NAN(IND)% 0 main And for the one that added a float arg, 34.5% 3.04Ki -NAN(IND)% 0 fmt_fp 28.8% 2.54Ki -NAN(IND)% 0 printf_core 5.1% 464 -NAN(IND)% 0 [section Data] So when a float argument wasn't passed into printf, it did not include fmt_fp, a delegate that handles floating point for printf One issue that can complicate this analysis is linking multiple libraries that reference standard library (or functions in other libraries). If you're linking together object code, without more IR context, LLVM is going to have to be more conservative. So I think if you link in a WASM object code file that references printf, it won't be able to perform all the IPO that will allow it to trim the CFG.

carlopi 5y ago
Take this other example: https://gcc.godbolt.org/z/nebP68Tx8 https://gcc.godbolt.org/z/nebP68Tx8 Here by playing HumanCompiler it should be possible to prove that the if condition never evaluates to true, so removing the if is safe. This is an example of optimization that PartialExecuter is able to do. Note that some combinations of other optimizations might also be potentially able to get to this result (say adding a tag "is always power of 2", but doing this in a general way it's what PartialExecuter does well). Somehow similarly, clang might be instructed to enable a check to avoid including printf_float and somehow detect it and exclude it (this is what happens here), but this is hardly generalizable.

Hercuros 5y ago

How much does this optimization save in terms of executable size on realistic examples (i.e. a full-sized code base)? I would naively expect that for most functions you know too little about their arguments or the state in which they will be executed to be able to tell that certain branches will definitely not be taken. Especially since any function that has some mildly interesting side-effects (like loading and storing from a pointer or a class/struct field, or even _calling into any function that does that_) would seem to foil the analysis and turn large chunks of code into "unknown reachability". Rephrasing, I would expect the set of basic blocks that can be removed just by essentially repeated constant propagation of statically-known function arguments to be pretty small. But I would be happy to be proved wrong if that intuition is not right. Printf is somewhat of an exception, since the format strings are usually known at compile time, meaning that a lot of the control flow can indeed be deduced by compile-time evaluation, but for most functions I would not expect that.

cafxx 5y ago

Sounds somewhat similar to the closed-world assumption that graalvm makes (https://www.graalvm.org/22.0/reference-manual/native-image/ https://www.graalvm.org/22.0/reference-manual/native-image/), and the optimizations that assumption enables.

sriram_malhar 5y ago

I don't see any benchmark of this approach ... how much code does it eliminate, what's the performance improvement attributable to PartialExecutor alone?

kateinoigakukun 5y ago

I really hope this will be upstreamed :)