tclquadcode

Check-in [32281c70dd]
Login

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

Overview
Comment:Added logic to free values that will no longer be used. Results in a new quadcode instruction, 'free', whose input parameter is the value to be dismissed.
Timelines: family | ancestors | descendants | both | kbk-free-values
Files: files | file ages | folders
SHA1:32281c70ddfb095a956f9cc84166524fd6acfada
User & Date: kbk 2015-03-08 02:01:34
Context
2015-03-09
01:53
Make retrograde type inference hack work again. check-in: dc00e24c34 user: kbk tags: kbk-free-values
2015-03-08
16:52
Merge the code to generate the lifetimes from the model; [6d228ecd45] crashes due to type problems... check-in: 3b984c101d user: dkf tags: llvm-integration-memory-part2
02:01
Added logic to free values that will no longer be used. Results in a new quadcode instruction, 'free', whose input parameter is the value to be dismissed. check-in: 32281c70dd user: kbk tags: kbk-free-values
2015-02-01
15:38
Add support for shifts and incrScalar1 check-in: a18c116f4c user: dkf tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to codegen.compile.tcl.

39
40
41
42
43
44
45





46
47
48
49
50
51
52
53
54

55
56
57
58
59
60
61
	quads-list-dataflows $quads $vars
	db reachdef $quads
	# Enumerate the data sources for all phi functions
	set phis [db ssa2 $quads]
	# Rewrite the three-address code into SSA form
	set quads [db ssa3 $quads [dict keys $vars] $phis]






	db destroy

	# Stratify the variable dependencies
	set vdep [vardepends $quads]
	set vtypes {}
	bdd::datalog::scc x $vdep {
	    if {[llength $x] > 1} {
		analyzeDependencyLoop $quads $vdep $x vtypes
	    } else {

		assignTypeToVariable $quads [lindex $x 0] vtypes
	    }
	}

	# Determine the types of arguments
	assignParameterTypes vtypes $quads








>
>
>
>
>









>







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
	quads-list-dataflows $quads $vars
	db reachdef $quads
	# Enumerate the data sources for all phi functions
	set phis [db ssa2 $quads]
	# Rewrite the three-address code into SSA form
	set quads [db ssa3 $quads [dict keys $vars] $phis]

	# Add instructions to clean up memory
	set vars [initDB $quads]
	quads-list-dataflows $quads $vars
	set quads [db freeValues $quads [dict keys $vars]]

	db destroy

	# Stratify the variable dependencies
	set vdep [vardepends $quads]
	set vtypes {}
	bdd::datalog::scc x $vdep {
	    if {[llength $x] > 1} {
		analyzeDependencyLoop $quads $vdep $x vtypes
	    } else {
		puts "assign type to [lindex $x 0]"
		assignTypeToVariable $quads [lindex $x 0] vtypes
	    }
	}

	# Determine the types of arguments
	assignParameterTypes vtypes $quads

Changes to demo.tcl.

192
193
194
195
196
197
198




199
200
201
202
203
204
205
# puts "After converting to SSA form:"
# set i 0
# foreach q $quads {
#     puts "$i: $q"
#     incr i
# }





# Stratify the dependencies of one SSA variable on another. These
# strata are strongly connected components of the dependency graph,
# and are the natural places to attempt structural induction.

puts "vardepends: [time {
    set vdep [vardepends $quads]
}]"







>
>
>
>







192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
# puts "After converting to SSA form:"
# set i 0
# foreach q $quads {
#     puts "$i: $q"
#     incr i
# }

set vars [initDB $quads]
quads-list-dataflows $quads $vars
set quads [db freeValues $quads [dict keys $vars]]

# Stratify the dependencies of one SSA variable on another. These
# strata are strongly connected components of the dependency graph,
# and are the natural places to attempt structural induction.

puts "vardepends: [time {
    set vdep [vardepends $quads]
}]"

Changes to quadcode.tcl.

133
134
135
136
137
138
139

140
141
142
143
144
145
146
...
253
254
255
256
257
258
259

260
261
262
263
264
265
266
...
685
686
687
688
689
690
691

692
693
694
695
696
697
698
699
700
701
702
703















