# quadcode sequence. The following passes are provided:

# deadjump:
#	This pass is a simple peephole optimization that finds
#	'jumpTrue' and 'jumpFalse' statements whose test condition is
#	constant, and optimizes them away.
#
# deadcond:
#	This pass optimizes conditional jumps where the condition
#	is known to be true because the jump is reachable only from
#	another jump that depends on the same condition.
#
# deadbb:
#	This pass removes basic blocks that are entirely unreachable.
#	It also coalesces blocks in the case where a single-exit predecessor
#	transfers control to a single-entry successor (this can happen,
#	for instance, if an intervening check for variable existence
#	has been removed). It re-establishes the depth first numbering
#	of the blocks, and rebuilds predecessor relations, du-chains,

	}
	my debug-deadjump {
	    puts "After removing dead conditional jumps:"
	    my dump-bb
	}
	return $changed
    }
    
    # deadcode --
    #
    #	Removes redundant conditional jumps
    #
    # Preconditions:
    #	Dominance tree (bbidom, bblevel, bbkids) must be up to date.
    #
    # Results:
    #	Returnns 1 if anything was removed, 0 otherwise.
    #
    # Side effects:
    #	Rewrites 'bbcontent', 'bbpred', 'udchain' and 'duchain' to reflect
    #	the fact that code was removed.
    #
    # Other optimizations can leave code in a state that looks something like:
    #
    #  1: {instanceOf NUMERIC} {temp 0 0} {var x 0}
    #     jumpFalse {bb X} {temp 0 0}
    #     jump {bb 2}
    #
    #  2: jumpFalse {bb Y} {temp 0 0}
    #     jump {bb 3}
    #
    # with the unreachable code at block Y getting in the way of
    # further optimizations. This pass clears away that particular dross
    # by rewriting block 2 in the above example to simply
    #     jump {bb 3}
    # since there is no way that the 'false' branch can be taken.
    # {temp 0 0} is known to be true since block 1 just tested it.
    #
    # Formally, the value of a condition is known if there is a block B
    # that tests it:
    #
    #    B: ... jumpTrue C, cond
    #           jump D
    #
    # and there is another jumpTrue or jumpFalse referring to 'cond' in
    # a block E,
    # and either C or D dominates or is equal to E.
    #
    # We proceed in a single pass to walk the dominance tree, accumulating
    # a dictionary that maps the conditions to the known values.
    # Every conditional jump that we encounter, for which the value is known,
    # is eliminated.
      
    method deadcond {} {

	my debug-deadcond {
	    puts "Before deadcond:"
	    my dump-bb
	}
	    
	return [my deadcond-worker 0 {}]

    }

    # deadcond-worker --
    #
    #	Visits a block and its dominance subtree, looking for redundant
    #	conditional jumps.
    #
    # Parameters:
    #	b - Block to visit.
    #	d - Dictionary whose keys are SSA variables and whose values are
    #	    those variables' known values on entry to b
    #
    # Results:
    #	Returns 1 if something changed in the subtree, 0 otherwise.

    method deadcond-worker {b d} {

	my debug-deadcond {
	    puts "$b: predetermined values: $d"
	}

	set changed 0

	# If the block ends in a conditional jump, it is known to dominate
	# both successors, because there are no critical edges. Find out what
	# the variable's value is on each of the two jumps out of the block

	set bb [lindex $bbcontent $b]
	set q [lindex $bb end-1]
	set opcode [lindex $q 0 0]
	if {$opcode eq "jumpTrue"} {
	    set trueBranch [lindex $q 1 1] 
	    set falseBranch [lindex $bb end 1 1]
	    set isCond 1
	} elseif {$opcode eq "jumpFalse"} {
	    set trueBranch [lindex $bb end 1 1]
	    set falseBranch [lindex $q 1 1]
	    set isCond 1
	} else {
	    set isCond 0
	}

	# Enumerate immediately dominated blocks as a dictionary to
	# enable quick removal

	set k {}
	foreach kid [lindex $bbkids $b] {
	    dict set k $kid {}
	}

	# Handle conditional branches

	if {$isCond} {
	    my debug-deadcond {
		puts "Examine conditional jump $b:end-1: $q"
	    }
	    set v [lindex $q 2]
	    if {[dict exists $d $v]} {

		lset bbcontent $b {}
		if {[dict get $d $v]} {
		    set branch $trueBranch
		    my removePred $falseBranch $b
		    dict unset k $falseBranch
		} else {
		    set branch $falseBranch
		    my removePred $trueBranch $b
		    dict unset k $trueBranch
		}
		my removeUse $v $b
		set newq [list jump [list bb $branch]]
		my debug-deadcond {
		    puts "Replace end of the block with $newq"
		}
		set bb [lreplace $bb[set bb ""] end-1 end $newq]
		lset bbcontent $b $bb
		set changed 1

	    } else {

		# Visit dominance trees of the successor blocks, with
		# known values for $v.

		set d2 $d
		my debug-deadcond {
		    puts "  In $trueBranch, $v = 1"
		}
		dict unset k $trueBranch
		dict set d2 $v 1
		if {[my deadcond-worker $trueBranch $d2]} {
		    set changed 1
		}
		my debug-deadcond {
		    puts "In $falseBranch, $v = 0"
		}
		dict unset k $falseBranch
		dict set d2 $v 0
		if {[my deadcond-worker $falseBranch $d2]} {
		    set changed 1
		}
	    }
	}

	# Handle any dominance children that the above code did not handle

	dict for {kid -} $k {
	    if {[my deadcond-worker $kid $d]} {
		set changed 1
	    }
	}

	return $changed
    }
    
    
    # deadbb --
    #
    #	Removes dead basic blocks from the system.
    #
    # Results:
    #	Returns 1 if anything was removed, 0 otherwise

	}
	foreach pass {
	    copyprop
	    cleanupMoveFromCallFrame
	    cleanupMoveToCallFrame
	    cleanupCallFrameUse
	    cleanupNarrow


	    bbidom
	    bblevel
	    deadcond
	    deadjump
	    deadbb
	    deadvars
	    uselessphis
	    bbidom
	    bblevel
	    constfold
	    partialredundancy
	} {
	    set cmd [string map [list @pass $pass] {
		set result [my @pass]
	    }]
	    lappend timings $pass [lindex [time $cmd] 0]