4 ms·

>Like what exactly is the implementation of the top 20 optimizations? It can’t be that high right.. I love the full-throated arrogance of this - "I have no ide

>Like what exactly is the implementation of the top 20 optimizations? It can’t be that high right.. I love the full-throated arrogance of this - "I have no idea but I'm sure it's not hard" lol So I'll tell you - each pass is at minimum a paper (mem2reg) and at maximum several dissertations (polly) to understand. Then have fun implementing a basic basic alpha in your compiler that doesn't have all the creature comforts of LLVM - iterators, efficient data-structures, debugging aids, etc. And then give up because a paper or a dissertation is out-of-date like as soon as it's in deadtree form, while LLVM is a living, breathing, tapestry of insights, breakthroughs, and hacks too. I highly recommend you attempt even one pass to get a feel: pick any language that has a parser impl and design an IR for it and then optimize it (designing an IR from scratch can't be that hard can it?)

jimsimmons 3y ago
(tbc I was forthcoming with my arrogance, like it genuinely didn’t make sense to me) Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing. Again not trying to trivialize or be rude. I wish this was something I could ask ChatGPT and trust its outputs but you know I can’t
- lemming 3y ago
  The Programmers’ Credo: we do these things not because they are easy, but because we thought they were going to be easy https://twitter.com/Pinboard/status/761656824202276864 https://twitter.com/Pinboard/status/761656824202276864
- mathisfun123 3y ago
  >Why would constant propagation need a PhD level proficiency to implement? This is false premise or one of those other ones - constant prop might not be complex but constant prop isn't in the top 20 perf codegen relevant passes.
- NavinF 3y ago
  > ask ChatGPT and trust its outputs If anyone's wondering, its response to the GP comment is 100% correct as far as I can tell. Only problem is that it's missing technical details and has a hard time giving specific examples. --- There are several reasons why programming languages might choose to rely on LLVM or other external compilers and optimization frameworks rather than implementing optimizations on their own: Focus on language design: Many programming languages prioritize language design and functionality over compiler optimization. Implementing optimizations can be a complex and time-consuming process, and language designers may prefer to focus on other aspects of the language. Difficulty of optimization: While some optimizations may seem simple in theory, they can be difficult to implement in practice, especially for complex programs. Additionally, different optimizations may interact with each other in unpredictable ways, making it challenging to optimize code effectively. Targeting multiple platforms: Many programming languages are designed to be portable and run on multiple platforms. Relying on external compilers and optimization frameworks like LLVM can help ensure that code is optimized for each platform without requiring extensive platform-specific optimizations. Access to expertise: Compiler optimization is a specialized field that requires a deep understanding of computer architecture, algorithms, and programming languages. By relying on external frameworks like LLVM, programming languages can leverage the expertise of experienced optimization engineers and researchers. As for the implementation of the top 20 optimizations, the specific details will depend on the optimization and the programming language being used. However, many optimizations involve analyzing the code to identify opportunities for improvement and then applying transformations to the code to make it more efficient. Some optimizations, like constant propagation and loop unrolling, may involve relatively simple transformations, while others, like register allocation and instruction scheduling, can be more complex. --- snippets from "Use highly technical details and examples to answer this question.": Memory reuse involves optimizing the use of memory to reduce the number of accesses and minimize cache misses. This can involve techniques such as loop-invariant code motion, which moves code that does not depend on loop variables outside of the loop, or loop fusion, which combines multiple loops that iterate over the same data into a single loop. However, these optimizations may also depend on the specific architecture being targeted, as the optimal memory access patterns may differ depending on the cache size and associativity Writing a high-quality compiler that can handle all of the edge cases and produce optimized code for a wide range of architectures requires a significant amount of expertise and resources. Additionally, using an external compiler can provide a degree of portability, as the same code can be compiled for multiple architectures without requiring changes to the code itself --- snippet from "Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing.": Constant propagation is indeed a relatively simple optimization technique in theory, and it does not require a PhD level proficiency to implement it. In fact, most compilers include some form of constant propagation as part of their optimization pipeline, and many of these implementations are relatively straightforward. However, there are several factors that can make constant propagation more challenging to implement in practice. Some of these factors include: Handling interactions with other optimizations: Constant propagation can interact with other optimizations in non-trivial ways, such as dead code elimination and loop unrolling. Ensuring that these optimizations work together correctly can require careful analysis and testing. Dealing with complex data structures: In some cases, constant propagation may need to deal with complex data structures, such as arrays or pointers. Ensuring that constant propagation works correctly in these cases can require more advanced techniques, such as dataflow analysis or points-to analysis. Supporting language features: Different programming languages may have different rules for when constant propagation is allowed or required. For example, some languages may allow constants to be defined using complex expressions or function calls, while others may require constants to be literal values. Supporting these language features can require additional analysis and code generation logic.
