regsubtest
    # Failure handling, [subst], [try]
    wideretest
    substtest
    substtest2
    switchfail
    trimtest


    magicreturn
    returntest
    errortest1
    errortest2
    errortest2-caller
    errortest3
    errortest4 errortest4a errortest4b
    errortest5 errortest6
................................................................................
    wordcounter3
    wordcounter4
    # Calls of uncompiled code
    calltest
    calltest2
    calltest3
    # Callframe tests


#    callframe::test1		TEMP direct ops
#    callframe::test2		TEMP direct ops
#    callframe::test3		TEMP direct ops
#    callframe::test4		TEMP direct ops
    # The interprocedural tests
    mrtest::*
    coscaller1
    coscaller2
    xsum xsum2
    # Namespace tests
    # nstestaux::pts	TEMP depends on direct ops
    nstest::nstest0
    nstest::nstest1
    # nstest::nstest2   fails with command not found
    nstest::nstest3
    nstest::nstest4
    # nstest::nstest5   fails with invalid command name
    nstest::nstest6
    nstest::nstest7
    nstest::nstest8
    nstest9
    upvartest::*
    # Miscellaneous other tests
    bctest
................................................................................
    asmtest

    # List expansion tests

    expandtest::joinsp expandtest::join/ expandtest::join, expandtest::fixed
    expandtest::fixedUp
    expandtest::test1 expandtest::test2 expandtest::test3
    # expandtest::test4   Needs support for return -code continue
    # expandtest::test5   Needs support for loop exception ranges
    expandtest::test6
    expandtest::test7
    expandtest::test8
    expandtest::test9
    expandtest::test10
    expandtest::test11
    expandtest::test12
................................................................................
    linesearch::colinear
    linesearch::sameline
    linesearch::getAllLines1
    linesearch::getAllLines2
    regexptest::*
    vartest::*
    nsvartest::*
    # directtest::*		TEMP direct ops
    upvar0
    upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*

    regsubtest
    # Failure handling, [subst], [try]
    wideretest
    substtest
    substtest2
    switchfail
    trimtest
    # See email chain at
    # https://sourceforge.net/p/tcl/mailman/message/36579552/
#   magicreturn							BUG
    returntest
    errortest1
    errortest2
    errortest2-caller
    errortest3
    errortest4 errortest4a errortest4b
    errortest5 errortest6
................................................................................
    wordcounter3
    wordcounter4
    # Calls of uncompiled code
    calltest
    calltest2
    calltest3
    # Callframe tests
    # Direct operations are not yet implemented in the
    # callframe-refactor branch
#    callframe::test1		TEMP direct ops			BUG
#    callframe::test2		TEMP direct ops			BUG
#    callframe::test3		TEMP direct ops			BUG
#    callframe::test4		TEMP direct ops			BUG
    # The interprocedural tests
    mrtest::*
    coscaller1
    coscaller2
    xsum xsum2
    # Namespace tests
    # nstestaux::pts	TEMP depends on direct ops		BUG
    nstest::nstest0
    nstest::nstest1
    # nstest::nstest2   fails with command not found		BUG
    nstest::nstest3
    nstest::nstest4
    # nstest::nstest5   fails with invalid command name		BUG
    nstest::nstest6
    nstest::nstest7
    nstest::nstest8
    nstest9
    upvartest::*
    # Miscellaneous other tests
    bctest
................................................................................
    asmtest

    # List expansion tests

    expandtest::joinsp expandtest::join/ expandtest::join, expandtest::fixed
    expandtest::fixedUp
    expandtest::test1 expandtest::test2 expandtest::test3
    # expandtest::test4   Needs support for return -code continue   BUG
    # expandtest::test5   Needs support for loop exception ranges   BUG
    expandtest::test6
    expandtest::test7
    expandtest::test8
    expandtest::test9
    expandtest::test10
    expandtest::test11
    expandtest::test12
................................................................................
    linesearch::colinear
    linesearch::sameline
    linesearch::getAllLines1
    linesearch::getAllLines2
    regexptest::*
    vartest::*
    nsvartest::*
    # directtest::*		TEMP direct ops				BUG
    upvar0
    upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*

