8 ms·

I like the style of the blog but a minor nit I'd change is have a definition what SSA is right at the top. It discusses SSA for quite a while "SSA is a property

by rdtsc 1y ago

I like the style of the blog but a minor nit I'd change is have a definition what SSA is right at the top. It discusses SSA for quite a while "SSA is a property of intermediate representations (IRs)", "it's frequently used" and only 10 paragraphs down actually defines what SSA is > SSA stands for “static single assignment”, and was developed in the 80s as a way to enhance the existing three-argument code (where every statement is in the form x = y op z) so that every program was circuit-like, using a very similar procedure to the one described above. I understand it's one of those "well if you don't know what it is, the post is not for you" but I think it's a nice article and could get people who are not familiar with the details interested in it > The reason this works so well is because we took a function with mutation, and converted it into a combinatorial circuit, a type of digital logic circuit that has no state, and which is very easy to analyze. That's an interesting insight, it made sense to me. I only dealt with SSA when decompiling bytecode or debugging compiler issues, and never knew why it was needed, but that sort of made it click.

vidarh 1y ago
This post is frankly one of the most convoluted discussions of SSA I've read. There's lots of info there, but I'd frankly suggest going back and look at a paper on implementing it. I think I first came across SSA in a paper adding it to Wirths Oberon compiler, and it was much more accessible. Edit: It was this paper by Brandis and Mössenböck: https://share.google/QNoV9G8yMBWQJqC82 https://share.google/QNoV9G8yMBWQJqC82
- jhallenworld 1y ago
  Also I recommend Bob Morgan's book: https://turbo51.com/download/Building-an-Optimizing-Compile-Book-Preview.pdf https://turbo51.com/download/Building-an-Optimizing-Compile-...
  - Rochus 1y ago
    Indeed a great book; I even have a paper copy. The SSA book is also pretty good: https://web.archive.org/web/20201111210448/https://ssabook.gforge.inria.fr/latest/ https://web.archive.org/web/20201111210448/https://ssabook.g...
    - mananaysiempre 1y ago
      I’ve found the SSA book to be... unforgiving in its difficulty. Not in the sense that I thought it to be a bad book but rather in that I was getting the feeling that a dilettante in compilers like me wasn’t the target audience.
      - Rochus 1y ago
        Like so many compiler books from academia.
      - pbiggar 1y ago
        I was involved in making the book. It is very much a book for academics, and came out of an academic conference bringing together people working at the forefront of SSA-based research.
        mananaysiempre 1y ago
        I mean, once again, I’m not really complaining about the book. It’s fairly mathy, sure, but so what. I also actually welcome that it’s a coherent book rather than a bunch of papers in a trenchcoat or a menagerie of neat things people have thought of (*cough* Paxos variants). It’s rather that it’s a bit unusual in that it’s a coherent book whose prerequisites (on top of an old-timey compilers course, say) I don’t think actually exist in book form (I’d love to be proven wrong, as that’s likely what I need to read). The introductory part does make it self-contained in a sense, but it’s more like those grad-level maths books that include a definitions chapter or three: technically you don’t need to know any of that stuff beforehand, true, but in reality if it does more for you than just fill a few gaps and fix terminology, then you’re not going to have a good time with the rest. Again, just my experience, I don’t know if that’s what you were going for. If there was a criticism implied in my initial comment, it’s that I think that the kind of person that goes looking for literature recommendations in this thread isn’t going to have a good time with it, either; so at the very least they should know what they’re signing up for. But I don’t think you’re really disagreeing with that part?..
  - penguin_booze 1y ago
    This only contains the first 3 chapters.
    - cestith 1y ago
      Google says there’s no eBook available, for what that’s worth. https://books.google.com/books/about/Building_an_Optimizing_Compiler.html?id=CXlhQgAACAAJ https://books.google.com/books/about/Building_an_Optimizing_... Yet Amazon says it’s on Kindle. https://www.amazon.com/Building-Optimizing-Compiler-Bob-Morgan-ebook/dp/B008COCE9G https://www.amazon.com/Building-Optimizing-Compiler-Bob-Morg...
