Menu
Can I translate an Abstract Syntax Tree directly into SSA form, or will I need to create a control flow graph and then create the Static Single Assignment form from said CFG?
And in the context of a control flow graph: how do I represent this for a c-like program? I'm thinking I could store a graph of the CFG for all the basic blocks in every function, but then when I call a function for example, this may complicate things. Another way I can think of is a CFG for the entire program, i.e. all the source files, but then how would I store information about functions? Could I maybe store a pointer to the function in the basic block (i.e. the parent node)?
If I am generating SSA from a CFG, do I need to worry about having a CFG that represents the control flow of statements? I'm thinking I would only need to represent the basic block control flow.
448
In compiler design, Static Single Assignment ( shortened SSA) is a means of structuring the IR (intermediate representation) such that every variable is allotted a value only once and every variable is defined before it's use.
As of version 4 (released in April 2005) GCC, the GNU Compiler Collection, makes extensive use of SSA. The frontends generate "GENERIC" code that is then converted into "GIMPLE" code by the "gimplifier".
It is a property of program representations (usually IR) designed for enabling various optimizations. Instead of 'normal' variables that can be assigned multiple times, SSA variables can only be assigned once.
Yes, you can create SSA form without building a CFG first, but you cannot use the classical SSA construction algorithm by Cytron et al to do it. There is another algorithm described in the paper Simple and Efficient Construction of Static Single Assignment Form (disclaimer: I'm one of the authors). This algorithm is used in libFirm, in OpenJDK, and in the Go compiler.
Most compilers (afaik) use the one-CFG-per-function model. Each basic block is a node. Statements (aka operations/instructions/etc) belong to one basic block. Some store instructions as a list within each basic block. Some store instructions as a partially ordered graph similar to the CFG.
63
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
