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

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add a micropass to optimize away conditional jumps that are identical to a conditional jump in a dominator. (Partial redundancy elimination appears to create these.)
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 344567b9193266ff7c6823e973a175b2c2cad2d33907912e59fa09e5e1a4aa9a
User & Date: kbk 2018-12-08 21:46:26
Context
2018-12-17
23:19
Integrate kbk-jumpthread: replace the node-by-node splitting with a single pass that identifies many threading opportunities and also reduces the number of splits. Eliminate the old nodesplit pass, and the renameTemps pass, which is no longer required. check-in: a934a75e1f user: kbk tags: trunk
2018-12-09
20:55
Open a branch for experiments with more accurate and faster jump threading. check-in: 67902a50a2 user: kbk tags: kbk-jumpthread
2018-12-08
21:46
Add a micropass to optimize away conditional jumps that are identical to a conditional jump in a dominator. (Partial redundancy elimination appears to create these.) check-in: 344567b919 user: kbk tags: trunk
21:45
Add a micropass to optimize away conditional jumps that are identical to a conditional jump in a dominator. (Partial redundancy elimination appears to create these.) Closed-Leaf check-in: 1c9b4510d1 user: kbk tags: kbk-deadcond
2018-12-07
02:43
Fixes that make poly1305 compilable. check-in: 602b3659c7 user: kbk tags: trunk
Changes

Changes to quadcode/deadcode.tcl.

13
14
15
16
17
18
19





20
21
22
23
24
25
26
...
138
139
140
141
142
143
144









































































































































































145
146
147
148
149
150
151
# quadcode sequence. The following passes are provided:

# deadjump:
#	This pass is a simple peephole optimization that finds
#	'jumpTrue' and 'jumpFalse' statements whose test condition is
#	constant, and optimizes them away.
#





# deadbb:
#	This pass removes basic blocks that are entirely unreachable.
#	It also coalesces blocks in the case where a single-exit predecessor
#	transfers control to a single-entry successor (this can happen,
#	for instance, if an intervening check for variable existence
#	has been removed). It re-establishes the depth first numbering
#	of the blocks, and rebuilds predecessor relations, du-chains,
................................................................................
	}
	my debug-deadjump {
	    puts "After removing dead conditional jumps:"
	    my dump-bb
	}
	return $changed
    }









































































































































































     
    # deadbb --
    #
    #	Removes dead basic blocks from the system.
    #
    # Results:
    #	Returns 1 if anything was removed, 0 otherwise






>
>
>
>
>







 







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







13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
# quadcode sequence. The following passes are provided:

# deadjump:
#	This pass is a simple peephole optimization that finds
#	'jumpTrue' and 'jumpFalse' statements whose test condition is
#	constant, and optimizes them away.
#
# deadcond:
#	This pass optimizes conditional jumps where the condition
#	is known to be true because the jump is reachable only from
#	another jump that depends on the same condition.
#
# deadbb:
#	This pass removes basic blocks that are entirely unreachable.
#	It also coalesces blocks in the case where a single-exit predecessor
#	transfers control to a single-entry successor (this can happen,
#	for instance, if an intervening check for variable existence
#	has been removed). It re-establishes the depth first numbering
#	of the blocks, and rebuilds predecessor relations, du-chains,
................................................................................
	}
	my debug-deadjump {
	    puts "After removing dead conditional jumps:"
	    my dump-bb
	}
	return $changed
    }
     
    # deadcode --
    #
    #	Removes redundant conditional jumps
    #
    # Preconditions:
    #	Dominance tree (bbidom, bblevel, bbkids) must be up to date.
    #
    # Results:
    #	Returnns 1 if anything was removed, 0 otherwise.
    #
    # Side effects:
    #	Rewrites 'bbcontent', 'bbpred', 'udchain' and 'duchain' to reflect
    #	the fact that code was removed.
    #
    # Other optimizations can leave code in a state that looks something like:
    #
    #  1: {instanceOf NUMERIC} {temp 0 0} {var x 0}
    #     jumpFalse {bb X} {temp 0 0}
    #     jump {bb 2}
    #
    #  2: jumpFalse {bb Y} {temp 0 0}
    #     jump {bb 3}
    #
    # with the unreachable code at block Y getting in the way of
    # further optimizations. This pass clears away that particular dross
    # by rewriting block 2 in the above example to simply
    #     jump {bb 3}
    # since there is no way that the 'false' branch can be taken.
    # {temp 0 0} is known to be true since block 1 just tested it.
    #
    # Formally, the value of a condition is known if there is a block B
    # that tests it:
    #
    #    B: ... jumpTrue C, cond
    #           jump D
    #
    # and there is another jumpTrue or jumpFalse referring to 'cond' in
    # a block E,
    # and either C or D dominates or is equal to E.
    #
    # We proceed in a single pass to walk the dominance tree, accumulating
    # a dictionary that maps the conditions to the known values.
    # Every conditional jump that we encounter, for which the value is known,
    # is eliminated.
      
    method deadcond {} {

	my debug-deadcond {
	    puts "Before deadcond:"
	    my dump-bb
	}
	    
	return [my deadcond-worker 0 {}]

    }

    # deadcond-worker --
    #
    #	Visits a block and its dominance subtree, looking for redundant
    #	conditional jumps.
    #
    # Parameters:
    #	b - Block to visit.
    #	d - Dictionary whose keys are SSA variables and whose values are
    #	    those variables' known values on entry to b
    #
    # Results:
    #	Returns 1 if something changed in the subtree, 0 otherwise.

    method deadcond-worker {b d} {

	my debug-deadcond {
	    puts "$b: predetermined values: $d"
	}

	set changed 0

	# If the block ends in a conditional jump, it is known to dominate
	# both successors, because there are no critical edges. Find out what
	# the variable's value is on each of the two jumps out of the block

	set bb [lindex $bbcontent $b]
	set q [lindex $bb end-1]
	set opcode [lindex $q 0 0]
	if {$opcode eq "jumpTrue"} {
	    set trueBranch [lindex $q 1 1] 
	    set falseBranch [lindex $bb end 1 1]
	    set isCond 1
	} elseif {$opcode eq "jumpFalse"} {
	    set trueBranch [lindex $bb end 1 1]
	    set falseBranch [lindex $q 1 1]
	    set isCond 1
	} else {
	    set isCond 0
	}

	# Enumerate immediately dominated blocks as a dictionary to
	# enable quick removal

	set k {}
	foreach kid [lindex $bbkids $b] {
	    dict set k $kid {}
	}

	# Handle conditional branches

	if {$isCond} {
	    my debug-deadcond {
		puts "Examine conditional jump $b:end-1: $q"
	    }
	    set v [lindex $q 2]
	    if {[dict exists $d $v]} {

		lset bbcontent $b {}
		if {[dict get $d $v]} {
		    set branch $trueBranch
		    my removePred $falseBranch $b
		    dict unset k $falseBranch
		} else {
		    set branch $falseBranch
		    my removePred $trueBranch $b
		    dict unset k $trueBranch
		}
		my removeUse $v $b
		set newq [list jump [list bb $branch]]
		my debug-deadcond {
		    puts "Replace end of the block with $newq"
		}
		set bb [lreplace $bb[set bb ""] end-1 end $newq]
		lset bbcontent $b $bb
		set changed 1

	    } else {

		# Visit dominance trees of the successor blocks, with
		# known values for $v.

		set d2 $d
		my debug-deadcond {
		    puts "  In $trueBranch, $v = 1"
		}
		dict unset k $trueBranch
		dict set d2 $v 1
		if {[my deadcond-worker $trueBranch $d2]} {
		    set changed 1
		}
		my debug-deadcond {
		    puts "In $falseBranch, $v = 0"
		}
		dict unset k $falseBranch
		dict set d2 $v 0
		if {[my deadcond-worker $falseBranch $d2]} {
		    set changed 1
		}
	    }
	}

	# Handle any dominance children that the above code did not handle

	dict for {kid -} $k {
	    if {[my deadcond-worker $kid $d]} {
		set changed 1
	    }
	}

	return $changed
    }
    
     
    # deadbb --
    #
    #	Removes dead basic blocks from the system.
    #
    # Results:
    #	Returns 1 if anything was removed, 0 otherwise

Changes to quadcode/transformer.tcl.

596
597
598
599
600
601
602
603
604
605
606
607


608
609


610
611
612
613
614
615
616
	}
	foreach pass {
	    copyprop
	    cleanupMoveFromCallFrame
	    cleanupMoveToCallFrame
	    cleanupCallFrameUse
	    cleanupNarrow
	    deadjump
	    deadbb
	    bbidom
	    bblevel
	    constfold


	    deadvars
	    uselessphis


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






<
<


|
>
>


>
>







596
597
598
599
600
601
602


603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
	}
	foreach pass {
	    copyprop
	    cleanupMoveFromCallFrame
	    cleanupMoveToCallFrame
	    cleanupCallFrameUse
	    cleanupNarrow


	    bbidom
	    bblevel
	    deadcond
	    deadjump
	    deadbb
	    deadvars
	    uselessphis
	    bbidom
	    bblevel
	    constfold
	    partialredundancy
	} {
	    set cmd [string map [list @pass $pass] {
		set result [my @pass]
	    }]
	    lappend timings $pass [lindex [time $cmd] 0]