- jchw 1y ago
  Honestly, I think it's just something you either like or don't. If all you were trying to do was understand SSA, I agree this blog post is probably inefficient at that particular task, but often blog posts are entertainment as much as education, so meandering through a bunch of different things along the way is part of the deal. Personally I thought there were a lot of pretty interesting insights that I haven't seen a lot of discussion about in other places, though I will admit I mostly learned about SSA from Wikipedia and from people yelling about compilers online.
- Rochus 1y ago
  Thanks for the link. Looks like an interesting paper. Here is the original reference: https://dl.acm.org/doi/10.1145/197320.197331 https://dl.acm.org/doi/10.1145/197320.197331. And here is a better readable postscript version: https://web.archive.org/web/20170706013237/ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe94.ps.gz https://web.archive.org/web/20170706013237/ftp://ftp.ssw.uni...
- anonymousDan 1y ago
  As someone who knows a bit about SSA, what do you make of LLVM's design decision not to use SSA for memory but only registers (i.e. it doesn't have memory SSA)? It has always confused me a bit as to why this was done.
  - vidarh 1y ago
    I don't really follow LLVM. I find it too big and convoluted for the stuff I'm doing.
strbean 1y ago
I learned a bit about SSA in a compiler course. Among many other things, it is crucial for register assignment. You want to know each distinct value that will exist, and the lifetimes of those values, in order to give each a register. Then, if have more distinct values existing at one time than you have registers, you have to push stuff to the stack.
- tylerhou 1y ago
  It is not critical for register assignment -- in fact, SSA makes register assignment more difficult (see the swap problem; the lost copy problem). Lifetime analysis is important for register assignment, and SSA can make lifetime analysis easier, but plenty of non-SSA compilers (lower-tier JIT compilers often do not use SSA because SSA is heavyweight) are able to register allocate just fine without it.
  - tonfa 1y ago
    One nice thing is that it makes register assignment polynomial (the coloring of SSA variables graph is polynomial since it's not an arbitrary graph).
tylerhou 1y ago
Here's a concise explanation of SSA. Regular (imperative) code is hard to optimize because in general statements are not pure -- if a statement has side effects, then it might not preserve the behavior to optimize that statement by, for example: 1. Removing that statement (dead code elimination) 2. Deduplicating that statement (available expressions) 3. Reordering that statement with other statements (hoisting; loop-invariant code motion) 4. Duplicating that statement (can be useful to enable other optimizations) All of the above optimizations are very important in compilers, and they are much, much easier to implement if you don't have to worry about preserving side effects while manipulating the program. So the point of SSA is to translate a program into an equivalent program whose statements have as few side effects as possible. The result is often something that looks like a functional program. (See: https://www.cs.princeton.edu/~appel/papers/ssafun.pdf https://www.cs.princeton.edu/~appel/papers/ssafun.pdf, which is famous in the compilers community.) In fact, if you view basic blocks themselves as a function, phi nodes "declare" the arguments of the basic block, and branches correspond to tailcalling the next basic block with corresponding values. This has motivated basic block arguments in MLIR. The "combinatorial circuit" metaphor is slightly wrong, because most SSA implementations do need to consider state for loads and stores into arbitrary memory, or arbitrary function calls. Also, it's not easy to model a loop of arbitrary length as a (finite) combinatorial circuit. Given that the author works at an AI accelerator company, I can see why he leaned towards that metaphor, though.
- deleted 1y ago
  [deleted]
- rdtsc 1y ago
  Thank you. That’s a great explanation.
- esrauch 1y ago
  > Given that the author works at an AI accelerator company I actually believe he works at Buf.build and his resume is stale, the author previously posted about their Go Protobuf parser hyperpb which is a Buf project. Maybe still "author recently worked at an AI accelerator company" though.
DannyBee 1y ago
The motivation and reason it works is also wrong anyway. Like i get it's a gentle intro, but i think there are ways to accomplish that without being egregiously history rewriting ;) Ken zadeck was my office mate for years, so this is my recollection, but it's also been a few decades, so sorry for any errors :) The reason of why it works is definitely wrong - they weren't even using rewriting forms of SSA, and didn't for a long time. Even the first "fully SSA" compiler (generally considered to be open64) did not rewrite the IR into SSA. The reason it works so well is because it enables you to perform effective per-variable dataflow. In fact, this is the only problem it solves - the ability to perform unrestricted per-variable dataflow quickly. This was obvious given the historical context at the time, but less obvious now that it is history :) In the simplest essence, SSA enables you to follow chains of dataflow for a variable very easily and simply, and that's probably what i would have said instead. It's true that for simple scalar programs, the variable name reuse that breaks these dataflow chains mostly occur at explicit mutation points, but this is not always correct depending on the compiler IR, and definitely not correct you extend it to memory, among other things. It's also not correct at all as you extend the thing SSA enables you to do (per-variable dataflow quickly) to other classes of problems (SSU, SSI, etc). History wise - this post also sort of implies SSA came out of nowhere and was some revolutionary thing nobody had ever thought about, just sort of developed in the 80's. In fact, it was a formalization of attempts at per-variable dataflow they had been working on for a while. I'd probably just say that as a gentle intro, but if you want the rest of history, here you go: Well before SSA, it was already known that lower bounds on bitvector dataflow (the dominant approach at the time of SSA) were not great. Over the years, it turned out they were much better than initially expected, but in the end, worse than anyone wanted as programs got bigger and bigger. N^2 or N^3 bitvector operations for most problems. Incrementality is basically impossible[2]. They were also hard to understand and debug because of dependencies between related variables, etc. Attempts at faster/better dataflow existed in two rough forms, neither of which are bound by the same lower bound: 1. Structured dataflow/Interval analysis algorithms/Elimination dataflow - reduce the CFG into various types of regions with a known system of equations, solve the equations, distribute the results to the regions. Only works well on reducible graphs Can be done incrementally with care. This was mostly studied in parallel to bitvectors, and was thought heavily about before it became known that there was a class of rapid dataflow problems (IE before the late 70's). Understanding the region equations well enough to debug them requires a very deep understanding of the basis of dataflow - lattices, etc. In that sense it was worse than bitvectors to understand for most people. Graph reducibility restrictions were annoying but tractable on forward graphs through node splitting and whatnot (studies showed 90+% of programs at the time had reducible flowgraphs already), but almost all backwards CFG's are not reducible, making backwards dataflow problems quite annoying. In the end, as iterative dataflow became provably faster/etc, and compilers became the province of more than just theory experts, this sort of died[3]. If you ever become a compiler theory nerd, it's actually really interesting to look at IMHO. 2. Per-variable dataflow approaches. This is basically "solve a dataflow problem for single variable or cluster of variables at a time instead of for all variables at once". There were not actually a ton of people who thought this would ever turn into a practical approach: a. The idea of solving reaching definitions (for example) one variable at a time seemed like it would be much slower than solving it for all variables at once. b. It was very non-obvious how to be able to effectively partition variables to be able to compute a problem on one variable (or a cluster of variables) at a time without it devolving into either bitvector-like time bounds or structured dataflow like math complexity. It was fairly obvious at the time that if you culd make it work, you could probably get much faster incremental dataflow solution. SSA came out of this approach. Kenny's thesis dealt with incremental dataflow and partitioned variable problems, and proved time bounds on various times of partitioned/clustered variable problems. You can even see the basis of SSA in how it thinks about things. Here, i'll quote from a few parts: " As the density of Def sites per variable increases, the average size of the affected area for each change will decrease...". His thesis is (amont other things) on a method for doing this that is typical for the time (IE not SSA): "The mechanism used to enhance performance is raising the density of Def sites for each variable. The most obvious way to increase the Use and Def density is to attempt a reduction on the program flow graph. This reduction would replace groups of nodes by a single new node. This new node would then be labeled with infcrmation that summarized the effects of execution through that group of nodes." This is because, as i mentioned, figuring out how to do it by partitioning the variables based on dominance relationships was not known - that is literally SSA, and also because Kenny wanted to finish his thesis before the heat death of the sun. In this sense, they were already aware that if they got "the right number of names" for a variable, the amount of dataflow computation needed for most problems (reaching defs, etc) would become very small, and that changes would be easy to handle. They knew fairly quickly that for the dataflow problems they wanted to solve, they needed each variable to have a single reaching definition (and reaching definitions was well known), etc. SSA was the incremental culmination of going from there to figuring out a clustering/partitioning of variables that was not based on formally structured control flow regions (which are all-variables things), but instead based on local dataflow for a variable with incorporation of the part of the CFG structure that could actually affect the local result for a given variable. It was approached systematically - understanding the properties they needed, figuring out algorithms that solved them, etc. Like a lot of things that turn out to be unexpectedly useful, take the world by storm, whatever, etc, history later seems to try to often represent them as a eureka moment. [1] Bitvectors are assumed to be fixed size, and thus constant cost, but feel free to add another factor of N here if you want. [2] This is not true in the sense that we knew how to recompute the result incrementally, and end up with a correct result, but doing so provably faster than solving the problem from scratch was not possible. [3] They actually saw somewhat of a resurgence in the world of GPUs and more general computation graphs because it all becomes heavily applicable again to solving. However, we almost always have eventually developed easier to understand (even if potentially slower theory-wise) global algorithms and use those instead, because we have the compute power to do it, and this tradeoff is IMHO worth it.
paulmooreparks 1y ago
Yes, this is a problem I see more and more often. Besides the fact that it's always a good habit to spell out an acrostic or abbreviation the first time it's used in an article, there's also the fact that this is, you know, the web, and it's very easy to make a link to a Wikipedia article or something that will explain the term, if you don't want to bother adding your own explanation.
pbiggar 1y ago
I don't think it really explains what it's for though. Here's my explanation (from my PhD thesis on compilers): Static single assignment (SSA) form provides an efficient intermediate representation for program analysis [Cytron et al., 1989, 1991]. It was introduced as a way of efficiently representing dataflow analyses. SSA uses a single key idea: that all variables in the program are renamed so that each variable is assigned a value at a single unique statement in the program. From this key idea, SSA is able to provide a number of advantages over other techniques of dataflow analyses: Factored use-def chain: With a def-use chain, dataflow results may be propagated directly from the assignment of a variable to all of its uses. However, a def-use chain requires an edge from each definition to each use, which may be expensive when a program has many definitions and uses of the same variable. In practice, this occurs in the presence of switch-statements. SSA factors the def-use chain over a φ-node, avoiding this pathological case. Flow-sensitivity: A flow-insensitive algorithm performed on an SSA form is much more precise than if SSA form were not used. The flow-insensitive problem of multiple definitions to the same variable is solved by the single assignment property. The allows a flow-insensitive algorithm to approach the precision of a flow-sensitive algorithm. Memory usage: Without SSA form, an analysis must store information for every variable at every program point. SSA form allows a sparse analysis, where an analysis must store information only for every assignment in the program. With a unique version per assignment, the memory usage of storing the results of an analysis can be considerably lower than using bit-vector or set-based approaches.

