Check-in [cf87d02677]
Bounty program for improvements to Tcl and certain Tcl packages.

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: cf87d02677dd17f6205cfefbdd7b4d8e6587d7413dfd6f0ac5597cbd8517f62d
User & Date: kbk 2018-12-06 03:13:08
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
74
75
76
77
78
79
80
81
...
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
...
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
224
225
226
227




228
229
230
231
232
233
234
...
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
...
866
867
868
869
870
871
872
873
874










875
876
877
878
879
880
881
	    dictAppend dictExists dictGet dictGetOrNexist
	    dictLappend dictSet dictSetOrUnset dictSize dictUnset
	    div
	    eq expand exists expon extractArray extractCallFrame extractExists
	    extractFail extractMaybe extractScalar
	    frameArgs frameDepth
	    ge gt
	    initArray initArrayIfNotExists initIfNotExists
	    instanceOf isBoolean
	    le
	    listAppend listConcat listIn listIndex listLength listRange
	    listSet
	    lshift lt
	    maptoint mod moveFromCallFrame mult
	    narrowToType neq not
................................................................................
# 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.
................................................................................
	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]
    if {$did_something} {
	puts "pre_insert did something!"
    }

    # 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]} {
	puts "Eliminate did something!"
	set did_something 1
    }

    # 5. Now, dead code elimination and copy propagation will eliminate
    #    any messes that step 4 left behind.
    
    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
................................................................................

    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} {
................................................................................
			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






|







 







|







 







<
<
<












<



<
<
<
<
<
<
<
<
<
<
<
|







>
>
>
>







 







>
>
>
>
>





>



<
<
<
<
<











>
|
|
|
|
|
|
>


|
|







 







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







67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
...
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
...
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
...
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
...
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
	    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
................................................................................
# 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.
................................................................................
	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
................................................................................

    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} {
................................................................................
			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