704
705
706
707
708
709
710
...
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
...
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
...
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
....
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
....
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
....
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
....
1572
1573
1574
1575
1576
1577
1578































































































































































































1579
1580
1581
1582
1583
1584
1585
....
2307
2308
2309
2310
2311
2312
2313

2314
2315
2316
2317
2318
2319

2320
2321
2322
2323
2324
2325
2326
....
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407

2408
2409
2410















2411
2412
2413
2414
2415
2416
2417
		bytecode-stack-state-worker bytecode \
		    $target $head $depth
		# fallthrough to do the 'branch not taken'
	    }
	    add -
	    div -
	    eq -

	    gt -
	    le -
	    listIndexImm -
	    lt -
	    mod -
	    mult -
	    ne -
................................................................................
	}

	# Translate the current bytecode
	switch -exact -- [lindex $insn 0] {
	    add -
	    div -
	    eq -

	    gt -
	    le -
	    lt -
	    mod -
	    lshift -
	    rshift -
	    mult -
................................................................................

    $db relation dom st st2;	# st dominates st2
    $db relation sdom st st2;	# st dominates st2 strictly
    $db relation frontier st st2;
    ;				# st2 is in st's dominance frontier

    $db relation liveat v st;	# v is live on entry to st

    $db relation needphi v st2
    ;				# a phi function is needed at st2 for
    ;				# variable v
    $db relation defreaches isphi v st st2
    ;				# a phi function or unique assignment
    ;                           # for v before st reaches st2
    $db relation valreaches v st st2
    ;				# the value of v on entry to st reaches st2
    $db relation reachesNonUniquely v st st2
    ;				# The assignment at st of v has another
    ;				# reaching definition at st2
















    $db relation hasCantBeIntOperand st;
    ;				# st has a non-integer operand on at least one
    ;				# code path
    $db relation hasCantBeDoubleOperand st;
    ;				# st has a non-real operand on at least one
    ;				# code path
}
................................................................................
#
# Side effects:
#	Values are loaded into the given relations.