by rdtsc 1y ago

vidarh 1y ago

This post is frankly one of the most convoluted discussions of SSA I've read. There's lots of info there, but I'd frankly suggest going back and look at a paper on implementing it. I think I first came across SSA in a paper adding it to Wirths Oberon compiler, and it was much more accessible. Edit: It was this paper by Brandis and Mössenböck: https://share.google/QNoV9G8yMBWQJqC82 https://share.google/QNoV9G8yMBWQJqC82

jhallenworld 1y ago
Also I recommend Bob Morgan's book: https://turbo51.com/download/Building-an-Optimizing-Compile-Book-Preview.pdf https://turbo51.com/download/Building-an-Optimizing-Compile-...
- Rochus 1y ago
  Indeed a great book; I even have a paper copy. The SSA book is also pretty good: https://web.archive.org/web/20201111210448/https://ssabook.gforge.inria.fr/latest/ https://web.archive.org/web/20201111210448/https://ssabook.g...
  - mananaysiempre 1y ago
    I’ve found the SSA book to be... unforgiving in its difficulty. Not in the sense that I thought it to be a bad book but rather in that I was getting the feeling that a dilettante in compilers like me wasn’t the target audience.
    - Rochus 1y ago
      Like so many compiler books from academia.
    - pbiggar 1y ago
      I was involved in making the book. It is very much a book for academics, and came out of an academic conference bringing together people working at the forefront of SSA-based research.
      - mananaysiempre 1y ago
        I mean, once again, I’m not really complaining about the book. It’s fairly mathy, sure, but so what. I also actually welcome that it’s a coherent book rather than a bunch of papers in a trenchcoat or a menagerie of neat things people have thought of (*cough* Paxos variants). It’s rather that it’s a bit unusual in that it’s a coherent book whose prerequisites (on top of an old-timey compilers course, say) I don’t think actually exist in book form (I’d love to be proven wrong, as that’s likely what I need to read). The introductory part does make it self-contained in a sense, but it’s more like those grad-level maths books that include a definitions chapter or three: technically you don’t need to know any of that stuff beforehand, true, but in reality if it does more for you than just fill a few gaps and fix terminology, then you’re not going to have a good time with the rest. Again, just my experience, I don’t know if that’s what you were going for. If there was a criticism implied in my initial comment, it’s that I think that the kind of person that goes looking for literature recommendations in this thread isn’t going to have a good time with it, either; so at the very least they should know what they’re signing up for. But I don’t think you’re really disagreeing with that part?..
