Check-in [0bbe5a5dd3]
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:Rewrite pre_insert and pre_phi_translate to NOT use a persistent cache. The missing piece in VanD04 is that pre_insert must call pre_phi_translate for all the anticipated expressions first, and then use the dictionary that results for the translated values. There are still further bugs, but we're over this hump at least.
Timelines: family | ancestors | descendants | both | notworking | kbk-pre
Files: files | file ages | folders
SHA3-256: 0bbe5a5dd3eed54359b801114a3af3c7bc0b9532b8fb4bce1bca365efb41c82c
User & Date: kbk 2018-12-05 05:37:17
Context
2018-12-06
01:42
Remove speculative phis if they turned out not to be useful check-in: bd6294fade user: kbk tags: notworking, kbk-pre
2018-12-05
05:37
Rewrite pre_insert and pre_phi_translate to NOT use a persistent cache. The missing piece in VanD04 is that pre_insert must call pre_phi_translate for all the anticipated expressions first, and then use the dictionary that results for the translated values. There are still further bugs, but we're over this hump at least. check-in: 0bbe5a5dd3 user: kbk tags: notworking, kbk-pre
2018-12-03
05:08
Stop constant folding from leaving dead code behind, Add a test for simple nested iterations, using [lmap]. Temporarily patch 'foreach' operations from being hoistable - I don't think this will be necessary, but it's tickling other bugs. Make translation of values across a phi work if one of the inputs to the phi is a literal. Put 'bbidom' and 'bblevel' directly after dead code elimination, because virtually everything depends on having dominators, which deadcode destroys. check-in: 4f50ed77b2 user: kbk tags: notworking, kbk-pre
Changes

Changes to demos/perftest/tester.tcl.

2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
    upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*
    redundant-purify
    licm
    licm2
    cse cse-caller
    wideimpure
}
set toCompile'slow' {
    parseBuiltinsTxt::main
}
 






|
<







2524
2525
2526
2527
2528
2529
2530
2531

2532
2533
2534
2535
2536
2537
2538
    upvar0a
    upvartest0::*
    upvartest1::*
    upvartest2::*
    flightawarebench::*
    hash::*
    redundant-purify
    licm1 licm2

    cse cse-caller
    wideimpure
}
set toCompile'slow' {
    parseBuiltinsTxt::main
}
 

Changes to quadcode/pre.tcl.

111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
...
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
...
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
...
633
634
635
636
637
638
639
640
641
642

643




644
645
646
647
648
649
650
651
...
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
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
952
953
954
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
1034
1035
1036
1037

1038
1039
1040

1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053


1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087

1088
1089


1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104






1105
1106
1107
1108

1109
1110
1111
1112
1113
1114



1115




1116
1117
1118
1119
1120
1121

1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134




1135
1136
1137
1138




1139










1140
1141
1142
1143
1144
1145
1146
1147
....
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
....
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315


1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343


1344
1345
1346
1347
1348

1349


1350
1351


1352













1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381




1382

1383
1384
1385
1386
1387
1388

1389
1390
1391

1392
1393

1394
1395
1396
1397
1398
1399
1400
# phi operations will have become worthless, either because two such
# operations become the same operation, or because all inputs to a phi
# become the same input. It may be necessary to repeat this
# optimization after cleaning up useless phi's.

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

    # TEMP - examine just the specific target scenario
    if {0 && ([my full-name] ne "::cse(INT,INT)"
	      || [llength $bbcontent] != 11)} {return 0}

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

    # 0. Initialize the global variable numbering tables.