- klik99 3y ago
  A language is like the most flexible user interface possible - anything can be combined with anything else. Imagine how many edge cases, exceptions, quirks, etc you would have to manage and have it still work. Sure you can limit your scope and say "for these constraints, the optimization will give 10x speed up", but in practice that won't cover many cases. For any optimization process to be worth it, it has to applicable in a wide range of situations (simplifying I know) while guaranteeing no ill side effects. Proving algorithms, especially ones that have to function in the real world, is very difficult.
- jlebar 3y ago
  For example, to evaluate something as simple as 1.3+2.4, you need an exact model of your target architecture's fp unit. If you want to cross compile, generate code for x86 while running the compiler on anything other than x86, this means you need to implement 80-bit long double fp in software. If you want to cross compile for PowerPC, you get to build software support for their bespoke "double double" format, which is not IEEE754 128 bit but a totally different thing. Some GPUs (and also CPUs) flush fp denormals, so you also have to handle this in your constant folding. And all that is just to handle addition, one small part of constant folding.
  - vidarh 3y ago
    You're making assumptions about the input languages guarantees about floating point math here. That illustrates the challenge with LLVM: It needs to be complex because it aims to support a very large set of both inputs and outputs. What you say is true in the general case. It may or may not be true for a given compiler depending on input language and output architectures. And, indeed on whether you need to care about cross compilation. It makes an important point that one needs to be more precise when evaluating complexity.
- vidarh 3y ago
  They are not hard assuming you constrain the problem. LLVM is complex because it's trying to generalise to support a huge number of input languages and a huge number of outputs. The upside is that it lets you write generic optimisation passes. The downside is complexity. It's still an open question whether or not that is a good approach in general vs. more specialized code generators and accepting that this means writing specialized optimisation passes. Your answer to that is likely to vary greatly based on goals and which languages and architectures you care about supporting.