- penguin_booze 1y ago
  This only contains the first 3 chapters.
  - cestith 1y ago
    Google says there’s no eBook available, for what that’s worth. https://books.google.com/books/about/Building_an_Optimizing_Compiler.html?id=CXlhQgAACAAJ https://books.google.com/books/about/Building_an_Optimizing_... Yet Amazon says it’s on Kindle. https://www.amazon.com/Building-Optimizing-Compiler-Bob-Morgan-ebook/dp/B008COCE9G https://www.amazon.com/Building-Optimizing-Compiler-Bob-Morg...
jchw 1y ago
Honestly, I think it's just something you either like or don't. If all you were trying to do was understand SSA, I agree this blog post is probably inefficient at that particular task, but often blog posts are entertainment as much as education, so meandering through a bunch of different things along the way is part of the deal. Personally I thought there were a lot of pretty interesting insights that I haven't seen a lot of discussion about in other places, though I will admit I mostly learned about SSA from Wikipedia and from people yelling about compilers online.
Rochus 1y ago
Thanks for the link. Looks like an interesting paper. Here is the original reference: https://dl.acm.org/doi/10.1145/197320.197331 https://dl.acm.org/doi/10.1145/197320.197331. And here is a better readable postscript version: https://web.archive.org/web/20170706013237/ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe94.ps.gz https://web.archive.org/web/20170706013237/ftp://ftp.ssw.uni...
anonymousDan 1y ago
As someone who knows a bit about SSA, what do you make of LLVM's design decision not to use SSA for memory but only registers (i.e. it doesn't have memory SSA)? It has always confused me a bit as to why this was done.
- vidarh 1y ago
  I don't really follow LLVM. I find it too big and convoluted for the stuff I'm doing.

