upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*
    redundant-purify
    licm
    licm2
    cse cse-caller
    wideimpure
}
set toCompile'slow' {
    parseBuiltinsTxt::main
}
 

    upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*
    redundant-purify
    licm1 licm2

    cse cse-caller
    wideimpure
}
set toCompile'slow' {
    parseBuiltinsTxt::main
}
 

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

    # TEMP - examine just the specific target scenario
    if {0 && ([my full-name] ne "::cse(INT,INT)"
	      || [llength $bbcontent] != 11)} {return 0}

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

    # 0. Initialize the global variable numbering tables.

................................................................................
	    # others.
	    if {$op eq "phi"} {

		# phi - give the result a unique value number, and add it
		#       to phi_gen
		set expr [list {} $result]
		set v [my pre_gvn_lookup_or_add $expr]
		lappend phi_gen_b $result $argl

	    } elseif {$op eq "copy"} {

		# copy - give the result the same value number as the source.
		set src [lindex $argl 0]
		set expr [list {} $result]
		set srcexpr [list {} $src]
................................................................................
    my variable pre_tmp_gen
    my variable pre_phi_gen

    my variable pre_avail_out

    my variable pre_antic_in
    
    my variable pre_translate_cache

    # Initialize anticipable sets to empty. This initial value should
    # be accessed only in the case of an infinite loop, whose blocks will
    # have no postdominators.
    set pre_antic_in [lrepeat [llength $bbcontent] {}]
    set pre_translate_cache {}

    # Calculate the retrograde order in which blocks are to be visited
    set bs [my bbrorder]

    # Iterate to convergence
    set changed 1
    while {$changed} {
................................................................................
		set antic_in_f [lindex $pre_antic_in $f]
		my debug-pre {
		    puts "      which has anticipable values:"
		    dict for {vvv eee} $antic_in_f {
			puts "        value $vvv = $eee"
		    }
		}
		set antic_out [my pre_phi_translate $antic_in_f $b $f]
		my debug-pre {
		    puts "      giving anticipable values on output of $b:"

		    dict for {vvv eee} $antic_out {




			puts "        value $vvv = $eee"
		    }
		}
		
	    } else {

		my debug-pre {
		    puts "      has multiple successors: $succs"
................................................................................
#	'copy' and 'phi' instructions are inserted in the quadcode
#	to make fully anticipable expressions available at merge
#	points where they are only partially available. This process
#	involves inserting computation of the needed expressions
#	on any predecessors where they are not available, and then
#	introducing a phi operation to combine the new expressions.
#
# Figures 4.8-4.9 on pp. 78-79 of [VanD].






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

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

    set pre_new_sets [lrepeat [llength $bbcontent] {}]
    set did [lrepeat [llength $bbcontent] {}]

    # Iterate to convergence
    set did_something 0
    set changed 1
    while {$changed} {
	set changed 0

	# Process the basic blocks in forward sequence





	set b -1
	foreach didvals $did {

	    incr b

	    # Initially, the new instructions making values available
	    # are inherited from the dominator, and they also become
	    # the leaders for their values.
	    set avail_in_dom [lindex $pre_avail_out [lindex $bbidom $b]]









	    set new_sets_b $avail_in_dom


	    set avail_out_b [lindex $pre_avail_out $b]
	    lset pre_avail_out $b {}
	    dict for {v e} $new_sets_b {
		dict set avail_out_b $v $e
	    }
	    lset pre_avail_out $b $avail_out_b
		
	    # Handle merge points
	    set preds [lindex $bbpred $b]



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

		# Walk through the anticipable expressions at each merge point


















		dict for {v e} [lindex $pre_antic_in $b] {
















		    if {[dict exists $didvals $v]} {
			my debug-pre {
			    puts "Already hoisted value $v past $b"




























































			}
			continue
		    }
		    
		    my debug-pre {
			puts "Examine value $v = $e in block $b"
		    }



		    
		    # If an expression is a copy, we don't need to do
		    # anything because its value is known to be available.
		    # If an expression is available in the dominator, it's
		    # already available here, so there's no need to do anything
		    # more

		    if {[lindex $e 0] ne {}
			&& ![dict exists $avail_in_dom $e]} {

			# The expression e (whose value number is v)
			# is not a copy. The expression is anticipable
			# in block b but not its dominator.  This is
			# the case that may need a phi and one or more
			# assignments.

			if {[my pre_insert_do_expr $b $v $e]} {
			    dict set didvals $v {}
			    set changed 1
			    set did_something 1
			}
		    }
		}		    
	    }
	    lset did $b $didvals
	}
    }
    return $did_something
}
 
# quadcode::transformer method pre_insert_do_expr --
#
#	When an expression is found that is available at a merge point
#	but not its dominator, makes that expression available if possible.
#
# Parameters:
#	b - Basic block number of the merge point
#	preds - Dictionary whose keys are the predecessors of basic block b
#	v - Value number of the expression under consideration
#	e - Expression under consideration
#
# Results:
#	Returns 1 if the procedure did anything.
#
# Figure 4.8, page 78 of [VanD].
#
# TODO - Need to think about how to maintain a name and a debugging context
#	 for code that has been moved - or to suppress this optimization
#	 at low -O levels

oo::define quadcode::transformer method pre_insert_do_expr {b v e} {

    my variable pre_new_sets

    my debug-pre {
	puts "Examine value $v: $e for code motion at entry to block $b"
    }

    if {[my pre_gvn_is_literal $v -]} {
	my debug-pre {
	    puts "$v: $e is a literal - there's nothing to be done."
	}	    
	return 0;		# There's nothing to insert for a literal
    }
	

    # Is this a point where it's appropriate to insert (It is if
    # the value is available on at least one predecessor, and not on all).


    set avail [my pre_insertion_point $b $v $e]
    if {[dict size $avail] == 0} {
	my debug-pre {
	    puts "$v: $e is not eligible to be hoisted above block $b"
	}
	return 0
    }

    my debug-pre {
	puts "The expression will be made available from:"
	dict for {p eprime} $avail {
	    puts "  block $p -> $eprime"
	}
    }

    set t [my pre_insert_make_mods $b $v $e $avail]

    set news [lindex $pre_new_sets $b]
    lset pre_new_sets $b {}
    dict set news $v $t
    lset pre_new_sets $b $news

    return 1
}
 
# quadcode::transformer method pre_insertion_point --
#
#	Tests whether the predecessors of the start of a given basic block
#	are appropriate insertion points for a partially available expression.
#
# Parameters:
#	b - Block being examined
#	v - Global value number of the expression being examined
#	e - Expression being examined, which will always be complex.
#
# Results:
#	Returns a dictionary whose keys are the basic block numbers
#	of predecessor blocks, and whose values are expressions
#	in the blocks.
#
# The expressions will be either SSA temporaries that contain the
# corresponding value at the end of the predecessor block, or complex
# expressions that must be evaluated in the predecessor. If the block
# is an inappropriate point to insert the evaluation of the given
# value, the returned dictionary will be empty.
#
# This procedure is roughly the second half of Figure 5.8 on page 78
# of [VanD04].

oo::define quadcode::transformer method pre_insertion_point {b v e} {

    my variable pre_avail_out
    set bbb -1

    set avail {};		# Return value of this method, being
    ;				# accumulated
    set by_some 0;		# Flag is true if the expression is available
    ;				# in at least one predecessor
    set all_same 1;		# Flag is true if all predecessors present
    ;				# the same value for the available expression

    set ve [dict create $v $e];	# Dictionary with the single pair v->e,
    ;				# to use as an argument to phi_translate

    # Iterate through the predecessors
    dict for {p -} [lindex $bbpred $b] {

	# Find the expression, eprime, that would make e available in the
	# predecessor
	dict for {vprime eprime} [my pre_phi_translate1 $v $e $p $b] break

	# Is the translated expression available in the predecessor already?
	set avail_out_p [lindex $pre_avail_out $p]
	if {![dict exists $avail_out_p $vprime]} {

	    # Not available - add it as something that needs to be evaluated
	    dict set avail $p $eprime
	    set all_same 0

	} else {

	    # It is available - add the temporary to the available set and
	    # update 'all_same'
	    set leader [dict get $avail_out_p $vprime]
	    set lexpr [list {} $leader]
	    dict set avail $p $lexpr
	    set by_some 1
	    if {![info exists first_s]} {
		set first_s $lexpr
	    } elseif {$first_s ne $lexpr} {
		set all_same 0
	    }
	}
    }

    # The expression will benefit from code motion at this point if
    # it is available in at least one predecessor, and it is not available
    # in the same SSA temporary in all predecessors. We also force code
    # motion if an expression is unavailable at a loop header

    if {($by_some && !$all_same)} {
	return $avail
    } else {
	return {}
    }
    
}
 
# quadcode::transformer method pre_insert_make_mods --
#
#	Inserts a phi at a merge point (and possible expression
#	evaluations above a merge point) to hoist one anticipated
#	expression above the merge.
#
# Parameters:
#	b - Basic block that the expression is leaving
#	v - Global value number of the expression
#	e - Expression being moved above block b
#	avail - Dictionary whose keys are the predecessor blocks
#	        and whose values are the expressions that need
#	        to be evaluated in the predecessors to make e
#	        fully available.
#
# Results:
#	Returns the name of the temporary that replaces the
#	expression in b.
#
# Side effects:
#	Adds any needed code to reify the expression in the predecessors,
#	and adds a phi at the start of b to pick up the expression value.
#	The value becomes available at the exit of b.
#
# The logic mostly follows Figure 4.9 on page 79 of [VanD04].

oo::define quadcode::transformer method pre_insert_make_mods {b v e avail} {

    my variable pre_avail_out

    my debug-pre {
	puts "Make value $v: $e available in block $b"
    }
    
    # Start building a phi to represent the temporary
    my debug-pre {
	puts "  Make temporary to hold $e at entry to block $b"
    }

    set outv [my pre_make_temp_for_expr $v $e]
    my debug-pre {
	puts "    Call it $outv!"

    }
    set phi [list phi $outv]
    dict set udchain $outv $b

    # Reify the expression in each predecessor block
    dict for {p eprime} $avail {

	my debug-pre {
	    puts "  Reify $eprime in block $p"
	}
	set argl [lassign $eprime opcode]
	if {$opcode ne {}} {



	    set avail_out_p [lindex $pre_avail_out $p]
	    my debug-pre {
		puts "   Avail values in $p before this mod are\
                         [dict keys $avail_out_p]"
	    }
	    lset pre_avail_out $p {}

	    # A complex expression actually needs to be evaluated
	    # in the predecessor block. Make the instruction and update
	    # ud- and du-chains
	    my debug-pre {
		puts "    Need to find temporary for value $v"
	    }
	    set t [my pre_make_temp_for_expr $v $eprime]
	    my debug-pre {
		puts "    Call it $t!"
	    }
	    dict set udchain $t $p
	    set tv [my pre_gvn_lookup_or_add $eprime]
	    my pre_gvn_add [list {} $t] $tv
	    set insn [list $opcode $t]
	    foreach a $argl {
		if {[lindex $a 0] ne "value"} {
		    lappend insn $a
		} else {
		    set v [lindex $a 1]
		    if {[dict exists $avail_out_p $v]} {
			set var [dict get $avail_out_p $v]
			my addUse $var $p
			lappend insn $var
		    } elseif {[my pre_gvn_is_literal $v lit]} {
			lappend insn $lit
		    } else {
			error "$v is unavailable at end of $p!"

		    }
		}


	    }

	    # Insert the instruction in the block
	    set pb [lindex $bbcontent $p]
	    lset bbcontent $p {}
	    my debug-pre {
		puts "  Add $insn before end of block $p"
	    }
	    set pb [linsert $pb[set pb ""] end-1 $insn]
	    lset bbcontent $p $pb
	    
	    # Make the value available at exit from the predecessor
	    my debug-pre {
		puts "  Add value $tv: $t to the avail set on output from $p"
	    }






	    dict set avail_out_p $tv $t
	    lset pre_avail_out $p $avail_out_p
	    my debug-pre {
		puts "  ... which is now [dict keys [lindex $pre_avail_out $p]]"

	    }
	    
	} else {

	    # A simple value is already available and just needs to go
	    # on the phi being constructed



	    




	    set t [lindex $argl 0]
	}

	# Add the reified value to the phi under construction
	lappend phi [list bb $p] $t
	my addUse $t $b

	
    }

    # Paste the newly-build phi at the start of the block
    my debug-pre {
	puts "Add $phi at the start of $b"
    }
    set bb [lindex $bbcontent $b]
    lset bbcontent $b {}
    set bb [linsert $bb[set bb {}] 0 $phi]
    lset bbcontent $b $bb

    # Make the value available at exit from the block




    set avail_out_b [lindex $pre_avail_out $b]
    lset pre_avail_out $b {}
    dict set avail_out_b $v $outv
    lset pre_avail_out $b $avail_out_b















    return $outv
}
 
# quadcode::transformer method pre_eliminate --
#
#	Eliminates redundant code once partial availability has been
#	resolved
#
................................................................................
#	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_new_sets
    my variable pre_phi_gen
    my variable pre_tmp_gen
    my variable pre_translate_cache
    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_new_sets
    unset -nocomplain pre_phi_gen
    unset -nocomplain pre_tmp_gen
    unset -nocomplain pre_translate_cache
    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}
 
