Scalar register propagation.

cfg.rb

require 'pp'

class BasicBlock
  include Enumerable

  attr_accessor :instructions, :children

  def initialize(&block)
    @instructions = []
    @children = []
    block.call(self)
  end

  def <<(instruction)
    @instructions << instruction
  end

  def >>(basic_block)
    @children << basic_block
  end

  def each(visited = [], &block)
    unless visited.include?(self)
      instructions.each(&block)
      children.each do |basic_block|
        basic_block.each(visited << self, &block)
      end
    end
  end

  def to_s
    map(&:to_s).join("\n")
  end

  def vector2scalar
    each(&:update_type)
    each(&:resolve_type)
  end
end

class Instruction
  attr_accessor :operation, :arguments

  def initialize(operation, *arguments)
    @operation = operation
    @arguments = arguments
  end

  def to_s
    "#{operation} #{arguments.map(&:to_s).join(" ")}"
  end

  def dst
    arguments[0]
  end

  def srcs
    arguments[1..-1]
  end

  def update_type
    alpha = Instruction.new(:alpha, *srcs)
    dst.update_type(alpha)
  end

  def resolve_type
    dst.resolve_type
  end
end

class Argument
  attr_accessor :id, :name, :type

  @@ids = Hash.new(0)

  def self.allocate(type)
    allocated = @@ids[type]
    @@ids[type] += 1
    allocated
  end

  def initialize(name, type = :v)
    @type = type
    @name = name
    @id = Argument.allocate(type)
  end

  def to_s
    "#{type}#{id}(#{name})"
  end

  def update_type(instruction)
    @type = instruction
    @id = nil
  end

  def resolve_type(visited = [])
    if type.is_a?(Instruction)
      scalar = type.arguments.reduce(true) do |memo, argument|
        if visited.include?(argument)
          memo
        else
          argument.resolve_type(visited << self)
          memo && argument.type == :s
        end
      end
      @type = scalar ? :s : :v
      @id = Argument.allocate(@type)
    end
  end
end

example1.rb

require_relative 'cfg'

# Collect all arguments once (SSA Dependent)
c1 = Argument.new(:c1, :s)
c2 = Argument.new(:c2, :s)
a1 = Argument.new(:a1)
b1 = Argument.new(:b1)
a2 = Argument.new(:a2)
a3 = Argument.new(:a3)
a4 = Argument.new(:a4)
a5 = Argument.new(:a5)

# Build CFG.

bb5 = BasicBlock.new do |basic_block|
  # a5 = phi(a2, a4)
  basic_block << Instruction.new(:phi, a5, a2, a4)
end

bb3 = BasicBlock.new do |basic_block|
  # a3 = a2 + 1
  basic_block << Instruction.new(:add, a3, a2, c1)
end

bb2 = BasicBlock.new do |basic_block|
  # a2 = phi(a1, a3).
  basic_block << Instruction.new(:phi, a2, a1, a3)

  basic_block >> bb3
  basic_block >> bb5
end
bb3 >> bb2

bb4 = BasicBlock.new do |basic_block|
  # a4 = b1 + 2
  basic_block << Instruction.new(:add, a4, b1, c2)

  basic_block >> bb5
end

bb1 = BasicBlock.new do |basic_block|
  # a1 = 1.
  basic_block << Instruction.new(:mov, a1, c1)
  # b1 = 2.
  basic_block << Instruction.new(:mov, b1, c2)

  basic_block >> bb2
  basic_block >> bb4
end

# Run the analysis.
puts bb1
bb1.vector2scalar
puts "---"
puts bb1

example2.rb

require_relative 'cfg'

# Collect all arguments once (SSA Dependent)
c1 = Argument.new(:c1, :s)
c2 = Argument.new(:c2, :s)
a1 = Argument.new(:a1)
b1 = Argument.new(:b1)
a2 = Argument.new(:a2)
a3 = Argument.new(:a3)
a4 = Argument.new(:a4)
i1 = Argument.new(:i1)
a5 = Argument.new(:a5)

# Build CFG.

bb5 = BasicBlock.new do |basic_block|
  # a5 = phi(a2, a4)
  basic_block << Instruction.new(:phi, a5, a2, a4)
end

bb3 = BasicBlock.new do |basic_block|
  # a3 = a2 + 1
  basic_block << Instruction.new(:add, a3, a2, c1)
end

bb2 = BasicBlock.new do |basic_block|
  # a2 = phi(a1, a3).
  basic_block << Instruction.new(:phi, a2, a1, a3)

  basic_block >> bb3
  basic_block >> bb5
end
bb3 >> bb2

bb4 = BasicBlock.new do |basic_block|
  # a4 = b1 + i1
  basic_block << Instruction.new(:add, a4, b1, i1)

  basic_block >> bb5
end

