Check-in [ce1088b7a7]
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:Fix crashing bug in creating variable name for a phi operation. Fix bug where partial redundancy elimination got stale dominators, causing much weirdness. Add additional tracing to available expression calculation.
Timelines: family | ancestors | descendants | both | notworking | kbk-pre
Files: files | file ages | folders
SHA3-256: ce1088b7a768b200da743ec9449555c5ccafaf37e38b70e2f8d93ad9778606a3
User & Date: kbk 2018-12-03 01:06:14
Context
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
01:06
Fix crashing bug in creating variable name for a phi operation. Fix bug where partial redundancy elimination got stale dominators, causing much weirdness. Add additional tracing to available expression calculation. check-in: ce1088b7a7 user: kbk tags: notworking, kbk-pre
2018-12-02
23:27
Turn on partial redundancy elimination. Correct bug in availability analysis that led to infinite loop in 'msrange2' check-in: 68da56cfee user: kbk tags: notworking, kbk-pre
Changes

Changes to quadcode/pre.tcl.

466
467
468
469
470
471
472



473

474
475
476
477
478
479
480
...
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
....
1031
1032
1033
1034
1035
1036
1037




1038
1039
1040
1041
1042
1043
1044
....
1067
1068
1069
1070
1071
1072
1073



1074
1075



1076
1077
1078
1079
1080
1081
1082
....
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
	puts "  Compute available exprs at merge point $b"
    }

    # A merge point may need to have phi's inserted. Start with the values
    # that are available from the dominator.

    set avail_in [lindex $pre_avail_out [lindex $bbidom $b]]





    # Merge in any values that arrive from all predecessors but
    # do not originate in the dominator
    set firsttime 1
    set newphis {}
    dict for {p -} $preds {
	set avout_p [lindex $pre_avail_out $p]
	my debug-pre {
................................................................................
		} else {
		    dict set newphis $v [list bb $p] [dict get $avout_p $v]
		}
	    }
	}
    }

    if {[dict size $newphis] == 0} {
	return $avail_in
    }

    # Create any speculative phis
    set newbb {}
    dict for {v argl} $newphis {
	dict for {- var} $argl break
	set var [my newVarInstance $var]
	dict for {frombb in} $argl {
	    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]





    return $avail_in
    
}

 
# quadcode::transformer method pre_buildsets2 --
#
................................................................................
	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]




	    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"
................................................................................
	    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



	    dict set avail_out_p $tv $t
	    lset pre_avail_out $p $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]
................................................................................
	    set cname [lindex $c 1]
	    if {[lindex $cname 0] eq "var" || [lindex $tempname 0] ne "var"} {
		set tempname $cname
	    }
	}
    }

    return [my newVarInstance $cname]
}
 
# quadcode::transformer method pre_phi_translate --
#
#	Translates a set of expressions that are valid in a successor
#	block to ones that are valid in the predecessor block
#






>
>
>
|
>







 







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







 







>
>
>
>







 







>
>
>


>
>
>







 







|







466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
...
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
534
535
536
....
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
....
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
....
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
	puts "  Compute available exprs at merge point $b"
    }

    # A merge point may need to have phi's inserted. Start with the values
    # that are available from the dominator.

    set avail_in [lindex $pre_avail_out [lindex $bbidom $b]]
    my debug-pre {
	puts "Available from dominator [lindex $bbidom $b]:\
              [dict keys $avail_in]"
    }
    
    # Merge in any values that arrive from all predecessors but
    # do not originate in the dominator
    set firsttime 1
    set newphis {}
    dict for {p -} $preds {
	set avout_p [lindex $pre_avail_out $p]
	my debug-pre {
................................................................................
		} else {
		    dict set newphis $v [list bb $p] [dict get $avout_p $v]
		}
	    }
	}
    }

    if {[dict size $newphis] > 0} {



	# Create any speculative phis
	set newbb {}
	dict for {v argl} $newphis {
	    dict for {- var} $argl break
	    set var [my newVarInstance $var]
	    dict for {frombb in} $argl {
		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]
    }
	
    my debug-pre {
	puts "  Available on entry to $b: [dict keys $avail_in]"
    }
    return $avail_in
    
}

 
# quadcode::transformer method pre_buildsets2 --
#
................................................................................
	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"