# Optimizing data motion into and out of callframes in Tcl

Kevin B Kenny

16 February 2019

## Introduction

As of the current version ([0718166269]), the handling of variables in
the callframe reflects some fairly fundamental oversights in the effect of
Tcl operations on variables. Essentially, what it does is to introduce
`moveToCallFrame` and `moveToCallFrame` operations around a partial
subset of operations that might change or refer to a variable in a
callframe. This subset includes command invocations that are known to
access caller variables, assignments to potentially-aliased variables,
some direct operations, and very little else. It fails to account for
all the operations, while simultaneously introducing unnecessary data
motion. It also forecloses on optimizations such as deferring writes
to non-local variables to loop exits.

This discussion is written at least partly for the benefit of its
author, to help with understanding what optimizations are safe and
profitable, and how to compute them. It will, however, hopefully aid
those who come after in understanding how the the decisions that were
made.

## Back to basics - the code generation strategy

One general strategy has been overwhelmingly successful in other areas
of quadcode manipulation. Rather than attempting to add operations
that handle the awkward cases when they are detected, it has been much
easier to generate code for the worst case always, and then optimize
it away. The code for variable accesses, for instance, is truly
horrific when initially generated:
  + test that a variable exists, and throw an error otherwise
  + test that the variable is not an array, and throw an error
    otherwise.
  + test that the value is of an admissible type for the operation
    that will use it, and throw an error otherwise.
  + downcast the value to an instance of the correct type.
  + if the value is used in an arithmetic operation, purify the value,
    that is, extract the machine-native representation.

Nevertheless, all of these tests become redundant if a second access
to the variable is dominated by the first. In that case, partial
redundancy elimination will eliminate all five of these steps and
simply use the pure value in the arithmetic operation. The partial
redundancy elimination is based largely on the value-based algorithms
developed in (LT Simpson's PhD
thesis)[https://www.clear.rice.edu/comp512/Lectures/Papers/SimpsonThesis.pdf].

We therefore assume here that we will take the brutally simple
approach of generating code that:
  + whenever a local variable (whether potentially aliased or not) is
    loaded, generate a `moveFromCallFrame` instruction transferring a
	Tcl value into an SSA value.
  + whenever a local variable (whether potientially aliased or not) is
    stored, generate a `moveToCallFrame` instruction transferring an
    SSA value into a Tcl value.
  + whenever an operation (an invocation, a direct operation, etc.)
    may potentially refer to a local variable or an alias
    thereof. make sure that it has the callframe as one of its inputs.
  + whenever an operation (an invocation, a direct operation, etc.)
    may potentially modify a local variable or an alias thereof,
	make sure that it has the callframe as both an input and an
    output.
  + upon procedure exit (normal or abnormal) make sure that any
    potentially aliased local variables are actually returned to the
    callframe. 

The last three items in the list ensure that we can track
antidependencies correctly; they become dependencies on the callframe
value. This, in turn, will require that we modify the `directSet`,
`directGet`, `directIncr`, etc. instructions, to include callframe
references. (This change will also address a set of issues marked with
**TODO** in `quadcode/translate.tcl` where it is assumed that the
`existStk`, `loadStk`, `storeStk`, etc. bytecode instructions refer
only to qualified names.)

Simpson mentions fairly briefly how memory load operations (he uses
the example of array accesses, but our `moveFromCallFrame`
fits the scheme) can also be eliminated by his techniques. The
treatment is considerly less well developed than that for simple
values. Moreover, he calls out that memory store operations are not
amenable to his technique owing to anti-dependencies (a STORE
operation may not be hoisted above a LOAD operation that might refer
to the same memory). His technique also does not contemplate downward
code motion, where a STORE operation that does not affect a loop's
operation might be moved to after the loop exit. To address these
deficiencies, it falls to us to develop a better theory of Tcl
variable accesses.

	if {[lsearch -exact -index 0 $bb upvar] >= 0} {
	    return 1
	}
    }
    return 0
}
 