strbean 1y ago

I learned a bit about SSA in a compiler course. Among many other things, it is crucial for register assignment. You want to know each distinct value that will exist, and the lifetimes of those values, in order to give each a register. Then, if have more distinct values existing at one time than you have registers, you have to push stuff to the stack.

tylerhou 1y ago
It is not critical for register assignment -- in fact, SSA makes register assignment more difficult (see the swap problem; the lost copy problem). Lifetime analysis is important for register assignment, and SSA can make lifetime analysis easier, but plenty of non-SSA compilers (lower-tier JIT compilers often do not use SSA because SSA is heavyweight) are able to register allocate just fine without it.
- tonfa 1y ago
  One nice thing is that it makes register assignment polynomial (the coloring of SSA variables graph is polynomial since it's not an arbitrary graph).

tylerhou 1y ago

Here's a concise explanation of SSA. Regular (imperative) code is hard to optimize because in general statements are not pure -- if a statement has side effects, then it might not preserve the behavior to optimize that statement by, for example: 1. Removing that statement (dead code elimination) 2. Deduplicating that statement (available expressions) 3. Reordering that statement with other statements (hoisting; loop-invariant code motion) 4. Duplicating that statement (can be useful to enable other optimizations) All of the above optimizations are very important in compilers, and they are much, much easier to implement if you don't have to worry about preserving side effects while manipulating the program. So the point of SSA is to translate a program into an equivalent program whose statements have as few side effects as possible. The result is often something that looks like a functional program. (See: https://www.cs.princeton.edu/~appel/papers/ssafun.pdf https://www.cs.princeton.edu/~appel/papers/ssafun.pdf, which is famous in the compilers community.) In fact, if you view basic blocks themselves as a function, phi nodes "declare" the arguments of the basic block, and branches correspond to tailcalling the next basic block with corresponding values. This has motivated basic block arguments in MLIR. The "combinatorial circuit" metaphor is slightly wrong, because most SSA implementations do need to consider state for loads and stores into arbitrary memory, or arbitrary function calls. Also, it's not easy to model a loop of arbitrary length as a (finite) combinatorial circuit. Given that the author works at an AI accelerator company, I can see why he leaned towards that metaphor, though.

deleted 1y ago
[deleted]
rdtsc 1y ago
Thank you. That’s a great explanation.
esrauch 1y ago
> Given that the author works at an AI accelerator company I actually believe he works at Buf.build and his resume is stale, the author previously posted about their Go Protobuf parser hyperpb which is a Buf project. Maybe still "author recently worked at an AI accelerator company" though.

DannyBee 1y ago

The motivation and reason it works is also wrong anyway. Like i get it's a gentle intro, but i think there are ways to accomplish that without being egregiously history rewriting ;) Ken zadeck was my office mate for years, so this is my recollection, but it's also been a few decades, so sorry for any errors :) The reason of why it works is definitely wrong - they weren't even using rewriting forms of SSA, and didn't for a long time. Even the first "fully SSA" compiler (generally considered to be open64) did not rewrite the IR into SSA. The reason it works so well is because it enables you to perform effective per-variable dataflow. In fact, this is the only problem it solves - the ability to perform unrestricted per-variable dataflow quickly. This was obvious given the historical context at the time, but less obvious now that it is history :) In the simplest essence, SSA enables you to follow chains of dataflow for a variable very easily and simply, and that's probably what i would have said instead. It's true that for simple scalar programs, the variable name reuse that breaks these dataflow chains mostly occur at explicit mutation points, but this is not always correct depending on the compiler IR, and definitely not correct you extend it to memory, among other things. It's also not correct at all as you extend the thing SSA enables you to do (per-variable dataflow quickly) to other classes of problems (SSU, SSI, etc). History wise - this post also sort of implies SSA came out of nowhere and was some revolutionary thing nobody had ever thought about, just sort of developed in the 80's. In fact, it was a formalization of attempts at per-variable dataflow they had been working on for a while. I'd probably just say that as a gentle intro, but if you want the rest of history, here you go: Well before SSA, it was already known that lower bounds on bitvector dataflow (the dominant approach at the time of SSA) were not great. Over the years, it turned out they were much better than initially expected, but in the end, worse than anyone wanted as programs got bigger and bigger. N^2 or N^3 bitvector operations for most problems. Incrementality is basically impossible[2]. They were also hard to understand and debug because of dependencies between related variables, etc. Attempts at faster/better dataflow existed in two rough forms, neither of which are bound by the same lower bound: 1. Structured dataflow/Interval analysis algorithms/Elimination dataflow - reduce the CFG into various types of regions with a known system of equations, solve the equations, distribute the results to the regions. Only works well on reducible graphs Can be done incrementally with care. This was mostly studied in parallel to bitvectors, and was thought heavily about before it became known that there was a class of rapid dataflow problems (IE before the late 70's). Understanding the region equations well enough to debug them requires a very deep understanding of the basis of dataflow - lattices, etc. In that sense it was worse than bitvectors to understand for most people. Graph reducibility restrictions were annoying but tractable on forward graphs through node splitting and whatnot (studies showed 90+% of programs at the time had reducible flowgraphs already), but almost all backwards CFG's are not reducible, making backwards dataflow problems quite annoying. In the end, as iterative dataflow became provably faster/etc, and compilers became the province of more than just theory experts, this sort of died[3]. If you ever become a compiler theory nerd, it's actually really interesting to look at IMHO. 2. Per-variable dataflow approaches. This is basically "solve a dataflow problem for single variable or cluster of variables at a time instead of for all variables at once". There were not actually a ton of people who thought this would ever turn into a practical approach: a. The idea of solving reaching definitions (for example) one variable at a time seemed like it would be much slower than solving it for all variables at once. b. It was very non-obvious how to be able to effectively partition variables to be able to compute a problem on one variable (or a cluster of variables) at a time without it devolving into either bitvector-like time bounds or structured dataflow like math complexity. It was fairly obvious at the time that if you culd make it work, you could probably get much faster incremental dataflow solution. SSA came out of this approach. Kenny's thesis dealt with incremental dataflow and partitioned variable problems, and proved time bounds on various times of partitioned/clustered variable problems. You can even see the basis of SSA in how it thinks about things. Here, i'll quote from a few parts: " As the density of Def sites per variable increases, the average size of the affected area for each change will decrease...". His thesis is (amont other things) on a method for doing this that is typical for the time (IE not SSA): "The mechanism used to enhance performance is raising the density of Def sites for each variable. The most obvious way to increase the Use and Def density is to attempt a reduction on the program flow graph. This reduction would replace groups of nodes by a single new node. This new node would then be labeled with infcrmation that summarized the effects of execution through that group of nodes." This is because, as i mentioned, figuring out how to do it by partitioning the variables based on dominance relationships was not known - that is literally SSA, and also because Kenny wanted to finish his thesis before the heat death of the sun. In this sense, they were already aware that if they got "the right number of names" for a variable, the amount of dataflow computation needed for most problems (reaching defs, etc) would become very small, and that changes would be easy to handle. They knew fairly quickly that for the dataflow problems they wanted to solve, they needed each variable to have a single reaching definition (and reaching definitions was well known), etc. SSA was the incremental culmination of going from there to figuring out a clustering/partitioning of variables that was not based on formally structured control flow regions (which are all-variables things), but instead based on local dataflow for a variable with incorporation of the part of the CFG structure that could actually affect the local result for a given variable. It was approached systematically - understanding the properties they needed, figuring out algorithms that solved them, etc. Like a lot of things that turn out to be unexpectedly useful, take the world by storm, whatever, etc, history later seems to try to often represent them as a eureka moment. [1] Bitvectors are assumed to be fixed size, and thus constant cost, but feel free to add another factor of N here if you want. [2] This is not true in the sense that we knew how to recompute the result incrementally, and end up with a correct result, but doing so provably faster than solving the problem from scratch was not possible. [3] They actually saw somewhat of a resurgence in the world of GPUs and more general computation graphs because it all becomes heavily applicable again to solving. However, we almost always have eventually developed easier to understand (even if potentially slower theory-wise) global algorithms and use those instead, because we have the compute power to do it, and this tradeoff is IMHO worth it.