proc quads-list-dataflows {quads vars} {
    global verbose

    # There is an artificial entry block whose index is two slots
    # beyond the end of the input list, and an artificial exit block
    # at one slot beyond the end of the input list. The entry writes
    # all variables (this rule detects uninitialized values)

    set fakeEntry [expr {[llength $quads] + 1}]
    loadSeq $fakeEntry 0
    dict for {vname vnum} $vars {
	loadWrites $fakeEntry $vnum
    }

    # Walk through the instructions, and record their effects on dataflow.

    set i 0
    foreach insn $quads {
	switch -exact -- [lindex $insn 1 0] {
	    temp -
	    var {
................................................................................
	define-db-methods $vbits $stbits
    } else {
	db clearAll
    }
    return $vars
}


proc define-db-methods {vbits stbits} {
    
    #########################################################################
    #
    # Now that the database schema is loaded, it is possible to compile
    # Datalog code against it. The compiler requires the relation
    # definitions and the bit assignments of the domains, so cannot be run
................................................................................
    #	None
    #
    # Side effects:
    #	The reaching definitions are added to the database in the
    #	'flowsPast' and 'reaches' relations.
    
    db datalogMethod reachdef {quads} {
	set fakeEntry [expr {[llength $quads] + 1}]
    } {
	% The flowspast relation tracks code paths that are transparent to a var
	flowsPast(_, st, st2) :- seq(st, st2).
	flowsPast(v, st3, st2) :- flowsPast(v, st3, st),
                                  !writes(st, v),
                                  flowsPast(v, st, st2).

................................................................................
    #	A.
    #
    # In this case, the operation at A can be replaced with v2 :- ...,
    # and all the copies B can be elided
    
    db datalogMethod revprop {quads vnames} {
	set dead {}
	set fakeEntry [expr {[llength $quads] + 1}]
    } {
	
	% An assignment of variable v at statement st can be replaced with
	% variable v2 to eliminate a copy of v to v2 at statement st2 if
	% there's no reason not to do so.
	
	revprop(v, v2, st, st2) :- reaches(v, st, st2),
................................................................................
	cantRevprop2(_, v2, _, st2) :- !writes(st2, v2).
	cantRevprop2(v, _, st, st2) :- reaches(v, st3, st2), st3 != st.

	% Reverse propagation can't eliminate anything from the 
	% function prelude. (Otherwise, it will try to rename literals
	% to the variables into which they're copied.)

	cantRevprop(_, _, $fakeEntry).
	
	revprop(v, v2, st, st2)?

    } d {
	dict with d {
	    lset quads $st 1 [lindex $vnames $v2]
	    dict set dead $st2 {}
	}
................................................................................
    #	None. Results appear in the databse
    #
    # Side effects:
    #   The relations, 'reachable', 'reachableWithout' and 'dom'
    #   are stored back into the database.

    db datalogMethod dominators {quads} {
	set fakeEntry [expr {[llength $quads] + 1}]
    } {
	% What statements are reachable from the entry point?
	reachable($fakeEntry).
	reachable(st2) :- reachable(st), seq(st, st2).
	
	% What statements st are reachable without visiting statement st2?
	reachableWithout($fakeEntry, _).
	reachableWithout(st2, st3) :- reachableWithout(st, st3),
	                              seq(st, st2),
                                      st2 != st3.

	% The entry dominates everything
	dom($fakeEntry, st) :- reachable(st).

	% Every reachable statement dominates itself.
	dom(st, st2) :- reachable(st), st = st2.
	
	% Statement st dominates st2 if there is no path from the entry to
	% st2 that does not visit st.
	dom(st, st2) :- reachable(st2), !reachableWithout(st2, st).
................................................................................
		}
	    }
	    lset quads $pc $newquad
	    incr pc
	}
	return $quads
    }
































































































































































































    # types1 --
    #
    #	Attempts to assign data type to program variables in SSA form.
    #
    # Parameters:
    #	vnames - List of variable names 
................................................................................
	set xx [expr { $xx + 1.0 }]
	set ser [expr { $ser + $cof / $xx }]
	set cof -5.36382e-6
	set xx [expr { $xx + 1.0 }]
	set ser [expr { $ser + $cof / $xx }]
	return [expr { $tmp + log( 2.50662827465 * $ser ) }]
    }

    #
    #########################################################################
    
    # Create bytecode for the example procedure, and translate to three-address
    # code.
    set procname math::ln_Gamma

} else {
    package require math
    auto_load ::math::ln_Gamma
    set procname math::ln_Gamma
}
set bytecode [::tcl::unsupported::getbytecode proc $procname]

................................................................................
    set i 0
    foreach q $quads {
	puts "$i: $q"
	incr i
    }
}

    set vars [initDB $quads]
    quads-list-dataflows $quads $vars
    db reachdef $quads

# Enumerate the data sources for all phi functions
    set phis [db ssa2 $quads]

# Rewrite the three-address code into SSA form
    set quads [db ssa3 $quads [dict keys $vars] $phis]


if {$verbose} {
    puts "After converting to SSA form:"
    set i 0















    foreach q $quads {
	puts "$i: $q"
	incr i
    }
}

# Experimental datalog-based type analysis







>







 







>







 







>












>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
<
<
<
<
<







 







<







 







<







 







<







 







<
<







 







|


|



|





|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>





|
>







 







|
|
|


|


|

>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
...
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
...
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
...
744
745
746
747
748
749
750











751
752
753
754
755
756
757
...
905
906
907
908
909
910
911

912
913
914
915
916
917
918
...
979
980
981
982
983
984
985

986
987
988
989
990
991
992
....
1182
1183
1184
1185
1186
1187
1188

1189
1190
1191
1192
1193
1194
1195
....
1213
1214
1215
1216
1217
1218
1219


1220
1221
1222
1223
1224
1225
1226
....
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
....
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
....
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
....
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
		bytecode-stack-state-worker bytecode \
		    $target $head $depth
		# fallthrough to do the 'branch not taken'
	    }
	    add -
	    div -
	    eq -
	    ge -
	    gt -
	    le -
	    listIndexImm -
	    lt -
	    mod -
	    mult -
	    ne -