# quadcode::transformer method cleanupMoveFromCallFrame --
#
#	Removes and replaces 'moveFromCallFrame' where it is known that
#	a target procedure does not write a callframe variable
#
# Results:
#	Returns 1 if any code was changed by this method, 0 otherwise

#
# Side effects:
#	The 'moveFromCallFrame' instruction is deleted, and its
#	result is replaced with the operand on the corresponding
#       'moveToCallFrame', if the operation is known not to write
#	the variable.
#
# FIXME: This procedure needs to be updated to deal with namespace variables.
#	 'moveFromCallFrame' may have been inserted after a quad has assigned
#	 to a potentially aliased variable, rather than after an 'invoke'

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

    my debug-callframe {
	puts "before cleanupMoveFromCallFrame:"
	my dump-bb
    }

    # $vw will hold a dictionary whose keys are quadcode instructions
    # and whose values are the lists of variables that the
    # corresponding instructions might store in the callframe.

    set vw {}

    # Walk through the quadcode looking for 'moveFromCallFrame'

    set changed 0

    for {set b 0} {$b < [llength $bbcontent]} {incr b} {
	set outpc -1
	for {set pc 0} {$pc < [llength [lindex $bbcontent $b]]} {incr pc} {
	    set q [lindex $bbcontent $b $pc]
	    if {[lindex $q 0] ne "moveFromCallFrame"} {
		lset bbcontent $b [incr outpc] $q
		continue
	    }
	    my debug-callframe {
		puts "Examine $b:$pc: $q"
	    }

	    # Found 'moveFromCallFrame'. Make sure the variable name is literal
	    lassign $q opcode tovar fromcf var
	    if {[lindex $var 0] ne "literal"} {
		my debug-callframe {
		    puts "    variable name not literal, can't optimize."
		}
		lset bbcontent $b [incr outpc] $q
		continue
	    }
	    set vname [lindex $var 1]

	    # Find the instruction that produced the callframe
	    set producer [my cfProducer [lindex $q 2]]
	    my debug-callframe {
		puts "    produced by: $producer"
	    }

	    # Find out what variables that the producer potentially changes
	    if {![dict exists $vw $producer]} {

		switch -exact [lindex $producer 0] {

		    "nsupvar" - "variable" - "upvar" {

			# The producer created a new link. The result variable
			# was 'written'

			dict set vw $producer \
			    [list 1 [list [lindex $producer 3]]]
		    }

		    callFrameNop {

			# If the producer is 'callframeNop', then the
			# potential change happened because a potentially
			# aliased variable was moved to the callframe.
			# The affected variables are its potential aliases

			if {[lindex $producer 3 0] eq "literal"} {
			    dict set vw $producer \
				[list 1 [my may-alias [lindex $producer 3]]]
			} else {
			    dict set vw $producer {0 {}}
			}
		    }

		    startCatch {

			# When catching an error, resynchronize to make sure
			# that errorCode and errorInfo are up to date.
			# Our ultraconservative alias analysis has no
			# real way of handling this, so simply spoil everything

			dict set vw $producer [list 1 [dict keys $links]]
		    }

		    "invoke" - "invokeExpanded" {

			# The variables altered by the 'invoke', plus
			# all aliases, are potentially changed.

			set aliases {}
			set atypes [lmap x [lrange $producer 4 end] {
			    typeOfOperand $types $x
			}]
			lassign [my variablesProducedBy $producer $atypes] \
			    known wlist
			if {$known} {
			    foreach v $wlist {
				dict set aliases $v {}
				foreach a [my may-alias $v] {
				    dict set aliases $a {}
				}
			    }
			    dict set vw $producer \
				[list 1 [dict keys $aliases]]
			} else {
			    dict set vw $producer {0 {}}
			}
		    }
		}
	    }

	    lassign [dict get $vw $producer] known vlist
	    my debug-callframe {
		if {$known} {
		    puts "    which writes variable(s) [list $vlist]"
		} else {
		    puts "    which potentially writes any variable"
		}
	    }

	    # Is this variable written by the operation?
	    if {!$known || $vname in $vlist} {
		my debug-callframe {
		    puts "    which might include $vname, so can't remove quad"
		}
		lset bbcontent $b [incr outpc] $q
		continue
	    }
	    my debug-callframe {
		puts "    which does not include $vname"
	    }

	    # This variable is known not to be written by the invocation.
	    # Trace its data source
	    set source [my cfPreviousDataSource $var $producer]
	    if {$source eq ""} {
		my debug-callframe {
		    puts "    $vname has an unknown source, can't optimize"
		}
		lset bbcontent $b [incr outpc] $q
		continue
	    }

	    my debug-callframe {
		puts "    replace uses of $tovar with $source, delete quad"
	    }
	    my removeUse $fromcf $b
	    my replaceUses $tovar $source
	    dict unset duchain $tovar
	    set changed 1

	}

	# Truncate the basic block to its new length

	set bb [lindex $bbcontent $b]
	if {[incr outpc] < [llength $bb]} {
	    lset bbcontent $b {}
	    set bb [lreplace $bb[set bb {}] $outpc end]
	    lset bbcontent $b $bb
	}
	set bb {}
    }

    my debug-callframe {
	puts "after cleanupMoveFromCallFrame:"
	my dump-bb
    }

    return $changed
}
 
