lset bbcontent $b [incr newpc] $q
		    }

		    "add" {
			lassign $argl x y
			set res [list literal [expr {$x + $y}]]
			my debug-constfold {












































			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

			lset bbcontent $b [incr newpc] $q
		    }

		    "add" {
			lassign $argl x y
			set res [list literal [expr {$x + $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitand" {
			lassign $argl x y
			set res [list literal [expr {$x & $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitnot" {
			lassign $argl x
			set res [list literal [expr {~$x}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitor" {
			lassign $argl x y
			set res [list literal [expr {$x | $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitxor" {
			lassign $argl x y
			set res [list literal [expr {$x ^ $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

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

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


    # Compute Global Value Numbering for the values present in the quadcode

    set VN [my pre_gvn]
    my debug-pre {
	puts "Value numbering:"
	dict for {k v} $VN {
	    if {$v ne $k} {

		puts "   found congruence $k -> $v"
	    }
	}

    }

    # Compute the 'defined' predicate for the basic blocks

    set defined [my pre_defined $VN]
    my debug-pre {
	puts "Defined expressions:"
	set b -1
	foreach vset $defined {
	    puts "[incr b]: [dict keys $vset]"
	}
    }

    # Find sets of available expressions

    lassign [my pre_avail $defined] AVIN AVOUT
    my debug-pre {
	puts "Available expressions"
	set b -1
	foreach inset $AVIN outset $AVOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    AVIN =  $inset"
	    puts "    AVOUT = $outset"
	}
    }


    # Find sets of expressions altered within each block

    set altered [my pre_altered $VN]
    my debug-pre {
	puts "Altered expressions"
	set b -1
	foreach al $altered {
	    incr b
	    puts "  Block #$b: [dict keys $al]"
	}
    }

    # Find expressions that are locally anticipable at entry to blocks

    set antloc [my pre_antloc $defined $altered]
    my debug-pre {
	puts "Locally anticipable expressions"
	set b -1
	foreach an $antloc {
	    incr b
	    puts "  Block #$b: [dict keys $an]"
	}
    }

    # Compute globally anticipable expressions

    lassign [my pre_ant_global $altered $antloc] ANTIN ANTOUT
    my debug-pre {
	puts "Globally anticipable expressions"
	set b -1
	foreach inset $ANTIN outset $ANTOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    ANTIN =  $inset"
	    puts "    ANTOUT = $outset"
	}
    }

    # Compute earliest points where an expression may be moved.
    # These are edges on the call graph where the expression may
    # appear. (Since we have no critical edges, the expression
    # can always be inserted at either the tail of the predecessor
    # block or the head of the successor).

    set EARLIEST [my pre_earliest $AVOUT $altered $ANTIN $ANTOUT]
    my debug-pre {
	puts "Earliest insertion points:"
	dict for {edge vars} $EARLIEST {
	    if {[dict size $vars] > 0} {
		lassign $edge from to
		puts "    $from->$to: [dict keys $vars]"
	    }
	}
    }

    # Compute LATER, which is an indication that an expression
    # may be moved later than an edge (LATER) or the start of
    # a block (LATERIN)
................................................................................

    lassign [my pre_later $antloc $EARLIEST] LATERIN LATER

    # Report on insertion and deletion points

    dict for {edge exprs} $LATER {
	lassign $edge from to
	dict for {e -} $exprs {


	    if {![dict exists [lindex $LATERIN $to] $e]} {
		puts "Insert $e on the flowgraph edge from $from to $to"
	    }



	}
    }

    set b -1
    foreach exprs $antloc laters $LATERIN {
	incr b
	if {$b == 0} continue
	puts "Block $b: ANTLOC = [dict keys $exprs]"
	puts "Block $b: LATERIN = [dict keys $laters]"
	dict for {e -} $exprs {
	    if {![dict exists $laters $e]} {
		puts "Remove $e from block $b"
	    }

	}
    }


    return 0

}
 
# quadcode::transformer method pre_gvn --
#
#	Calculates a Global Value Numbering for values in a quadcode
#	sequence.
#
# Results:


#	Returns a dictionary whose keys are the names of program variables
#	and whose values are the names of program variables that represent
#	the equivalence classes.











#
# This procedure implements the 'RPO' algorithm presented in
# Figure 4.3 of [Simpson] (see references in the file header.
# While perhaps not as fast, it is significantly simpler than
# the 'SCC' algorithm and yields the same results.
#
# This procedure assumes that 'deadbb' has been run before it,
# so that it will find basic blocks already in depth-first order.

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



    # Initially all value numbers are unknown

    set VN {}

    # Iterate to convergence

    while {1} {
	set changed 0
	set VNforSig {}



	# Iterate through all basic blocks in depth-first order
	set b -1
	foreach bb $bbcontent {
	    incr b

	    # Walk through the instructions of each block
................................................................................

		# Ignore instructions that do not produce a value
		set result [lindex $q 1]
		if {[lindex $result 0] ni {"temp" "var"}} {
		    continue
		}

		# TODO - Detect meaningless phi

		# Make a signature for the expression computed
		# by the current instruction
		set sig [my pre_gvn_sig $VN $q]

		# If there is already a value number for the signature, use
		# it. Otherwise, make the current result the exemplar of the
		# congruence class. Set 'changed' if the the value number
		# changes from the previous round.
		if {![dict exists $VNforSig $sig]} {

		    dict set VNforSig $sig $result



		}

		set v [dict get $VNforSig $sig]
		if {![dict exists $VN $result]
		    || [dict get $VN $result] ne $v} {
		    set changed 1
		    my debug-pre {
			puts "Value number for $result is now $v"
		    }
		    dict set VN $result $v
		}
	    }
	}
	
	if {!$changed} break
    }
    return $VN


}
 
# quadcode::transformer method pre_gvn_sig --
#
#	Develops a signature for a quadcode instruction's result
#	in Global Value Numbering
................................................................................
	    bb - pc {
		lappend signature {}
	    }
	    temp - var {
		if {![dict exists $VN $a]} {
		    lappend signature TOP
		} else {
		    lappend signature [dict get $VN $a]
		}
	    }
	    default {
		lappend signature $a
	    }
	} 
    }
................................................................................
 
# quadcode::transformer method pre_defined --
#
#	Computes the local predicate, 'defined', for use in the
#	dataflow equations.
#
# Results:
#	Returns a list of dictionaries. The indices of the list are basic
#	block numbers, and each key in a dictionary is the exemplar of a
#	value defined in the basic block. The values in the dictionary are
#	immaterial.

oo::define quadcode::transformer method pre_defined {VN} {

    set DEFINED {}

    # Walk through the basic blocks

    set b -1
    foreach bb $bbcontent {
	incr b

	set defined {}

	# Walk through the individual instructions
	
	set pc -1
	foreach q $bb {
	    incr pc

	    lassign $q opcode result

	    # If an instruction defines a value, add the value to the set
	    
	    if {$result ne {} && [dict exists $VN $result]} {
		dict set defined [dict get $VN $result] {}
	    }
	}

	# Add the set to the list
	
	lappend DEFINED $defined
    }
................................................................................
 
# quadcode::transformer method pre_avail --
#
#	Calculates the available expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	defined - List of dictionaries. The list is indexed by basic
#	          block number. The keys in the dictionaries are the
#		  exemplars of values set in the block. The values are
#	          immaterial.
#
# Results:
#	Returns an ordered pair {AVIN AVOUT}.
#
#	AVIN is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values available on input
#	to each block.
#

#	AVOUT is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values available on
#	output from the block.
#
# This procedure solves the data flow equations given in Figure 5.6
# on page 63 of [Simpson].

oo::define quadcode::transformer method pre_avail {defined} {

    my debug-pre {
	puts "Calculate available expressions:"
    }



    set AVIN [lrepeat [llength $defined] {}]
    set AVOUT $defined


    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $defined] 0]
    set worklist [::quadcode::numheap new]
    for {set i 1} {$i < [llength $defined]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate AVIN for the block as the intersection of AVOUT
	# of all predecessors




	set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	set avin [lindex $AVOUT $firstpred]
	foreach p $otherpreds {
	    set othervs [lindex $AVOUT $p]
	    dict for {v -} $avin {
		if {![dict exists $othervs $v]} {
		    dict unset avin $v
		}
	    }
	}
	my debug-pre {
	    puts "    Available on input: [dict keys $avin]"
	}
	
	# Detect whether AVIN has changed. 
	set changed 0
	set oldavin [lindex $AVIN $b]
	dict for {v -} $avin {
	    if {![dict exists $oldavin $v]} {
		set changed 1
		break
	    }
	}

	# If AVIN has changed, we have to recalculate AVOUT
	if {$changed} {

	    my debug-pre {
		puts "    AVIN has changed, must update AVOUT"
	    }
	    lset AVIN $b $avin

	    set changed 0
	    set avout [lindex $AVOUT $b]
	    dict for {v -} $avin {
		if {![dict exists $avout $v]} {
		    dict set avout $v {}
		    my debug-pre {
			puts "        AVOUT now includes $v"

		    }
		    set changed 1
		}
	    }
	}

	# If AVOUT has changed, we have to revisit the successors of this
	# block
	if {$changed} {

	    my debug-pre {
		puts "    AVOUT has changed, must update successors"
		puts "    AVOUT($b) = [dict keys $avout]"
	    }
	    lset AVOUT $b $avout
	    foreach s [my bbsucc $b] {
		if {![lindex $pending $s]} {
		    my debug-pre {
			puts "        Add $s to worklist"
		    }
		    $worklist add $s
		    lset pending $s 1
		} else {
		    my debug-pre {
			puts "        $s is already on worklist"

		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_altered --
#
#	For each basic block in the program, compute the set of values
#	that are altered by fixed values in the block
#
# Parameters:
#	VN - Dictionary whose keys are quadcode values and whose values
#	     are exemplars of the corresponding expressions.







#
# Results:
#	Returns a list indexed by basic block number. The list values
#	are dictionaries whose keys are the exemplars of altered values
#	and whose values are immaterial
#
# This is the algorithm of Figure 7.2 on page 75 of [Simpson]







oo::define quadcode::transformer method pre_altered {VN} {


    variable ::quadcode::gvn_eliminable

    set S {}
    set D {}
    set isFixed {}

    # Walk through expressions in bottom-up order

    set b -1
    foreach bb $bbcontent {

	incr b
	set pc -1
	foreach q $bb {
	    incr pc

	    set argl [lassign $q opcode result]
	    if {![dict exists $VN $result]} continue
	    set e [dict get $VN $result]
	    if {[dict exists S $e]} continue
	    dict set S $e {}

	    # Keep track of which operands are fixed
	    if {![dict exists $gvn_eliminable $opcode]} {
		dict set isFixed $e {}
	    }



	    # Walk through operands of the expression





	    foreach a $argl {
		puts "expression has arg $a"
		if {![dict exists $VN $a]} continue
		set o [dict get $VN $a]
		puts "$e depends on $a => $o"


		# Set the dependencies of the result e to include
		# the operand o and its dependencies

		dict set S $e $o {}
		# If we haven't seen the operand, and this is a phi,
		# quit here. 
		if {![dict exists $S $o] && $opcode eq "phi"} continue
		dict for {ss -} [dict get $S $o] {
		    dict set S $e $ss {}
		}
	    }

	    # Set the dependents of fixed values 
	    
	    dict for {f -} [dict get $S $e] {
		if {![dict exists $isFixed $f]} continue
		dict set D $f $e {}
	    }
	}
    }

    set ALTERED {}

    # Walk through basic blocks
    set b -1
    foreach bb $bbcontent {
	incr b

	set altered {}
	set pc -1
	foreach q $bb {
	    incr pc
	    lassign $q opcode result
	    if {[dict exists $gvn_eliminable $opcode]} continue
	    if {![dict exists $VN $result]} continue
	    set x [dict get $VN $result]
	    if {![dict exists $D $x]} continue
	    dict for {v -} [dict get $D $x] {
		dict set altered $v {}
	    }
	}
	lappend ALTERED $altered
    }
    return $ALTERED
}
 
# quadcode::transformer method pre_antloc --
#
#	For each basic block in the program, compute the set of locally
#	anticipable expressions, that is, ones that can be moved ahead of
#	the block.
#
# Parameters:
#	defined - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that acquire
#                 values in the block. Dictionary values are immaterial.
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have
#                 values altered in the block. Dictionary values are immaterial.
#
# Results:
#	Returns a list of dictionaries. List indices are basic block numbers.
#	Dictionary keys are exemplars of expressions that are locally
#	anticipable from the block. Dictionary values are immaterial.
#
# Page 76 of [Simpson]: antloc_b = defined_b - altered_b



oo::define quadcode::transformer method pre_antloc {defined altered} {

    set ANTLOC {}
    set b -1
    foreach defns $defined alts $altered {
	incr b
	set antloc $defns
	dict for {alt -} $alts {
	    dict unset antloc $alt
	}
	lappend ANTLOC $antloc
    }
    return $ANTLOC
}
 
# quadcode::transformer method pre_ant_global --
#
#	Calculates the anticipable expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have their
#                 values change in the block. Dictionary values are immaterial.
#	antloc - List of dictionaries. List indices are basic block numbers.
#	         Dictionary keys are exemplars of expressions that are locally
#	         anticipable from the block. Dictionary values are immaterial.
#
# Results:
#	Returns an ordered pair {ANTIN ANTOUT}.
#
#	ANTIN is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values globally anticipable
#       on input to each block.
#
#	ANTOUT is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values globally anticipable on
#	output from the block.
#
# This procedure solves data flow equations given in Figure 6.3
# on page 69 of [Simpson].

oo::define quadcode::transformer method pre_ant_global {altered antloc} {

    my debug-pre {
	puts "Calculate global anticipable expressions:"
    }

    set ANTOUT [lrepeat [llength $altered] {}]
    set ANTIN $antloc

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in reverse depth-first order

    set pending [lrepeat [llength $altered] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $altered]} {incr i} {
................................................................................
    while {[$worklist size] > 0} {
	set b [expr {-[$worklist removeFirst]}]
	lset pending $b 0

	my debug-pre {
	    puts " Block #$b:"
	}



	# Calculate ANTOUT for the block as the intersection of ANTIN
	# of all predecessors

	set succs [my bbsucc $b]
	if {[llength $succs] == 0} {
	    # Exit block - nothing anticipable on output
	    set antout {}
	} else {
	    set othersuccs [lassign $succs firstsucc]
	    set antout [lindex $ANTIN $firstsucc]
	    foreach s $othersuccs {
		set othervs [lindex $ANTIN $s]
		dict for {v -} $antout {
		    if {![dict exists $othervs $v]} {
			dict unset antout $v
		    }
		}
	    }
	}
	my debug-pre {
	    puts "    Anticipable on output: [dict keys $antout]"
	}
	
	# Detect whether ANTOUT has changed. 
	set changed 0
	set oldantout [lindex $ANTOUT $b]
	dict for {v -} $antout {
	    if {![dict exists $oldantout $v]} {
		set changed 1
		break
	    }
	}

	# If ANTOUT has changed, we have to recalculate ANTIN
	if {$changed} {
	    my debug-pre {
		puts "    ANTOUT has changed, must update ANTIN"
	    }

	    lset ANTOUT $b $antout

	    set changed 0
	    set antin [lindex $ANTIN $b]
	    dict for {v -} $antout {
		if {![dict exists $altered $v] && ![dict exists $antin $v]} {
		    dict set antin $v {}
		    my debug-pre {
			puts "        ANTIN now includes $v"

		    }
		    set changed 1
		}
	    }
	}

	# If ANTIN has changed, we have to revisit the predecessors of this
	# block
	if {$changed} {

	    my debug-pre {
		puts "    ANTIN has changed, must update predecessors"
	    }
	    lset ANTIN $b $antin
	    dict for {p -} [lindex $bbpred $b] {
		if {![lindex $pending $p]} {
		    my debug-pre {
			puts "        Add $p to worklist"
		    }
		    $worklist add [expr {-$p}]
		    lset pending $p 1
		} else {
		    my debug-pre {
			puts "        $p is already on worklist"

		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_earliest --
#
#	Calculate the earliest edge in the control flow graph where the
#	calculation of a given expression may appear.
#
# Parameters:
#	AVOUT - List of dictionaries. List indices are basic block numbers,
#	        dictionary keys are exemplars of values available on output
#	        from the basic block, dictionary values are immaterial.
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have
#                 values altered in the block. Dictionary values are immaterial.
#	ANTIN - List of dictionaries indexed by block number and
#	        keyed by exemplar, giving the set of values globally anticipable
#               on input to each block.
#	ANTOUT - List of dictionaries indexed by block number and
#	         keyed by exemplar, giving the set of values globally
#                anticipable on output from the block.
#
# Results:
#	Returns a dictionary whose keys are ordered pairs {from to}
#	representing edges in the control flow graph (where 'from' and
#	'to' are basic block numbers), and whose values are dictionaries
#	whose keys are exemplars of values and whose values are immaterial.
#	The inner dictionaries are the sets of values for which the
#	graph edge {from, to} is the earliest place that computation is
#	permissible.

#
# This analysis is part of the data flow equations in Figure 6.3 on
# page 69 of [Simpson].

oo::define quadcode::transformer method pre_earliest {AVOUT altered
						      ANTIN ANTOUT} {

    my debug-pre {
	puts "Compute earliest insertion points"
    }

    # Walk through basic blocks

    set i -1
    foreach avout_i $AVOUT altered_i $altered antout_i $ANTOUT {
	incr i
	foreach j [my bbsucc $i] {

	    my debug-pre {
		puts "   Edge $i->$j:"
	    }

	    # Edge (i, j) exists in the flow graph. Calculate EARLIEST

	    # At the earliest point, a value must be anticipable
	    set earliest [lindex $ANTIN $j]
	    my debug-pre {
		puts "        ANTIN: [dict keys $earliest]"
	    }

	    # At the earliest point, a value must not be available
	    dict for {v -} $avout_i {
		dict unset earliest $v
	    }
	    my debug-pre {
		puts "        After removing AVOUT: [dict keys $earliest]"
	    }

	    # At the earliest point, a value must not simply flow through
	    # to the exit of the successor block
	    dict for {v -} $antout_i {
		if (![dict exists $altered_i $v]) {
		    my debug-pre {
			puts "        Remove $v because it simply\
                                      passes through $j"
		    }
		    dict unset earliest $v
		}
	    }
	    my debug-pre {
		puts "    What's left is [dict keys $earliest]"
	    }


	    dict set EARLIEST [list $i $j] $earliest
	}
    }
    
    return $EARLIEST
}
................................................................................
 
# quadcode::transformer method pre_later --
#
#	Calculates an indication of whether an expression can be
#	shifted later in the flowgraph
#
# Parameters:
#	ANTLOC - List of dictionaries. The list is indexed by basic
#	         block number. The keys in the dictionaries are the
#		 exemplars of values that are locally anticipable
#	         in the block. The values are immaterial.
#
#	EARLIEST - Two-level dictionary. The outer key is an ordered
#		   pair {i j} identifying an edge {i -> j} in the
#	           control flow graph.  The inner key is an exemplar
#	           of a value. The presence of the value indicates
#	           that the given flowgraph edge is the earliest point
#	           to which the computation of the given value may be
#	           moved. The values in the dictionary are immaterial.
#
# Results:
#	Returns an ordered pair {LATER LATERIN}.
#
#	LATER is a two-level dictionary.The outer key is an ordered
#       pair {i j} identifying an edge {i -> j} in the
#	control flow graph.  The inner key is an exemplar
#	of a value. The presence of the value indicates
#	that the computation of the given value may be moved
#	to at least the given edge. The values of the dictionary are
#	immaterial.
#
#	LATERIN is a list of dictionaries. The index in the list
#	is the number of a basic block. The dictionary keys are
#	exemplars of values. A value is present in the dictionary if
#	the computation may be moved downward at least to the start


#	of the corresponding basic block. The dictionary values are
#	immaterial.
#
# This procedure solves part of the dataflow equations shown in
# Figure 6.4 on page 70 of [Simpson].

oo::define quadcode::transformer method pre_later {ANTLOC EARLIEST} {

    my debug-pre {
	puts "Calculate LATER:"
    }




    set LATER $EARLIEST



    set LATERIN [lrepeat [llength $ANTLOC] {}]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $ANTLOC] 0]
    set worklist [::quadcode::numheap new]
    for {set i 1} {$i < [llength $ANTLOC]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate LATERIN for the block as the intersection of
	# LATER on each of its afferent edges.




	set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	set edge [list $firstpred $b]
	set laterin [dict get $LATER $edge]
	foreach p $otherpreds {
	    set edge [list $p $b]
	    set l [dict get $LATER $edge]
	    dict for {v -} $laterin {
		if {![dict exists $l $v]} {
		    dict unset $laterin $v
		}
	    }
	}

	my debug-pre {
	    puts "    LATERIN: [dict keys $laterin]"
	}
	
	# Detect whether LATERIN has changed. 
	set changed 0
	set oldlaterin [lindex $LATERIN $b]
	dict for {v -} $laterin {
	    if {![dict exists $oldlaterin $v]} {
		set changed 1
		break
	    }
	}

	# If LATERIN has changed, we have to recalculate LATER for
	# each successor
	
	if {$changed} {
	    my debug-pre {
		puts "    LATERIN has changed, must update LATER"
	    }
	    lset LATERIN $b $laterin

	    set intsct {}; # LATERIN_i - ANTLOC_i
	    set antloc [lindex $ANTLOC $b]
	    dict for {v -} $laterin {
		if {![dict exists $antloc $v]} {
		    my debug-pre {
			puts "        $v is not locally anticipable in $b"
		    }
		    dict set intsct $v {}
		}
	    }
	    foreach s [my bbsucc $b] {

		my debug-pre {
		    puts "        $b -> $s:"
		}
		set changed 0
		set edge [list $b $s]
		set later [dict get $LATER $edge]
		dict for {v -} $intsct {
		    if {![dict exists $later $v]} {

			my debug-pre {
			    puts "            LATER now includes $v"
			}
			dict set later $v {}
			set changed 1
		    }


		}

		if {$changed} {

		    my debug-pre {
			puts "        LATER has changed, must update bb $s"
		    }
		    dict set LATER $edge $later
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
................................................................................
    }

    $worklist destroy

    return [list $LATERIN $LATER]
    
}

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

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

    # Compute Global Value Numbering for the values present in the quadcode

    lassign [my pre_gvn] VN pre_exemplar cands
    my debug-pre {
	puts "Value numbering:"
	dict for {k n} [lsort -stride 2 -index 0 -ascii -increasing $VN] {
	    set v [lindex $pre_exemplar $n]
	    if {[lindex $v 0] ne $k} {
		puts "   found congruence $k -> $n ($v)"
	    }
	}
	puts "Candidates for PRE: [my pre_format_bitset $cands]"
    }

    # Compute the 'defined' predicate for the basic blocks

    set defined [my pre_defined $VN]
    my debug-pre {
	puts "Defined expressions:"
	set b -1
	foreach vset $defined {
	    puts "[incr b]: [my pre_format_bitset $vset]"
	}
    }

    # Find sets of available expressions

    lassign [my pre_avail $defined] AVIN AVOUT
    my debug-pre {
	puts "Available expressions"
	set b -1
	foreach inset $AVIN outset $AVOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    AVIN =  [my pre_format_bitset $inset]"
	    puts "    AVOUT = [my pre_format_bitset $outset]"
	}
    }


    # Find sets of expressions altered within each block

    set altered [my pre_altered $pre_exemplar $cands $AVIN $AVOUT]
    my debug-pre {
	puts "Altered expressions"
	set b -1
	foreach al $altered {
	    incr b
	    puts "  Block #$b: [my pre_format_bitset $al]"
	}
    }

    # Find expressions that are locally anticipable at entry to blocks

    set antloc [my pre_antloc $cands $defined $altered]
    my debug-pre {
	puts "Locally anticipable expressions"
	set b -1
	foreach an $antloc {
	    incr b
	    puts "  Block #$b: [my pre_format_bitset $an]"
	}
    }

    # Compute globally anticipable expressions

    lassign [my pre_ant_global $altered $antloc] ANTIN ANTOUT
    my debug-pre {
	puts "Globally anticipable expressions"
	set b -1
	foreach inset $ANTIN outset $ANTOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    ANTIN =  [my pre_format_bitset $inset]"
	    puts "    ANTOUT = [my pre_format_bitset $outset]"
	}
    }

    # Compute earliest points where an expression may be moved.
    # These are edges on the call graph where the expression may
    # appear. (Since we have no critical edges, the expression
    # can always be inserted at either the tail of the predecessor
    # block or the head of the successor).

    set EARLIEST [my pre_earliest $AVOUT $altered $ANTIN $ANTOUT]
    my debug-pre {
	puts "Earliest insertion points:"
	dict for {edge vars} $EARLIEST {
	    if {$vars != 0} {
		lassign $edge from to
		puts "    $from->$to: [my pre_format_bitset $vars]"
	    }
	}
    }

    # Compute LATER, which is an indication that an expression
    # may be moved later than an edge (LATER) or the start of
    # a block (LATERIN)
................................................................................

    lassign [my pre_later $antloc $EARLIEST] LATERIN LATER

    # Report on insertion and deletion points

    dict for {edge exprs} $LATER {
	lassign $edge from to
	my debug-pre {
	    puts "Edge $from -> $to: LATER = [my pre_format_bitset $exprs]"
	    puts "Node $to: LATERIN =\
                  [my pre_format_bitset [lindex $LATERIN $to]]"

	}
	set insert [expr {$exprs & ~[lindex $LATERIN $to]}]
	if {$insert != 0} {
	    puts "Insert on edge ($from -> $to): [my pre_format_bitset $insert]"
	}
    }

    set b -1
    foreach exprs $antloc laters $LATERIN {
	incr b
	if {$b == 0} continue
	my debug-pre {
	    puts "Block $b: ANTLOC = [my pre_format_bitset $exprs]"
	    puts "Block $b: LATERIN = [my pre_format_bitset $laters]"
	}
	set delete [expr {$exprs & ~$laters}]
	if {$delete != 0} {
	    puts "Delete from block $b: [my pre_format_bitset $delete]"
	}
    }

    unset pre_exemplar
    return 0

}
 
# quadcode::transformer method pre_gvn --
#
#	Calculates a Global Value Numbering for values in a quadcode
#	sequence.
#
# Results:
#	Returns a tjree-element list.
#
#	The first element is a dictionary whose keys are the names of


#	program variables and whose values are value numbers. Two value
#	numbers are distinct if it cannot be shown that they result
#	from the same computation.
#
#	The second element is a dictionary whose keys are the value
#	numbers and whose values are ordered pairs: program variables
#	that represent the values, and the expressions that compute the
#	values.
#
#	The third element is a bit set containing those values that are
#	candidates - that is, could conceivably be moved from block to block
#
# This procedure implements the 'RPO' algorithm presented in
# Figure 4.3 of [Simpson] (see references in the file header.
# While perhaps not as fast, it is significantly simpler than
# the 'SCC' algorithm and yields the same results.
#
# This procedure assumes that 'deadbb' has been run before it,
# so that it will find basic blocks already in depth-first order.

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

    variable ::quadcode::gvn_eliminable

    # Initially all value numbers are unknown

    set VN {}

    # Iterate to convergence

    while {1} {
	set changed 0
	set VNforSig {}
	set exemplarForVN {}
	set cands 0

	# Iterate through all basic blocks in depth-first order
	set b -1
	foreach bb $bbcontent {
	    incr b

	    # Walk through the instructions of each block
................................................................................

		# Ignore instructions that do not produce a value
		set result [lindex $q 1]
		if {[lindex $result 0] ni {"temp" "var"}} {
		    continue
		}

		# TODO - Detect meaningless phi?

		# Make a signature for the expression computed
		# by the current instruction
		set sig [my pre_gvn_sig $VN $q]

		# If there is already a value number for the signature, use
		# it. Otherwise, make the current result the exemplar of the
		# congruence class. Set 'changed' if the the value number
		# changes from the previous round.
		if {![dict exists $VNforSig $sig]} {
		    set vn [llength $exemplarForVN]
		    dict set VNforSig $sig $vn
		    lappend exemplarForVN [list $result $sig]
		    if {[dict exists $gvn_eliminable [lindex $q 0 0]]} {
			set cands [expr {$cands | (1 << $vn)}]
		    }
		}
		set vn [dict get $VNforSig $sig]
		if {![dict exists $VN $result]
		    || [dict get $VN $result] ne $vn} {
		    set changed 1
		    my debug-pre {
			puts "Value number for $result is now $vn"
		    }
		    dict set VN $result $vn
		}
	    }
	}
	
	if {!$changed} break
    }

    return [list $VN $exemplarForVN $cands]

}
 
# quadcode::transformer method pre_gvn_sig --
#
#	Develops a signature for a quadcode instruction's result
#	in Global Value Numbering
................................................................................
	    bb - pc {
		lappend signature {}
	    }
	    temp - var {
		if {![dict exists $VN $a]} {
		    lappend signature TOP
		} else {
		    lappend signature [list value [dict get $VN $a]]
		}
	    }
	    default {
		lappend signature $a
	    }
	} 
    }
................................................................................
 
# quadcode::transformer method pre_defined --
#
#	Computes the local predicate, 'defined', for use in the
#	dataflow equations.
#
# Results:
#	Returns a list of bit vectors.  Each vector represents the set
#	of values defined in a basic block.



oo::define quadcode::transformer method pre_defined {VN} {

    set DEFINED {}

    # Walk through the basic blocks

    set b -1
    foreach bb $bbcontent {
	incr b

	set defined 0

	# Walk through the individual instructions
	
	set pc -1
	foreach q $bb {
	    incr pc

	    lassign $q opcode result

	    # If an instruction defines a value, add the value to the set
	    
	    if {$result ne {} && [dict exists $VN $result]} {
		set defined [expr {$defined | (1 << [dict get $VN $result])}]
	    }
	}

	# Add the set to the list
	
	lappend DEFINED $defined
    }
................................................................................
 
# quadcode::transformer method pre_avail --
#
#	Calculates the available expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	defined - List of bit vectors corresponding to the sets of values


#	          defined in the basic blocks
#
# Results:
#	Returns an ordered pair {AVIN AVOUT}.
#
#	AVIN is a list of bit vectors giving the sets of values available
#	at the start of the basic blocks.

#
#	AVOUT is a list of bit vectors giving thes sets of values available
#	at the end of the basic blocks


#
# This procedure solves the data flow equations given in Figure 5.6
# on page 63 of [Simpson].

oo::define quadcode::transformer method pre_avail {defined} {

    my debug-pre {
	puts "Calculate available expressions:"
    }

    # Initially, assume all variables are available on input to all blocks
    # other than the entry, and then prove otherwise.
    set AVIN [lrepeat [llength $defined] -1]

    set AVOUT [lrepeat [llength $defined] -1]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $defined] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $defined]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate AVIN for the block as the intersection of AVOUT
	# of all predecessors

	if {$b == 0} {
	    set avin 0
	} else {
	    set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	    set avin [lindex $AVOUT $firstpred]
	    foreach p $otherpreds {
		set avin [expr {$avin & [lindex $AVOUT $p]}]




	    }
	}
	my debug-pre {
	    puts "    Available on input: [my pre_format_bitset $avin]"
	}
	










	# If AVIN has changed, we have to recalculate AVOUT

	if {$avin != [lindex $AVIN $b]} {
	    my debug-pre {
		puts "    AVIN has changed, must update AVOUT"
	    }
	    lset AVIN $b $avin

	    set avout [expr {$avin | [lindex $defined $b]}]




	    my debug-pre {

		puts "    Available on output: [my pre_format_bitset $avout]"
	    }





	    # If AVOUT has changed, we have to revisit the successors of this
	    # block

	    if {$avout != [lindex $AVOUT $b]} {
		my debug-pre {
		    puts "    AVOUT has changed, must update successors"

		}
		lset AVOUT $b $avout
		foreach s [my bbsucc $b] {
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
			}
			$worklist add $s
			lset pending $s 1
		    } else {
			my debug-pre {
			    puts "        $s is already on worklist"
			}
		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_altered --
#
#	For each basic block in the program, compute the set of values
#	that are altered by fixed values in the block
#
# Parameters:
#	exemplars - List of ordered pairs (name, expression) that
#	            show exemplar names and expression computed for
#	            each value.
#	cands - Bit set that identifies which values are candidates for
#	        code motion
#	AVIN - List of bit vectors indicating the expressions available
#	       on entry to the program's blocks
#	AVOUT - List of bit vectors indicating the expressions available
#	        on exit from the program's blocks
#
# Results:
#	Returns a list indexed by basic block number. The list values
#	are dictionaries whose keys are the exemplars of altered values
#	and whose values are immaterial
#
# This is the algorithm of Figure 7.1 on page 75 of [Simpson]. Simpson
# is quite unclear on the issue that (AVOUT-AVIN) should apply only to
# fixed values, and then the altered candidates appear only as a
# consequence of tracking the dependents on thosed fixed
# values. Nevertheless, if this filtering is not done, nothing ever
# becomes locally anticipable, because its own calculation turns up in
# (AVOUT-AVIN).

oo::define quadcode::transformer method pre_altered {exemplars cands
						     AVIN AVOUT} {



    set ALTERED {}



    # Walk through the basic blocks

    set b -1

    foreach avin $AVIN avout $AVOUT {
	incr b











	set altered [expr {$avout & ~$avin & ~$cands}]


	# Walk through all expressions in bottom-up order, and through
	# the operands of each expression



	set e -1
	foreach ex $exemplars {
	    incr e
	    set argl [lassign [lindex $ex 1] opcode]
	    foreach a $argl {



		lassign $a kind o
		if {$kind ne "value"} continue


		# Add altered values to the bit vector

		if {$altered & (1 << $o)} {
		    set altered [expr {$altered | (1 << $e)}]




		}
	    }
	}









	lappend ALTERED $altered





    }















    return $ALTERED
}
 
# quadcode::transformer method pre_antloc --
#
#	For each basic block in the program, compute the set of locally
#	anticipable expressions, that is, ones that can be moved ahead of
#	the block.
#
# Parameters:
#	cands - Bit set that identifies candidate expressions for
#	        partial redundancy elimination
#	defined - List of bit sets, indexed by basic block number, indicating
#	          what values are defined within the block
#	altered - List of bit sets, indexed by basic block number, indicating
#		  what values are altered within the block
#
# Results:
#	Returns a list of bit sets, indexed by basic block number, indicating
#	what values are locally anticipable within the block. Note that

#
# Page 76 of [Simpson]: antloc_b = defined_b - altered_b
# Simpson does not appear to constrain this to candidates, but it doesn't
# ever make sense to move a non-candidate.

oo::define quadcode::transformer method pre_antloc {cands defined altered} {

    set ANTLOC {}
    set b -1
    foreach defns $defined alts $altered {
	incr b




	lappend ANTLOC [expr {$defns & ~$alts & $cands}]
    }
    return $ANTLOC
}
 
# quadcode::transformer method pre_ant_global --
#
#	Calculates the anticipable expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	altered - List of bit vectors that enumerate the values altered
#	          in each block.
#	antloc - List of bit vectors that enumerate the candidate values
#	         for code motion that are locally anticipable in each block


#
# Results:
#	Returns an ordered pair {ANTIN ANTOUT}.
#
#	ANTIN is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that are anticipable on
#	entry into basic blocks.
#
#	ANTOUT is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that are anticipable on
#	exit from basic blocks
#
# This procedure solves data flow equations given in Figure 6.3
# on page 69 of [Simpson].

oo::define quadcode::transformer method pre_ant_global {altered antloc} {

    my debug-pre {
	puts "Calculate global anticipable expressions:"
    }

    set ANTOUT [lrepeat [llength $altered] -1]
    set ANTIN [lrepeat [llength $altered] -1]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in reverse depth-first order

    set pending [lrepeat [llength $altered] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $altered]} {incr i} {
................................................................................
    while {[$worklist size] > 0} {
	set b [expr {-[$worklist removeFirst]}]
	lset pending $b 0

	my debug-pre {
	    puts " Block #$b:"
	}
	set alt [lindex $altered $b]
	set aloc [lindex $antloc $b]

	# Calculate ANTOUT for the block as the intersection of ANTIN
	# of all predecessors

	set succs [my bbsucc $b]
	if {[llength $succs] == 0} {
	    # Exit block - nothing anticipable on output
	    set antout 0
	} else {
	    set othersuccs [lassign $succs firstsucc]
	    set antout [lindex $ANTIN $firstsucc]
	    foreach s $othersuccs {
		set antout [expr {$antout & [lindex $ANTIN $s]}]





	    }
	}
	my debug-pre {
	    puts "    Anticipable on output: [my pre_format_bitset $antout]"
	}
	










	# If ANTOUT has changed, we have to recalculate ANTIN




	if {$antout != [lindex $ANTOUT $b]} {
	    lset ANTOUT $b $antout








	    set antin [expr {($antout & ~$alt) | $aloc}]






	    # If ANTIN has changed, we have to revisit the predecessors of this
	    # block

	    if {$antin != [lindex $ANTIN $b]} {
		my debug-pre {
		    puts "    ANTIN has changed, must update predecessors"
		}
		lset ANTIN $b $antin
		dict for {p -} [lindex $bbpred $b] {
		    if {![lindex $pending $p]} {
			my debug-pre {
			    puts "        Add $p to worklist"
			}
			$worklist add [expr {-$p}]
			lset pending $p 1
		    } else {
			my debug-pre {
			    puts "        $p is already on worklist"
			}
		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_earliest --
#
#	Calculate the earliest edge in the control flow graph where the
#	calculation of a given expression may appear.
#
# Parameters:
#	AVOUT - List, indexed by basic block number, of bit vectors that
#	        enumerate the values available on exit from the corresponding
#	        basic blocks
#	altered - List, indexed by basic block number, of bit vectors that
#	          enumerate the values that are spoilt in the corresponding
#	          basic blocks
#	ANTIN - List, indexed by basic block number, of bit vectors that
#		enumerate the values that are globally anticipable on entry
#	        to the corresponding basic blocks.
#	ANTOUT - List, indexed by basic block number, of bit vectors that
#	         enumerate the values that are globally anticipable on exit
#	         from the corresponding basic blocks.
#
# Results:
#	Returns a dictionary whose keys are ordered pairs {from to}
#	representing edges in the control flow graph (where 'from' and
#	'to' are basic block numbers), and whose values are bit vectors

#	representing the sets of values for which the edges are the


#	earliest points where the values may be computed.
#
# This analysis is part of the data flow equations in Figure 6.3 on
# page 69 of [Simpson].

oo::define quadcode::transformer method pre_earliest {AVOUT altered
						      ANTIN ANTOUT} {

    set EARLIEST {}



    # Walk through flowgraph edges (i -> j)

    set i -1
    foreach avout_i $AVOUT altered_i $altered antout_i $ANTOUT {
	incr i
	foreach j [my bbsucc $i] {





	    # Edge (i, j) exists in the flow graph. Calculate EARLIEST


	    set antin_j [lindex $ANTIN $j]






	    set earliest [expr {$antin_j & ~$avout_i



















				& ($altered_i | ~$antout_i)}]

	    dict set EARLIEST [list $i $j] $earliest
	}
    }
    
    return $EARLIEST
}
................................................................................
 
# quadcode::transformer method pre_later --
#
#	Calculates an indication of whether an expression can be
#	shifted later in the flowgraph
#
# Parameters:
#	ANTLOC - List of bit sets, indexed by basic block number, indicating
#	         what values are locally anticipable within the block.
#
#	EARLIEST - Dictionary whose keys are ordered pairs {i j}
#	           identifying edges {i -> j} in the
#	           control flow graph.  The values are bit vectors enumerating
#	           sets of values for which the corresponding edgs is the
#	           earliest possible placement.




#
# Results:
#	Returns an ordered pair {LATER LATERIN}.
#
#	LATER is a dictionary whose keys are ordered pairs {i j}
#	identifying edges {i -> j} in the control flow graph.
#	The values are bit sets that enumerate the candidate values
#	that may be computed on the corresponding edge or a later point
#	in the program.


#




#	LATERIN is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that may be calculated
#	on entry to the corresponding basic block or later in the program.

#
# This procedure solves part of the dataflow equations shown in
# Figure 6.4 on page 70 of [Simpson].

oo::define quadcode::transformer method pre_later {ANTLOC EARLIEST} {

    my debug-pre {
	puts "Calculate LATER:"
    }

    # Initialize LATER with the universal set for every flowgraph edge,
    # and LATERIN with the universal set for every basic block

    set LATER []
    dict for {edge -} $EARLIEST {
	dict set LATER $edge -1
    }
    set LATERIN [lrepeat [llength $ANTLOC] -1]
    
    # Initially, the worklist is the complete set of basic blocks,
    # in depth-first order

    set pending [lrepeat [llength $ANTLOC] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $ANTLOC]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate LATERIN for the block as the intersection of
	# LATER on each of its afferent edges.

	if {$b == 0} {
	    set laterin 0
	} else {
	    set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	    set edge [list $firstpred $b]
	    set laterin [dict get $LATER $edge]
	    foreach p $otherpreds {
		set edge [list $p $b]
		set laterin [expr {$laterin & [dict get $LATER $edge]}]




	    }
	}

	my debug-pre {
	    puts "    LATERIN: [my pre_format_bitset $laterin]"
	}
	










	# If LATERIN has changed, we have to recalculate LATER for
	# each successor
	
	if {$laterin != [lindex $LATERIN $b]} {
	    my debug-pre {
		puts "    LATERIN has changed, must update LATER"
	    }
	    lset LATERIN $b $laterin


	    set intsct [expr {$laterin & ~[lindex $ANTLOC $b]}]








	    foreach s [my bbsucc $b] {

		my debug-pre {
		    puts "        $b -> $s:"
		}

		set edge [list $b $s]



		set later [expr {$intsct | [dict get $EARLIEST $edge]}]
		my debug-pre {
		    puts "            LATER = [my pre_format_bitset $later]"
		}



		# If LATER has changed, we need to requeue the successor
		# node.
	       


		if {$later != [dict get $LATER $edge]} {
		    my debug-pre {
			puts "        LATER has changed, must update bb $s"
		    }
		    dict set LATER $edge $later
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
................................................................................
    }

    $worklist destroy

    return [list $LATERIN $LATER]
    
}
 
# quadcode::transformer method pre_format_bitset --
#
#	Formats a set of values for debug printing
#
# Parameters:
#	vset - Set of values to be printed
#
# Results:
#	Returns a list of exemplars corresponding to the set of values

oo::define quadcode::transformer method pre_format_bitset {vset} {

    my variable pre_exemplar

    if {$vset == -1} {
	return "EVERYTHING"
    }
    if {$vset < 0} {
	set result "EVERYTHING BUT"
	set vset [expr {~$vset}]
    } else {
	set result {}
    }
    set vn -1
    foreach ex $pre_exemplar {
	incr vn
	if {$vset & (1 << $vn)} {
	    lappend result [lindex $ex 0]
	}
    }
    return $result
}