1. 22
  1.  

  2. 5

    An interesting alternative to phi nodes is basic block parameters (which happen to be provably equivalent, but somewhat easier to work with).

    See here.

    1. 1

      I was really happy with how block parameters turned out for Cranelift IR. If you’re designing a new IR, I would recommend looking into it. It’s equivalent to SSA, so you can use all the same optimization techniques.

      In the register allocator, passing arguments to a block is very similar to passing arguments to a function call. This makes it a nice notation for an SSA-based register allocator.

    2. 2

      Excellent write up on SSA, LLVM and even a little bit on register allocation. Thanks @yossarian! Forwarding this to a few people.

      1. 2

        compilers that use SSA forms internally do not emit real φ functions in generated code […] Not because they can’t: the SSA form of a program can be executed by evaluating φ with concrete control flow.

        I’m curious how this would work. I thought you always need to translate SSA to something to execute it.

        This paper looks interesting: Interpreting programs in static single assignment form

        LLVM has an interpreter, but it looks like even in that case they translate Phi to something else first:

           void visitPHINode(PHINode &PN) {
             llvm_unreachable("PHI nodes already handled!");
           }
        
        1. 1

          Simplistic idea: before execution, traverse backwards from each phi node and tag each of its control-flow predecessors (i.e. nodes who could branch or jump to that phi node) with their index in the phi node. Then, during execution, when you encounter a tagged node, store the index in a variable and then use it (after the jump) to evaluate the phi node.

          Less simplistic idea: transform the phi node into moves that occur before each of the control-flow predecessors.

          Both require some extra sort of preprocessing step, which I suppose is cheating if you’re gonna be tough about it. You could always just look ahead for a phi node every time you reach a branch or jump and then do one of the above.

        2. 1

          One small correction: _N is not a prefix.

          1. 1

            Indeed it isn’t. Thanks, fixing now.