paulmooreparks 1y ago

Yes, this is a problem I see more and more often. Besides the fact that it's always a good habit to spell out an acrostic or abbreviation the first time it's used in an article, there's also the fact that this is, you know, the web, and it's very easy to make a link to a Wikipedia article or something that will explain the term, if you don't want to bother adding your own explanation.

pbiggar 1y ago

I don't think it really explains what it's for though. Here's my explanation (from my PhD thesis on compilers): Static single assignment (SSA) form provides an efficient intermediate representation for program analysis [Cytron et al., 1989, 1991]. It was introduced as a way of efficiently representing dataflow analyses. SSA uses a single key idea: that all variables in the program are renamed so that each variable is assigned a value at a single unique statement in the program. From this key idea, SSA is able to provide a number of advantages over other techniques of dataflow analyses: Factored use-def chain: With a def-use chain, dataflow results may be propagated directly from the assignment of a variable to all of its uses. However, a def-use chain requires an edge from each definition to each use, which may be expensive when a program has many definitions and uses of the same variable. In practice, this occurs in the presence of switch-statements. SSA factors the def-use chain over a φ-node, avoiding this pathological case. Flow-sensitivity: A flow-insensitive algorithm performed on an SSA form is much more precise than if SSA form were not used. The flow-insensitive problem of multiple definitions to the same variable is solved by the single assignment property. The allows a flow-insensitive algorithm to approach the precision of a flow-sensitive algorithm. Memory usage: Without SSA form, an analysis must store information for every variable at every program point. SSA form allows a sparse analysis, where an analysis must store information only for every assignment in the program. With a unique version per assignment, the memory usage of storing the results of an analysis can be considerably lower than using bit-vector or set-based approaches.