dictAppend dictExists dictGet dictGetOrNexist
	    dictLappend dictSet dictSetOrUnset dictSize dictUnset
	    div
	    eq expand exists expon extractArray extractCallFrame extractExists
	    extractFail extractMaybe extractScalar
	    frameArgs frameDepth
	    ge gt
	    initArray initArrayIfNotExists initIfNotExists
	    instanceOf isBoolean
	    le
	    listAppend listConcat listIn listIndex listLength listRange
	    listSet
	    lshift lt
	    maptoint mod moveFromCallFrame mult
	    narrowToType neq not
................................................................................
# 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.
................................................................................
	my audit-duchain pre-3
	my audit-phis pre-3
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }
    set did_something [my pre_insert]
    if {$did_something} {
	puts "pre_insert did something!"
    }

    # 4. Rewrite the program to replace calculations of available values
    #    with copies from the temps that hold the values

    if {[catch {
	my audit-duchain pre-4
	my audit-phis pre-4
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }
    if {[my pre_eliminate]} {
	puts "Eliminate did something!"
	set did_something 1
    }

    # 5. Now, dead code elimination and copy propagation will eliminate
    #    any messes that step 4 left behind.
    
    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
................................................................................

    my variable pre_antic_in
    my variable pre_avail_out
    
    my debug-pre {
	puts "Try to find code insertion points"
    }






    # This procedure iterates to convergence. 'changed' tracks whether
    # we did anything on a single pass.
    set did_something 0
    set changed 1

    while {$changed} {
	set changed 0

	# new_sets contains the newly introduced phi's. It is a list indexed
	# by basic block number, whose elements are dictionaries mapping
	# global value number to the term in the phi operation.
	set new_sets {}

	# Iterate through the basic blocks
	set b -1
	foreach antin $pre_antic_in preds $bbpred dom $bbidom {
	    incr b

	    my debug-pre {
		puts "  bb $b:"
	    }

	    # Inherit the set of created phi's from the block's
	    # dominator, and make them available on the block's output

	    if {$b > 0} {
		set new_phis [lindex $new_sets $dom]
	    } else {
		set new_phis {}
	    }
	    lappend new_sets $new_phis

	    set avail_out_b [lindex $pre_avail_out $b]
	    lset pre_avail_out $b {}
	    dict for {v phi} $new_phis {
		dict set avail_out_b $v $phi
	    }
	    lset pre_avail_out $b $avail_out_b

	    # If the block has more than one predecessor, it's a potential
	    # place for a phi to be inserted

	    if {[dict size $preds] > 1} {
................................................................................
			continue
		    }

		    # A value that is available from the dominator is
		    # fully available
		    if {[dict exists $avail_out_d $v]} {
			my debug-pre {
			    puts "      it's available in the dominator,\
                                        can't need a phi."










			}
			continue
		    }

		    # Go through the predecessors and find the leaders
		    # that supply the value. Set avail to the
		    # expressions that compute the value in the

	    dictAppend dictExists dictGet dictGetOrNexist
	    dictLappend dictSet dictSetOrUnset dictSize dictUnset
	    div
	    eq expand exists expon extractArray extractCallFrame extractExists
	    extractFail extractMaybe extractScalar
	    frameArgs frameDepth
	    ge gt
	    initIfNotExists
	    instanceOf isBoolean
	    le
	    listAppend listConcat listIn listIndex listLength listRange
	    listSet
	    lshift lt
	    maptoint mod moveFromCallFrame mult
	    narrowToType neq not
................................................................................
# 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.
................................................................................
	my audit-duchain pre-3
	my audit-phis pre-3
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }
    set did_something [my pre_insert]




    # 4. Rewrite the program to replace calculations of available values
    #    with copies from the temps that hold the values

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

	set did_something 1
    }












    # 5. 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

    # 6. Now, dead code elimination and copy propagation will eliminate
    #    any messes that step 4 left behind.
    
    return $did_something

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

    my variable pre_antic_in
    my variable pre_avail_out
    
    my debug-pre {
	puts "Try to find code insertion points"
    }

    # new_sets contains the newly introduced phi's. It is a list indexed
    # by basic block number, whose elements are dictionaries mapping
    # global value number to the term in the phi operation.
    set new_sets {}

    # This procedure iterates to convergence. 'changed' tracks whether
    # we did anything on a single pass.
    set did_something 0
    set changed 1
    set did_phis {}
    while {$changed} {
	set changed 0






	# Iterate through the basic blocks
	set b -1
	foreach antin $pre_antic_in preds $bbpred dom $bbidom {
	    incr b

	    my debug-pre {
		puts "  bb $b:"
	    }

	    # Inherit the set of created phi's from the block's
	    # dominator, and make them available on the block's output
	    if {[llength $new_sets] == $b} {
		if {$b > 0} {
		    set new_phis [lindex $new_sets $dom]
		} else {
		    set new_phis {}
		}
		lappend new_sets $new_phis
	    }
	    set avail_out_b [lindex $pre_avail_out $b]
	    lset pre_avail_out $b {}
	    dict for {v e} [lindex $new_sets $b] {
		dict set avail_out_b $v $e
	    }
	    lset pre_avail_out $b $avail_out_b

	    # If the block has more than one predecessor, it's a potential
	    # place for a phi to be inserted

	    if {[dict size $preds] > 1} {
................................................................................
			continue
		    }

		    # A value that is available from the dominator is
		    # fully available
		    if {[dict exists $avail_out_d $v]} {
			my debug-pre {
			    puts "      it's available in the dominator already\
                                        as [dict get $avail_out_b $v]"
			}
			continue
		    }

		    # A value that we made a phi for already is fully available
		   
		    if {[dict exists [lindex $new_sets $b] $v]} {
			my debug-pre {
			    puts "      it's already been processed as\
                                        [dict get [lindex $new_sets $b] $v]"
			}
			continue
		    }

		    # Go through the predecessors and find the leaders
		    # that supply the value. Set avail to the
		    # expressions that compute the value in the