domfront.lua

#!/usr/bin/env lua
local function visit(node, visited_set, exited_nodes)
   visited_set[node] = true

   for _, successor in ipairs(node.next) do
      if not visited_set[successor] then
         visit(successor, visited_set, exited_nodes)
      end
   end

   table.insert(exited_nodes, node)
end

local function enumerate(entry_node)
   local nodes = {}
   visit(entry_node, {}, nodes)

   for i = 1, math.floor(#nodes / 2) do
      nodes[i], nodes[#nodes - i + 1] = nodes[#nodes - i + 1], nodes[i]
   end

   for i = 1, #nodes do
      nodes[i].index = i
   end

   return nodes
end

local function intersect(node1, node2)
   local pointer1 = node1
   local pointer2 = node2

   while pointer1 ~= pointer2 do
      while pointer1.index > pointer2.index do
         pointer1 = pointer1.idom
      end

      while pointer2.index > pointer1.index do
         pointer2 = pointer2.idom
      end
   end

   return pointer1
end

local function set_idoms(nodes, entry_node)
   entry_node.idom = entry_node
   local changed

   repeat
      changed = false

      for _, node in ipairs(nodes) do
         if node ~= entry_node then
            local new_idom

            for _, predecessor in ipairs(node.prev) do
               if predecessor.idom then
                  if not new_idom then
                     new_idom = predecessor
                  else
                     new_idom = intersect(predecessor, new_idom)
                  end
               end
            end

            if new_idom ~= node.idom then
               node.idom = new_idom
               changed = true
            end
         end
      end
   until not changed
end

local function set_fronts(nodes)
   for _, node in ipairs(nodes) do
      node.front = {}
   end

   for _, node in ipairs(nodes) do
      if #node.prev >= 2 then
         for _, predecessor in ipairs(node.prev) do
            local pointer = predecessor

            while pointer ~= node.idom do
               if not pointer.front[node] then
                  pointer.front[node] = true
                  table.insert(pointer.front, node)
               end

               pointer = pointer.idom
            end
         end
      end
   end
end

local function add_node(name_to_node, name)
   if not name_to_node[name] then
      name_to_node[name] = {
         name = name,
         prev = {},
         next = {}
      }
   end

   return name_to_node[name]
end

local function read_graph(stream)
   local entry_node
   local name_to_node = {}

   while true do
      local line = stream:read("*l")

      if not line then
         break
      end

      local name, successors = line:match("^%s*(.-)%s*%->(.*)$")

      if name then
         local node = add_node(name_to_node, name)

         if not entry_node then
            entry_node = node
         end

         for successor_name in successors:gmatch("%S+") do
            local successor = add_node(name_to_node, successor_name)
            table.insert(node.next, successor)
            table.insert(successor.prev, node)
         end
      end
   end

   return entry_node
end

local function names(nodes)
   local res = {}

   for _, node in ipairs(nodes) do
      table.insert(res, node.name)
   end

   table.sort(res)
   return res
end

local function write_graph(stream, nodes)
   for _, node in ipairs(nodes) do
      stream:write(("[%d]: %s (idom: %s)\n"):format(node.index, node.name, node.idom.name))
      stream:write(("   prev: %s\n"):format(table.concat(names(node.prev), " ")))
      stream:write(("   next: %s\n"):format(table.concat(names(node.next), " ")))
      stream:write(("   front: %s\n"):format(table.concat(names(node.front), " ")))
   end
end

local help_message = [[
domfront.lua takes no arguments. It reads graph from stdin in format
   NAME -> NAME NAME NAME ...
where names to the right of the arrow are successors to node
named on the left. Lines not matching this format are ignored.
The first name is the entry node. Unreachable nodes are dropped.
domfront.lua prints graph to stdout, with added information about
immediate dominators and dominance frontiers calculated using
simple algorithm described by in a paper by Cooper, Harvey, Kennedy, 2001.
]]

local function main(args)
   if #args > 0 then
      io.stdout:write(help_message)
      os.exit(0)
   else
      local graph = read_graph(io.stdin)

      if not graph then
         io.stderr:write("Graph is empty.\n")
         os.exit(1)
      else
         local nodes = enumerate(graph)
         set_idoms(nodes, graph)
         set_fronts(nodes)
         write_graph(io.stdout, nodes)
         os.exit(0)
      end
   end
end

main(arg)