................................................................................
	    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]
................................................................................
	    set cname [lindex $c 1]
	    if {[lindex $cname 0] eq "var" || [lindex $tempname 0] ne "var"} {
		set tempname $cname
	    }
	}
    }

    return [my newVarInstance $tempname]
}
 
# quadcode::transformer method pre_phi_translate --
#
#	Translates a set of expressions that are valid in a successor
#	block to ones that are valid in the predecessor block
#

Changes to quadcode/ssa.tcl.

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
...
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
 

# bbidom --
#
#	Compute the immediate dominators of the basic blocks
#
# Results:
#	None.
#
# Side effects:
#	Sets 'bbidom' to a list of immediate dominators, indexed by
#	basic block number.
#	Sets 'bbkids' to a list indexed by basic block numbers of the
#	blocks that are immediately dominated by the block.
#
................................................................................
    my debug-ssa {
	puts "after computing dominance relations:"
	set i -1
	foreach id $bbidom kid $bbkids {
	    puts "[incr i]: idom $id kids $kid"
	}
    }
    return
}
 
# quadcode::transformer method bblevel -
#
#	Calculate level numbering in the dominance tree
#
# Preconditions:
#	The 'bbkids' relation must contain the lists of blocks immediately
#	dominated (the inverse of the 'idom' relationship).
#
# Results:
#	None.
#
# Side effects:
#	'bblevel' is updated for the current block's subtree

oo::define quadcode::transformer method bblevel {} {
    set bblevel [lrepeat [llength $bbkids] -1]
    set bbnlevels -1
    my bblevel-worker 0 0
    my debug-ssa {
	puts "bblevel $bblevel"
    }

}
oo::define quadcode::transformer method bblevel-worker {blk level} {
    lset bblevel $blk $level
    if {$level > $bbnlevels} {
	set bbnlevels $level
    }
    incr level






|







 







|











|











>







63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
...
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
 

# bbidom --
#
#	Compute the immediate dominators of the basic blocks
#
# Results:
#	Returns zero.
#
# Side effects:
#	Sets 'bbidom' to a list of immediate dominators, indexed by
#	basic block number.
#	Sets 'bbkids' to a list indexed by basic block numbers of the
#	blocks that are immediately dominated by the block.
#
................................................................................
    my debug-ssa {
	puts "after computing dominance relations:"
	set i -1
	foreach id $bbidom kid $bbkids {
	    puts "[incr i]: idom $id kids $kid"
	}
    }
    return 0
}
 
# quadcode::transformer method bblevel -
#
#	Calculate level numbering in the dominance tree
#
# Preconditions:
#	The 'bbkids' relation must contain the lists of blocks immediately
#	dominated (the inverse of the 'idom' relationship).
#
# Results:
#	Returns zero.
#
# Side effects:
#	'bblevel' is updated for the current block's subtree

oo::define quadcode::transformer method bblevel {} {
    set bblevel [lrepeat [llength $bbkids] -1]
    set bbnlevels -1
    my bblevel-worker 0 0
    my debug-ssa {
	puts "bblevel $bblevel"
    }
    return 0
}
oo::define quadcode::transformer method bblevel-worker {blk level} {
    lset bblevel $blk $level
    if {$level > $bbnlevels} {
	set bbnlevels $level
    }
    incr level

Changes to quadcode/transformer.tcl.

601
602
603
604
605
606
607


608
609
610
611
612
613
614
	    cleanupCallFrameUse
	    cleanupNarrow
	    deadjump
	    deadbb
	    deadvars
	    uselessphis
	    constfold


	    partialredundancy
	} {
	    set cmd [string map [list @pass $pass] {
		set result [my @pass]
	    }]
	    lappend timings $pass [lindex [time $cmd] 0]
	    if {$result} {






>
>







601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
	    cleanupCallFrameUse
	    cleanupNarrow
	    deadjump
	    deadbb
	    deadvars
	    uselessphis
	    constfold
	    bbidom
	    bblevel
	    partialredundancy
	} {
	    set cmd [string map [list @pass $pass] {
		set result [my @pass]
	    }]
	    lappend timings $pass [lindex [time $cmd] 0]
	    if {$result} {