................................................................................
	    # others.
	    if {$op eq "phi"} {

		# phi - give the result a unique value number, and add it
		#       to phi_gen
		set expr [list {} $result]
		set v [my pre_gvn_lookup_or_add $expr]
		lappend phi_gen_b $result $argl

	    } elseif {$op eq "copy"} {

		# copy - give the result the same value number as the source.
		set src [lindex $argl 0]
		set expr [list {} $result]
		set srcexpr [list {} $src]
................................................................................
    my variable pre_tmp_gen
    my variable pre_phi_gen

    my variable pre_avail_out

    my variable pre_antic_in
    
    my variable pre_translate_cache

    # Initialize anticipable sets to empty. This initial value should
    # be accessed only in the case of an infinite loop, whose blocks will
    # have no postdominators.
    set pre_antic_in [lrepeat [llength $bbcontent] {}]
    set pre_translate_cache {}

    # Calculate the retrograde order in which blocks are to be visited
    set bs [my bbrorder]

    # Iterate to convergence
    set changed 1
    while {$changed} {
................................................................................
		set antic_in_f [lindex $pre_antic_in $f]
		my debug-pre {
		    puts "      which has anticipable values:"
		    dict for {vvv eee} $antic_in_f {
			puts "        value $vvv = $eee"
		    }
		}
		set antic_out [my pre_phi_translate $antic_in_f $b $f]
		my debug-pre {
		    puts "      giving anticipable values on output of $b:"

		    dict for {vvv eee} $antic_out {




			puts "        value $vvv = $eee"
		    }
		}
		
	    } else {

		my debug-pre {
		    puts "      has multiple successors: $succs"
................................................................................
#	'copy' and 'phi' instructions are inserted in the quadcode
#	to make fully anticipable expressions available at merge
#	points where they are only partially available. This process
#	involves inserting computation of the needed expressions
#	on any predecessors where they are not available, and then
#	introducing a phi operation to combine the new expressions.
#
# Figures 4.8-4.9 on pp. 78-79 of [VanD].






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

    my variable pre_antic_in
    my variable pre_avail_out
    my variable pre_new_sets
    
    my debug-pre {
	puts "Try to find code insertion points"
    }

    set pre_new_sets [lrepeat [llength $bbcontent] {}]
    set did [lrepeat [llength $bbcontent] {}]

    # Iterate to convergence
    set did_something 0
    set changed 1
    while {$changed} {
	set changed 0

	# Process the basic blocks in forward sequence





	set b -1
	foreach didvals $did {

	    incr b

	    # Initially, the new instructions making values available
	    # are inherited from the dominator, and they also become
	    # the leaders for their values.
	    set avail_in_dom [lindex $pre_avail_out [lindex $bbidom $b]]









	    set new_sets_b $avail_in_dom


	    set avail_out_b [lindex $pre_avail_out $b]
	    lset pre_avail_out $b {}
	    dict for {v e} $new_sets_b {
		dict set avail_out_b $v $e
	    }
	    lset pre_avail_out $b $avail_out_b
		
	    # Handle merge points
	    set preds [lindex $bbpred $b]



	    if {[dict size $preds] > 1} {

		# Walk through the anticipable expressions at each merge point


















		dict for {v e} [lindex $pre_antic_in $b] {
















		    if {[dict exists $didvals $v]} {
			my debug-pre {
			    puts "Already hoisted value $v past $b"




























































			}
			continue
		    }
		    
		    my debug-pre {
			puts "Examine value $v = $e in block $b"
		    }



		    
		    # If an expression is a copy, we don't need to do
		    # anything because its value is known to be available.
		    # If an expression is available in the dominator, it's
		    # already available here, so there's no need to do anything
		    # more

		    if {[lindex $e 0] ne {}
			&& ![dict exists $avail_in_dom $e]} {

			# The expression e (whose value number is v)
			# is not a copy. The expression is anticipable
			# in block b but not its dominator.  This is
			# the case that may need a phi and one or more
			# assignments.

			if {[my pre_insert_do_expr $b $v $e]} {
			    dict set didvals $v {}
			    set changed 1
			    set did_something 1
			}
		    }
		}		    
	    }
	    lset did $b $didvals
	}
    }
    return $did_something
}
 
# quadcode::transformer method pre_insert_do_expr --
#
#	When an expression is found that is available at a merge point
#	but not its dominator, makes that expression available if possible.
#
# Parameters:
#	b - Basic block number of the merge point
#	preds - Dictionary whose keys are the predecessors of basic block b
#	v - Value number of the expression under consideration
#	e - Expression under consideration
#
# Results:
#	Returns 1 if the procedure did anything.
#
# Figure 4.8, page 78 of [VanD].
#
# TODO - Need to think about how to maintain a name and a debugging context
#	 for code that has been moved - or to suppress this optimization
#	 at low -O levels

oo::define quadcode::transformer method pre_insert_do_expr {b v e} {

    my variable pre_new_sets

    my debug-pre {
	puts "Examine value $v: $e for code motion at entry to block $b"
    }

    if {[my pre_gvn_is_literal $v -]} {
	my debug-pre {
	    puts "$v: $e is a literal - there's nothing to be done."
	}	    
	return 0;		# There's nothing to insert for a literal
    }
	

    # Is this a point where it's appropriate to insert (It is if
    # the value is available on at least one predecessor, and not on all).


    set avail [my pre_insertion_point $b $v $e]
    if {[dict size $avail] == 0} {
	my debug-pre {
	    puts "$v: $e is not eligible to be hoisted above block $b"
	}
	return 0
    }

    my debug-pre {
	puts "The expression will be made available from:"
	dict for {p eprime} $avail {
	    puts "  block $p -> $eprime"
	}
    }

    set t [my pre_insert_make_mods $b $v $e $avail]

    set news [lindex $pre_new_sets $b]
    lset pre_new_sets $b {}
    dict set news $v $t
    lset pre_new_sets $b $news

    return 1
}
 
# quadcode::transformer method pre_insertion_point --
#
#	Tests whether the predecessors of the start of a given basic block
#	are appropriate insertion points for a partially available expression.
#
# Parameters:
#	b - Block being examined
#	v - Global value number of the expression being examined
#	e - Expression being examined, which will always be complex.
#
# Results:
#	Returns a dictionary whose keys are the basic block numbers
#	of predecessor blocks, and whose values are expressions
#	in the blocks.
#
# The expressions will be either SSA temporaries that contain the
# corresponding value at the end of the predecessor block, or complex
# expressions that must be evaluated in the predecessor. If the block
# is an inappropriate point to insert the evaluation of the given
# value, the returned dictionary will be empty.
#
# This procedure is roughly the second half of Figure 5.8 on page 78
# of [VanD04].

oo::define quadcode::transformer method pre_insertion_point {b v e} {

    my variable pre_avail_out
    set bbb -1

    set avail {};		# Return value of this method, being
    ;				# accumulated
    set by_some 0;		# Flag is true if the expression is available
    ;				# in at least one predecessor
    set all_same 1;		# Flag is true if all predecessors present
    ;				# the same value for the available expression

    set ve [dict create $v $e];	# Dictionary with the single pair v->e,
    ;				# to use as an argument to phi_translate

    # Iterate through the predecessors
    dict for {p -} [lindex $bbpred $b] {

	# Find the expression, eprime, that would make e available in the
	# predecessor
	dict for {vprime eprime} [my pre_phi_translate1 $v $e $p $b] break

	# Is the translated expression available in the predecessor already?
	set avail_out_p [lindex $pre_avail_out $p]
	if {![dict exists $avail_out_p $vprime]} {

	    # Not available - add it as something that needs to be evaluated
	    dict set avail $p $eprime
	    set all_same 0

	} else {

	    # It is available - add the temporary to the available set and
	    # update 'all_same'
	    set leader [dict get $avail_out_p $vprime]
	    set lexpr [list {} $leader]
	    dict set avail $p $lexpr
	    set by_some 1
	    if {![info exists first_s]} {
		set first_s $lexpr
	    } elseif {$first_s ne $lexpr} {
		set all_same 0
	    }
	}
    }

    # The expression will benefit from code motion at this point if
    # it is available in at least one predecessor, and it is not available
    # in the same SSA temporary in all predecessors. We also force code
    # motion if an expression is unavailable at a loop header

    if {($by_some && !$all_same)} {
	return $avail
    } else {
	return {}
    }
    
}
 
# quadcode::transformer method pre_insert_make_mods --
#
#	Inserts a phi at a merge point (and possible expression
#	evaluations above a merge point) to hoist one anticipated
#	expression above the merge.
#
# Parameters:
#	b - Basic block that the expression is leaving
#	v - Global value number of the expression
#	e - Expression being moved above block b
#	avail - Dictionary whose keys are the predecessor blocks
#	        and whose values are the expressions that need
#	        to be evaluated in the predecessors to make e
#	        fully available.
#
# Results:
#	Returns the name of the temporary that replaces the
#	expression in b.
#
# Side effects:
#	Adds any needed code to reify the expression in the predecessors,
#	and adds a phi at the start of b to pick up the expression value.
#	The value becomes available at the exit of b.
#
# The logic mostly follows Figure 4.9 on page 79 of [VanD04].

oo::define quadcode::transformer method pre_insert_make_mods {b v e avail} {

    my variable pre_avail_out

    my debug-pre {
	puts "Make value $v: $e available in block $b"
    }
    
    # Start building a phi to represent the temporary
    my debug-pre {
	puts "  Make temporary to hold $e at entry to block $b"
    }

    set outv [my pre_make_temp_for_expr $v $e]
    my debug-pre {
	puts "    Call it $outv!"

    }
    set phi [list phi $outv]
    dict set udchain $outv $b

    # Reify the expression in each predecessor block
    dict for {p eprime} $avail {

	my debug-pre {
	    puts "  Reify $eprime in block $p"
	}
	set argl [lassign $eprime opcode]
	if {$opcode ne {}} {



	    set avail_out_p [lindex $pre_avail_out $p]
	    my debug-pre {
		puts "   Avail values in $p before this mod are\
                         [dict keys $avail_out_p]"
	    }
	    lset pre_avail_out $p {}

	    # A complex expression actually needs to be evaluated
	    # in the predecessor block. Make the instruction and update
	    # ud- and du-chains
	    my debug-pre {
		puts "    Need to find temporary for value $v"
	    }
	    set t [my pre_make_temp_for_expr $v $eprime]
	    my debug-pre {
		puts "    Call it $t!"
	    }
	    dict set udchain $t $p
	    set tv [my pre_gvn_lookup_or_add $eprime]
	    my pre_gvn_add [list {} $t] $tv
	    set insn [list $opcode $t]
	    foreach a $argl {
		if {[lindex $a 0] ne "value"} {
		    lappend insn $a
		} else {
		    set v [lindex $a 1]
		    if {[dict exists $avail_out_p $v]} {
			set var [dict get $avail_out_p $v]
			my addUse $var $p
			lappend insn $var
		    } elseif {[my pre_gvn_is_literal $v lit]} {
			lappend insn $lit
		    } else {
			error "$v is unavailable at end of $p!"

		    }
		}


	    }

	    # Insert the instruction in the block
	    set pb [lindex $bbcontent $p]
	    lset bbcontent $p {}
	    my debug-pre {
		puts "  Add $insn before end of block $p"
	    }
	    set pb [linsert $pb[set pb ""] end-1 $insn]
	    lset bbcontent $p $pb
	    
	    # Make the value available at exit from the predecessor
	    my debug-pre {
		puts "  Add value $tv: $t to the avail set on output from $p"
	    }






	    dict set avail_out_p $tv $t
	    lset pre_avail_out $p $avail_out_p
	    my debug-pre {
		puts "  ... which is now [dict keys [lindex $pre_avail_out $p]]"

	    }
	    
	} else {

	    # A simple value is already available and just needs to go
	    # on the phi being constructed



	    




	    set t [lindex $argl 0]
	}

	# Add the reified value to the phi under construction
	lappend phi [list bb $p] $t
	my addUse $t $b

	
    }

    # Paste the newly-build phi at the start of the block
    my debug-pre {
	puts "Add $phi at the start of $b"
    }
    set bb [lindex $bbcontent $b]
    lset bbcontent $b {}
    set bb [linsert $bb[set bb {}] 0 $phi]
    lset bbcontent $b $bb

    # Make the value available at exit from the block




    set avail_out_b [lindex $pre_avail_out $b]
    lset pre_avail_out $b {}
    dict set avail_out_b $v $outv
    lset pre_avail_out $b $avail_out_b















    return $outv
}
 
# quadcode::transformer method pre_eliminate --
#
#	Eliminates redundant code once partial availability has been
#	resolved
#
................................................................................
#	None

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

    my variable pre_antic_in
    my variable pre_avail_out
    my variable pre_exp_gen
    my variable pre_new_sets
    my variable pre_phi_gen
    my variable pre_tmp_gen
    my variable pre_translate_cache
    my variable pre_vexprs
    my variable pre_vn

    unset -nocomplain pre_antic_in
    unset -nocomplain pre_avail_out
    unset -nocomplain pre_exp_gen
    unset -nocomplain pre_new_sets
    unset -nocomplain pre_phi_gen
    unset -nocomplain pre_tmp_gen
    unset -nocomplain pre_translate_cache
    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}
 
# quadcode::transformer method pre_make_temp_for_expr --
................................................................................
# Parameters:
#	es - Dictionary whose keys are global value numbers and
#	     whose values are expressions in the successor block
#	p - Predecessor block
#	s - Successor block
#
# Results:
#	Returns the translated expressions in the same dictionary
#	form as 'es'
#
# Side effects:
#	Caches the result of translation.
#
# Described on page 1 of [VaHo03].

oo::define quadcode::transformer method pre_phi_translate {es p s} {

    # Translate each expression in turn
    set translated {}
    dict for {v e} $es {
	lassign [my pre_phi_translate1 $v $e $p $s] newv newe
	dict set translated $newv $newe
    }
    return $translated
}
 
# quadcode::transformer method pre_phi_translate1 --
#
#	Translates an expression that is valid in a successof block to
#	one that is valid in a predecessor block.
#
# Parameters:


#	v - The expression's global value number
#	e - The expression being translated
#	p - The predecessor block
#	s - The successor block
#
# Results:
#	Returns the result of the translation
#
# Side effects:
#	Result is cached. The cache is necessary not only for speed but
#	also because 'pre_phi_insert' depends on being able to look up
#	an already-computed translation.

oo::define quadcode::transformer method pre_phi_translate1 {v e p s} {

    my variable pre_translate_cache
    my variable pre_phi_gen
    
    my debug-pre {
	puts "        Translate value $v: $e on edge $p -> $s"
    }

    set phis [lindex $pre_phi_gen $s]
    ;			       # Phi operations at the successor block
    set skey [list bb $p];     # Key for looking up predecessor value at a phi

    # Find the cached translations for this flowgraph edge. If this value
    # is already cached, return the translation


    if {[dict exists $pre_translate_cache $p $s]} {
	set es [dict get $pre_translate_cache $p $s]
    } else {
	set es {}
    }

    if {[dict exists $es $v]} {


	my debug-pre {
	    puts "        (cached) [dict get $es $v]"


	}













	return [dict get $es $v]
    }

    # Take apart the expression
    set argl [lassign $e opcode]
    set eout [list $opcode]

    if {$opcode eq {}} {

	# Translate a single SSA temporary
	set a [lindex $argl 0]
	if {[dict exists $phis $a $skey]} {
	    set a [dict get $phis $a $skey]
	}
	lappend eout $a

    } else {

	# Translate an expression that calculates something. All of its
	# dependent values will already have been translated. Rewrite
	# values, and leave other args unchanged.
	foreach a $argl {
	    if {[lindex $a 0] ne "value"} {
		lappend eout $a
	    } else {
		# The arg is 'value N', and we must have already translated
		# it. Retrieve it from the cache
		set vprime [lindex $a 1]
		if {[dict exists $es $vprime]} {




		    lappend eout [list value [lindex [dict get $es $vprime] 0]]

		} else {
		    error "$p->$s Value $vprime is not cached, but $e depends on it?"
		}
	    }
	}
    }

    set vout [my pre_gvn_lookup_or_add $eout]
    set result [list $vout $eout]
    dict set pre_translate_cache $p $s $v $result

    my debug-pre {
	puts "        result is value $vout: $eout"

    }
    
    return $result
}
 
# quadcode::transformer method pre_clean --
#






<
<
<
<







 







|







 







<
<




<







 







<


>
|
>
>
>
>
|







 







|
>
>
>
>
>





<





|
|
<
<





|
>
>
>
>
>

<
>


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


|
|


|
<
<
>
>
>


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

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|

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



|

|


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

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

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

>
>
>
>
>
>
>
>
>
>
|







 







<


<






<


<







 







|
|
|
|
|
|







|
|










>
>







|
<
<
<
<
<
|

<








|

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







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



>


<
>

<
>







111
112
113
114
115
116
117




118
119
120
121
122
123
124
...
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
...
570
571
572
573
574
575
576


577
578
579
580

581
582
583
584
585
586
587
...
626
627
628
629
630
631
632

633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
...
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
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
952
953


954

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
....
1106
1107
1108
1109
1110
1111
1112

1113
1114

1115
1116
1117
1118
1119
1120

1121
1122

1123
1124
1125
1126
1127
1128
1129
....
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203





1204
1205

1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220



1221
1222
1223
1224
1225
1226

1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
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
1266

1267
1268
1269
1270
1271
1272

1273
1274

1275
1276
1277
1278
1279
1280
1281
1282
# phi operations will have become worthless, either because two such
# operations become the same operation, or because all inputs to a phi
# become the same input. It may be necessary to repeat this
# optimization after cleaning up useless phi's.

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





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

    # 0. Initialize the global variable numbering tables.

................................................................................
	    # others.
	    if {$op eq "phi"} {

		# phi - give the result a unique value number, and add it
		#       to phi_gen
		set expr [list {} $result]
		set v [my pre_gvn_lookup_or_add $expr]
		dict set phi_gen_b $result $argl

	    } elseif {$op eq "copy"} {

		# copy - give the result the same value number as the source.
		set src [lindex $argl 0]
		set expr [list {} $result]
		set srcexpr [list {} $src]
................................................................................
    my variable pre_tmp_gen
    my variable pre_phi_gen

    my variable pre_avail_out

    my variable pre_antic_in
    


    # Initialize anticipable sets to empty. This initial value should
    # be accessed only in the case of an infinite loop, whose blocks will
    # have no postdominators.
    set pre_antic_in [lrepeat [llength $bbcontent] {}]


    # Calculate the retrograde order in which blocks are to be visited
    set bs [my bbrorder]

    # Iterate to convergence
    set changed 1
    while {$changed} {
................................................................................
		set antic_in_f [lindex $pre_antic_in $f]
		my debug-pre {
		    puts "      which has anticipable values:"
		    dict for {vvv eee} $antic_in_f {
			puts "        value $vvv = $eee"
		    }
		}

		my debug-pre {
		    puts "      giving anticipable values on output of $b:"
		}
		set antic_out {}
		dict for {olde pair} [my pre_phi_translate $antic_in_f $b $f] {
		    lassign $pair newv newe
		    dict set antic_out $newv $newe
		    my debug-pre {
			puts "        value $newv: $newe"
		    }
		}
		
	    } else {

		my debug-pre {
		    puts "      has multiple successors: $succs"
................................................................................
#	'copy' and 'phi' instructions are inserted in the quadcode
#	to make fully anticipable expressions available at merge
#	points where they are only partially available. This process
#	involves inserting computation of the needed expressions
#	on any predecessors where they are not available, and then
#	introducing a phi operation to combine the new expressions.
#
# Figures 4.8-4.9 on pp. 78-79 of [VanD04]. Note that the logic in
# [VanD04], despite the length of the algorithm, is pretty sketchy. In
# particular, there's no indication of how 'new_sets' is used - it's
# constructed, but not referred to.  In addition, the information for
# 'phi_translate' is also unclear. We try to replicate here from
# first principles.

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

    my variable pre_antic_in
    my variable pre_avail_out

    
    my debug-pre {
	puts "Try to find code insertion points"
    }

    # This procedure iterates to convergence. 'changed' tracks whether
    # we did anything on a single pass.


    set did_something 0
    set changed 1
    while {$changed} {
	set changed 0

	# new_sets contains the newly introduced phi's. It is a list indexed
	# by basic block number, whose elements are dictionaries mapping
	# global value number to the term in the phi operation.
	set new_sets {}

	# Iterate through the basic blocks
	set b -1

	foreach antin $pre_antic_in preds $bbpred dom $bbidom {
	    incr b





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

	    # Inherit the set of created phi's from the block's
	    # dominator, and make them available on the block's output
	    if {$b > 0} {
		set new_phis [lindex $new_sets $dom]
	    } else {
		set new_phis {}
	    }
	    lappend new_sets $new_phis
	    set avail_out_b [lindex $pre_avail_out $b]
	    lset pre_avail_out $b {}
	    dict for {v phi} $new_phis {
		dict set avail_out_b $v $phi
	    }
	    lset pre_avail_out $b $avail_out_b



	    # If the block has more than one predecessor, it's a potential
	    # place for a phi to be inserted

	    if {[dict size $preds] > 1} {


		my debug-pre {
		    puts "    bb $b is a merge point"
		}

		# What expressions are available from the block's dominator?
		set avail_out_d [lindex $pre_avail_out $dom]

		# Find the translations for the anticipable values
		set translated_p {}
		dict for {p -} $preds {
		    dict set translated_p $p [my pre_phi_translate $antin $p $b]
		}

		# Potential phis correspond to all anticipable
		# expressions in the block. (We will downselect to
		# those that are partially available - that is,
		# complex expressions that are available in at least
		# one predecessor but not in all.)
		dict for {v e} $antin {

		    my debug-pre {
			puts "    examine anticipated value $v: $e"
		    }
		    lassign $e opcode argl

		    # A simple variable must be fully available
		    if {$opcode == {}} {
			my debug-pre {
			    puts "      it's a simple value, can't need a phi"
			}
			continue
		    }

		    # A value that is available from the dominator is
		    # fully available
		    if {[dict exists $avail_out_d $v]} {
			my debug-pre {

			    puts "      it's available in the dominator,\
                                        can't need a phi."
			}
			continue
		    }

		    # Go through the predecessors and find the leaders
		    # that supply the value. Set avail to the
		    # expressions that compute the value in the
		    # predecessors; by_some to indicate whether any
		    # predecessor has the value available, and
		    # all_same to indicate whether all predecessors
		    # have the value available in the same place.
		    set avail {}
		    set by_some 0
		    set all_same 1
		    unset -nocomplain first_s
		    dict for {p trans} $translated_p {
			lassign [dict get $trans $v] v1 e1
			set avail_out_p [lindex $pre_avail_out $p]
			if {![dict exists $avail_out_p $v1]} {

			    my debug-pre {
				puts "      it's unavailable in predecessor $p"
			    }
			    # The value is unavailable in the predecessor
			    dict set avail $p [list $v1 $e1]

			    set all_same 0
			} else {

			    # The value is available as e2 in the predecessor
			    set var2 [dict get $avail_out_p $v1]
			    set e2 [list {} $var2]
			    my debug-pre {
				puts "      it's available as $var2 in\
                                            predecessor $p"
			    }
			    set e2 [list {} $var2]
			    dict set avail $p [list $v1 $e2]
			    set by_some 1
			    if {![info exists first_s]} {
				set first_s $e2
			    } elseif {$first_s ne $e2} {
				set all_same 0
			    }
			}
		    }

		    # If the value is fully available or not available,
		    # there's nothing to do
		    if {$all_same} {
			my debug-pre {
			    puts "    it's fully available in block $b"
			}
			continue
		    }
		    if {!$by_some} {
			my debug-pre {
			    puts "    it's unavailable in block $b"
			}
			continue
		    }

		    my debug-pre {
			puts "    it's partially available in block $b"
		    }

		    # Rewrite the code to make the value available
		    dict for {p pair} $avail {



			# Examine a predecessor block to see if the value is
			# available
			lassign $pair v1 e1
			set argl [lassign $e1 opcode]
			if {[lindex $e1 0] eq {}} {



























































			    # The value is available, we're done
			    continue
			}


















































































































































			# Create a temp to hold the value in the predecessor
			set t [my pre_make_temp_for_expr $v $e]
			my debug-pre {

			    puts "    Created $t to hold $e1 in $p"
			}

			dict set udchain $t $p










			# Create an instruction to evaluate the value in
			# the predecessor
			set avail_out_p [lindex $pre_avail_out $p]



















			set insn [list $opcode $t]
			foreach a $argl {
			    if {[lindex $a 0] ne "value"} {
				lappend insn $a
			    } else {


				set s1 [dict get $avail_out_p [lindex $a 1]]

				lappend insn $s1




				my addUse $s1 $p
			    }
			}
			my debug-pre {
			    puts "    Add $insn at the end of block $p"
			}


			set bb [lindex $bbcontent $p]
			lset bbcontent $p {}



			set bb [linsert $bb[set bb ""] end-1 $insn]
			lset bbcontent $p $bb





			# Track that the new instruction is the leader for
			# the value,
			set texpr [list {} $t]
			my pre_gvn_add $texpr $v1
			set avail_out_p [lindex $pre_avail_out $p]
			lset pre_avail_out $p {}
			dict set avail_out_p $v1 $t
			lset pre_avail_out $p $avail_out_p


			dict set avail $p [list $v1 $texpr]

		    }




		    # Make the temporary to hold the phi result
		    set t [my pre_make_temp_for_expr $v $e]
		    dict set udchain $t $b

		    # Make the phi instruction
		    set insn [list phi $t]
		    dict for {p pair} $avail {
			lassign $pair v1 e1
			set invar [lindex $e1 1]




			my addUse $invar $b
			lappend insn [list bb $p] $invar
		    }



		    my debug-pre {
			puts "insert $insn at the start of $b"
		    }
		    set bb [lindex $bbcontent $b]
		    lset bbcontent $b {}
		    set bb [linsert $bb[set bb ""] 0 $insn]
		    lset bbcontent $b $bb
		    

		    # Record the phi result in the avail set and the
		    # new_sets 
		    set texpr [list {} $t]
		    my pre_gvn_add $texpr $v
		    set avail_out_b [lindex $pre_avail_out $b]
		    lset pre_avail_out $b {}
		    dict set avail_out_b $v $t
		    lset pre_avail_out $b $avail_out_b
		    set new_sets_b [lindex $new_sets $b]
		    lset new_sets $b {}
		    dict set new_sets_b $v $t
		    lset new_sets $b $new_sets_b

		    # Record that we modified the code

		    set changed 1
		    set did_something 1
		}

	    }
	}
    }

    return $did_something
}
 
# quadcode::transformer method pre_eliminate --
#
#	Eliminates redundant code once partial availability has been
#	resolved
#
................................................................................
#	None

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

    my variable pre_antic_in
    my variable pre_avail_out
    my variable pre_exp_gen

    my variable pre_phi_gen
    my variable pre_tmp_gen

    my variable pre_vexprs
    my variable pre_vn

    unset -nocomplain pre_antic_in
    unset -nocomplain pre_avail_out
    unset -nocomplain pre_exp_gen

    unset -nocomplain pre_phi_gen
    unset -nocomplain pre_tmp_gen

    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}
 
# quadcode::transformer method pre_make_temp_for_expr --
................................................................................
# Parameters:
#	es - Dictionary whose keys are global value numbers and
#	     whose values are expressions in the successor block
#	p - Predecessor block
#	s - Successor block
#
# Results:
#	Returns the translated expressions as a dictionary. The keys are
#	value numbers in the successor block, and the values are ordered
#	pairs giving the value number in the predecessor and the expression
#	in the predecessor.
#

# Described on page 1 of [VaHo03].

oo::define quadcode::transformer method pre_phi_translate {es p s} {

    # Translate each expression in turn
    set translated {}
    dict for {v e} $es {
	lassign [my pre_phi_translate1 $translated $v $e $p $s] newv newe
	dict set translated $v [list $newv $newe]
    }
    return $translated
}
 
# quadcode::transformer method pre_phi_translate1 --
#
#	Translates an expression that is valid in a successof block to
#	one that is valid in a predecessor block.
#
# Parameters:
#	translated - Expressions translated already in the current block
#	             Keys are value numbers, values are the translations
#	v - The expression's global value number
#	e - The expression being translated
#	p - The predecessor block
#	s - The successor block
#
# Results:
#	Returns the result of the translation






oo::define quadcode::transformer method pre_phi_translate1 {es v e p s} {


    my variable pre_phi_gen
    
    my debug-pre {
	puts "        Translate value $v: $e on edge $p -> $s"
    }

    set phis [lindex $pre_phi_gen $s]
    ;			       # Phi operations at the successor block
    set pkey [list bb $p];     # Key for looking up predecessor value at a phi

    # Handle temporaries by mapping them through any phis
    if {[lindex $e 0] eq {}} {
	set t [lindex $e 1]

	if {[dict exists $phis $t $pkey]} {




	    # temporary participates in a phi
	    set tprime [dict get $phis $t $pkey]
	    set eprime [list {} $tprime]
	    set vprime [my pre_gvn_lookup $eprime]
	    my debug-pre {

		puts "          value $v: $t in $s maps to\
                                value $vprime: $tprime in $p"
	    }
	    return [list $vprime $eprime]
	} else {
	    my debug-pre {
		puts "          value $v: $t does not appear in a phi in $s,\
                                so it maps to itself in $p"
	    }
	    return [list $v $e]
	}
    }
    
    # Handle complex expressions by finding them in the set that have
    # already been translated
    if {[dict exists $es $v]} {
	return [dict get $es $v]
    }

    # Take apart the expression
    set argl [lassign $e opcode]
    set eout [list $opcode]

    # Translate the args to the expression.













    foreach a $argl {
	if {[lindex $a 0] ne "value"} {
	    lappend eout $a
	} else {
	    # The arg is 'value N', and we must have already translated
	    # it. Retrieve it from the cache
	    set vprime [lindex $a 1]
	    if {[dict exists $es $vprime]} {
		lassign [dict get $es $vprime] v2 e2
		if {$v2 < 0} {
		    lappend eout [lindex $e2 1]
		} else {
		    lappend eout [list value $v2]
		}
	    } else {
		error "$p->$s Value $vprime is not cached, but $e depends on it?"

	    }
	}
    }

    set vout [my pre_gvn_lookup_or_add $eout]
    set result [list $vout $eout]


    my debug-pre {

	puts "          value $v: $e in $s maps to value $vout: $eout in $p"
    }
    
    return $result
}
 
# quadcode::transformer method pre_clean --
#