class Ikra::AST::SSAGenerator

Converts an AST to single static assignment form (SSA). TODO: Make SSA form minimal, i.e., remove unnecessary assignments (Phi node artifacts).

Public Class Methods

new() click to toggle source
# File lib/ast/ssa_generator.rb, line 12
def initialize
    @aliases = {}
    @ssa_id = 0
end
transform_to_ssa!(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 8
def self.transform_to_ssa!(node)
    node.accept(self.new)
end

Public Instance Methods

merge_aliases(*branch_aliases) { |orig_name| ... } click to toggle source

Merges all “alias” hash maps given by `branch_aliases`. If a conflict is detected, i.e., a variable is renamed to different names in at least to branches, `block` is executed with the original variable name as argument. The block should return the new resolved variable name.

# File lib/ast/ssa_generator.rb, line 52
def merge_aliases(*branch_aliases, &block)
    result = {}

    orig_names = Set.new(branch_aliases.map do |aliases|
        aliases.keys
    end.flatten)

    for orig_name in orig_names
        new_names = Set.new(branch_aliases.map do |aliases|
            aliases[orig_name]
        end)

        if new_names.size > 1
            # Renamed to different values
            result[orig_name] = yield(orig_name)
        else
            result[orig_name] = new_names.first
        end
    end

    return result
end
new_ssa_var_name(old_name = nil) click to toggle source
# File lib/ast/ssa_generator.rb, line 17
def new_ssa_var_name(old_name = nil)
    @ssa_id = @ssa_id + 1

    if old_name == nil
        return "_ssa_var_#{@ssa_id}"
    else
        return "_ssa_var_#{old_name}_#{@ssa_id}"
    end
end
process_while_until_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 146
def process_while_until_node(node)
    node.condition.accept(self)

    before_loop_aliases = @aliases.dup

    node.body_stmts.accept(self)
    loop_body_aliases = @aliases.dup

    # Insert merge statements at the end of the loop body
    @aliases = merge_aliases(before_loop_aliases, loop_body_aliases) do |orig_var|
        # Conflict found
        name_before = before_loop_aliases[orig_var]
        name_inside = loop_body_aliases[orig_var]

        if name_before != nil
            resolved_name = name_before

            node.body_stmts.add_statement(LVarWriteNode.new(
                identifier: name_before, 
                value: LVarReadNode.new(identifier: name_inside)))
        else
            resolved_name = name_inside
        end

        # Resolved name is `name_before`
        resolved_name
    end
end
visit_for_node(node) click to toggle source

TODO: Handle `TernaryNode`

# File lib/ast/ssa_generator.rb, line 116
def visit_for_node(node)
    node.range_from.accept(self)
    node.range_to.accept(self)

    before_loop_aliases = @aliases.dup

    node.body_stmts.accept(self)
    loop_body_aliases = @aliases.dup

    # Insert merge statements at the end of the loop body
    @aliases = merge_aliases(before_loop_aliases, loop_body_aliases) do |orig_var|
        # Conflict found
        name_before = before_loop_aliases[orig_var]
        name_inside = loop_body_aliases[orig_var]

        if name_before != nil
            resolved_name = name_before

            node.body_stmts.add_statement(LVarWriteNode.new(
                identifier: name_before, 
                value: LVarReadNode.new(identifier: name_inside)))
        else
            resolved_name = name_inside
        end

        # Resolved name is `name_before`
        resolved_name
    end
end
visit_if_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 75
def visit_if_node(node)
    node.condition.accept(self)

    branch1_aliases = @aliases.dup
    branch2_aliases = @aliases.dup

    @aliases = branch1_aliases
    node.true_body_stmts.accept(self)
    branch1_aliases = @aliases

    @aliases = branch2_aliases
    node.false_body_stmts.accept(self)
    branch2_aliases = @aliases

    @aliases = merge_aliases(branch1_aliases, branch2_aliases) do |orig_var|
        # Conflict found: `orig_var` renamed in both branches
        name1 = branch1_aliases[orig_var]
        name2 = branch2_aliases[orig_var]

        resolved_name = new_ssa_var_name(orig_var)

        if not node.true_body_stmts.is_a?(BeginNode)
            raise AssertionError.new("Expected a BeginNode")
        end

        if not node.false_body_stmts.is_a?(BeginNode)
            raise AssertionError.new("Expected a BeginNode")
        end

        # TODO: Should check liveness of variables
        node.true_body_stmts.add_statement(LVarWriteNode.new(
            identifier: resolved_name, value: LVarReadNode.new(identifier: name1)))
        node.false_body_stmts.add_statement(LVarWriteNode.new(
            identifier: resolved_name, value: LVarReadNode.new(identifier: name2)))

        resolved_name
    end
end
visit_lvar_read_node(node) click to toggle source
Calls superclass method
# File lib/ast/ssa_generator.rb, line 27
def visit_lvar_read_node(node)
    super

    if @aliases.include?(node.identifier)
        # This variable was renamed
        node.replace(LVarReadNode.new(identifier: @aliases[node.identifier]))
    end
end
visit_lvar_write_node(node) click to toggle source
Calls superclass method
# File lib/ast/ssa_generator.rb, line 36
def visit_lvar_write_node(node)
    super

    # Give the variable a new name
    new_name = new_ssa_var_name(node.identifier)
    @aliases[node.identifier] = new_name

    node.replace(LVarWriteNode.new(
        identifier: new_name,
        value: node.value))
end
visit_until_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 179
def visit_until_node(node)
    process_while_until_node(node)
end
visit_until_post_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 187
def visit_until_post_node(node)
    process_while_until_node(node)
end
visit_while_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 175
def visit_while_node(node)
    process_while_until_node(node)
end
visit_while_post_node(node) click to toggle source
# File lib/ast/ssa_generator.rb, line 183
def visit_while_post_node(node)
    process_while_until_node(node)
end