Can I translate an AST to SSA, or do I need to translate to a CFG then to SSA?

Question

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.

Answer 1

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.