# phi operations will have become worthless, either because two such
# operations become the same operation, or because all inputs to a phi
# become the same input. It may be necessary to repeat this
# optimization after cleaning up useless phi's.

oo::define quadcode::transformer method partialredundancy {} {

    variable ::quadcode::pre_iteration
    puts "[my full-name] attempt [incr pre_iteration]"

    my debug-pre {
	puts "Before partial redundancy elimination:"
	my dump-bb
    }

    # 0. Initialize the global variable numbering tables.

    if {[catch {
	my audit-duchain pre-5
	my audit-phis pre-5
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }

    # 6. If we inserted any phis speculatively, and we didn't use any of them,
    #    clean them up so that we can return 'false' for did_something and
    #    not fight with dead code removal. Then clean up working storage

    if {!$did_something} {
	my pre_remove_speculative_phis
    }
    my pre_cleanup
    return $did_something

}

# quadcode::transformer method pre_init --
#
#	Initializes the tables for global value numbering and partial

oo::define quadcode::transformer method pre_buildsets1 {} {

    my variable pre_exp_gen
    my variable pre_phi_gen
    my variable pre_tmp_gen
    my variable pre_avail_out
    my variable pre_speculative_phis

    set pre_exp_gen {}
    set pre_phi_gen {}
    set pre_tmp_gen {}
    set pre_avail_out [lrepeat [llength $bbcontent] {}]
    set pre_speculative_phis {}

    variable ::quadcode::gvn_eliminable

    # Walk through basic blocks in the forward direction
    set b -1
    foreach bb $bbcontent {
	incr b

# This is less general than the phi-insertion step of [Chow97], but
# the case of values that are both partially available and partially
# anticipable is more complex than we are attempting yet.

oo::define quadcode::transformer method pre_avail_in {b bbVar} {

    my variable pre_avail_out
    my variable pre_speculative_phis

    upvar 1 $bbVar bb

    set preds [lindex $bbpred $b]
    set n [dict size $preds]
    if {$n == 0} {

		my addUse $in $b
	    }
	    set insn [linsert $argl 0 phi $var]
	    my debug-pre {
		puts "  Speculative: $b:[llength $newbb]: $insn"
	    }
	    dict set udchain $var $b
	    dict set pre_speculative_phis $b $var {}
	    lappend newbb $insn
	    my pre_gvn_add [list {} $var] $v
	    dict set avail_in $v $var
	}
	set bb [linsert $bb[set bb ""] 0 {*}$newbb]
    }
	

	    lappend newbb $q
	}
	lset bbcontent $b $newbb
    }

    return $changed
}

# quadcode::transformer method pre_remove_speculative_phis --
#
#	Removes any speculatively-inserted phis after partial redundancy
#	elimination is complete
#
# Results:
#	None.
#
# Side effects:
#	Speculative phis are removed.
#
# This method must execute if and only if the partial reduncancy
# elimination modified no code other than the speculatively-inserted
# phi operations. They are _ipso facto_ unused.
#
# If this step were not to take place, we'd have to return 'changed' in
# order to recalculate types, which would check for further optimizations,
# remove the speculative phis in dead code removal, and then reinvoke
# this method, which would put them back in.

oo::define quadcode::transformer method pre_remove_speculative_phis {} {

    my variable pre_speculative_phis

    my debug-pre {
	puts "Remove any speculative phi instructions"
	dict for {b vars} $pre_speculative_phis {
	    puts "$b: [dict keys $vars]"
	}
    }

    # Walk through the speculative phis, grouped by block
    dict for {b phis} $pre_speculative_phis {

	# Get the basic block content and walk through the instructions
	set bb [lindex $bbcontent $b]
	set newbb {}
	lset bbcontent $b {}
	set pc -1
	foreach q $bb {
	    incr pc
	    set res [lindex $q 1]

	    # Delete any instruction that is a speculative phi
	    if {![dict exists $phis $res]} {
		lappend newbb $q
	    } else {
		my debug-pre {
		    puts "  $b:$pc: $q"
		}
		dict unset udchain $res
		foreach {- v} [lrange $q 2 end] {
		    my removeUse $v $b
		}
	    }
	}

	# Put the new basic block content back
	lset bbcontent $b $newbb
    }
    return
}

# quadcode::transformer method pre_cleanup --
#
#	Cleans up globals left behind by partial redundancy elimination
#
# Results:
#	None

oo::define quadcode::transformer method pre_cleanup {} {

    my variable pre_antic_in
    my variable pre_avail_out
    my variable pre_exp_gen
    my variable pre_phi_gen
    my variable pre_speculative_phis
    my variable pre_tmp_gen
    my variable pre_vexprs
    my variable pre_vn

    unset -nocomplain pre_antic_in
    unset -nocomplain pre_avail_out
    unset -nocomplain pre_exp_gen
    unset -nocomplain pre_phi_gen
    unset -nocomplain pre_speculative_phis
    unset -nocomplain pre_tmp_gen
    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}


		my audit-phis $pass
	    }
	    my debug-tidy {
		lappend debugLine $result
	    }
	}
	my debug-tidy {
	    puts "$debugLine -- $changed"
	}
	if {$changed} {
	    set somethingChanged 1
	}
    }

    # If any of these changes actually changed anything, it may
    # have narrowed types, so we need to return for more interprocedural
    # type analysis


	
    my debug-tidy {


	puts "tidy: did something change? $somethingChanged"

    }
    return $somethingChanged

}

# quadcode::transformer method sourceFile --
#
#	Returns the source file that this module was compiled from