Mirror of forum.nim-lang.org

13471 :: NJVL "no jumps, versioned locations"

• Araq (orginal) [2025-10-21T11:33:27+02:00] view original

  NJVL is an intermediate representation that eliminates unstructured control flow (return, break, goto) in favor of control flow variables. Versioned locations give us all the benefits of SSA without its quirky phi nodes that are subtle to understand and to get rid of during code generation. This design enables powerful optimizations with simple, single-pass algorithms.

  1. Control Flow Variables (cfvars)

  Instead of jumps, use boolean variables to represent control flow:

  
  # Rewrite:
  if cond: return
  body
  
  # To:
  var ret = false
  if cond: jret = true
  if not ret:
    body
  Run

  (In the actual implementation control flow vars get some special instructions like jtrue and jfalse that ensure these collapse to goto instructions without overhead.)

  2. Versioned Locations

  All variables get version numbers (like SSA, but for any location):

  
  (var (v x.0 +0) +42)     # x version 0 = 42
  (asgn (v x.0 +1) +99)    # x version 1 = 99
  (call foo (v x.0 +1))    # Use x version 1
  Run

  SSA's phi nodes are replaced by join information for ifs and either for loop back edges. These are at fixed positions in the tree and cannot occur arbitrarily. The versioning scheme (plus join and either) can be ignored entirely by a code generator.

  3. Structured Control Flow

  • (ite condition then-branch else-branch join-points) - if-then-else
  • (loop before-cond cond body after) - while loops
  • (continue (either var +N initial backedge)) - loop back-edges

  Key Benefits

  A single IR to rule them all. Easy to implement:

  • Inlining: The structured control flow means inlining is a simple substitution operation.
  • Move analysis: The versioned locations mean move analysis is a simple forward tree traversal.
  • Destructor injection: The structured control flow means destructor injection is at a simple single exit point per scope.
  • Common subexpression elimination: a simple tree traversal.
  • Copy propagation: a simple tree traversal.
  • "Not nil" checking: a simple tree traversal.
  • Borrow checking: a simple tree traversal.

  For a native code generator:

  • Path fusion and specialization give low level optimizers enough room to schedule instructions as they see fit.
  • Leads to an easy tree based register allocation algorithm that is a generalization of "linear scan" that does not need any "spilling" logic.

---