# variant block.

    my jt_forward

    # Determine whether the division into variants is trying to split
    # anything.

    set changed [my jt_has_multiple_variants]
    if {$changed} {


        # We will be doing a 'violent' rewrite of the control flow. Rather
        # than trying to maintain data flows in the face of this, it is
        # easier to deconstruct SSA form, perform the rewriting using
        # conventional assignments, and then reconvert to SSA.
        my deconstructSSA

        # Split the blocks into the variants computed by jt_forward, and
        # recompute the control flow (bbpred and block successors).
        my jt_split_paths
        my debug-jumpthread {
            puts "After splitting the paths:"
            my dump-bb
        }


        # Splitting the paths may have introduced new critical edges, so
        # make sure that they get resplit. 
        my splitCritical

        my debug-jumpthread {
            puts "After splitting critical edges:"
            my dump-bb
        }

        # Splitting critical edges requires that topologic order be restored
        # to the blocks.
        my sortbb
        my debug-jumpthread {
            puts "After re-sorting basic blocks:"
            my dump-bb
        }


        # Restore SSA form, compute ud- and du-chains, and propagate copies.
        my ssa
        my debug-jumpthread {
            puts "After reconstructing SSA:"
            my dump-bb
        }
        my ud_du_chain
        my copyprop

        # The code should now be ready to repeat type analysis and cleanup
        # optimizations.

    }
        
    # Clean up the working storage
    
    my jt_cleanup

    return $changed
}

# quadcode::transformer method jt_unpackPhis --
#
#	Unpacks phi operations for fast lookup when doing jump threading.
#
# Results:

#
#	Constructs the list, jt_antin, indexed by basic block number,
#	containing dictionaries.  The dictionaries describe the conditions
#	that will inform jump threading downstream of the entry to the basic
#	blocks. The dictionaries have two levels. The first level key gives
#	the name of a value in the quadcode, and the second gives a condition
#	on that value's type.  The second key is either 'is TYPECONST'
#	or 'isnot TYPECONST' for a given value in quadcode::dataType.
#	The values in the dictionary are ordinal numbers of conditions in the
#	block, and will be used to construct bit vectors of what conditions
#	are satisfied in a copy of the block.

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

    namespace upvar ::quadcode jt_removable jt_removable

#	conditions forward into the successor. If the successor has
#	a set of conditions that has not yet been visited, adds it
#	to 'jt_variants' and stacks it for processing.

oo::define quadcode::transformer method jt_forward_worker {b mask} {

    namespace upvar ::quadcode::dataType ARRAY ARRAY CONST0 CONST0 \
        CONST1 CONST1 IMPURE IMPURE NEXIST NEXIST ZEROONE ZEROONE

    my debug-jumpthread {
        puts "  bb $b:"
    }

    # Find out what assertions are guaranteed by $mask
    set asserted [my jt_maskToAssertions $b $mask]

        switch -exact -- $op {

            "arrayExists" {
                if {[quadcode::dataType::isa $fromtype $ARRAY]} {
                    dict set localtypes $result $CONST1
                } elseif {![quadcode::dataType::mightbea $fromtype $ARRAY]} {
                    dict set localtypes $result $CONST0
                } else {
                    dict set localtypes $result $ZEROONE
                }
            }

            "copy" {
                dict set localtypes $result $fromtype
            }

            "exists" {
                if {$fromtype == $NEXIST} {
                    dict set localtypes $result $CONST0
                } elseif {!($fromtype & $NEXIST)} {
                    dict set localtypes $result $CONST1
                } else {
                    dict set localtypes $result $ZEROONE
                }
            }

            "instanceOf" {
                if {[quadcode::dataType::isa $fromtype $totype]} {
                    dict set localtypes $result $CONST1
                } elseif {![quadcode::dataType::mightbea $fromtype $totype]} {
                    dict set localtypes $result $CONST0
                } else {
                    dict set localtypes $result $ZEROONE
                }
            }
            
            "jump" {
                my jt_processSuccessor $b $mask \
                    [lindex $result 1] $localtypes
                break

                    $fromtype $failbranch $okbranch $localtypes
                break
            }

            "narrowToType" {
                dict set localtypes $result [expr {$fromtype & $totype}]
            }

            "phi" {
                if {![dict exists $localtypes $result]} {
                    dict set localtypes $result [dict get $types $result]
                }
            }

            "purify" {
                dict set localtypes $result [expr {$fromtype & ~$IMPURE}]
            }

            default {
                if {[lindex $result 0] in {"temp" "var"}} {
                    dict set localtypes $result [dict get $types $result]
                }
            }
        }

        my debug-jumpthread {
            if {[lindex $result 0] in {"temp" "var"}} {
                puts [format "      local type of %s is %#llx (%s)" \
                          $result [dict get $localtypes $result] \
                          [nameOfType [dict get $localtypes $result]]]
            }
        }
    }

    return
}


