Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | 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! |
---|---|
Timelines: | family | ancestors | descendants | both | kbk-pre |
Files: | files | file ages | folders |
SHA3-256: |
cf87d02677dd17f6205cfefbdd7b4d8e |
User & Date: | kbk 2018-12-06 03:13:08.016 |
Context
2018-12-06
| ||
03:15 | Merge kbk-pre - add the optimizations of loop inversion (enables loop-invariant code motion) and partial redundancy elimination, and fix multiple bugs exposed by these optimizations. check-in: 0e06123e97 user: kbk tags: trunk | |
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 | |
Changes
Changes to quadcode/pre.tcl.
︙ | ︙ | |||
67 68 69 70 71 72 73 | dictAppend dictExists dictGet dictGetOrNexist dictLappend dictSet dictSetOrUnset dictSize dictUnset div eq expand exists expon extractArray extractCallFrame extractExists extractFail extractMaybe extractScalar frameArgs frameDepth ge gt | | | 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | dictAppend dictExists dictGet dictGetOrNexist dictLappend dictSet dictSetOrUnset dictSize dictUnset div eq expand exists expon extractArray extractCallFrame extractExists extractFail extractMaybe extractScalar frameArgs frameDepth ge gt initIfNotExists instanceOf isBoolean le listAppend listConcat listIn listIndex listLength listRange listSet lshift lt maptoint mod moveFromCallFrame mult narrowToType neq not |
︙ | ︙ | |||
112 113 114 115 116 117 118 | # 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 | | | 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | # 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. |
︙ | ︙ | |||
183 184 185 186 187 188 189 | my audit-duchain pre-3 my audit-phis pre-3 } trouble opts]} { puts stderr "TROUBLE: $trouble" return -options ${opts} $trouble } set did_something [my pre_insert] | < < < < < < < < < < < < < < < | > > > > | 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 | my audit-duchain pre-3 my audit-phis pre-3 } trouble opts]} { puts stderr "TROUBLE: $trouble" return -options ${opts} $trouble } set did_something [my pre_insert] # 4. Rewrite the program to replace calculations of available values # with copies from the temps that hold the values if {[catch { my audit-duchain pre-4 my audit-phis pre-4 } trouble opts]} { puts stderr "TROUBLE: $trouble" return -options ${opts} $trouble } if {[my pre_eliminate]} { set did_something 1 } # 5. 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 # 6. Now, dead code elimination and copy propagation will eliminate # any messes that step 4 left behind. return $did_something } # quadcode::transformer method pre_init -- # # Initializes the tables for global value numbering and partial |
︙ | ︙ | |||
787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 | 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 | > > > > > > < < < < < > | | | | | | > | | | 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 | my variable pre_antic_in my variable pre_avail_out my debug-pre { puts "Try to find code insertion points" } # 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 {} # This procedure iterates to convergence. 'changed' tracks whether # we did anything on a single pass. set did_something 0 set changed 1 set did_phis {} while {$changed} { set changed 0 # 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 {[llength $new_sets] == $b} { 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 e} [lindex $new_sets $b] { dict set avail_out_b $v $e } 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} { |
︙ | ︙ | |||
866 867 868 869 870 871 872 | continue } # A value that is available from the dominator is # fully available if {[dict exists $avail_out_d $v]} { my debug-pre { | | > > > > | > > > > > > | 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 | 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 already\ as [dict get $avail_out_b $v]" } continue } # A value that we made a phi for already is fully available if {[dict exists [lindex $new_sets $b] $v]} { my debug-pre { puts " it's already been processed as\ [dict get [lindex $new_sets $b] $v]" } continue } # Go through the predecessors and find the leaders # that supply the value. Set avail to the # expressions that compute the value in the |
︙ | ︙ |