gavinhoward 3y ago
> (designing an IR from scratch can't be that hard can it?) I'm not GP, but I am someone designing an IR. No, it's not that hard. A lot of work, yes, but not that hard.
- mathisfun123 3y ago
  Everyone always does this - plays down the amount of work thing X is if they themselves have done thing X. From this perspective you are ineluctably led to a binary classification of hardess: 1. Things that have not been done are hard. 2. Things that have been done are easy. Ok maybe but given the choice between implementing my own IR and using LLVM IR and going to the beach, I choose the latter.
  - gavinhoward 3y ago
    Yes. My definition of hard is "I can't do it without leveling up," in whatever form leveling up may be, such as getting a PhD. I can do it without leveling up, so it is not hard for me. It just goes to show how much I hate C++ that I'll avoid LLVM specifically to avoid it.
  - UncleEntity 3y ago
    Depending on your definition of “from scratch” I’d agree it isn’t all that hard. I mean, if I can do it… Just a couple days ago I was poking at one of my yak shaving projects which involves a generator for IR nodes as part of a backend for… something, haven’t quite decided where it’s going yet. Doesn’t really matter because it’s just the next logical step after the already written AST node generator. This is just something I’m doing because I find it interesting and haven’t spent all that much time on it. All I know is if I want to lower AST to IR I need IR nodes and in order to know what functionality a IR generator needs I must have an IR to target. As they say, you eat an elephant one byte at a time.
- klik99 3y ago
  "designing an IR" may or may not be hard - designing a close-to-optimal generic IR that can be sourced from many different languages and target many different backends, each with their own idiosyncrasies on both ends may not even be "hard" by some definition of hard (apparently one where a lot of work can still be easy), but then designing optimizations and transforms that practically work pretty good across all those hacks and edge cases, enough that major companies now base their toolchains on your optimizations? I'm pretty sure that's gotta be hard
pjmlp 3y ago
Yet, Chrome has given up on using LLVM for V8 JIT exactly because its slowdown wasn't worth the performance gains they were getting out of it. The ART team has taken a similar deciion regaring AOT/JIT toolchain for native code compilation. Adopting LLVM isn't always a success story.
- plagiarist 3y ago
  They have probably made an informed decision. Instead of, "how hard can it be to write optimization passes and different architectures? Like one or two sprints?"
KerrAvon 3y ago
They're asking for ELI5, not saying "you all suck because this is obviously easy."

jimsimmons 3y ago

(tbc I was forthcoming with my arrogance, like it genuinely didn’t make sense to me) Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing. Again not trying to trivialize or be rude. I wish this was something I could ask ChatGPT and trust its outputs but you know I can’t

lemming 3y ago
The Programmers’ Credo: we do these things not because they are easy, but because we thought they were going to be easy https://twitter.com/Pinboard/status/761656824202276864 https://twitter.com/Pinboard/status/761656824202276864
mathisfun123 3y ago
>Why would constant propagation need a PhD level proficiency to implement? This is false premise or one of those other ones - constant prop might not be complex but constant prop isn't in the top 20 perf codegen relevant passes.
NavinF 3y ago
> ask ChatGPT and trust its outputs If anyone's wondering, its response to the GP comment is 100% correct as far as I can tell. Only problem is that it's missing technical details and has a hard time giving specific examples. --- There are several reasons why programming languages might choose to rely on LLVM or other external compilers and optimization frameworks rather than implementing optimizations on their own: Focus on language design: Many programming languages prioritize language design and functionality over compiler optimization. Implementing optimizations can be a complex and time-consuming process, and language designers may prefer to focus on other aspects of the language. Difficulty of optimization: While some optimizations may seem simple in theory, they can be difficult to implement in practice, especially for complex programs. Additionally, different optimizations may interact with each other in unpredictable ways, making it challenging to optimize code effectively. Targeting multiple platforms: Many programming languages are designed to be portable and run on multiple platforms. Relying on external compilers and optimization frameworks like LLVM can help ensure that code is optimized for each platform without requiring extensive platform-specific optimizations. Access to expertise: Compiler optimization is a specialized field that requires a deep understanding of computer architecture, algorithms, and programming languages. By relying on external frameworks like LLVM, programming languages can leverage the expertise of experienced optimization engineers and researchers. As for the implementation of the top 20 optimizations, the specific details will depend on the optimization and the programming language being used. However, many optimizations involve analyzing the code to identify opportunities for improvement and then applying transformations to the code to make it more efficient. Some optimizations, like constant propagation and loop unrolling, may involve relatively simple transformations, while others, like register allocation and instruction scheduling, can be more complex. --- snippets from "Use highly technical details and examples to answer this question.": Memory reuse involves optimizing the use of memory to reduce the number of accesses and minimize cache misses. This can involve techniques such as loop-invariant code motion, which moves code that does not depend on loop variables outside of the loop, or loop fusion, which combines multiple loops that iterate over the same data into a single loop. However, these optimizations may also depend on the specific architecture being targeted, as the optimal memory access patterns may differ depending on the cache size and associativity Writing a high-quality compiler that can handle all of the edge cases and produce optimized code for a wide range of architectures requires a significant amount of expertise and resources. Additionally, using an external compiler can provide a degree of portability, as the same code can be compiled for multiple architectures without requiring changes to the code itself --- snippet from "Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing.": Constant propagation is indeed a relatively simple optimization technique in theory, and it does not require a PhD level proficiency to implement it. In fact, most compilers include some form of constant propagation as part of their optimization pipeline, and many of these implementations are relatively straightforward. However, there are several factors that can make constant propagation more challenging to implement in practice. Some of these factors include: Handling interactions with other optimizations: Constant propagation can interact with other optimizations in non-trivial ways, such as dead code elimination and loop unrolling. Ensuring that these optimizations work together correctly can require careful analysis and testing. Dealing with complex data structures: In some cases, constant propagation may need to deal with complex data structures, such as arrays or pointers. Ensuring that constant propagation works correctly in these cases can require more advanced techniques, such as dataflow analysis or points-to analysis. Supporting language features: Different programming languages may have different rules for when constant propagation is allowed or required. For example, some languages may allow constants to be defined using complex expressions or function calls, while others may require constants to be literal values. Supporting these language features can require additional analysis and code generation logic.
klik99 3y ago
A language is like the most flexible user interface possible - anything can be combined with anything else. Imagine how many edge cases, exceptions, quirks, etc you would have to manage and have it still work. Sure you can limit your scope and say "for these constraints, the optimization will give 10x speed up", but in practice that won't cover many cases. For any optimization process to be worth it, it has to applicable in a wide range of situations (simplifying I know) while guaranteeing no ill side effects. Proving algorithms, especially ones that have to function in the real world, is very difficult.
jlebar 3y ago
For example, to evaluate something as simple as 1.3+2.4, you need an exact model of your target architecture's fp unit. If you want to cross compile, generate code for x86 while running the compiler on anything other than x86, this means you need to implement 80-bit long double fp in software. If you want to cross compile for PowerPC, you get to build software support for their bespoke "double double" format, which is not IEEE754 128 bit but a totally different thing. Some GPUs (and also CPUs) flush fp denormals, so you also have to handle this in your constant folding. And all that is just to handle addition, one small part of constant folding.
- vidarh 3y ago
  You're making assumptions about the input languages guarantees about floating point math here. That illustrates the challenge with LLVM: It needs to be complex because it aims to support a very large set of both inputs and outputs. What you say is true in the general case. It may or may not be true for a given compiler depending on input language and output architectures. And, indeed on whether you need to care about cross compilation. It makes an important point that one needs to be more precise when evaluating complexity.
vidarh 3y ago
They are not hard assuming you constrain the problem. LLVM is complex because it's trying to generalise to support a huge number of input languages and a huge number of outputs. The upside is that it lets you write generic optimisation passes. The downside is complexity. It's still an open question whether or not that is a good approach in general vs. more specialized code generators and accepting that this means writing specialized optimisation passes. Your answer to that is likely to vary greatly based on goals and which languages and architectures you care about supporting.

gavinhoward 3y ago

> (designing an IR from scratch can't be that hard can it?) I'm not GP, but I am someone designing an IR. No, it's not that hard. A lot of work, yes, but not that hard.

mathisfun123 3y ago
Everyone always does this - plays down the amount of work thing X is if they themselves have done thing X. From this perspective you are ineluctably led to a binary classification of hardess: 1. Things that have not been done are hard. 2. Things that have been done are easy. Ok maybe but given the choice between implementing my own IR and using LLVM IR and going to the beach, I choose the latter.
- gavinhoward 3y ago
  Yes. My definition of hard is "I can't do it without leveling up," in whatever form leveling up may be, such as getting a PhD. I can do it without leveling up, so it is not hard for me. It just goes to show how much I hate C++ that I'll avoid LLVM specifically to avoid it.
- UncleEntity 3y ago
  Depending on your definition of “from scratch” I’d agree it isn’t all that hard. I mean, if I can do it… Just a couple days ago I was poking at one of my yak shaving projects which involves a generator for IR nodes as part of a backend for… something, haven’t quite decided where it’s going yet. Doesn’t really matter because it’s just the next logical step after the already written AST node generator. This is just something I’m doing because I find it interesting and haven’t spent all that much time on it. All I know is if I want to lower AST to IR I need IR nodes and in order to know what functionality a IR generator needs I must have an IR to target. As they say, you eat an elephant one byte at a time.
klik99 3y ago
"designing an IR" may or may not be hard - designing a close-to-optimal generic IR that can be sourced from many different languages and target many different backends, each with their own idiosyncrasies on both ends may not even be "hard" by some definition of hard (apparently one where a lot of work can still be easy), but then designing optimizations and transforms that practically work pretty good across all those hacks and edge cases, enough that major companies now base their toolchains on your optimizations? I'm pretty sure that's gotta be hard

pjmlp 3y ago

Yet, Chrome has given up on using LLVM for V8 JIT exactly because its slowdown wasn't worth the performance gains they were getting out of it. The ART team has taken a similar deciion regaring AOT/JIT toolchain for native code compilation. Adopting LLVM isn't always a success story.

plagiarist 3y ago
They have probably made an informed decision. Instead of, "how hard can it be to write optimization passes and different architectures? Like one or two sprints?"

KerrAvon 3y ago

They're asking for ELI5, not saying "you all suck because this is obviously easy."