Have you had experience implementing SSA via sea-of-nodes representation? Could it be that in this case dominance frontier is no longer important and one could use the simpler SSA construction algorithms that do not require dominance frontiers?