# copyprop.tcl --
#
# Performs copy propagation on a program in SSA form.
#
# Copyright (c) 2017 by Kevin B. Kenny
#
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
#
#------------------------------------------------------------------------------
# quadcode::transformer method copyprop --
#
# Perform copy propagation on a program in SSA form.
#
# Results:
# Returns 1 if any copies were removed, 0 otherwise
#
# Side effects:
# Quadcode is rewritten so that any use of temporaries that result from
# copy operations is replaced with the sources of the copies.
#
# Copies to source variables are to be left alone because it it is not
# necessarily safe to eliminate them until it is proven that aliasing
# will not affect the results. As an exception, it is safe to propagate
# a copy of a source variable to itself.
#
# For temporaries, it is safe to propagate copies.
oo::define quadcode::transformer method copyprop {} {
set changed 0
my debug-copyprop {
puts "Before copy propagation:"
my dump-bb
}
# Walk thorough all the instructions, looking for copies
foreach b [my bborder] {
set outpc -1
for {set pc 0} {$pc < [llength [lindex $bbcontent $b]]} {incr pc} {
set q [lindex $bbcontent $b $pc]
if {[lindex $q 0] eq "copy"} {
lassign $q - to from
# Is this copy killable?
if {[lindex $to 0] eq "temp"
|| [lrange $from 0 1] eq [lrange $to 0 1]} {
# Kill a copy
my debug-copyprop {
puts "Fold copy:"
puts " $b:$pc: $q"
}
my replaceUses $to $from
dict unset udchain $to
set changed 1
continue; # delete the quad
} elseif {[lindex $to 0] eq "var"
&& [lindex $from 0] eq "temp"
&& $outpc >= 0
&& [lindex $bbcontent $b $outpc 1] eq $from
&& [lindex $bbcontent $b $outpc 0] ne "phi"
&& [my hasUniqueUse $from]} {
# unique use of a temporary copies it to a variable
# immediately following creating it. Peephole optimize
# by coalescing the two quads.
my debug-copyprop {
puts "Peephole-optimize copy:"
puts " $b:$outpc:\
[lindex $bbcontent $b $outpc]"
puts " $b:$pc: $q"
}
# Put the variable in place of the temp. No need
# to repair its du- and ud-chains, since it's not
# moving from block to block
lset bbcontent $b $outpc 1 $to
# the temp is now irrelevant
dict unset duchain $from
dict unset udchain $from
set changed 1
continue; # delete the copy
}
}
lset bbcontent $b [incr outpc] $q
}
lset bbcontent $b [lrange [lindex $bbcontent $b] 0 $outpc]
}
my deadvars
my uselessphis
my debug-copyprop {
puts "After copy propagation:"
my dump-bb
}
return $changed
}