upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*
    redundant-purify
    licm
    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 --
#