DOM algorithm fails if there's a unreachable basic block

[chsasank]

bril/examples/dom.py

Line 52 in 57877b1

nodes = list(reversed(postorder(succ, entry))) # Reverse postorder.

Take this program for example (modified from interp test):

@print(n: int): int {
}
@main: int {
  v: int = const 4;
  jmp .somewhere;
  v: int = const 2;
.somewhere:
  tmp: int = call @print v;
  ret v;
}

Applying to_ssa creates this wrong output

@print(n: int): int {
}
@main: int {
.b1:
  v.0: int = const 4;
  jmp .somewhere;
.b2:
  v.1: int = const 2;
  jmp .somewhere;
.somewhere:
  tmp.0: int = phi __undefined tmp.1 .b1 .b2;
  tmp.1: int = call @print v.0;
  ret v.0;
}

Note the garbage phi instruction tmp.0. This happens because dominators are computed as follows in dom.py (which is then used by to_ssa.py)

{'b1': {'b1'}, 'b2': {'somewhere', 'b1'}, 'somewhere': {'somewhere', 'b1'}}

This is obviously wrong. This happens because get_dom algorithm fails when there's a node/basic block that doesn't have any predecessor that is not reachable from entry.

[chsasank]

One solution is to ignore unreachable nodes. i,e modify this line

bril/examples/dom.py

Line 54 in 57877b1

dom = {v: set(nodes) for v in succ}

to

    dom = {v: set(nodes) for v in nodes}

This creates issues with other algorithms

[chsasank]

Sorry, I am wrong about above solution. This doesn't work. To fix my issue of accurate SSA transformation, I deleted basic blocks are not reachable. Here's my solution: chsasank/llama.lisp@7960abd#diff-bbd860f50f670b11d6286871f98a63200c8929d51b33d2c4b1cc1494f1f3687b