# quadcode::transformer method pre_make_temp_for_expr --
................................................................................
# Parameters:
#	es - Dictionary whose keys are global value numbers and
#	     whose values are expressions in the successor block
#	p - Predecessor block
#	s - Successor block
#
# Results:
#	Returns the translated expressions in the same dictionary
#	form as 'es'
#
# Side effects:
#	Caches the result of translation.
#
# Described on page 1 of [VaHo03].

oo::define quadcode::transformer method pre_phi_translate {es p s} {

    # Translate each expression in turn
    set translated {}
    dict for {v e} $es {
	lassign [my pre_phi_translate1 $v $e $p $s] newv newe
	dict set translated $newv $newe
    }
    return $translated
}
 
# quadcode::transformer method pre_phi_translate1 --
#
#	Translates an expression that is valid in a successof block to
#	one that is valid in a predecessor block.
#
# Parameters:


#	v - The expression's global value number
#	e - The expression being translated
#	p - The predecessor block
#	s - The successor block
#
# Results:
#	Returns the result of the translation
#
# Side effects:
#	Result is cached. The cache is necessary not only for speed but
#	also because 'pre_phi_insert' depends on being able to look up
#	an already-computed translation.

oo::define quadcode::transformer method pre_phi_translate1 {v e p s} {

    my variable pre_translate_cache
    my variable pre_phi_gen
    
    my debug-pre {
	puts "        Translate value $v: $e on edge $p -> $s"
    }

    set phis [lindex $pre_phi_gen $s]
    ;			       # Phi operations at the successor block
    set skey [list bb $p];     # Key for looking up predecessor value at a phi

    # Find the cached translations for this flowgraph edge. If this value
    # is already cached, return the translation


    if {[dict exists $pre_translate_cache $p $s]} {
	set es [dict get $pre_translate_cache $p $s]
    } else {
	set es {}
    }

    if {[dict exists $es $v]} {


	my debug-pre {
	    puts "        (cached) [dict get $es $v]"


	}













	return [dict get $es $v]
    }

    # Take apart the expression
    set argl [lassign $e opcode]
    set eout [list $opcode]

    if {$opcode eq {}} {

	# Translate a single SSA temporary
	set a [lindex $argl 0]
	if {[dict exists $phis $a $skey]} {
	    set a [dict get $phis $a $skey]
	}
	lappend eout $a

    } else {

	# Translate an expression that calculates something. All of its
	# dependent values will already have been translated. Rewrite
	# values, and leave other args unchanged.
	foreach a $argl {
	    if {[lindex $a 0] ne "value"} {
		lappend eout $a
	    } else {
		# The arg is 'value N', and we must have already translated
		# it. Retrieve it from the cache
		set vprime [lindex $a 1]
		if {[dict exists $es $vprime]} {




		    lappend eout [list value [lindex [dict get $es $vprime] 0]]

		} else {
		    error "$p->$s Value $vprime is not cached, but $e depends on it?"
		}
	    }
	}
    }

    set vout [my pre_gvn_lookup_or_add $eout]
    set result [list $vout $eout]
    dict set pre_translate_cache $p $s $v $result

    my debug-pre {
	puts "        result is value $vout: $eout"

    }
    
    return $result
}
 
