}

}

proc cse {x a} {
    set s 0
    for {set i 0} {$i < $a} {incr i} {
	if {$i % 2 == 0} {
	    incr s [expr {2*$x + 1}]
	} else {
	    incr s [expr {2*$x + 2}]
	}
    }
    return $s
}

    }

}

proc cse {x a} {
    set s 0
    for {set i 0} {$i < $a} {incr i} {
	if {($i & 1) == 0} {
	    incr s [expr {2*$x + 1}]
	} else {
	    incr s [expr {2*$x + 2}]
	}
    }
    return $s
}

	    puts "    AVIN =  $inset"
	    puts "    AVOUT = $outset"
	}
    }

    # Find sets of expressions altered within each block

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

    # 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
    
























    return 0

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

    return [list $AVIN $AVOUT]
    
}
 
# quadcode::transformer method pre_altered --
#
#	Computes the expressions altered in each block of the quadcode
#	sequence.
#
# Parameters:
#	VN - Dictionary that maps quadcode variable names to exemplars
#	     of their congruence classes.
#	AVIN - List of dictionaries. List indices are basic block numbers,
#	       dictionary keys are exemplars of values available on input
#	       to the basic block, dictionary values are immaterial.
#	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.
#
# Results:
#	Returns a list of dictionaries. List indices are basic block
#	numbers. Dictionary keys are exemplars of values altered in the


#	block. Dictionary values are immaterial.
#
# Algorithm is in Figure 7.1 on page 75 of [Simpson].
#
# FIXME: THIS IS WRONG:  We need to maintain dependencies per expression...
#        so we need a data structure that maintains the operands of
#	 all expressions in the program.


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


    set ALTERED {}



    # Walk through the basic blocks

    set b -1
    foreach bb $bbcontent avin $AVIN avout $AVOUT {
	incr b







	# Initially, altered_b is AVOUT_b - AVIN_b


	set altered $avin
	dict for {val -} $avout {
	    dict unset altered $val

	}
































	# Walk through the quadcode instructions in a block





	set pc -1
	foreach q $bb {
	    incr pc
	    set arglist [lassign $q opcode result]

	    if {![dict exists $VN $result]} continue
	    set e [dict get $VN $result]

	    # Walk through the operands of an expression
	    foreach arg $arglist {
		if {![dict exists $VN $arg]} continue
		set o [dict get $VN $arg]

		# If an operand is in the altered set, add the
		# result to the altered set
		if {[dict exists $altered $o]} {
		    dict set altered $e {}
		}
	    }
	}

	my debug-pre {
	    puts "Altered in block #$b: $altered"
	}

	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

	    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]"
	}
................................................................................
    }

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

    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