#	Returns a bit vector of anticipated conditions satisfied at entry
#	to block $s.

oo::define quadcode::transformer method jt_assertionsToMask {p pmask ptypes s} {

    my variable jt_antin

    my debug-jumpthread {
        puts "\t    make assertion mask for $p -> $s"
    }

    set smask 0
    set cn -1
    dict for {v conds} [lindex $jt_antin $s] {
        dict for {c -} $conds {
            incr cn
            if {[my jt_test_assertion $p $pmask $ptypes $s $v $c]} {
                my debug-jumpthread {
                    puts "\t      include $v $c"
                }
                set smask [expr {$smask | (1 << $cn)}]
            }
        }
    }
    return $smask

#	cond - Condition being tested
#
# Results:
#	Returns 1 if the condition is satisfied, 0 otherwise

oo::define quadcode::transformer method jt_test_assertion {p pmask ptypes
                                                           s v cond} {
    namespace upvar ::quadcode::dataType NEXIST NEXIST

    lassign $cond kind t

    # Find the name of the variable in the predecessor
    set w [my jt_translate_phi $s $v $p]

    if {$w eq "Nothing"} {
        set u $NEXIST
    } elseif {[lindex $w 0] eq "literal"} {

        # The operand is a literal - extract its data type
        set u [::quadcode::typeOfLiteral [lindex $w 1]]
    } elseif {[dict exists $ptypes $w]} {

        # The operand is defined in the predecessor block, get its type
        set u [dict get $ptypes $w]

#
# Results:
#	Returns the type of the operand, or 0 if the operand does not
#	represent a value.

oo::define quadcode::transformer method jt_localtype {opd localtypes} {

    namespace upvar ::quadcode::dataType NEXIST NEXIST

    switch -exact -- [lindex $opd 0] {
        "Nothing" {
            return $NEXIST
        }
        "literal" {
            return [quadcode::typeOfLiteral [lindex $opd 1]]
        }
        "temp" - "var" {
            if {[dict exists $localtypes $opd]} {
                return [dict get $localtypes $opd]
            } else {

        if {[dict size $vs] > 1} {
            return 1
        }
    }

    return 0
}

# quadcode::transformer method jt_split_paths --
#
#	Duplicates basic blocks in the program to allow for jump threading.
#
# Results:
#	None.
#
# Side effects:
#	The 'bbcontent' array is augmented to hold the additional copies.
#	The 'bbpred' array is updated to reflect the revised control flows.

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

    # Destroy the predecessor relation. It will be recomputed as we
    # reconstruct the control flow
    set bbpred [lrepeat [llength $bbcontent] {}]

    # Make the required number of copies of each basic block
    set bmap [my jt_duplicate_blocks]

    # Rewrite the jumps at the end of each block to go to the new block.
    my jt_retarget_jumps $bmap
    
    return
}

# quadcode::transformer method jt_duplicate_blocks --
#
#	Makes the required number of duplicates of each block in the
#	program when performing jump threading.
#
# Results:
#	Returns a dictionary, bmap,  where
#	    [dict get $bmap $block $variant]
#	gives the number of the basic block in the new program that
#	corresponds to the requeste variant in the old program.

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

    my variable jt_variants

    # Make the required number of duplicates of each basic block.
    set newcontent {}
    set bmap {}
    set b -1
    set newb -1
    foreach vs $jt_variants bb $bbcontent {
        incr b
        lappend bbpred {}
        dict for {mask -} $vs {
            dict set bmap $b $mask [incr newb]
            lappend newcontent $bb
            my debug-jumpthread {
                puts [format "  Block %d (%#llx) -> new block %d" \
                          $b $mask $newb]
            }
        }
    }
    set bbcontent $newcontent
    return $bmap
}

# quadcode::transformer method jt_retarget_jumps --
#
#	Rewrites the jump instructions at the end of blocks after
#	performing block copying for jump threading.
#
# Parameters:
#	bmap - Dictionary describing where to find block copies.
#	       [dict get $bmap $b $variant] is the block number in
#	       the new program corresponding to variant $variant of
#	       block $b in the old program.
#
# Results:
#	None.
#
# Side effects:
#	Rewrites the jumps in the program, and re-establishes the control
#	flow graph.
#
# The rewrites encompass several cases:
#
#	0  - The block has no exits, do nothing
#	1a - The block has 1 exit, and the original had 1. End the
#	     block with an unconditional jump
#	1b - The block has 1 exit, but the original had 2. End the block
#	     with an unconditional jump, deleting any conditional jump that
#	     may have been there.
#	2  - The block has 2 exits, Rewrite both jumps to target the correct
#	     copies of the successor.

oo::define quadcode::transformer method jt_retarget_jumps {bmap} {

    my variable jt_variants

    # Walk through the blocks of the original program
    set b -1
    set oldb -1
    foreach vs $jt_variants {
        incr oldb

        # Walk through the variants, which are the blocks of the new program.
        dict for {mask targets} $vs {
            incr b
            set bb [lindex $bbcontent $b]
            lset bbcontent $b {}

            # How many jumps need to be rewritten in the block?
            
            switch -exact -- [dict size $targets] {

                0 {
                    # 0-exit block - do nothing
                    my debug-jumpthread {
                        puts "        Block $b has no exits"
                    }
                }

                1 {
                    # 1-exit block
                    if {[lindex $bb end-1 1 0] eq "bb"} {
                        my debug-jumpthread {
                            puts "        Block $b: reduce a 2-exit block\
                                          to 1-exit"
                        }
                        # Original block was two-exit
                        set start end-1
                    } else {
                        my debug-jumpthread {
                            puts "        Block $b has one exit"
                        }
                        # Original block was one-exit
                        set start end
                    }
                    # Replace jump(s) at the end of the block
                    dict for {bwas mask} $targets break
                    set newtarget [dict get $bmap $bwas $mask]
                    set newq [list jump [list bb $newtarget]]
                    set bb [lreplace $bb[set bb ""] $start end $newq]
                    my bblink $b $newtarget
                    my debug-jumpthread {
                        puts "  $b:end: $newq   # $bwas ([format %llx $mask])"
                    }
                }

                2 {
                    my debug-jumpthread {
                        puts "        Block $b has two exits"
                    }
                    # Two-exit block - rewrite the jumps
                    set q [lindex $bb end-1]
                    set newq [my jt_retarget $q $targets $bmap]
                    lset bb end-1 $newq
                    my bblink $b [lindex $newq 1 1]
                    my debug-jumpthread {
                        puts "  $b:end-1: $newq"
                    }
                    
                    set q [lindex $bb end]
                    set newq [my jt_retarget $q $targets $bmap]
                    lset bb end $newq
                    my bblink $b [lindex $newq 1 1]
                    my debug-jumpthread {
                        puts "  $b:end: $newq"
                    }
                }
            }

            # Put the basic block content back.
            lset bbcontent $b $bb
        }
    }

    return
}

# quadcode::transformer method jt_retarget --
#
#	Rewrites a single jump instruction during jump threading.
#
# Parameters:
#	q - Jump instruction being rewritten
#	targets - Dictionary whose keys are jump targets in the original
#	          program and whose values are block variants for those
#	          targets
#	bmap - Dictionary describing where to find the block variants.
#	       [dict get $bmap $b $variant] gives the basic block
#	       number in the new program corresponding to variant $variant
#	       of block $b in the original program.
#
# Results:
#	Returns the rewritten instruction.

oo::define quadcode::transformer method jt_retarget {q targets bmap} {

    set tgt [lindex $q 1 1]
    set var [dict get $targets $tgt]
    lset q 1 1 [dict get $bmap $tgt $var]

    return $q
}

# quadcode::transformer method jt_cleanup --
#
#	Cleans up working storage after the jump threading pass.
#
# Results:
#	None.

#		 eliminates variable-to-variable copies in the process,
#		 and fills in the arguments to phi functions.

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

	my bbidom
	my bblevel
	set aliasFor [my bbssa1]
	my bbssa2 $aliasFor
    }


# bbidom --
#
#	Compute the immediate dominators of the basic blocks
#

#
#	First pass of the SSA conversion
#
# Preconditions:
#	The immediate dominance tree (bbidom and bbkids) must be known,
#	and dominance depths (bblevel) must have been calculated.
#
# Results:
#	Returns a dictionary that describes the placed phi operations.
#	Keys are the result variables of the phi's; values are the
#	variable names that the phi's replace.
#
# Side effects:
#	Contents of basic blocks are rewritten to add phi functions at the
#	beginning of the blocks for the variables that converge on the block.
#	The 'vars' variable is set to a list of variable names in
#	the program.

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

    set varcount {}
    
    # Find out the 'globals' - the variables that flow from one block
    # to another - and the basic blocks in which variables are written.

    set global {}
    set vardict {}
    set writers {}
    set b -1

		}
	    }
	}
    }

    # Find places to insert phi nodes

    set aliasFor {}
    set phis [lrepeat [llength $bbcontent] {}]
    dict for {v -} $global {
	if {[dict exists $writers $v]} {
	    if {[dict exists $writers $v]} {
		set w [dict keys [dict get $writers $v]]
	    } else {
		set w {}
	    }
	    foreach n [my bbfrontier+ $w] {
		set newv [my newVarInstance $v]
		set list [lindex $phis $n]
		lset phis $n {}
		lappend list [list phi $newv]
		lset phis $n $list
		dict set aliasFor $newv $v
	    }
	}
    }

    # Insert phi nodes

    set b 0
    foreach content $bbcontent phi $phis {
	lset bbcontent $b [concat $phi $content]
	incr b
    }

    set vars [dict keys $vardict]
    return $aliasFor

}

