tclquadcode

Check-in [50af9aa069]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Start writing discussion of callframe management
Timelines: family | ancestors | descendants | both | kbk-refactor-callframe
Files: files | file ages | folders
SHA3-256:50af9aa069345e22c57c8d4313159d4a9906fa547df45e1c948f4d0c87c50279
User & Date: kbk 2019-02-16 21:40:16
Context
2019-02-16
21:43
Fix some Markdown typos check-in: a0fc4f2102 user: kbk tags: kbk-refactor-callframe
21:40
Start writing discussion of callframe management check-in: 50af9aa069 user: kbk tags: kbk-refactor-callframe
2019-01-29
13:19
Fix misorderered scalar check/copy to result check-in: 36e8177510 user: kbk tags: notworking, kbk-refactor-callframe
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to demos/perftest/tester.tcl.

2646
2647
2648
2649
2650
2651
2652


2653
2654
2655
2656
2657
2658
2659
2660
....
2694
2695
2696
2697
2698
2699
2700


2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
....
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
....
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
    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::*







>
>
|







 







>
>
|
|
|
|






|


|


|







 







|
|







 







|







2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
....
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
....
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
....
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
    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::*

Added doc/20190216callframe/callframe.md.

























































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# 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.

Changes to quadcode/callframe.tcl.

30
31
32
33
34
35
36
37
38
39
40
41
42
43

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431

432
433
434
435
436
437
438
	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:







|

|
<


<
>


<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
>







30
31
32
33
34
35
36
37
38
39

40
41

42
43
44


































































































































































































































































































































































































45
46
47
48
49
50
51
52
	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: