Check-in [bd6294fade]
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:Remove speculative phis if they turned out not to be useful
Timelines: family | ancestors | descendants | both | notworking | kbk-pre
Files: files | file ages | folders
SHA3-256: bd6294fade404264738227f1ec5f9e5aebb25ccb517a67d3e0d31b3feba97481
User & Date: kbk 2018-12-06 01:42:44
Context
2018-12-06
03:13
Array initialization cannot be hoisted because every array needs its own initArray. Code insertion must ignore operations that it has already inserted, or infinite loops can result. All tests pass! Closed-Leaf check-in: cf87d02677 user: kbk tags: kbk-pre
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
Changes

Changes to quadcode/pre.tcl.

111
112
113
114
115
116
117



118
119
120
121
122
123
124
...
209
210
211
212
213
214
215
216
217








218
219
220
221
222
223
224
...
255
256
257
258
259
260
261

262
263
264
265
266

267
268
269
270
271
272
273
...
439
440
441
442
443
444
445

446
447
448
449
450
451
452
...
512
513
514
515
516
517
518

519
520
521
522
523
524
525
....
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
# 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.

................................................................................
    if {[catch {
	my audit-duchain pre-5
	my audit-phis pre-5
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }
    my pre_cleanup









    return $did_something

}
 
# quadcode::transformer method pre_init --
#
#	Initializes the tables for global value numbering and partial
................................................................................

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

    my variable pre_exp_gen
    my variable pre_phi_gen
    my variable pre_tmp_gen
    my variable pre_avail_out


    set pre_exp_gen {}
    set pre_phi_gen {}
    set pre_tmp_gen {}
    set pre_avail_out [lrepeat [llength $bbcontent] {}]


    variable ::quadcode::gvn_eliminable

    # Walk through basic blocks in the forward direction
    set b -1
    foreach bb $bbcontent {
	incr b
................................................................................
# This is less general than the phi-insertion step of [Chow97], but
# the case of values that are both partially available and partially
# anticipable is more complex than we are attempting yet.

oo::define quadcode::transformer method pre_avail_in {b bbVar} {

    my variable pre_avail_out


    upvar 1 $bbVar bb

    set preds [lindex $bbpred $b]
    set n [dict size $preds]
    if {$n == 0} {

................................................................................
		my addUse $in $b
	    }
	    set insn [linsert $argl 0 phi $var]
	    my debug-pre {
		puts "  Speculative: $b:[llength $newbb]: $insn"
	    }
	    dict set udchain $var $b

	    lappend newbb $insn
	    my pre_gvn_add [list {} $var] $v
	    dict set avail_in $v $var
	}
	set bb [linsert $bb[set bb ""] 0 {*}$newbb]
    }
	
................................................................................
	    lappend newbb $q
	}
	lset bbcontent $b $newbb
    }

    return $changed
}
 































































# quadcode::transformer method pre_cleanup --
#
#	Clean up globals left behind by partial redundancy elimination
#
# Results:
#	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
}
 






>
>
>







 







<

>
>
>
>
>
>
>
>







 







>





>







 







>







 







>







 








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


|










>








>







111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
...
212
213
214
215
216
217
218

219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
...
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
...
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
...
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
....
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
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
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
# 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 {} {

    variable ::quadcode::pre_iteration
    puts "[my full-name] attempt [incr pre_iteration]"

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

    # 0. Initialize the global variable numbering tables.

................................................................................
    if {[catch {
	my audit-duchain pre-5
	my audit-phis pre-5
    } trouble opts]} {
	puts stderr "TROUBLE: $trouble"
	return -options ${opts} $trouble
    }


    # 6. If we inserted any phis speculatively, and we didn't use any of them,
    #    clean them up so that we can return 'false' for did_something and
    #    not fight with dead code removal. Then clean up working storage

    if {!$did_something} {
	my pre_remove_speculative_phis
    }
    my pre_cleanup
    return $did_something

}
 