# quadcode::transformer method bbssa2 -
#
#	Second pass of SSA transformation
#
# Preconditions:
#	A list of variables in the program must be in the 'vars' variable
#	(quads-list-vars will compute this). The immediate dominance tree
#	(bbidom and bbkids) must have been computed, and dominance frontiers
#	(bbfrontier) must be known. Dummy phi functions must have already
#	been placed at confluence points (bbssa1).
#
# Parameters:
#	aliasFor - Dictionary that, for each placed 'phi' operation, lists
#	           the variable that the 'phi' replaces. Keys are the result
#                  variables of the 'phi' instructions.
#
# Results:
#	None.
#
# Side effects:
#	Rewrites all basic blocks to begin with phi functions for confluent
#	variables, and removes copies.

oo::define quadcode::transformer method bbssa2 {aliasFor} {
    my debug-ssa {
	puts "before variable renaming:"
	my dump-bb
    }

    set stack {}

    foreach v $vars {
	dict set stack $v [list "Nothing"]
    }
    my renamevars 0 stack $aliasFor

    my debug-ssa {
	puts "after variable renaming:"
	my dump-bb
    }

    unset vars

#	Renames the variables in a basic block and its dominance children
#	to the correct names for SSA form
#
# Parameters:
#	b - Basic block number
#	vstack - Name of a variable in callers scope that maintains the
#		 stack of current variable names.
#	aliasFor - Dictionary that maps the names of phi results to the
#	           names of the program variables that they replace.
#
# Results:
#	None.
#
# Side effects:
#	Basic blocks are rewritten. Phi functions are filled in and copies
#	are removed.
#
# This procedure is called once in bbssa2 for the entry block. It
# recurses down the dominance tree to fill in the variables for all
# the other blocks.

oo::define quadcode::transformer method renamevars {b vstack aliasFor} {
    upvar 1 $vstack stack

    my debug-ssa {
	puts "Rename vars in basic block $b"
    }

    # Iterate over the quads in the basic block
    set newcontent {}
    set oldcontent [lindex $bbcontent $b]

    foreach q $oldcontent {
	set op [lindex $q 0]
	set lhs [lindex $q 1]

	# Rewrite variable uses
	if {$op ne "phi"} {
	    set i 2

	# Replace unsets with Nothing
	if {$op eq "unset"} {
	    set newlhs Nothing
	    set stk [dict get $stack $lhs]
	    dict set stack $lhs {}
	    lappend stk $newlhs
	    dict set stack $lhs $stk
	} elseif {$op eq "phi"} {
	    set oldv [dict get $aliasFor $lhs]
	    my debug-ssa {
		puts "  rename $oldv -> $var"
	    }
	    lappend newcontent $q
	    set stk [dict get $stack $oldv]
	    dict set stack $oldv {}
	    lappend stk $lhs
	    dict set stack $oldv $stk
	} elseif {[lindex $lhs 0] in {"temp" "var"}} {
	    set newlhs [my newVarInstance $lhs]
	    lset q 1 $newlhs
	    lappend newcontent $q
	    set stk [dict get $stack $lhs]
	    dict set stack $lhs {}
	    lappend stk $newlhs
	    dict set stack $lhs $stk
	    my debug-ssa {
		puts "  rename $lhs -> $newlhs"
	    }
	} else {
	    lappend newcontent $q
	}
    }

    # Patch the phi's in the successor blocks.
    foreach s [my bbsucc $b] {
	set j 0
	foreach q [lindex $bbcontent $s] {
	    if {[lindex $q 0] eq "phi"} {
		my debug-ssa {
		    puts "Patch $q in successor block $s"
		}
		set oldv [dict get $aliasFor [lindex $q 1]]
		my debug-ssa {
		    puts "  it originally referred to $oldv"
		}
		set source [lindex [dict get $stack $oldv] end]
		my debug-ssa {
		    puts "  and now includes $b -> $source"
		}
		lappend q [list bb $b] $source
		lset bbcontent $s $j $q
	    } else {
		break
	    }
	    incr j
	}
    }
    lset bbcontent $b $newcontent

    # Recurse down the dominance tree
    foreach k [lindex $bbkids $b] {
	my renamevars $k stack $aliasFor
    }

    # Pop the variables that we pushed
    my debug-ssa {
	puts "Pop vars when leaving block $b"
    }
    foreach q $oldcontent {
	lassign $q op lhs
	if {[lindex $lhs 0] in {"temp" "var"}} {
	    if {$op eq "phi"} {
		set lhs [dict get $aliasFor $lhs]
	    }
	    my debug-ssa {
		puts "   pop $lhs"
	    }
	    set stk [dict get $stack $lhs]
	    dict set stack $lhs {}
	    set stk [lreplace $stk[set stk {}] end end]
	    dict set stack $lhs $stk
	}
    }

    }
    
    my debug-convssa {
	puts "convssa: after copy insertion:"
	my dump-bb
    }
}

# quadcode::transformer method deconstructSSA --
#
#	Converts a quadcode sequence from SSA form back to multiple
#	assignments.
#
# Results:
#	None.
#
# Side effects:
#	Phi operations are removed and assignment operations are added.
#
# This transformation is used in passes that make sweeping changes to
# program structure. In some of these passes, it is easier to destroy SSA
# form completely and reconstruct it afterward than it is to attempt to
# track the data flows.

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

    my debug-decontstructSSA {
	puts "Deconstruct SSA form for [my full-name]:"
    }

    # Walk through the basic blocks, rewriting each one in turn
    set newcontent {}
    set b -1
    foreach bb $bbcontent {
	incr b
	my debug-deconstructSSA {
	    puts "  bb $b:"
	}

	# Copy over the quads in one block, removing the phis and stopping
	# at the first jump at the end of the block
	set newb {}
	set newpc -1
	set pc -1
	set singleExit 1
	foreach q $bb {
	    incr pc
	    if {[lindex $q 0 0] eq "phi"} {
		continue
	    }
	    if {[lindex $q 0 0] eq "jump"} {
		break
	    }
	    if {[lindex $q 1 0] eq "bb"} {
		set singleExit 0
	    }
	    my debug-deconstructSSA {
		puts "    [incr newpc]: $q"
	    }
	    lappend newb $q
	}

	# If the block is single-exit, examine the phi operations
	# in the successor block and convert them to assignments here.

	if {[lindex $q 0 0] eq "jump" && $singleExit} {
	    set s [lindex $q 1 1]
	    set bkey [list bb $b]
	    my debug-deconstructSSA {
		puts "      # assignments from block $s:"
	    }
	    foreach q2 [lindex $bbcontent $s] {
		set argl [lassign $q2 opcode dest]
		if {[lindex $opcode 0] ne "phi"} {
		    break
		}
		set src [dict get $argl $bkey]
		if {$src eq "Nothing"} {
		    set q3 [list unset $dest]
		} else {
		    set q3 [list copy $dest $src]
		}
		my debug-deconstructSSA {
		    puts "    [incr newpc]: $q3"
		}
		lappend newb $q3
	    }
	}

	# Put the jump back in at the end of a single-exit block
	if {[lindex $q 0 0] eq "jump"} {
	    my debug-deconstructSSA {
		puts "    [incr newpc]: $q"
	    }
	    lappend newb $q
	}
	    
	# Done with the new basic block
	lappend newcontent $newb
    }

    # Replace the program with the rewritten one

    set bbcontent $newcontent
    return
}