bb1 = BasicBlock.new do |basic_block|
  # a1 = 1.
  basic_block << Instruction.new(:mov, a1, c1)
  # b1 = 2.
  basic_block << Instruction.new(:mov, b1, c2)

  basic_block >> bb2
  basic_block >> bb4
end

# Run the analysis.
puts bb1
bb1.vector2scalar
puts "---"
puts bb1

example3.rb

require_relative 'cfg'

# Collect all arguments once (SSA Dependent)
c1 = Argument.new(:c1, :s)
c2 = Argument.new(:c2, :s)
a1 = Argument.new(:a1)
b1 = Argument.new(:b1)
a2 = Argument.new(:a2)
a3 = Argument.new(:a3)
a4 = Argument.new(:a4)
i1 = Argument.new(:i1)
a5 = Argument.new(:a5)

# Build CFG.

bb5 = BasicBlock.new do |basic_block|
  # a5 = phi(a2, a4)
  basic_block << Instruction.new(:phi, a5, a2, a4)
end

bb3 = BasicBlock.new do |basic_block|
  # a3 = a2 + i1
  basic_block << Instruction.new(:add, a3, a2, i1)
end

bb2 = BasicBlock.new do |basic_block|
  # a2 = phi(a1, a3).
  basic_block << Instruction.new(:phi, a2, a1, a3)

  basic_block >> bb3
  basic_block >> bb5
end
bb3 >> bb2

bb4 = BasicBlock.new do |basic_block|
  # a4 = b1 + 2
  basic_block << Instruction.new(:add, a4, b1, c2)

  basic_block >> bb5
end

bb1 = BasicBlock.new do |basic_block|
  # a1 = 1.
  basic_block << Instruction.new(:mov, a1, c1)
  # b1 = 2.
  basic_block << Instruction.new(:mov, b1, c2)

  basic_block >> bb2
  basic_block >> bb4
end

# Run the analysis.
puts bb1
bb1.vector2scalar
puts "---"
puts bb1

example4.rb

require_relative 'cfg'

# Collect all arguments once (SSA Dependent)
id1 = Argument.new(:id)
a1 = Argument.new(:a1)
a2 = Argument.new(:a2)
a3 = Argument.new(:a3)
a4 = Argument.new(:a4)
b1 = Argument.new(:b1)
b2 = Argument.new(:b2)
b3 = Argument.new(:b3)
b4 = Argument.new(:b4)
b5 = Argument.new(:b5)
c1 = Argument.new(:c1)
c2 = Argument.new(:c2)
c3 = Argument.new(:c3)
c4 = Argument.new(:c4)
r1 = Argument.new(:r1)

# Build CFG.

bb6 = BasicBlock.new do |basic_block|
  # a4 = phi(a2, a1)
  basic_block << Instruction.new(:phi, a4, a2, a1)

  # b5 = phi(b2, b3)
  basic_block << Instruction.new(:phi, b5, b2, b3)

  # c4 = phi(c1, c2)
  basic_block << Instruction.new(:phi, c4, c1, c2)

  # r1 = c4
  basic_block << Instruction.new(:mov, r1, c4)
end

bb5 = BasicBlock.new do |basic_block|
  # b4 = a1 + c2
  basic_block << Instruction.new(:add, b4, a1, c2)

  # c3 = c2 - 1
  basic_block << Instruction.new(:sub, c3, c2, Argument.new(:const1, :s))
end

bb4 = BasicBlock.new do |basic_block|
  # c2 = phi(c1, c3)
  basic_block << Instruction.new(:phi, c2, c1, c3)

  # b3 = phi(b1, b3)
  basic_block << Instruction.new(:phi, b3, b1, b4)

  basic_block >> bb5
  basic_block >> bb6
end
bb5 >> bb4

bb3 = BasicBlock.new do |basic_block|
  # a3 = b2 + a2.
  basic_block << Instruction.new(:mul, a3, b2, a2)
end

bb2 = BasicBlock.new do |basic_block|
  # b2 = b1 + a1 + id1.
  basic_block << Instruction.new(:add, b2, b1, a1, id1)

  # a2 = phi(a1, a3).
  basic_block << Instruction.new(:phi, a2, a1, a3)

  basic_block >> bb3
  basic_block >> bb6
end
bb3 >> bb2

bb1 = BasicBlock.new do |basic_block|
  # id1 = @id.
  basic_block << Instruction.new(:mov, id1, Argument.new(:@id))

  # a1 = 2.
  basic_block << Instruction.new(:mov, a1, Argument.new(:const2, :s))

  # b1 = 2.
  basic_block << Instruction.new(:mov, b1, Argument.new(:const3, :s))

  # c1 = a1 + b1.
  basic_block << Instruction.new(:add, c1, a1, b1)

  basic_block >> bb2
  basic_block >> bb4
