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
		    }

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
	    set pc -1
	    foreach q $bb {
		incr pc

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

    return $signature
}

# 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
    }

    return $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} {
	set b [$worklist removeFirst]
	lset pending $b 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

    return [list $AVIN $AVOUT]
    
}

# 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} {
	$worklist add [expr {-$i}]
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    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

    return [list $ANTIN $ANTOUT]
    
}

# 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} {
	set b [$worklist removeFirst]
	lset pending $b 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]
    
}