Class: SyntaxTree::YARV::SeaOfNodes

Inherits:
Object
  • Object
show all
Defined in:
lib/syntax_tree/yarv/sea_of_nodes.rb

Overview

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.

Defined Under Namespace

Classes: Compiler, Edge, InsnNode, MergeNode, PhiNode, SubGraph

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dfg, nodes, local_graphs) ⇒ SeaOfNodes

Returns a new instance of SeaOfNodes.



462
463
464
465
466
 
# 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

Instance Attribute Details

#dfg ⇒ Object (readonly)

Returns the value of attribute dfg.



460
461
462
 
# File 'lib/syntax_tree/yarv/sea_of_nodes.rb', line 460

def dfg
  @dfg
end

#local_graphs ⇒ Object (readonly)

Returns the value of attribute local_graphs.



460
461
462
 
# File 'lib/syntax_tree/yarv/sea_of_nodes.rb', line 460

def local_graphs
  @local_graphs
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



460
461
462
 
# File 'lib/syntax_tree/yarv/sea_of_nodes.rb', line 460

def nodes
  @nodes
end

Class Method Details

.compile(dfg) ⇒ Object 



529
530
531
 
# File 'lib/syntax_tree/yarv/sea_of_nodes.rb', line 529

def self.compile(dfg)
  Compiler.new(dfg).compile
end

Instance Method Details

#to_mermaid ⇒ Object 



468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
 
# 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 ⇒ Object 



499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
 
# 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