parameterscompilationcompiler-constructionintermediate-languagessa

Do basic block parameters mean code locality?


Most modern compilers use some form of SSA for internal representation, which needs some notation for variables whose values can come from more than one source. The classic version uses phi nodes. Basic block parameters are also an option. As I understand it, they are logically equivalent, block parameters being arguably cleaner, with fewer special cases in the handling code.

I stumbled across this remark from three years ago, at https://www.reddit.com/r/ProgrammingLanguages/comments/9z8qu3/a_new_compiler_backend_called_cranelift_uses/

I must admit I prefer the parameter-passing approach myself, purely for easier debugging: parameter-passing means code locality.

With this style, and unlike PHI nodes, you can analyze each basic block in isolation:

No variable is declared in a far-away land.

No variable is potentially used in a far-away land.

Um?

It seems to me that block parameters are basically the same as phi nodes in this regard. Variables are indeed potentially used in a faraway land, i.e. definition and use may be separated by any number of jumps through blocks that do not mention the variable in question, and the correctness criterion is that definition must dominate all uses, just as if you were using phi nodes.

Am I missing something?


Solution

  • The Cranelift doc that’s the source of your source is a dead link.

    However, you seem to be asking about something orthogonal to a representation as phi functions or basic-block parameters: how to handle definitions in an outer scope. These could be passed either directly or indirectly as extra parameters of either a φ-function or a basic block. In fact, your φ-function will be composed of basic blocks.

    Let's say you have an expression like x*x >= y ? x*x : y, where x is a local variable and y is in some outer scope. You could indeed prevent y from being defined in a faraway land, if you make it a parameter of the local φ-function you generate. That is, you could compile this code as if you had called an inlined function phi_1(x,y), so that it captures all the state it needs. This could even compile efficiently, if you have a good backend for inline functions that you can re-use here.

    Alternatively, either nested blocks or nested functions can refer to variables defined in an outer scope.