# quadcode::transformer method cleanupMoveToCallFrame --
#
#	Removes and replaces 'moveToCallFrame' where it is known that
#	a target procedure does not access a callframe variable
#
# Results:
#	Returns 1 if any code was changed by this method, 0 otherwise
#
# Side effects:
#
#	If the operation is known neither to read nor to write a given
#	variable, then it is safe to remove that variable from the
#	'moveToCallFrame' instruction. It is also safe to do so if the
#	variable was just produced by a 'moveFromCallFrame' and the
#	input callframe of the 'moveFromCallFrame' and that of the
#	'moveToCallFrame' are the same frame. If these deletions cause
#	all the variables to be deleted from the instruction, then the
#	instruction itself is deleted, and references to the output
#	callframe are replaced by references to the input callframe.
#
#	TODO: Also, we can safely remove moveToCallFrame if the value that
#	we are moving was just moved from the same callframe under
#	the same name.
#
#	TODO: Can we track back further, by noting that some operations
#	      modify only specific callframe slots?

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

    my debug-callframe {
	puts "before cleanupMoveToCallFrame:"
	my dump-bb
    }

    # Walk through the quadcode looking for 'moveToCallFrame'

    set changed 0

    for {set b 0} {$b < [llength $bbcontent]} {incr b} {
	set outpc -1
	for {set pc 0} {$pc < [llength [lindex $bbcontent $b]]} {incr pc} {
	    set q [lindex $bbcontent $b $pc]
	    if {[lindex $q 0] ne "moveToCallFrame"} {
		lset bbcontent $b [incr outpc] $q
		continue
	    }
	    my debug-callframe {
		puts "Examine $b:$pc: $q"
	    }

	    set opdlist [lassign $q opcode cfout cfin]

	    # Find the instruction that consumes the callframe
	    set consumer [my cfConsumer $cfout]
	    my debug-callframe {
		puts "    consumed by: $consumer"
	    }

	    if {[lindex $consumer 0] in {"callFrameNop" "startCatch"}} {
		# The 'callFrameNop' is there because it needs explicitly to
		# consume the linked variable. Don't touch!
		my debug-callframe {
		    puts "    which is there to sync a linked variable,\
                              don't touch!"
		}
		lset bbcontent $b [incr outpc] $q
		continue
	    }

	    # Determine argument types of the consuming call, which always
	    # begins with some output and a callframe input
	    set atypes [lmap x [lrange $consumer 4 end] {
		typeOfOperand $types $x
	    }]

	    # Find out what variables that the consumer potentially reads.
	    # Because potentially changed variables may also be unchanged,
	    # list them also.

	    set known 1
	    set vdict {}
	    lassign [my variablesUsedBy $consumer $atypes] flag vlist
	    if {!$flag} {
		set known 0
	    } else {
		foreach v $vlist {
		    dict set vdict $v {}
		}
	    }
	    lassign [my variablesProducedBy $consumer $atypes] flag vlist
	    if {!$flag} {
		set known 0
	    } else {
		foreach v $vlist {
		    dict set vdict $v {}
		}
	    }

	    my debug-callframe {
		if {$known} {
		    puts "    which accesses variable(s)\
 		              [list [dict keys $vdict]]"
		} else {
		    puts "    which potentially accesses any variable"
		}
	    }

	    # Make sure that any variables that the callee is known to
	    # access, that are not otherwise listed in the callframe,
	    # get listed.
	    if {[lindex $bbcontent 0 0 0] eq "entry"} {
		set vars [lindex $bbcontent 0 0 2 1]
		dict for {v -} $vdict {
		    if {[lsearch -exact $vars $v] < 0} {
			my debug-callframe {
			    puts "    add pass-by-name variable $v to callframe"
			}
			lappend vars $v
			lset bbcontent 0 0 2 1 $vars
		    }
		}
	    }

	    set ok 1
	    set newq [list $opcode $cfout $cfin]
	    foreach {vnamelit var} $opdlist {
		lassign $vnamelit l vname
		if {$l ne "literal"} {
		    my debug-callframe {
			puts "    $vnamelit is not a literal, can't optimize"
		    }
		    set ok 0
		    break
		}
		if {[lindex $var 0] in {"temp" "var"}} {
		    lassign [my findDef $var] defb defpc defq
		    lassign $defq defopc defvar defcf defname
		} else {
		    set defopc "entry"
		}
		if {$defopc eq "moveFromCallFrame"
			&& $defvar eq $var
			&& $defcf eq $cfin
			&& [lindex $defname 1] eq $vname} {
		    my debug-callframe {
			puts "    $vname just came out of $cfin and\
                                  doesn't need to go back in."
		    }
		    my removeUse $var $b
		    set changed 1
		} elseif {$known && ![dict exists $vdict $vname]} {
		    my debug-callframe {
			puts "    consumer doesn't access $vname, so\
                                  don't put it in the callframe"
		    }
		    my removeUse $var $b
		    set changed 1
		} else {
		    my debug-callframe {
			puts "    consumer accesses $vname and it's not there"
		    }
		    lappend newq $vnamelit $var
		}
	    }

	    if {!$ok} {
		my debug-callframe {
		    puts "    optimization suppressed"
		}
		lset bbcontent $b [incr outpc] $q
	    } elseif {[llength $newq] eq 3} {
		my debug-callframe {
		    puts "    no variables to move, delete this quad\
                              and replace $cfout with $cfin"
		}
		my replaceUses $cfout $cfin
		my removeUse $cfin $b
		dict unset duchain $cfout
	    } else {
		my debug-callframe {
		    puts "    new quad: $newq"
		}
		lset bbcontent $b [incr outpc] $newq
	    }
	}

	# Truncate the basic block to its new length

	set bb [lindex $bbcontent $b]
	if {[incr outpc] < [llength $bb]} {
	    lset bbcontent $b {}
	    set bb [lreplace $bb[set bb {}] $outpc end]
	    lset bbcontent $b $bb
	}
	set bb {}
    }

    my debug-callframe {
	puts "after cleanupMoveToCallFrame:"
	my dump-bb
    }

    return $changed
}

 
# quadcode::transformer method cfConsumer --
#
#	Determines what 'invoke' or other operation consumes a callframe
#	that appears in a 'moveToCallframe' operation
#
# Parameters:

	if {[lsearch -exact -index 0 $bb upvar] >= 0} {
	    return 1
	}
    }
    return 0
}
 
# quadcode::transformer method cfRedundancy --
#
#	Removes various partial redundancies among callframe operations

#
# Results:

#	Returns 1 if anything changed, 0 otherwise.
#
# Side effects:


































































































































































































































































































































































































#	Removes many redundant operations.
 
# quadcode::transformer method cfConsumer --
#
#	Determines what 'invoke' or other operation consumes a callframe
#	that appears in a 'moveToCallframe' operation
#
# Parameters: