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.

Evacuate

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.

Chartography

I just finished reading the article-- it's great! I'm just wondering whether it constructs minimal or pruned SSA because sometimes it says "pruned", other times, "minimal", and most of the time "minimal and pruned". – Schlessinger

Is the algorithm really cfg-less? Seems to me that the one presented in the article operates on a cfg. – Grote

I don't think this is CFG-less at all, even though the abstract says it can go from bytecode directly to SSA. From the paper: "the algorithm presented in this paper is the first to construct minimal and pruned SSA on reducible CFGs" and "First, we consider a single basic block. Then, we extend the algorithm to whole CFGs. Finally, we show how to handle incomplete CFGs, which usually emerge when translating an AST to IR." None of those statements are about going from bytecode or linear instructions to SSA. – Denton