class SyntaxTree::YARV::SeaOfNodes

A sea of nodes is an intermediate representation used by a compiler to represent both control and data flow in the same graph. The way we use it allows us to have the vertices of the graph represent either an instruction in the instruction sequence or a synthesized node that we add to the graph. The edges of the graph represent either control flow or data flow.

Attributes

dfg[R]

local_graphs[R]

nodes[R]

Public Class Methods

compile(dfg) click to toggle source

# File lib/syntax_tree/yarv/sea_of_nodes.rb, line 529
def self.compile(dfg)
  Compiler.new(dfg).compile
end

new(dfg, nodes, local_graphs) click to toggle source

# File lib/syntax_tree/yarv/sea_of_nodes.rb, line 462
def initialize(dfg, nodes, local_graphs)
  @dfg = dfg
  @nodes = nodes
  @local_graphs = local_graphs
end

Public Instance Methods

to_mermaid() click to toggle source

# File lib/syntax_tree/yarv/sea_of_nodes.rb, line 468
def to_mermaid
  Mermaid.flowchart do |flowchart|
    nodes.each do |node|
      flowchart.node("node_#{node.id}", node.label, shape: :rounded)
    end

    nodes.each do |producer|
      producer.outputs.each do |consumer_edge|
        label =
          if !consumer_edge.label
            # No label.
          elsif consumer_edge.to.is_a?(PhiNode)
            # Edges into phi nodes are labelled by the offset of the
            # instruction going into the merge.
            "%04d" % consumer_edge.label
          else
            consumer_edge.label.to_s
          end

        flowchart.link(
          flowchart.fetch("node_#{producer.id}"),
          flowchart.fetch("node_#{consumer_edge.to.id}"),
          label,
          type: consumer_edge.type == :info ? :dotted : :directed,
          color: { data: :green, control: :red }[consumer_edge.type]
        )
      end
    end
  end
end

verify() click to toggle source

# File lib/syntax_tree/yarv/sea_of_nodes.rb, line 499
def verify
  # Verify edge labels.
  nodes.each do |node|
    # Not talking about phi nodes right now.
    next if node.is_a?(PhiNode)

    if node.is_a?(InsnNode) && node.insn.branch_targets.any? &&
         !node.insn.is_a?(Leave)
      # A branching node must have at least one branch edge and
      # potentially a fallthrough edge coming out.

      labels = node.outputs.map(&:label).sort
      raise if labels[0] != :branch0
      raise if labels[1] != :fallthrough && labels.size > 2
    else
      labels = node.inputs.filter { |e| e.type == :data }.map(&:label)
      next if labels.empty?

      # No nil labels
      raise if labels.any?(&:nil?)

      # Labels should start at zero.
      raise unless labels.min.zero?

      # Labels should be contiguous.
      raise unless labels.sort == (labels.min..labels.max).to_a
    end
  end
end