# 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 {} {

    my variable bbcontent
    my variable duchain
    my variable udchain

    set changed 0

    my debug-copyprop {
	puts "Before copy propagation:"
	my dump-bb
    }
    my deadjump
    my deadbb
    my deadvars
    my uselessphis
    my bbidom
    my bblevel


    # 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

}