# quadcode::transformer method pre_clean --
#

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





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

    # 0. Initialize the global variable numbering tables.

................................................................................
	    # others.
	    if {$op eq "phi"} {

		# phi - give the result a unique value number, and add it
		#       to phi_gen
		set expr [list {} $result]
		set v [my pre_gvn_lookup_or_add $expr]
		dict set phi_gen_b $result $argl

	    } elseif {$op eq "copy"} {

		# copy - give the result the same value number as the source.
		set src [lindex $argl 0]
		set expr [list {} $result]
		set srcexpr [list {} $src]
................................................................................
    my variable pre_tmp_gen
    my variable pre_phi_gen

    my variable pre_avail_out

    my variable pre_antic_in
    


    # Initialize anticipable sets to empty. This initial value should
    # be accessed only in the case of an infinite loop, whose blocks will
    # have no postdominators.
    set pre_antic_in [lrepeat [llength $bbcontent] {}]


    # Calculate the retrograde order in which blocks are to be visited
    set bs [my bbrorder]

    # Iterate to convergence
    set changed 1
    while {$changed} {
................................................................................
		set antic_in_f [lindex $pre_antic_in $f]
		my debug-pre {
		    puts "      which has anticipable values:"
		    dict for {vvv eee} $antic_in_f {
			puts "        value $vvv = $eee"
		    }
		}

		my debug-pre {
		    puts "      giving anticipable values on output of $b:"
		}
		set antic_out {}
		dict for {olde pair} [my pre_phi_translate $antic_in_f $b $f] {
		    lassign $pair newv newe
		    dict set antic_out $newv $newe
		    my debug-pre {
			puts "        value $newv: $newe"
		    }
		}
		
	    } else {

		my debug-pre {
		    puts "      has multiple successors: $succs"
................................................................................
#	'copy' and 'phi' instructions are inserted in the quadcode
#	to make fully anticipable expressions available at merge
#	points where they are only partially available. This process
#	involves inserting computation of the needed expressions
#	on any predecessors where they are not available, and then
#	introducing a phi operation to combine the new expressions.
#
# Figures 4.8-4.9 on pp. 78-79 of [VanD04]. Note that the logic in
# [VanD04], despite the length of the algorithm, is pretty sketchy. In
# particular, there's no indication of how 'new_sets' is used - it's
# constructed, but not referred to.  In addition, the information for
# 'phi_translate' is also unclear. We try to replicate here from
# first principles.

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

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


		my debug-pre {
		    puts "    bb $b is a merge point"
		}

		# What expressions are available from the block's dominator?
		set avail_out_d [lindex $pre_avail_out $dom]

		# Find the translations for the anticipable values
		set translated_p {}
		dict for {p -} $preds {
		    dict set translated_p $p [my pre_phi_translate $antin $p $b]
		}

		# Potential phis correspond to all anticipable
		# expressions in the block. (We will downselect to
		# those that are partially available - that is,
		# complex expressions that are available in at least
		# one predecessor but not in all.)
		dict for {v e} $antin {

		    my debug-pre {
			puts "    examine anticipated value $v: $e"
		    }
		    lassign $e opcode argl

		    # A simple variable must be fully available
		    if {$opcode == {}} {
			my debug-pre {
			    puts "      it's a simple value, can't need a phi"
			}
			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
		    # predecessors; by_some to indicate whether any
		    # predecessor has the value available, and
		    # all_same to indicate whether all predecessors
		    # have the value available in the same place.
		    set avail {}
		    set by_some 0
		    set all_same 1
		    unset -nocomplain first_s
		    dict for {p trans} $translated_p {
			lassign [dict get $trans $v] v1 e1
			set avail_out_p [lindex $pre_avail_out $p]
			if {![dict exists $avail_out_p $v1]} {

			    my debug-pre {
				puts "      it's unavailable in predecessor $p"
			    }
			    # The value is unavailable in the predecessor
			    dict set avail $p [list $v1 $e1]

			    set all_same 0
			} else {

			    # The value is available as e2 in the predecessor
			    set var2 [dict get $avail_out_p $v1]
			    set e2 [list {} $var2]
			    my debug-pre {
				puts "      it's available as $var2 in\
                                            predecessor $p"
			    }
			    set e2 [list {} $var2]
			    dict set avail $p [list $v1 $e2]
			    set by_some 1
			    if {![info exists first_s]} {
				set first_s $e2
			    } elseif {$first_s ne $e2} {
				set all_same 0
			    }
			}
		    }

		    # If the value is fully available or not available,
		    # there's nothing to do
		    if {$all_same} {
			my debug-pre {
			    puts "    it's fully available in block $b"
			}
			continue
		    }
		    if {!$by_some} {
			my debug-pre {
			    puts "    it's unavailable in block $b"
			}
			continue
		    }

		    my debug-pre {
			puts "    it's partially available in block $b"
		    }

		    # Rewrite the code to make the value available
		    dict for {p pair} $avail {



			# Examine a predecessor block to see if the value is
			# available
			lassign $pair v1 e1
			set argl [lassign $e1 opcode]
			if {[lindex $e1 0] eq {}} {



























































			    # The value is available, we're done
			    continue
			}


















































































































































			# Create a temp to hold the value in the predecessor
			set t [my pre_make_temp_for_expr $v $e]
			my debug-pre {

			    puts "    Created $t to hold $e1 in $p"
			}

			dict set udchain $t $p










			# Create an instruction to evaluate the value in
			# the predecessor
			set avail_out_p [lindex $pre_avail_out $p]



















			set insn [list $opcode $t]
			foreach a $argl {
			    if {[lindex $a 0] ne "value"} {
				lappend insn $a
			    } else {


				set s1 [dict get $avail_out_p [lindex $a 1]]

				lappend insn $s1




				my addUse $s1 $p
			    }
			}
			my debug-pre {
			    puts "    Add $insn at the end of block $p"
			}


			set bb [lindex $bbcontent $p]
			lset bbcontent $p {}



			set bb [linsert $bb[set bb ""] end-1 $insn]
			lset bbcontent $p $bb





			# Track that the new instruction is the leader for
			# the value,
			set texpr [list {} $t]
			my pre_gvn_add $texpr $v1
			set avail_out_p [lindex $pre_avail_out $p]
			lset pre_avail_out $p {}
			dict set avail_out_p $v1 $t
			lset pre_avail_out $p $avail_out_p


			dict set avail $p [list $v1 $texpr]

		    }




		    # Make the temporary to hold the phi result
		    set t [my pre_make_temp_for_expr $v $e]
		    dict set udchain $t $b

		    # Make the phi instruction
		    set insn [list phi $t]
		    dict for {p pair} $avail {
			lassign $pair v1 e1
			set invar [lindex $e1 1]




			my addUse $invar $b
			lappend insn [list bb $p] $invar
		    }



		    my debug-pre {
			puts "insert $insn at the start of $b"
		    }
		    set bb [lindex $bbcontent $b]
		    lset bbcontent $b {}
		    set bb [linsert $bb[set bb ""] 0 $insn]
		    lset bbcontent $b $bb
		    

		    # Record the phi result in the avail set and the
		    # new_sets 
		    set texpr [list {} $t]
		    my pre_gvn_add $texpr $v
		    set avail_out_b [lindex $pre_avail_out $b]
		    lset pre_avail_out $b {}
		    dict set avail_out_b $v $t
		    lset pre_avail_out $b $avail_out_b
		    set new_sets_b [lindex $new_sets $b]
		    lset new_sets $b {}
		    dict set new_sets_b $v $t
		    lset new_sets $b $new_sets_b

		    # Record that we modified the code

		    set changed 1
		    set did_something 1
		}

	    }
	}
    }

    return $did_something
}
 
