Check-in [71a4e793a1]
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to [email protected]
or submit via the online form by Sep 9.

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

Overview
Comment:Add bitwise Boolean operations to constant folding. Modify partial redundancy elimination to use bit vectors for dataflow calculations and debug the dataflow equations.
Timelines: family | ancestors | descendants | both | kbk-pre
Files: files | file ages | folders
SHA3-256: 71a4e793a15de0a4465095a50e2546a12ee1ac00ae4dbebf76d638c5fcf03912
User & Date: kbk 2018-11-11 22:34:10
Context
2018-11-12
01:38
Change signatures in preparation for code rewriting: include enough information in signatures so that INSERT can reconstruct an instruction check-in: c098311242 user: kbk tags: kbk-pre
2018-11-11
22:34
Add bitwise Boolean operations to constant folding. Modify partial redundancy elimination to use bit vectors for dataflow calculations and debug the dataflow equations. check-in: 71a4e793a1 user: kbk tags: kbk-pre
2018-11-10
22:17
Use the lexical-name algorithm for 'altered' for now. May change to value-driven later. check-in: 592020ed7a user: kbk tags: notworking, kbk-pre
Changes

Changes to quadcode/constfold.tcl.

75
76
77
78
79
80
81












































82
83
84
85
86
87
88
			lset bbcontent $b [incr newpc] $q
		    }

		    "add" {
			lassign $argl x y
			set res [list literal [expr {$x + $y}]]
			my debug-constfold {












































			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }







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







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
			lset bbcontent $b [incr newpc] $q
		    }

		    "add" {
			lassign $argl x y
			set res [list literal [expr {$x + $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitand" {
			lassign $argl x y
			set res [list literal [expr {$x & $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitnot" {
			lassign $argl x
			set res [list literal [expr {~$x}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitor" {
			lassign $argl x y
			set res [list literal [expr {$x | $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

		    "bitxor" {
			lassign $argl x y
			set res [list literal [expr {$x ^ $y}]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace [lindex $q 1] with $res"
			}
			my replaceUses [lindex $q 1] $res
			set changed 1
		    }

Changes to quadcode/pre.tcl.

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
...
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
...
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
...
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
...
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
439
440
441
442
443
444
445
446
...
450
451
452
453
454
455
456



457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482

483
484
485
486
487
488
489
490
491
492
493
494

495
496
497
498
499
500
501
502
503

504
505
506
507
508
509
510
511
512
513
514
515
516
517
518

519
520
521
522
523
524
525
...
530
531
532
533
534
535
536
537
538







539
540
541
542
543
544
545






546
547

548
549
550
551
552
553
554
555
556
557
558

559
560
561
562
563
564
565
566
567
568
569
570
571
572
573


574
575
576




577
578
579
580
581

582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648


649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
...
713
714
715
716
717
718
719


720
721
722
723
724
725
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
751
752
753
754
755
756
757
758

759
760
761
762
763
764
765
766
767

768
769
770
771
772
773
774
775
776

777
778
779
780
781
782
783
784
785
786
787
788
789
790

791
792
793
794
795
796
797
...
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829

830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881

882
883
884
885
886
887
888
...
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923


924
925
926
927
928
929
930
931
932
933
934
935



936



937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
...
955
956
957
958
959
960
961



962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017

1018
1019
1020
1021
1022
1023


1024
1025
1026

1027
1028
1029
1030
1031
1032
1033
....
1045
1046
1047
1048
1049
1050
1051


































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

    my debug-pre {
	puts "Before partial redundancy elimination:"
	my dump-bb
    }


    # Compute Global Value Numbering for the values present in the quadcode

    set VN [my pre_gvn]
    my debug-pre {
	puts "Value numbering:"
	dict for {k v} $VN {
	    if {$v ne $k} {

		puts "   found congruence $k -> $v"
	    }
	}

    }

    # Compute the 'defined' predicate for the basic blocks

    set defined [my pre_defined $VN]
    my debug-pre {
	puts "Defined expressions:"
	set b -1
	foreach vset $defined {
	    puts "[incr b]: [dict keys $vset]"
	}
    }

    # Find sets of available expressions

    lassign [my pre_avail $defined] AVIN AVOUT
    my debug-pre {
	puts "Available expressions"
	set b -1
	foreach inset $AVIN outset $AVOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    AVIN =  $inset"
	    puts "    AVOUT = $outset"
	}
    }


    # Find sets of expressions altered within each block

    set altered [my pre_altered $VN]
    my debug-pre {
	puts "Altered expressions"
	set b -1
	foreach al $altered {
	    incr b
	    puts "  Block #$b: [dict keys $al]"
	}
    }

    # Find expressions that are locally anticipable at entry to blocks

    set antloc [my pre_antloc $defined $altered]
    my debug-pre {
	puts "Locally anticipable expressions"
	set b -1
	foreach an $antloc {
	    incr b
	    puts "  Block #$b: [dict keys $an]"
	}
    }

    # Compute globally anticipable expressions

    lassign [my pre_ant_global $altered $antloc] ANTIN ANTOUT
    my debug-pre {
	puts "Globally anticipable expressions"
	set b -1
	foreach inset $ANTIN outset $ANTOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    ANTIN =  $inset"
	    puts "    ANTOUT = $outset"
	}
    }

    # Compute earliest points where an expression may be moved.
    # These are edges on the call graph where the expression may
    # appear. (Since we have no critical edges, the expression
    # can always be inserted at either the tail of the predecessor
    # block or the head of the successor).

    set EARLIEST [my pre_earliest $AVOUT $altered $ANTIN $ANTOUT]
    my debug-pre {
	puts "Earliest insertion points:"
	dict for {edge vars} $EARLIEST {
	    if {[dict size $vars] > 0} {
		lassign $edge from to
		puts "    $from->$to: [dict keys $vars]"
	    }
	}
    }

    # Compute LATER, which is an indication that an expression
    # may be moved later than an edge (LATER) or the start of
    # a block (LATERIN)
................................................................................

    lassign [my pre_later $antloc $EARLIEST] LATERIN LATER

    # Report on insertion and deletion points

    dict for {edge exprs} $LATER {
	lassign $edge from to
	dict for {e -} $exprs {


	    if {![dict exists [lindex $LATERIN $to] $e]} {
		puts "Insert $e on the flowgraph edge from $from to $to"
	    }



	}
    }

    set b -1
    foreach exprs $antloc laters $LATERIN {
	incr b
	if {$b == 0} continue
	puts "Block $b: ANTLOC = [dict keys $exprs]"
	puts "Block $b: LATERIN = [dict keys $laters]"
	dict for {e -} $exprs {
	    if {![dict exists $laters $e]} {
		puts "Remove $e from block $b"
	    }

	}
    }


    return 0

}
 
# quadcode::transformer method pre_gvn --
#
#	Calculates a Global Value Numbering for values in a quadcode
#	sequence.
#
# Results:


#	Returns a dictionary whose keys are the names of program variables
#	and whose values are the names of program variables that represent
#	the equivalence classes.











#
# This procedure implements the 'RPO' algorithm presented in
# Figure 4.3 of [Simpson] (see references in the file header.
# While perhaps not as fast, it is significantly simpler than
# the 'SCC' algorithm and yields the same results.
#
# This procedure assumes that 'deadbb' has been run before it,
# so that it will find basic blocks already in depth-first order.

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



    # Initially all value numbers are unknown

    set VN {}

    # Iterate to convergence

    while {1} {
	set changed 0
	set VNforSig {}



	# Iterate through all basic blocks in depth-first order
	set b -1
	foreach bb $bbcontent {
	    incr b

	    # Walk through the instructions of each block
................................................................................

		# Ignore instructions that do not produce a value
		set result [lindex $q 1]
		if {[lindex $result 0] ni {"temp" "var"}} {
		    continue
		}

		# TODO - Detect meaningless phi

		# Make a signature for the expression computed
		# by the current instruction
		set sig [my pre_gvn_sig $VN $q]

		# If there is already a value number for the signature, use
		# it. Otherwise, make the current result the exemplar of the
		# congruence class. Set 'changed' if the the value number
		# changes from the previous round.
		if {![dict exists $VNforSig $sig]} {

		    dict set VNforSig $sig $result



		}

		set v [dict get $VNforSig $sig]
		if {![dict exists $VN $result]
		    || [dict get $VN $result] ne $v} {
		    set changed 1
		    my debug-pre {
			puts "Value number for $result is now $v"
		    }
		    dict set VN $result $v
		}
	    }
	}
	
	if {!$changed} break
    }
    return $VN


}
 
# quadcode::transformer method pre_gvn_sig --
#
#	Develops a signature for a quadcode instruction's result
#	in Global Value Numbering
................................................................................
	    bb - pc {
		lappend signature {}
	    }
	    temp - var {
		if {![dict exists $VN $a]} {
		    lappend signature TOP
		} else {
		    lappend signature [dict get $VN $a]
		}
	    }
	    default {
		lappend signature $a
	    }
	} 
    }
................................................................................
 
# quadcode::transformer method pre_defined --
#
#	Computes the local predicate, 'defined', for use in the
#	dataflow equations.
#
# Results:
#	Returns a list of dictionaries. The indices of the list are basic
#	block numbers, and each key in a dictionary is the exemplar of a
#	value defined in the basic block. The values in the dictionary are
#	immaterial.

oo::define quadcode::transformer method pre_defined {VN} {

    set DEFINED {}

    # Walk through the basic blocks

    set b -1
    foreach bb $bbcontent {
	incr b

	set defined {}

	# Walk through the individual instructions
	
	set pc -1
	foreach q $bb {
	    incr pc

	    lassign $q opcode result

	    # If an instruction defines a value, add the value to the set
	    
	    if {$result ne {} && [dict exists $VN $result]} {
		dict set defined [dict get $VN $result] {}
	    }
	}

	# Add the set to the list
	
	lappend DEFINED $defined
    }
................................................................................
 
# quadcode::transformer method pre_avail --
#
#	Calculates the available expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	defined - List of dictionaries. The list is indexed by basic
#	          block number. The keys in the dictionaries are the
#		  exemplars of values set in the block. The values are
#	          immaterial.
#
# Results:
#	Returns an ordered pair {AVIN AVOUT}.
#
#	AVIN is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values available on input
#	to each block.
#

#	AVOUT is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values available on
#	output from the block.
#
# This procedure solves the data flow equations given in Figure 5.6
# on page 63 of [Simpson].

oo::define quadcode::transformer method pre_avail {defined} {

    my debug-pre {
	puts "Calculate available expressions:"
    }



    set AVIN [lrepeat [llength $defined] {}]
    set AVOUT $defined


    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $defined] 0]
    set worklist [::quadcode::numheap new]
    for {set i 1} {$i < [llength $defined]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate AVIN for the block as the intersection of AVOUT
	# of all predecessors




	set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	set avin [lindex $AVOUT $firstpred]
	foreach p $otherpreds {
	    set othervs [lindex $AVOUT $p]
	    dict for {v -} $avin {
		if {![dict exists $othervs $v]} {
		    dict unset avin $v
		}
	    }
	}
	my debug-pre {
	    puts "    Available on input: [dict keys $avin]"
	}
	
	# Detect whether AVIN has changed. 
	set changed 0
	set oldavin [lindex $AVIN $b]
	dict for {v -} $avin {
	    if {![dict exists $oldavin $v]} {
		set changed 1
		break
	    }
	}

	# If AVIN has changed, we have to recalculate AVOUT
	if {$changed} {

	    my debug-pre {
		puts "    AVIN has changed, must update AVOUT"
	    }
	    lset AVIN $b $avin

	    set changed 0
	    set avout [lindex $AVOUT $b]
	    dict for {v -} $avin {
		if {![dict exists $avout $v]} {
		    dict set avout $v {}
		    my debug-pre {
			puts "        AVOUT now includes $v"

		    }
		    set changed 1
		}
	    }
	}

	# If AVOUT has changed, we have to revisit the successors of this
	# block
	if {$changed} {

	    my debug-pre {
		puts "    AVOUT has changed, must update successors"
		puts "    AVOUT($b) = [dict keys $avout]"
	    }
	    lset AVOUT $b $avout
	    foreach s [my bbsucc $b] {
		if {![lindex $pending $s]} {
		    my debug-pre {
			puts "        Add $s to worklist"
		    }
		    $worklist add $s
		    lset pending $s 1
		} else {
		    my debug-pre {
			puts "        $s is already on worklist"

		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_altered --
#
#	For each basic block in the program, compute the set of values
#	that are altered by fixed values in the block
#
# Parameters:
#	VN - Dictionary whose keys are quadcode values and whose values
#	     are exemplars of the corresponding expressions.







#
# Results:
#	Returns a list indexed by basic block number. The list values
#	are dictionaries whose keys are the exemplars of altered values
#	and whose values are immaterial
#
# This is the algorithm of Figure 7.2 on page 75 of [Simpson]







oo::define quadcode::transformer method pre_altered {VN} {


    variable ::quadcode::gvn_eliminable

    set S {}
    set D {}
    set isFixed {}

    # Walk through expressions in bottom-up order

    set b -1
    foreach bb $bbcontent {

	incr b
	set pc -1
	foreach q $bb {
	    incr pc

	    set argl [lassign $q opcode result]
	    if {![dict exists $VN $result]} continue
	    set e [dict get $VN $result]
	    if {[dict exists S $e]} continue
	    dict set S $e {}

	    # Keep track of which operands are fixed
	    if {![dict exists $gvn_eliminable $opcode]} {
		dict set isFixed $e {}
	    }



	    # Walk through operands of the expression





	    foreach a $argl {
		puts "expression has arg $a"
		if {![dict exists $VN $a]} continue
		set o [dict get $VN $a]
		puts "$e depends on $a => $o"


		# Set the dependencies of the result e to include
		# the operand o and its dependencies

		dict set S $e $o {}
		# If we haven't seen the operand, and this is a phi,
		# quit here. 
		if {![dict exists $S $o] && $opcode eq "phi"} continue
		dict for {ss -} [dict get $S $o] {
		    dict set S $e $ss {}
		}
	    }

	    # Set the dependents of fixed values 
	    
	    dict for {f -} [dict get $S $e] {
		if {![dict exists $isFixed $f]} continue
		dict set D $f $e {}
	    }
	}
    }

    set ALTERED {}

    # Walk through basic blocks
    set b -1
    foreach bb $bbcontent {
	incr b

	set altered {}
	set pc -1
	foreach q $bb {
	    incr pc
	    lassign $q opcode result
	    if {[dict exists $gvn_eliminable $opcode]} continue
	    if {![dict exists $VN $result]} continue
	    set x [dict get $VN $result]
	    if {![dict exists $D $x]} continue
	    dict for {v -} [dict get $D $x] {
		dict set altered $v {}
	    }
	}
	lappend ALTERED $altered
    }
    return $ALTERED
}
 
# quadcode::transformer method pre_antloc --
#
#	For each basic block in the program, compute the set of locally
#	anticipable expressions, that is, ones that can be moved ahead of
#	the block.
#
# Parameters:
#	defined - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that acquire
#                 values in the block. Dictionary values are immaterial.
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have
#                 values altered in the block. Dictionary values are immaterial.
#
# Results:
#	Returns a list of dictionaries. List indices are basic block numbers.
#	Dictionary keys are exemplars of expressions that are locally
#	anticipable from the block. Dictionary values are immaterial.
#
# Page 76 of [Simpson]: antloc_b = defined_b - altered_b



oo::define quadcode::transformer method pre_antloc {defined altered} {

    set ANTLOC {}
    set b -1
    foreach defns $defined alts $altered {
	incr b
	set antloc $defns
	dict for {alt -} $alts {
	    dict unset antloc $alt
	}
	lappend ANTLOC $antloc
    }
    return $ANTLOC
}
 
# quadcode::transformer method pre_ant_global --
#
#	Calculates the anticipable expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have their
#                 values change in the block. Dictionary values are immaterial.
#	antloc - List of dictionaries. List indices are basic block numbers.
#	         Dictionary keys are exemplars of expressions that are locally
#	         anticipable from the block. Dictionary values are immaterial.
#
# Results:
#	Returns an ordered pair {ANTIN ANTOUT}.
#
#	ANTIN is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values globally anticipable
#       on input to each block.
#
#	ANTOUT is a list of dictionaries indexed by block number and
#	keyed by exemplar, giving the set of values globally anticipable on
#	output from the block.
#
# This procedure solves data flow equations given in Figure 6.3
# on page 69 of [Simpson].

oo::define quadcode::transformer method pre_ant_global {altered antloc} {

    my debug-pre {
	puts "Calculate global anticipable expressions:"
    }

    set ANTOUT [lrepeat [llength $altered] {}]
    set ANTIN $antloc

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in reverse depth-first order

    set pending [lrepeat [llength $altered] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $altered]} {incr i} {
................................................................................
    while {[$worklist size] > 0} {
	set b [expr {-[$worklist removeFirst]}]
	lset pending $b 0

	my debug-pre {
	    puts " Block #$b:"
	}



	# Calculate ANTOUT for the block as the intersection of ANTIN
	# of all predecessors

	set succs [my bbsucc $b]
	if {[llength $succs] == 0} {
	    # Exit block - nothing anticipable on output
	    set antout {}
	} else {
	    set othersuccs [lassign $succs firstsucc]
	    set antout [lindex $ANTIN $firstsucc]
	    foreach s $othersuccs {
		set othervs [lindex $ANTIN $s]
		dict for {v -} $antout {
		    if {![dict exists $othervs $v]} {
			dict unset antout $v
		    }
		}
	    }
	}
	my debug-pre {
	    puts "    Anticipable on output: [dict keys $antout]"
	}
	
	# Detect whether ANTOUT has changed. 
	set changed 0
	set oldantout [lindex $ANTOUT $b]
	dict for {v -} $antout {
	    if {![dict exists $oldantout $v]} {
		set changed 1
		break
	    }
	}

	# If ANTOUT has changed, we have to recalculate ANTIN
	if {$changed} {
	    my debug-pre {
		puts "    ANTOUT has changed, must update ANTIN"
	    }

	    lset ANTOUT $b $antout

	    set changed 0
	    set antin [lindex $ANTIN $b]
	    dict for {v -} $antout {
		if {![dict exists $altered $v] && ![dict exists $antin $v]} {
		    dict set antin $v {}
		    my debug-pre {
			puts "        ANTIN now includes $v"

		    }
		    set changed 1
		}
	    }
	}

	# If ANTIN has changed, we have to revisit the predecessors of this
	# block
	if {$changed} {

	    my debug-pre {
		puts "    ANTIN has changed, must update predecessors"
	    }
	    lset ANTIN $b $antin
	    dict for {p -} [lindex $bbpred $b] {
		if {![lindex $pending $p]} {
		    my debug-pre {
			puts "        Add $p to worklist"
		    }
		    $worklist add [expr {-$p}]
		    lset pending $p 1
		} else {
		    my debug-pre {
			puts "        $p is already on worklist"

		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_earliest --
#
#	Calculate the earliest edge in the control flow graph where the
#	calculation of a given expression may appear.
#
# Parameters:
#	AVOUT - List of dictionaries. List indices are basic block numbers,
#	        dictionary keys are exemplars of values available on output
#	        from the basic block, dictionary values are immaterial.
#	altered - List of dictionaries. List indices are basic block numbers.
#	          Dictionary keys are exemplars of expressions that have
#                 values altered in the block. Dictionary values are immaterial.
#	ANTIN - List of dictionaries indexed by block number and
#	        keyed by exemplar, giving the set of values globally anticipable
#               on input to each block.
#	ANTOUT - List of dictionaries indexed by block number and
#	         keyed by exemplar, giving the set of values globally
#                anticipable on output from the block.
#
# Results:
#	Returns a dictionary whose keys are ordered pairs {from to}
#	representing edges in the control flow graph (where 'from' and
#	'to' are basic block numbers), and whose values are dictionaries
#	whose keys are exemplars of values and whose values are immaterial.
#	The inner dictionaries are the sets of values for which the
#	graph edge {from, to} is the earliest place that computation is
#	permissible.

#
# This analysis is part of the data flow equations in Figure 6.3 on
# page 69 of [Simpson].

oo::define quadcode::transformer method pre_earliest {AVOUT altered
						      ANTIN ANTOUT} {

    my debug-pre {
	puts "Compute earliest insertion points"
    }

    # Walk through basic blocks

    set i -1
    foreach avout_i $AVOUT altered_i $altered antout_i $ANTOUT {
	incr i
	foreach j [my bbsucc $i] {

	    my debug-pre {
		puts "   Edge $i->$j:"
	    }

	    # Edge (i, j) exists in the flow graph. Calculate EARLIEST

	    # At the earliest point, a value must be anticipable
	    set earliest [lindex $ANTIN $j]
	    my debug-pre {
		puts "        ANTIN: [dict keys $earliest]"
	    }

	    # At the earliest point, a value must not be available
	    dict for {v -} $avout_i {
		dict unset earliest $v
	    }
	    my debug-pre {
		puts "        After removing AVOUT: [dict keys $earliest]"
	    }

	    # At the earliest point, a value must not simply flow through
	    # to the exit of the successor block
	    dict for {v -} $antout_i {
		if (![dict exists $altered_i $v]) {
		    my debug-pre {
			puts "        Remove $v because it simply\
                                      passes through $j"
		    }
		    dict unset earliest $v
		}
	    }
	    my debug-pre {
		puts "    What's left is [dict keys $earliest]"
	    }


	    dict set EARLIEST [list $i $j] $earliest
	}
    }
    
    return $EARLIEST
}
................................................................................
 
# quadcode::transformer method pre_later --
#
#	Calculates an indication of whether an expression can be
#	shifted later in the flowgraph
#
# Parameters:
#	ANTLOC - List of dictionaries. The list is indexed by basic
#	         block number. The keys in the dictionaries are the
#		 exemplars of values that are locally anticipable
#	         in the block. The values are immaterial.
#
#	EARLIEST - Two-level dictionary. The outer key is an ordered
#		   pair {i j} identifying an edge {i -> j} in the
#	           control flow graph.  The inner key is an exemplar
#	           of a value. The presence of the value indicates
#	           that the given flowgraph edge is the earliest point
#	           to which the computation of the given value may be
#	           moved. The values in the dictionary are immaterial.
#
# Results:
#	Returns an ordered pair {LATER LATERIN}.
#
#	LATER is a two-level dictionary.The outer key is an ordered
#       pair {i j} identifying an edge {i -> j} in the
#	control flow graph.  The inner key is an exemplar
#	of a value. The presence of the value indicates
#	that the computation of the given value may be moved
#	to at least the given edge. The values of the dictionary are
#	immaterial.
#
#	LATERIN is a list of dictionaries. The index in the list
#	is the number of a basic block. The dictionary keys are
#	exemplars of values. A value is present in the dictionary if
#	the computation may be moved downward at least to the start


#	of the corresponding basic block. The dictionary values are
#	immaterial.
#
# This procedure solves part of the dataflow equations shown in
# Figure 6.4 on page 70 of [Simpson].

oo::define quadcode::transformer method pre_later {ANTLOC EARLIEST} {

    my debug-pre {
	puts "Calculate LATER:"
    }




    set LATER $EARLIEST



    set LATERIN [lrepeat [llength $ANTLOC] {}]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $ANTLOC] 0]
    set worklist [::quadcode::numheap new]
    for {set i 1} {$i < [llength $ANTLOC]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate LATERIN for the block as the intersection of
	# LATER on each of its afferent edges.




	set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	set edge [list $firstpred $b]
	set laterin [dict get $LATER $edge]
	foreach p $otherpreds {
	    set edge [list $p $b]
	    set l [dict get $LATER $edge]
	    dict for {v -} $laterin {
		if {![dict exists $l $v]} {
		    dict unset $laterin $v
		}
	    }
	}

	my debug-pre {
	    puts "    LATERIN: [dict keys $laterin]"
	}
	
	# Detect whether LATERIN has changed. 
	set changed 0
	set oldlaterin [lindex $LATERIN $b]
	dict for {v -} $laterin {
	    if {![dict exists $oldlaterin $v]} {
		set changed 1
		break
	    }
	}

	# If LATERIN has changed, we have to recalculate LATER for
	# each successor
	
	if {$changed} {
	    my debug-pre {
		puts "    LATERIN has changed, must update LATER"
	    }
	    lset LATERIN $b $laterin

	    set intsct {}; # LATERIN_i - ANTLOC_i
	    set antloc [lindex $ANTLOC $b]
	    dict for {v -} $laterin {
		if {![dict exists $antloc $v]} {
		    my debug-pre {
			puts "        $v is not locally anticipable in $b"
		    }
		    dict set intsct $v {}
		}
	    }
	    foreach s [my bbsucc $b] {

		my debug-pre {
		    puts "        $b -> $s:"
		}
		set changed 0
		set edge [list $b $s]
		set later [dict get $LATER $edge]
		dict for {v -} $intsct {
		    if {![dict exists $later $v]} {

			my debug-pre {
			    puts "            LATER now includes $v"
			}
			dict set later $v {}
			set changed 1
		    }


		}

		if {$changed} {

		    my debug-pre {
			puts "        LATER has changed, must update bb $s"
		    }
		    dict set LATER $edge $later
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
................................................................................
    }

    $worklist destroy

    return [list $LATERIN $LATER]
    
}








































>



|


|
|
>
|


>









|












|
|


>



|





|





|





|












|
|













|

|







 







|
>
>
|
<
|
>
>
>







|
|
|
|
|
|
>



>










>
>
|
<
<
>
>
>
>
>
>
>
>
>
>
>










>
>










>
>







 







|










>
|
>
>
>
|
>
|

|


|

|






|
>







 







|







 







|
|
<
<











|












|







 







|
<
<
|




|
|
<

>
|
<
<










>
>
|
<
>






|







 







>
>
>
|
|
|
|
<
<
<
<



|


<
<
<
<
<
<
<
<
<
<

<
>





|
<
<
<
<
|
<
>
|
<
|
<
<
<
|
|
<
>
|
|
<
|
|
|
|
|
|
|
|
|
|
|
|
>







 







|
|
>
>
>
>
>
>
>






|
>
>
>
>
>
>

|
>

<
<
|
<
<

|


<
>

<
<
<

<
<
<
<
<
<
<
|
<
|
>
>

<
<
>
>
>
>

<
<
<
|
>

<
|

|
|
<
<
<
<


|
<
|
<
<
<
<
<
<
<
|

<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
|
<
<
<










|
|
|
|
|
|


|
|
<


>
>

|





<
<
<
<
|










|
|
|
|
<
<




|
|
|

|
|
|










|
|







 







>
>







|




|
<
<
<
<
<



|


<
<
<
<
<
<
<
<
<
<

<
<
<
<
>


<
<
<
<
<
<
<
>
|
<
<
<
<
<
|
|
<
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>







 







|
|
|
|
|
|
|
|
|
|
|
|




|
<
|
<
<
>







|
<
|
<
|





<
<
<
<
<


<
|
<
<
|
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
>







 







|
|
|
|
|
|
|
|
<
<
<
<




|
|
|
|
|
<
<

<
<
<
<
>
>
|
<










>
>
>
|
>
>
>
|
|

|



|







 







>
>
>
|
|
|
|
|
|
<
<
<
<




|


<
<
<
<
<
<
<
<
<
<



|





<
|
<
<
<
<
<
<
<
<

<



<

<
<
<
>
|
|
|
<
<
|
>
>
|
<
<
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
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
...
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
...
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
...
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
...
428
429
430
431
432
433
434
435


436
437
438
439
440
441
442

443
444
445


446
447
448
449
450
451
452
453
454
455
456
457
458

459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
...
477
478
479
480
481
482
483
484
485
486
487
488
489
490




491
492
493
494
495
496










497

498
499
500
501
502
503
504




505

506
507

508



509
510

511
512
513

514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
...
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570


571


572
573
574
575

576
577



578







579

580
581
582
583


584
585
586
587
588



589
590
591

592
593
594
595




596
597
598

599







600
601




602











603



604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623

624
625
626
627
628
629
630
631
632
633
634




635
636
637
638
639
640
641
642
643
644
645
646
647
648
649


650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
...
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
711
712
713










714




715
716
717







718
719





720
721

722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
...
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772

773


774
775
776
777
778
779
780
781
782

783

784
785
786
787
788
789





790
791

792


793



794



















795
796
797
798
799
800
801
802
...
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817




818
819
820
821
822
823
824
825
826


827




828
829
830

831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
...
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881




882
883
884
885
886
887
888










889
890
891
892
893
894
895
896
897

898








899

900
901
902

903



904
905
906
907


908
909
910
911


912
913
914
915
916
917
918
919
...
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
oo::define quadcode::transformer method partialredundancy {} {

    my debug-pre {
	puts "Before partial redundancy elimination:"
	my dump-bb
    }
    my variable pre_exemplar

    # Compute Global Value Numbering for the values present in the quadcode

    lassign [my pre_gvn] VN pre_exemplar cands
    my debug-pre {
	puts "Value numbering:"
	dict for {k n} [lsort -stride 2 -index 0 -ascii -increasing $VN] {
	    set v [lindex $pre_exemplar $n]
	    if {[lindex $v 0] ne $k} {
		puts "   found congruence $k -> $n ($v)"
	    }
	}
	puts "Candidates for PRE: [my pre_format_bitset $cands]"
    }

    # Compute the 'defined' predicate for the basic blocks

    set defined [my pre_defined $VN]
    my debug-pre {
	puts "Defined expressions:"
	set b -1
	foreach vset $defined {
	    puts "[incr b]: [my pre_format_bitset $vset]"
	}
    }

    # Find sets of available expressions

    lassign [my pre_avail $defined] AVIN AVOUT
    my debug-pre {
	puts "Available expressions"
	set b -1
	foreach inset $AVIN outset $AVOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    AVIN =  [my pre_format_bitset $inset]"
	    puts "    AVOUT = [my pre_format_bitset $outset]"
	}
    }


    # Find sets of expressions altered within each block

    set altered [my pre_altered $pre_exemplar $cands $AVIN $AVOUT]
    my debug-pre {
	puts "Altered expressions"
	set b -1
	foreach al $altered {
	    incr b
	    puts "  Block #$b: [my pre_format_bitset $al]"
	}
    }

    # Find expressions that are locally anticipable at entry to blocks

    set antloc [my pre_antloc $cands $defined $altered]
    my debug-pre {
	puts "Locally anticipable expressions"
	set b -1
	foreach an $antloc {
	    incr b
	    puts "  Block #$b: [my pre_format_bitset $an]"
	}
    }

    # Compute globally anticipable expressions

    lassign [my pre_ant_global $altered $antloc] ANTIN ANTOUT
    my debug-pre {
	puts "Globally anticipable expressions"
	set b -1
	foreach inset $ANTIN outset $ANTOUT {
	    incr b
	    puts "  Block #$b:"
	    puts "    ANTIN =  [my pre_format_bitset $inset]"
	    puts "    ANTOUT = [my pre_format_bitset $outset]"
	}
    }

    # Compute earliest points where an expression may be moved.
    # These are edges on the call graph where the expression may
    # appear. (Since we have no critical edges, the expression
    # can always be inserted at either the tail of the predecessor
    # block or the head of the successor).

    set EARLIEST [my pre_earliest $AVOUT $altered $ANTIN $ANTOUT]
    my debug-pre {
	puts "Earliest insertion points:"
	dict for {edge vars} $EARLIEST {
	    if {$vars != 0} {
		lassign $edge from to
		puts "    $from->$to: [my pre_format_bitset $vars]"
	    }
	}
    }

    # Compute LATER, which is an indication that an expression
    # may be moved later than an edge (LATER) or the start of
    # a block (LATERIN)
................................................................................

    lassign [my pre_later $antloc $EARLIEST] LATERIN LATER

    # Report on insertion and deletion points

    dict for {edge exprs} $LATER {
	lassign $edge from to
	my debug-pre {
	    puts "Edge $from -> $to: LATER = [my pre_format_bitset $exprs]"
	    puts "Node $to: LATERIN =\
                  [my pre_format_bitset [lindex $LATERIN $to]]"

	}
	set insert [expr {$exprs & ~[lindex $LATERIN $to]}]
	if {$insert != 0} {
	    puts "Insert on edge ($from -> $to): [my pre_format_bitset $insert]"
	}
    }

    set b -1
    foreach exprs $antloc laters $LATERIN {
	incr b
	if {$b == 0} continue
	my debug-pre {
	    puts "Block $b: ANTLOC = [my pre_format_bitset $exprs]"
	    puts "Block $b: LATERIN = [my pre_format_bitset $laters]"
	}
	set delete [expr {$exprs & ~$laters}]
	if {$delete != 0} {
	    puts "Delete from block $b: [my pre_format_bitset $delete]"
	}
    }

    unset pre_exemplar
    return 0

}
 
# quadcode::transformer method pre_gvn --
#
#	Calculates a Global Value Numbering for values in a quadcode
#	sequence.
#
# Results:
#	Returns a tjree-element list.
#
#	The first element is a dictionary whose keys are the names of


#	program variables and whose values are value numbers. Two value
#	numbers are distinct if it cannot be shown that they result
#	from the same computation.
#
#	The second element is a dictionary whose keys are the value
#	numbers and whose values are ordered pairs: program variables
#	that represent the values, and the expressions that compute the
#	values.
#
#	The third element is a bit set containing those values that are
#	candidates - that is, could conceivably be moved from block to block
#
# This procedure implements the 'RPO' algorithm presented in
# Figure 4.3 of [Simpson] (see references in the file header.
# While perhaps not as fast, it is significantly simpler than
# the 'SCC' algorithm and yields the same results.
#
# This procedure assumes that 'deadbb' has been run before it,
# so that it will find basic blocks already in depth-first order.

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

    variable ::quadcode::gvn_eliminable

    # Initially all value numbers are unknown

    set VN {}

    # Iterate to convergence

    while {1} {
	set changed 0
	set VNforSig {}
	set exemplarForVN {}
	set cands 0

	# Iterate through all basic blocks in depth-first order
	set b -1
	foreach bb $bbcontent {
	    incr b

	    # Walk through the instructions of each block
................................................................................

		# Ignore instructions that do not produce a value
		set result [lindex $q 1]
		if {[lindex $result 0] ni {"temp" "var"}} {
		    continue
		}

		# TODO - Detect meaningless phi?

		# Make a signature for the expression computed
		# by the current instruction
		set sig [my pre_gvn_sig $VN $q]

		# If there is already a value number for the signature, use
		# it. Otherwise, make the current result the exemplar of the
		# congruence class. Set 'changed' if the the value number
		# changes from the previous round.
		if {![dict exists $VNforSig $sig]} {
		    set vn [llength $exemplarForVN]
		    dict set VNforSig $sig $vn
		    lappend exemplarForVN [list $result $sig]
		    if {[dict exists $gvn_eliminable [lindex $q 0 0]]} {
			set cands [expr {$cands | (1 << $vn)}]
		    }
		}
		set vn [dict get $VNforSig $sig]
		if {![dict exists $VN $result]
		    || [dict get $VN $result] ne $vn} {
		    set changed 1
		    my debug-pre {
			puts "Value number for $result is now $vn"
		    }
		    dict set VN $result $vn
		}
	    }
	}
	
	if {!$changed} break
    }

    return [list $VN $exemplarForVN $cands]

}
 
# quadcode::transformer method pre_gvn_sig --
#
#	Develops a signature for a quadcode instruction's result
#	in Global Value Numbering
................................................................................
	    bb - pc {
		lappend signature {}
	    }
	    temp - var {
		if {![dict exists $VN $a]} {
		    lappend signature TOP
		} else {
		    lappend signature [list value [dict get $VN $a]]
		}
	    }
	    default {
		lappend signature $a
	    }
	} 
    }
................................................................................
 
# quadcode::transformer method pre_defined --
#
#	Computes the local predicate, 'defined', for use in the
#	dataflow equations.
#
# Results:
#	Returns a list of bit vectors.  Each vector represents the set
#	of values defined in a basic block.



oo::define quadcode::transformer method pre_defined {VN} {

    set DEFINED {}

    # Walk through the basic blocks

    set b -1
    foreach bb $bbcontent {
	incr b

	set defined 0

	# Walk through the individual instructions
	
	set pc -1
	foreach q $bb {
	    incr pc

	    lassign $q opcode result

	    # If an instruction defines a value, add the value to the set
	    
	    if {$result ne {} && [dict exists $VN $result]} {
		set defined [expr {$defined | (1 << [dict get $VN $result])}]
	    }
	}

	# Add the set to the list
	
	lappend DEFINED $defined
    }
................................................................................
 
# quadcode::transformer method pre_avail --
#
#	Calculates the available expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	defined - List of bit vectors corresponding to the sets of values


#	          defined in the basic blocks
#
# Results:
#	Returns an ordered pair {AVIN AVOUT}.
#
#	AVIN is a list of bit vectors giving the sets of values available
#	at the start of the basic blocks.

#
#	AVOUT is a list of bit vectors giving thes sets of values available
#	at the end of the basic blocks


#
# This procedure solves the data flow equations given in Figure 5.6
# on page 63 of [Simpson].

oo::define quadcode::transformer method pre_avail {defined} {

    my debug-pre {
	puts "Calculate available expressions:"
    }

    # Initially, assume all variables are available on input to all blocks
    # other than the entry, and then prove otherwise.
    set AVIN [lrepeat [llength $defined] -1]

    set AVOUT [lrepeat [llength $defined] -1]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in depth-first order

    set pending [lrepeat [llength $defined] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $defined]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate AVIN for the block as the intersection of AVOUT
	# of all predecessors

	if {$b == 0} {
	    set avin 0
	} else {
	    set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	    set avin [lindex $AVOUT $firstpred]
	    foreach p $otherpreds {
		set avin [expr {$avin & [lindex $AVOUT $p]}]




	    }
	}
	my debug-pre {
	    puts "    Available on input: [my pre_format_bitset $avin]"
	}
	










	# If AVIN has changed, we have to recalculate AVOUT

	if {$avin != [lindex $AVIN $b]} {
	    my debug-pre {
		puts "    AVIN has changed, must update AVOUT"
	    }
	    lset AVIN $b $avin

	    set avout [expr {$avin | [lindex $defined $b]}]




	    my debug-pre {

		puts "    Available on output: [my pre_format_bitset $avout]"
	    }





	    # If AVOUT has changed, we have to revisit the successors of this
	    # block

	    if {$avout != [lindex $AVOUT $b]} {
		my debug-pre {
		    puts "    AVOUT has changed, must update successors"

		}
		lset AVOUT $b $avout
		foreach s [my bbsucc $b] {
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
			}
			$worklist add $s
			lset pending $s 1
		    } else {
			my debug-pre {
			    puts "        $s is already on worklist"
			}
		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_altered --
#
#	For each basic block in the program, compute the set of values
#	that are altered by fixed values in the block
#
# Parameters:
#	exemplars - List of ordered pairs (name, expression) that
#	            show exemplar names and expression computed for
#	            each value.
#	cands - Bit set that identifies which values are candidates for
#	        code motion
#	AVIN - List of bit vectors indicating the expressions available
#	       on entry to the program's blocks
#	AVOUT - List of bit vectors indicating the expressions available
#	        on exit from the program's blocks
#
# Results:
#	Returns a list indexed by basic block number. The list values
#	are dictionaries whose keys are the exemplars of altered values
#	and whose values are immaterial
#
# This is the algorithm of Figure 7.1 on page 75 of [Simpson]. Simpson
# is quite unclear on the issue that (AVOUT-AVIN) should apply only to
# fixed values, and then the altered candidates appear only as a
# consequence of tracking the dependents on thosed fixed
# values. Nevertheless, if this filtering is not done, nothing ever
# becomes locally anticipable, because its own calculation turns up in
# (AVOUT-AVIN).

oo::define quadcode::transformer method pre_altered {exemplars cands
						     AVIN AVOUT} {



    set ALTERED {}



    # Walk through the basic blocks

    set b -1

    foreach avin $AVIN avout $AVOUT {
	incr b











	set altered [expr {$avout & ~$avin & ~$cands}]


	# Walk through all expressions in bottom-up order, and through
	# the operands of each expression



	set e -1
	foreach ex $exemplars {
	    incr e
	    set argl [lassign [lindex $ex 1] opcode]
	    foreach a $argl {



		lassign $a kind o
		if {$kind ne "value"} continue


		# Add altered values to the bit vector

		if {$altered & (1 << $o)} {
		    set altered [expr {$altered | (1 << $e)}]




		}
	    }
	}









	lappend ALTERED $altered





    }















    return $ALTERED
}
 
# quadcode::transformer method pre_antloc --
#
#	For each basic block in the program, compute the set of locally
#	anticipable expressions, that is, ones that can be moved ahead of
#	the block.
#
# Parameters:
#	cands - Bit set that identifies candidate expressions for
#	        partial redundancy elimination
#	defined - List of bit sets, indexed by basic block number, indicating
#	          what values are defined within the block
#	altered - List of bit sets, indexed by basic block number, indicating
#		  what values are altered within the block
#
# Results:
#	Returns a list of bit sets, indexed by basic block number, indicating
#	what values are locally anticipable within the block. Note that

#
# Page 76 of [Simpson]: antloc_b = defined_b - altered_b
# Simpson does not appear to constrain this to candidates, but it doesn't
# ever make sense to move a non-candidate.

oo::define quadcode::transformer method pre_antloc {cands defined altered} {

    set ANTLOC {}
    set b -1
    foreach defns $defined alts $altered {
	incr b




	lappend ANTLOC [expr {$defns & ~$alts & $cands}]
    }
    return $ANTLOC
}
 
# quadcode::transformer method pre_ant_global --
#
#	Calculates the anticipable expressions at entry and exit to each
#	basic block.
#
# Parameters:
#	altered - List of bit vectors that enumerate the values altered
#	          in each block.
#	antloc - List of bit vectors that enumerate the candidate values
#	         for code motion that are locally anticipable in each block


#
# Results:
#	Returns an ordered pair {ANTIN ANTOUT}.
#
#	ANTIN is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that are anticipable on
#	entry into basic blocks.
#
#	ANTOUT is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that are anticipable on
#	exit from basic blocks
#
# This procedure solves data flow equations given in Figure 6.3
# on page 69 of [Simpson].

oo::define quadcode::transformer method pre_ant_global {altered antloc} {

    my debug-pre {
	puts "Calculate global anticipable expressions:"
    }

    set ANTOUT [lrepeat [llength $altered] -1]
    set ANTIN [lrepeat [llength $altered] -1]

    # Initially, the worklist is the complete set of basic blocks,
    # except for the entry block, in reverse depth-first order

    set pending [lrepeat [llength $altered] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $altered]} {incr i} {
................................................................................
    while {[$worklist size] > 0} {
	set b [expr {-[$worklist removeFirst]}]
	lset pending $b 0

	my debug-pre {
	    puts " Block #$b:"
	}
	set alt [lindex $altered $b]
	set aloc [lindex $antloc $b]

	# Calculate ANTOUT for the block as the intersection of ANTIN
	# of all predecessors

	set succs [my bbsucc $b]
	if {[llength $succs] == 0} {
	    # Exit block - nothing anticipable on output
	    set antout 0
	} else {
	    set othersuccs [lassign $succs firstsucc]
	    set antout [lindex $ANTIN $firstsucc]
	    foreach s $othersuccs {
		set antout [expr {$antout & [lindex $ANTIN $s]}]





	    }
	}
	my debug-pre {
	    puts "    Anticipable on output: [my pre_format_bitset $antout]"
	}
	










	# If ANTOUT has changed, we have to recalculate ANTIN




	if {$antout != [lindex $ANTOUT $b]} {
	    lset ANTOUT $b $antout








	    set antin [expr {($antout & ~$alt) | $aloc}]






	    # If ANTIN has changed, we have to revisit the predecessors of this
	    # block

	    if {$antin != [lindex $ANTIN $b]} {
		my debug-pre {
		    puts "    ANTIN has changed, must update predecessors"
		}
		lset ANTIN $b $antin
		dict for {p -} [lindex $bbpred $b] {
		    if {![lindex $pending $p]} {
			my debug-pre {
			    puts "        Add $p to worklist"
			}
			$worklist add [expr {-$p}]
			lset pending $p 1
		    } else {
			my debug-pre {
			    puts "        $p is already on worklist"
			}
		    }
		}
	    }
	}
    }

    $worklist destroy
................................................................................
 
# quadcode::transformer method pre_earliest --
#
#	Calculate the earliest edge in the control flow graph where the
#	calculation of a given expression may appear.
#
# Parameters:
#	AVOUT - List, indexed by basic block number, of bit vectors that
#	        enumerate the values available on exit from the corresponding
#	        basic blocks
#	altered - List, indexed by basic block number, of bit vectors that
#	          enumerate the values that are spoilt in the corresponding
#	          basic blocks
#	ANTIN - List, indexed by basic block number, of bit vectors that
#		enumerate the values that are globally anticipable on entry
#	        to the corresponding basic blocks.
#	ANTOUT - List, indexed by basic block number, of bit vectors that
#	         enumerate the values that are globally anticipable on exit
#	         from the corresponding basic blocks.
#
# Results:
#	Returns a dictionary whose keys are ordered pairs {from to}
#	representing edges in the control flow graph (where 'from' and
#	'to' are basic block numbers), and whose values are bit vectors

#	representing the sets of values for which the edges are the


#	earliest points where the values may be computed.
#
# This analysis is part of the data flow equations in Figure 6.3 on
# page 69 of [Simpson].

oo::define quadcode::transformer method pre_earliest {AVOUT altered
						      ANTIN ANTOUT} {

    set EARLIEST {}



    # Walk through flowgraph edges (i -> j)

    set i -1
    foreach avout_i $AVOUT altered_i $altered antout_i $ANTOUT {
	incr i
	foreach j [my bbsucc $i] {





	    # Edge (i, j) exists in the flow graph. Calculate EARLIEST


	    set antin_j [lindex $ANTIN $j]






	    set earliest [expr {$antin_j & ~$avout_i



















				& ($altered_i | ~$antout_i)}]

	    dict set EARLIEST [list $i $j] $earliest
	}
    }
    
    return $EARLIEST
}
................................................................................
 
# quadcode::transformer method pre_later --
#
#	Calculates an indication of whether an expression can be
#	shifted later in the flowgraph
#
# Parameters:
#	ANTLOC - List of bit sets, indexed by basic block number, indicating
#	         what values are locally anticipable within the block.
#
#	EARLIEST - Dictionary whose keys are ordered pairs {i j}
#	           identifying edges {i -> j} in the
#	           control flow graph.  The values are bit vectors enumerating
#	           sets of values for which the corresponding edgs is the
#	           earliest possible placement.




#
# Results:
#	Returns an ordered pair {LATER LATERIN}.
#
#	LATER is a dictionary whose keys are ordered pairs {i j}
#	identifying edges {i -> j} in the control flow graph.
#	The values are bit sets that enumerate the candidate values
#	that may be computed on the corresponding edge or a later point
#	in the program.


#




#	LATERIN is a list indexed by basic block number of bit vectors
#	that enumerate the candidate values that may be calculated
#	on entry to the corresponding basic block or later in the program.

#
# This procedure solves part of the dataflow equations shown in
# Figure 6.4 on page 70 of [Simpson].

oo::define quadcode::transformer method pre_later {ANTLOC EARLIEST} {

    my debug-pre {
	puts "Calculate LATER:"
    }

    # Initialize LATER with the universal set for every flowgraph edge,
    # and LATERIN with the universal set for every basic block

    set LATER []
    dict for {edge -} $EARLIEST {
	dict set LATER $edge -1
    }
    set LATERIN [lrepeat [llength $ANTLOC] -1]
    
    # Initially, the worklist is the complete set of basic blocks,
    # in depth-first order

    set pending [lrepeat [llength $ANTLOC] 0]
    set worklist [::quadcode::numheap new]
    for {set i 0} {$i < [llength $ANTLOC]} {incr i} {
	$worklist add $i
	lset pending $i 1
    }

    # Pop blocks from the worklist for analysis

    while {[$worklist size] > 0} {
................................................................................
	my debug-pre {
	    puts " Block #$b:"
	}

	# Calculate LATERIN for the block as the intersection of
	# LATER on each of its afferent edges.

	if {$b == 0} {
	    set laterin 0
	} else {
	    set otherpreds [lassign [dict keys [lindex $bbpred $b]] firstpred]
	    set edge [list $firstpred $b]
	    set laterin [dict get $LATER $edge]
	    foreach p $otherpreds {
		set edge [list $p $b]
		set laterin [expr {$laterin & [dict get $LATER $edge]}]




	    }
	}

	my debug-pre {
	    puts "    LATERIN: [my pre_format_bitset $laterin]"
	}
	










	# If LATERIN has changed, we have to recalculate LATER for
	# each successor
	
	if {$laterin != [lindex $LATERIN $b]} {
	    my debug-pre {
		puts "    LATERIN has changed, must update LATER"
	    }
	    lset LATERIN $b $laterin


	    set intsct [expr {$laterin & ~[lindex $ANTLOC $b]}]








	    foreach s [my bbsucc $b] {

		my debug-pre {
		    puts "        $b -> $s:"
		}

		set edge [list $b $s]



		set later [expr {$intsct | [dict get $EARLIEST $edge]}]
		my debug-pre {
		    puts "            LATER = [my pre_format_bitset $later]"
		}



		# If LATER has changed, we need to requeue the successor
		# node.
	       


		if {$later != [dict get $LATER $edge]} {
		    my debug-pre {
			puts "        LATER has changed, must update bb $s"
		    }
		    dict set LATER $edge $later
		    if {![lindex $pending $s]} {
			my debug-pre {
			    puts "        Add $s to worklist"
................................................................................
    }

    $worklist destroy

    return [list $LATERIN $LATER]
    
}
 
# quadcode::transformer method pre_format_bitset --
#
#	Formats a set of values for debug printing
#
# Parameters:
#	vset - Set of values to be printed
#
# Results:
#	Returns a list of exemplars corresponding to the set of values

oo::define quadcode::transformer method pre_format_bitset {vset} {

    my variable pre_exemplar

    if {$vset == -1} {
	return "EVERYTHING"
    }
    if {$vset < 0} {
	set result "EVERYTHING BUT"
	set vset [expr {~$vset}]
    } else {
	set result {}
    }
    set vn -1
    foreach ex $pre_exemplar {
	incr vn
	if {$vset & (1 << $vn)} {
	    lappend result [lindex $ex 0]
	}
    }
    return $result
}