compiler-constructionssa

Including atomic values in basic blocks


Converting an abstract syntax tree expression to an SSA basic block entails writing out all the operations in the expression in a linear sequence e.g. x * y + 1 gets converted to a list of operations containing the * and + in that order.

Is it usual to include the variable and literal fetches in the list of operations? I.e. should the above produce a list of length 2 or 5?

On the one hand, loading the value of a global variable, or a constant, into a register is an operation that will end up having to be scheduled.

On the other hand, deciding what values will live in registers is something usually done during or after converting away from SSA form.

On the third hand, including atomic values in the linear sequence means you can answer questions like 'what global variables does this function access' by iterating through basic blocks and operations instead of also having to iterate through the arguments of every operation.

Are there other considerations that I'm missing?

To clarify: local variable names generally disappear in SSA (there's no need for them, you can just use a direct pointer to the operation that generated the value). I'm thinking about things that still need names - constants, global variable names, local variables whose address has been taken etc.


Solution

  • It depends on what you want your optimizer to do.

    If you want to have a lot of freedom scheduling the operand fetches (perhaps because they are expensive) you will want to make them explicit so you can manipulate them. (The old Cray machines had Data and Address registers: you could load an Address register and start a fetch to the data register, and then go do something else, finally touching the data register when there are not other computations you can schedule).

    If you don't care much, you can model an entire basic block as a single SSA node with lots of inputs and outputs.