# quadcode::transformer method pre_eliminate --
#
#	Eliminates redundant code once partial availability has been
#	resolved
#
................................................................................
#	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_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_tmp_gen

    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}
 
# quadcode::transformer method pre_make_temp_for_expr --
................................................................................
# Parameters:
#	es - Dictionary whose keys are global value numbers and
#	     whose values are expressions in the successor block
#	p - Predecessor block
#	s - Successor block
#
# Results:
#	Returns the translated expressions as a dictionary. The keys are
#	value numbers in the successor block, and the values are ordered
#	pairs giving the value number in the predecessor and the expression
#	in the predecessor.
#

# Described on page 1 of [VaHo03].

oo::define quadcode::transformer method pre_phi_translate {es p s} {

    # Translate each expression in turn
    set translated {}
    dict for {v e} $es {
	lassign [my pre_phi_translate1 $translated $v $e $p $s] newv newe
	dict set translated $v [list $newv $newe]
    }
    return $translated
}
 
# quadcode::transformer method pre_phi_translate1 --
#
#	Translates an expression that is valid in a successof block to
#	one that is valid in a predecessor block.
#
# Parameters:
#	translated - Expressions translated already in the current block
#	             Keys are value numbers, values are the translations
#	v - The expression's global value number
#	e - The expression being translated
#	p - The predecessor block
#	s - The successor block
#
# Results:
#	Returns the result of the translation






