142 lines
2.7 KiB
Ruby
142 lines
2.7 KiB
Ruby
# alpha conversion (variable renaming)
|
|
|
|
require_relative "ast-def"
|
|
|
|
class ID
|
|
@@num = 0
|
|
|
|
def initialize(name)
|
|
@unified = nil
|
|
@name = "#{ name }:#{ @@num }"
|
|
@@num += 1
|
|
end
|
|
|
|
attr_reader :name, :unified
|
|
|
|
def inspect
|
|
if @unified
|
|
@unified.inspect
|
|
else
|
|
"#<#{ self.class }:#{ @name }>"
|
|
end
|
|
end
|
|
|
|
def unify(other)
|
|
if @unified
|
|
@unified.unify(other)
|
|
elsif other.term != self
|
|
@unified = other
|
|
end
|
|
end
|
|
|
|
def term
|
|
@unified ? @unified.term : self
|
|
end
|
|
|
|
def ==(other)
|
|
term.name == other.term.name
|
|
end
|
|
|
|
alias eql? ==
|
|
|
|
def hash
|
|
if @unified
|
|
@unified.hash
|
|
else
|
|
@name
|
|
end
|
|
end
|
|
end
|
|
|
|
def merge(vars1, vars2)
|
|
vars1.each do |key, var|
|
|
if vars2[key] && vars2[key] != var
|
|
var.unify(vars2[key])
|
|
end
|
|
end
|
|
vars1.merge(vars2)
|
|
end
|
|
|
|
def check_opt_inc_dec(seq)
|
|
seq.each_cons(4) do |insn1, insn2, insn3, insn4|
|
|
next unless insn1.is_a?(IRead)
|
|
next unless insn2 == IPush[1]
|
|
next unless insn3 == IBinary[:+] || insn3 == IBinary[:-]
|
|
next unless insn4 == IWrite[insn1.var]
|
|
insn1.tmp.unify(insn4.tmp)
|
|
end
|
|
|
|
seq.each do |insn|
|
|
case insn
|
|
when IBranch, ILoop
|
|
check_opt_inc_dec(insn.s1)
|
|
check_opt_inc_dec(insn.s2)
|
|
end
|
|
end
|
|
end
|
|
|
|
def alpha(seq, vars)
|
|
nvars = vars.dup
|
|
seq.reverse_each do |insn|
|
|
case insn
|
|
when IRead
|
|
if insn.var
|
|
if insn.tmp
|
|
nvars[insn.var] ||= insn.tmp
|
|
nvars[insn.var].unify(insn.tmp)
|
|
else
|
|
insn.tmp = nvars[insn.var] ||= ID.new(insn.var)
|
|
end
|
|
end
|
|
when IWrite
|
|
if insn.var
|
|
if insn.tmp
|
|
nvars[insn.var] ||= insn.tmp
|
|
nvars[insn.var].unify(insn.tmp)
|
|
else
|
|
insn.tmp = nvars[insn.var]
|
|
end
|
|
nvars.delete(insn.var)
|
|
end
|
|
when IExit
|
|
nvars.clear
|
|
when IBranch
|
|
nvars1 = alpha(insn.s1, nvars)
|
|
nvars2 = alpha(insn.s2, nvars)
|
|
nvars = merge(nvars1, nvars2)
|
|
when ILoop
|
|
begin
|
|
nvars_back = nvars.dup
|
|
nvars1 = alpha(insn.s1, nvars)
|
|
nvars2 = alpha(insn.s1, alpha(insn.s2, nvars))
|
|
nvars = merge(nvars1, nvars2)
|
|
merge(nvars, nvars_back)
|
|
end until nvars.keys == nvars_back.keys
|
|
end
|
|
end
|
|
nvars
|
|
end
|
|
|
|
def rename(seq)
|
|
seq.each do |insn|
|
|
case insn
|
|
when IRead, IWrite
|
|
insn.tmp = ID.new(insn.var) if insn.var == "dummy"
|
|
insn.var.replace insn.tmp.term.name if insn.var
|
|
when IBranch, ILoop
|
|
rename(insn.s1)
|
|
rename(insn.s2)
|
|
end
|
|
end
|
|
end
|
|
|
|
if ARGV.size != 2
|
|
puts "usage: #$0 <seq1.txt> <seq2.txt>"
|
|
else
|
|
seq = eval(File.read(ARGV[0]))
|
|
alpha(seq, {})
|
|
check_opt_inc_dec(seq)
|
|
rename(seq)
|
|
File.write(ARGV[1], seq.pretty_inspect)
|
|
end
|