................................................................................
	}

	# Translate the current bytecode
	switch -exact -- [lindex $insn 0] {
	    add -
	    div -
	    eq -
	    ge -
	    gt -
	    le -
	    lt -
	    mod -
	    lshift -
	    rshift -
	    mult -
................................................................................

    $db relation dom st st2;	# st dominates st2
    $db relation sdom st st2;	# st dominates st2 strictly
    $db relation frontier st st2;
    ;				# st2 is in st's dominance frontier

    $db relation liveat v st;	# v is live on entry to st

    $db relation needphi v st2
    ;				# a phi function is needed at st2 for
    ;				# variable v
    $db relation defreaches isphi v st st2
    ;				# a phi function or unique assignment
    ;                           # for v before st reaches st2
    $db relation valreaches v st st2
    ;				# the value of v on entry to st reaches st2
    $db relation reachesNonUniquely v st st2
    ;				# The assignment at st of v has another
    ;				# reaching definition at st2

    $db relation killsLocal st v
    ;				# The statement st kills visibility of v
    ;				# either by writing v or being a phi that reads
    ;				# v.
    $db relation nonKillingPath v st st2
    ;				# Visibility of value v is preserved (not killed
    ;				# on some path from st to st2.
    $db relation usedOnEntry v st
    ;				# The value v is used on entry to st
    $db relation visibleOnExit v st
    ;				# The value v is visible on exit from st
    $db relation needsFree v st st2
    ;				# The variable v needs to be freed
    ;				# before passing control from st to st2
    
    $db relation hasCantBeIntOperand st;
    ;				# st has a non-integer operand on at least one
    ;				# code path
    $db relation hasCantBeDoubleOperand st;
    ;				# st has a non-real operand on at least one
    ;				# code path
}
................................................................................
#
# Side effects:
#	Values are loaded into the given relations.