# quadcode::transformer method pre_init --
#
#	Initializes the tables for global value numbering and partial
................................................................................

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

    my variable pre_exp_gen
    my variable pre_phi_gen
    my variable pre_tmp_gen
    my variable pre_avail_out
    my variable pre_speculative_phis

    set pre_exp_gen {}
    set pre_phi_gen {}
    set pre_tmp_gen {}
    set pre_avail_out [lrepeat [llength $bbcontent] {}]
    set pre_speculative_phis {}

    variable ::quadcode::gvn_eliminable

    # Walk through basic blocks in the forward direction
    set b -1
    foreach bb $bbcontent {
	incr b
................................................................................
# This is less general than the phi-insertion step of [Chow97], but
# the case of values that are both partially available and partially
# anticipable is more complex than we are attempting yet.

oo::define quadcode::transformer method pre_avail_in {b bbVar} {

    my variable pre_avail_out
    my variable pre_speculative_phis

    upvar 1 $bbVar bb

    set preds [lindex $bbpred $b]
    set n [dict size $preds]
    if {$n == 0} {

................................................................................
		my addUse $in $b
	    }
	    set insn [linsert $argl 0 phi $var]
	    my debug-pre {
		puts "  Speculative: $b:[llength $newbb]: $insn"
	    }
	    dict set udchain $var $b
	    dict set pre_speculative_phis $b $var {}
	    lappend newbb $insn
	    my pre_gvn_add [list {} $var] $v
	    dict set avail_in $v $var
	}
	set bb [linsert $bb[set bb ""] 0 {*}$newbb]
    }
	
................................................................................
	    lappend newbb $q
	}
	lset bbcontent $b $newbb
    }

    return $changed
}
 
# quadcode::transformer method pre_remove_speculative_phis --
#
#	Removes any speculatively-inserted phis after partial redundancy
#	elimination is complete
#
# Results:
#	None.
#
# Side effects:
#	Speculative phis are removed.
#
# This method must execute if and only if the partial reduncancy
# elimination modified no code other than the speculatively-inserted
# phi operations. They are _ipso facto_ unused.
#
# If this step were not to take place, we'd have to return 'changed' in
# order to recalculate types, which would check for further optimizations,
# remove the speculative phis in dead code removal, and then reinvoke
# this method, which would put them back in.

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

    my variable pre_speculative_phis

    my debug-pre {
	puts "Remove any speculative phi instructions"
	dict for {b vars} $pre_speculative_phis {
	    puts "$b: [dict keys $vars]"
	}
    }

    # Walk through the speculative phis, grouped by block
    dict for {b phis} $pre_speculative_phis {

	# Get the basic block content and walk through the instructions
	set bb [lindex $bbcontent $b]
	set newbb {}
	lset bbcontent $b {}
	set pc -1
	foreach q $bb {
	    incr pc
	    set res [lindex $q 1]

	    # Delete any instruction that is a speculative phi
	    if {![dict exists $phis $res]} {
		lappend newbb $q
	    } else {
		my debug-pre {
		    puts "  $b:$pc: $q"
		}
		dict unset udchain $res
		foreach {- v} [lrange $q 2 end] {
		    my removeUse $v $b
		}
	    }
	}

	# Put the new basic block content back
	lset bbcontent $b $newbb
    }
    return
}
 
# quadcode::transformer method pre_cleanup --
#
#	Cleans up globals left behind by partial redundancy elimination
#
# Results:
#	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_speculative_phis
    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_speculative_phis
    unset -nocomplain pre_tmp_gen
    unset -nocomplain pre_vexprs
    unset -nocomplain pre_vn

    return
}
 

Changes to quadcode/transformer.tcl.

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
		my audit-phis $pass
	    }
	    my debug-tidy {
		lappend debugLine $result
	    }
	}
	my debug-tidy {
	    puts $debugLine
	}
	if {$changed} {
	    set somethingChanged 1
	}
    }

    # If any of these changes actually changed anything, it may
    # have narrowed types, so we need to return for more interprocedural
    # type analysis
    if {$somethingChanged} {
	return 1
    }


	
    my bbidom
    my bblevel
	
    # TODO - Add partialredundancy!

    return $somethingChanged

}
 
# quadcode::transformer method sourceFile --
#
#	Returns the source file that this module was compiled from






|









<
<
|
>
>
|
<
<
<
<
<







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
		my audit-phis $pass
	    }
	    my debug-tidy {
		lappend debugLine $result
	    }
	}
	my debug-tidy {
	    puts "$debugLine -- $changed"
	}
	if {$changed} {
	    set somethingChanged 1
	}
    }

    # If any of these changes actually changed anything, it may
    # have narrowed types, so we need to return for more interprocedural
    # type analysis


	
    my debug-tidy {
	puts "tidy: did something change? $somethingChanged"
    }





    return $somethingChanged

}
 
# quadcode::transformer method sourceFile --
#
#	Returns the source file that this module was compiled from