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: |
ce1088b7a768b200da743ec9449555c5 |
User & Date: | kbk 2018-12-03 01:06:14.621 |
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 | 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]] | > > > | > | 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 | 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 { |
︙ | ︙ | |||
494 495 496 497 498 499 500 | } else { dict set newphis $v [list bb $p] [dict get $avout_p $v] } } } } | | < | < | | | | | | | | | | | | | | | | | | | > > > > | 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 | } 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 -- # |
︙ | ︙ | |||
1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 | 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" | > > > > | 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 | 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" |
︙ | ︙ | |||
1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 | 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] | > > > > > > | 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 | 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] |
︙ | ︙ | |||
1241 1242 1243 1244 1245 1246 1247 | set cname [lindex $c 1] if {[lindex $cname 0] eq "var" || [lindex $tempname 0] ne "var"} { set tempname $cname } } } | | | 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 | 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 | # bbidom -- # # Compute the immediate dominators of the basic blocks # # Results: | | | 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | # 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. # |
︙ | ︙ | |||
175 176 177 178 179 180 181 | my debug-ssa { puts "after computing dominance relations:" set i -1 foreach id $bbidom kid $bbkids { puts "[incr i]: idom $id kids $kid" } } | | | > | 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 | 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} { |
︙ | ︙ |