proc quads-list-dataflows {quads vars} {
    global verbose












    # Walk through the instructions, and record their effects on dataflow.

    set i 0
    foreach insn $quads {
	switch -exact -- [lindex $insn 1 0] {
	    temp -
	    var {
................................................................................
	define-db-methods $vbits $stbits
    } else {
	db clearAll
    }
    return $vars
}


proc define-db-methods {vbits stbits} {
    
    #########################################################################
    #
    # Now that the database schema is loaded, it is possible to compile
    # Datalog code against it. The compiler requires the relation
    # definitions and the bit assignments of the domains, so cannot be run
................................................................................
    #	None
    #
    # Side effects:
    #	The reaching definitions are added to the database in the
    #	'flowsPast' and 'reaches' relations.
    
    db datalogMethod reachdef {quads} {

    } {
	% The flowspast relation tracks code paths that are transparent to a var
	flowsPast(_, st, st2) :- seq(st, st2).
	flowsPast(v, st3, st2) :- flowsPast(v, st3, st),
                                  !writes(st, v),
                                  flowsPast(v, st, st2).

................................................................................
    #	A.
    #
    # In this case, the operation at A can be replaced with v2 :- ...,
    # and all the copies B can be elided
    
    db datalogMethod revprop {quads vnames} {
	set dead {}

    } {
	
	% An assignment of variable v at statement st can be replaced with
	% variable v2 to eliminate a copy of v to v2 at statement st2 if
	% there's no reason not to do so.
	
	revprop(v, v2, st, st2) :- reaches(v, st, st2),
................................................................................
	cantRevprop2(_, v2, _, st2) :- !writes(st2, v2).
	cantRevprop2(v, _, st, st2) :- reaches(v, st3, st2), st3 != st.

	% Reverse propagation can't eliminate anything from the 
	% function prelude. (Otherwise, it will try to rename literals
	% to the variables into which they're copied.)



	revprop(v, v2, st, st2)?

    } d {
	dict with d {
	    lset quads $st 1 [lindex $vnames $v2]
	    dict set dead $st2 {}
	}
................................................................................
    #	None. Results appear in the databse
    #
    # Side effects:
    #   The relations, 'reachable', 'reachableWithout' and 'dom'
    #   are stored back into the database.

    db datalogMethod dominators {quads} {
	set entryBlock 0
    } {
	% What statements are reachable from the entry point?
	reachable($entryBlock).
	reachable(st2) :- reachable(st), seq(st, st2).
	
	% What statements st are reachable without visiting statement st2?
	reachableWithout($entryBlock, _).
	reachableWithout(st2, st3) :- reachableWithout(st, st3),
	                              seq(st, st2),
                                      st2 != st3.

	% The entry dominates everything
	dom($entryBlock, st) :- reachable(st).

	% Every reachable statement dominates itself.
	dom(st, st2) :- reachable(st), st = st2.
	
	% Statement st dominates st2 if there is no path from the entry to
	% st2 that does not visit st.
	dom(st, st2) :- reachable(st2), !reachableWithout(st2, st).
................................................................................
		}
	    }
	    lset quads $pc $newquad
	    incr pc
	}
	return $quads
    }

    # freeValues --
    #
    #	Determines the points in SSA code at which a value must be freed
    #
    # Parameters:
    #	vnames - List of variable names
    #
    # Results:
    #	Returns a list of triples: {st1 st2 v} where the value v must be
    #	freed when passing control from st1 to st2
    #
    # Side effects:
    #	Leaves liveness information in the database

    db datalogMethod freeValues {quads vnames} {
	set actions {}
    } {

	% A value needs its refcount decremented between st and st2 if
	% st writes the value directly and st2 does not use it.
	needsFree(v, st, st2) :-
		writes(st, v), seq(st, st2), !usedOnEntry(v, st2).

	% A value needs its refcount decremented between st and st2
	% if st uses v, st is not a phi, st2 follows st, and st2 does not
	% use v.
	needsFree(v, st, st2) :-
		usedOnEntry(v, st), !isPhi(st), seq(st, st2), 
		!isLiteral(v), visibleOnExit(v, st), !usedOnEntry(v, st2).

	% A value is visible on exit from a statement if the statement writes
	% the value.
	visibleOnExit(v, st) :- writes(st, v).

	% A value is visible on exit from a statement if a path from a point
	% that writes the value reaches the exit of the statement.
	visibleOnExit(v, st3) :- 
		writes(st, v), 
		seq(st, st2),
		nonKillingPath(v, st2, st3).

	% A value is used on entry to a statement if it is directly
	% read in that statement.
	usedOnEntry(v, st) :- reads(st, v).

	% A value is used on entry to a statement if it is used by another
	% statement st3, and there is a code path from st to st3 that
	% preserves the value
	usedOnEntry(v, st) :-
		nonKillingPath(v, st, st2),
	        seq(st2, st3),
		reads(st3, v).

	% A value is preserved from the entry of st to the exit of
	% st if it's not killed locally
	nonKillingPath(v, st, st2) :- st=st2, !killsLocal(st, v).

	% A value is preserved from the entry of st to the exit of
	% st2 if it can be traced through a series of statements
	% that preserve it
	nonKillingPath(v, st, st2) :- 
		nonKillingPath(v, st, st3), 
		seq(st3, st4),
		nonKillingPath(v, st4, st2).

	% A value is killed locally by a statement if the statement
	% writes the value.
	killsLocal(st, v) :- writes(st, v).

	% A value is killed locally by a statement if the statement
	% is a phi that interacts with it.
	killsLocal(st, v) :- isPhi(st), reads(st, v).

        needsFree(v, st, st2)?
    } d {
	dict with d {
	    dict set actions $st $st2 [lindex $vnames $v] {}
	}
    } {

	# Now we know where memory has to be freed in the program.
	# [dict get $actions $pc $pc2] is a dictionary whose keys are
	# the names of variables that must be freed as control passes
	# from $pc to $pc2.
	#
	# The twist with this rewriting is that if control passes from
	# $pc to $pc2 by branching, we'll need to put the 'free's out of
	# line, alter the branch to jump to them and follow the 'free's
	# with a branch to the original branch target.

	set quads2 {};		# Output instruction sequence
	set fixup {};		# Dictionary whose keys are input instruction
	;			# indices and whose values are lists of
	;			# pairs: the instruction that has the given
	;			# index as a jump target and the operand
	;			# index of the target.
	set addr2 {};		# Dictionary whose keys are input instruction
	;			# locations and whose vlaues are the
	;			# indices of the corresponding output
	;			# instructions
	set returnLoc {};	# [dict get $returnLoc $from $to $j
	;			# is the place to return-jump to when
	;			# inserting code on the arc from $from to
	;			# $to; $j is the index in the instruction
	;			# where the pc has to be fixed

	set i 0
	foreach q $quads {

	    # Record the output instruction index for this input instruction
	    
	    dict set addr2 $i [llength $quads2]
	    
	    # Fix up any forward jumps that target this input instruction
	    
	    if {[dict exists $fixup $i]} {
		foreach f [dict get $fixup $i] {
		    lset quads2 {*}$f 1 [llength $quads2]
		} 
	    }

	    # Rewrite the current instruction, replacing PC references
	    # with the corresponding addresses in the output instruction
	    # stream. Leave forward jumps for any flow graph arcs that
	    # require out-of-line code to be added

	    for {set j 1} {$j < [llength $q]} {incr j} {
		switch -exact -- [lindex $q $j 0] {
		    pc {
			set target [lindex $q $j 1]
			if {[lindex $q 0] ne {phi}
			    && [dict exists $actions $i $target]
			    && $target != $i+1} {
			    dict set returnLoc $i $target $j [llength $quads2]
			    lset q $j 1 ?
			} elseif {[dict exists $addr2 $target]} {
			    lset q $j 1 [dict get $addr2 $target]
			} else {
			    lset q $j 1 ?
			    dict lappend fixup $target [list [llength $quads2] $j]
			}
		    }
		}
	    }

	    lappend quads2 $q

	    # Insert 'free' instructions on the fallthrough path, if any

	    if {[dict exists $actions $i [expr {$i+1}]]} {
		dict for {v -} [dict get $actions $i [expr {$i+1}]] {
		    lappend quads2 [list free {} $v]
		}
		dict unset actions $i [expr {$i+1}]
	    }
	    incr i
	}

	# Now we do the out-of-line actions

	dict for {from l} $actions {
	    dict for {to vs} $l {
		dict for {j newFrom} [dict get $returnLoc $from $to] {
		    lset quads2 $newFrom $j 1 [llength $quads2]
		}
		dict for {v -} $vs {
		    lappend quads2 [list free {} $v]
		}
		lappend quads2 [list jump [list pc [dict get $addr2 $to]]]
	    }
	}

	# If code is using 'assignTypeToVariable', then it will need the
	# PC's of variable origins patched. That also has to be done here

	set i 0
	foreach q $quads2 {
	    set j 0
	    foreach field $q {
		if {[lindex $field 0] in {var literal temp}
		    && [llength $field] >= 3
		    && [dict exists $addr2 [set addr [lindex $field 2]]]} {
		    lset quads2 $i $j 2 [dict get $addr2 $addr]
		}
		incr j
	    }
	    incr i
	}
	return $quads2
    }

    # types1 --
    #
    #	Attempts to assign data type to program variables in SSA form.
    #
    # Parameters:
    #	vnames - List of variable names 
................................................................................
	set xx [expr { $xx + 1.0 }]
	set ser [expr { $ser + $cof / $xx }]
	set cof -5.36382e-6
	set xx [expr { $xx + 1.0 }]
	set ser [expr { $ser + $cof / $xx }]
	return [expr { $tmp + log( 2.50662827465 * $ser ) }]
    }

    #
    #########################################################################
    
    # Create bytecode for the example procedure, and translate to three-address
    # code.
    set procname cos

} else {
    package require math
    auto_load ::math::ln_Gamma
    set procname math::ln_Gamma
}
set bytecode [::tcl::unsupported::getbytecode proc $procname]

................................................................................
    set i 0
    foreach q $quads {
	puts "$i: $q"
	incr i
    }
}

set vars [initDB $quads]
quads-list-dataflows $quads $vars
db reachdef $quads

# Enumerate the data sources for all phi functions
set phis [db ssa2 $quads]

# Rewrite the three-address code into SSA form
set quads [db ssa3 $quads [dict keys $vars] $phis]

set verbose 0
if {$verbose} {
    puts "After converting to SSA form:"
    set i 0
    foreach q $quads {
	puts "$i: $q"
	incr i
    }
}

# Try to determine refcount information

set vars [initDB $quads]
quads-list-dataflows $quads $vars
set quads [db freeValues $quads [dict keys $vars]]

if {$verbose} {
    puts "After memory management:"
    set i 0
    foreach q $quads {
	puts "$i: $q"
	incr i
    }
}

# Experimental datalog-based type analysis