oo::define quadcode::transformer method pre_phi_translate1 {es v e p s} {


    my variable pre_phi_gen
    
    my debug-pre {
	puts "        Translate value $v: $e on edge $p -> $s"
    }

    set phis [lindex $pre_phi_gen $s]
    ;			       # Phi operations at the successor block
    set pkey [list bb $p];     # Key for looking up predecessor value at a phi

    # Handle temporaries by mapping them through any phis
    if {[lindex $e 0] eq {}} {
	set t [lindex $e 1]

	if {[dict exists $phis $t $pkey]} {




	    # temporary participates in a phi
	    set tprime [dict get $phis $t $pkey]
	    set eprime [list {} $tprime]
	    set vprime [my pre_gvn_lookup $eprime]
	    my debug-pre {

		puts "          value $v: $t in $s maps to\
                                value $vprime: $tprime in $p"
	    }
	    return [list $vprime $eprime]
	} else {
	    my debug-pre {
		puts "          value $v: $t does not appear in a phi in $s,\
                                so it maps to itself in $p"
	    }
	    return [list $v $e]
	}
    }
    
    # Handle complex expressions by finding them in the set that have
    # already been translated
    if {[dict exists $es $v]} {
	return [dict get $es $v]
    }

    # Take apart the expression
    set argl [lassign $e opcode]
    set eout [list $opcode]

    # Translate the args to the expression.













    foreach a $argl {
	if {[lindex $a 0] ne "value"} {
	    lappend eout $a
	} else {
	    # The arg is 'value N', and we must have already translated
	    # it. Retrieve it from the cache
	    set vprime [lindex $a 1]
	    if {[dict exists $es $vprime]} {
		lassign [dict get $es $vprime] v2 e2
		if {$v2 < 0} {
		    lappend eout [lindex $e2 1]
		} else {
		    lappend eout [list value $v2]
		}
	    } else {
		error "$p->$s Value $vprime is not cached, but $e depends on it?"

	    }
	}
    }

    set vout [my pre_gvn_lookup_or_add $eout]
    set result [list $vout $eout]


    my debug-pre {

	puts "          value $v: $e in $s maps to value $vout: $eout in $p"
    }
    
    return $result
}
 
# quadcode::transformer method pre_clean --
#