end

# puts bb1
# Run the analysis.
bb1.vector2scalar
# puts "---"
puts bb1

example5.rb

require_relative 'cfg'

# Collect all arguments once (SSA Dependent)
a1 = Argument.new(:a1)
a2 = Argument.new(:a2)
a3 = Argument.new(:a3)
a4 = Argument.new(:a4)
a5 = Argument.new(:a5)
b1 = Argument.new(:b1)
b2 = Argument.new(:b2)
b3 = Argument.new(:b3)

# Build CFG.

bb7 = BasicBlock.new do |basic_block|
  # store a2
  basic_block << Instruction.new(:store, Argument.new(:mem, :s), a2)
end

bb6 = BasicBlock.new do |basic_block|
  # a4 = phi(a2, a3)
  basic_block << Instruction.new(:phi, a4, a2, a3)

  # a5 = a4 + 1
  basic_block << Instruction.new(:add, a5, a4, Argument.new(:const1, :s))
end

bb5 = BasicBlock.new do |basic_block|
  # b3 = b1 * a2
  basic_block << Instruction.new(:mul, b3, b1, a2)
end

bb4 = BasicBlock.new do |basic_block|
  # # a3 = a2 * 2
  # basic_block << Instruction.new(:mul, a3, a2, Argument.new(:const2, :s))

  # a3 = a2 * @id
  basic_block << Instruction.new(:mul, a3, a2, Argument.new(:id))

  basic_block >> bb6
end

bb3 = BasicBlock.new do |basic_block|
  # b2 = phi(b1, b3)
  basic_block << Instruction.new(:phi, b1, b3)

  basic_block >> bb4
  basic_block >> bb5
  basic_block >> bb6
end
bb5 >> bb3

bb2 = BasicBlock.new do |basic_block|
  # a2 = phi(a1, a5)
  basic_block << Instruction.new(:phi, a2, a1, a5)

  basic_block >> bb3
  basic_block >> bb7
end
bb6 >> bb2

bb1 = BasicBlock.new do |basic_block|
  # a1 = 0
  basic_block << Instruction.new(:mov, a1, Argument.new(:const0, :s))

  # b1 = 1
  basic_block << Instruction.new(:mov, b1, Argument.new(:const1, :s))

  basic_block >> bb2
end

# puts bb1
# Run the analysis.
bb1.vector2scalar
# puts "---"
puts bb1

explanation.txt

Start with a CFG, represented as a graph of BasicBlocks containing an array of Instructions each with an array of Arguments. Arguments have a name, a type, and an ID. (I guess it would be smarter to group type and ID)

We can solve the problem in two passes.

The first pass is O(n) visiting each instruction in pre-order. This step "expands" the assigned dst argument, adding an alpha instruction with all of the src arguments. For example:

The instruction
add %tmp3, %tmp1, %tmp2
where
%tmp1 -> vector
%tmp2 -> vector
%tmp3 -> scalar

becomes

add %tmp3, %tmp1, %tmp2
where
%tmp1 -> vector
%tmp2 -> vector
%tmp3 -> alpha %tmp1, %tmp2


The second pass is O(n^2) i think... It does the same pre-order traversal, collapsing the alpha types recursively.

add %tmp3, %tmp1, %tmp2
add %tmp4, %tmp3, %tmp1

%tmp1 -> vector
%tmp2 -> vector
%tmp3 -> alpha %tmp1, %tmp2
%tmp4 -> alpha (alpha %tmp1, %tmp2) %tmp1

becomes

%tmp1 -> vector
%tmp2 -> vector
%tmp3 -> vector
%tmp4 -> vector

by looking at the types of the registers in the alpha instructions. If all arguments are scalar we say we are scalar.

What about the loop?

mov %tmp1, 0
phi %tmp2, %tmp1, %tmp3
add %tmp3, %tmp2, 1

This starts as

%tmp1 -> scalar
%tmp2 -> vector
%tmp3 -> vector

after step 1 becomes

%tmp1 -> scalar
%tmp2 -> alpha %tmp1, (alpha %tmp2, 1)
%tmp3 -> alpha %tmp2, 1

We have %tmp2 depending on %tmp2. But when a variable depends on itself, that means we can say anything about it's type. a.type = a.type. So in the resolution of an argument we pass the original argument down through the recursion, and skip alpha arguments equal to original argument.

Making

%tmp1 -> scalar
%tmp2 -> alpha %tmp1, (alpha %tmp2, 1)
%tmp3 -> alpha %tmp2, 1

equivalent to

%tmp1 -> scalar
%tmp2 -> alpha %tmp1, (alpha 1)
%tmp3 -> alpha %tmp2, 1

which resolves to

%tmp1 -> scalar
%tmp2 -> scalar
%tmp3 -> scalar