Check-in [c388c8737b]
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to tclconference@googlegroups.com
or submit via the online form by Sep 9.

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

Overview
Comment:Add constant folding for unary +. It probably ought to be folded out altogether, since it serves only to trigger type checking. Add an outline of the actual process of jump threading once the threads have been determined.
Timelines: family | ancestors | descendants | both | notworking | kbk-jumpthread
Files: files | file ages | folders
SHA3-256:c388c8737b3f39611b81eff62c989bff40f1d7f05e3bb1b1e826cd5127655fc4
User & Date: kbk 2018-12-16 05:18:01
Original Comment: Add constant folding for unary +. It probably ought to be folded out altogether, since it serves only to trigger type checking.
Context
2018-12-17
22:08
Finish jump threading - actually do the block duplication and redirection of jumps. Add the logic for SSA deconstruction (required by jump threading) and make SSA construction work with the deconstructed result. check-in: a41b93130e user: kbk tags: notworking, kbk-jumpthread
2018-12-16
05:18
Add constant folding for unary +. It probably ought to be folded out altogether, since it serves only to trigger type checking. Add an outline of the actual process of jump threading once the threads have been determined. check-in: c388c8737b user: kbk tags: notworking, kbk-jumpthread
04:55
Add a 'cos2' test case to illustrate the cost of non-numeric ordering comparisons check-in: 86167d6917 user: kbk tags: notworking, kbk-jumpthread
Changes

Changes to quadcode/constfold.tcl.

690
691
692
693
694
695
696












697
698
699
700
701
702
703
			}
			dict unset udchain $result
			my replaceUses $result $res
			set changed 1
			continue; # delete the quad
		    }













		    "unset" {
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace $result with Nothing"
			}
			dict unset udchain $result
			my replaceUses $result Nothing







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







690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
			}
			dict unset udchain $result
			my replaceUses $result $res
			set changed 1
			continue; # delete the quad
		    }

		    "uplus" {
			set res [list literal [lindex $argl 0]]
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace $result with $res"
			}
			dict unset udchain $result
			my replaceUses $result $res
			set changed 1
			continue; # delete the quad
		    }
		    
		    "unset" {
			my debug-constfold {
			    puts "$b:$pc: $q"
			    puts "    replace $result with Nothing"
			}
			dict unset udchain $result
			my replaceUses $result Nothing

Changes to quadcode/jumpthread.tcl.

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
....
1108
1109
1110
1111
1112
1113
1114


































1115
1116
1117
1118
1119
1120
1121
    # Identify which subsets of the conditions are reachable on specific
    # control flow paths, so that blocks can be replicated to have known
    # entry conditions. Also report the (up to two) successors for each
    # variant block.

    my jt_forward

    my debug-jumpthread {
        my variable jt_variants
        puts "Variants found:"
        set b -1
        foreach vs $jt_variants {
            incr b
            dict for {m ss} $vs {
                puts [format "  %d (%llx): %s" $b $m $ss]
            }

        }

    }





    # TODO: Once all the variants have been listed, if any block has more than
    #       one variant, deconstruct SSA.  Replicate the blocks into variants,
    #       redirecting their exits as needed (and tracking preds). Sort the

    #       blocks.  Reconstruct SSA, solve ud- and du-chains, propagate
    #       copies, remove unreachable code, and recalculate bbidom/bblevel.

    #	    (May want to inspect the result to see whether another try at
    #	    loop inversion might help.)


    my debug-jumpthread {
        puts "NOT DONE!"
    }


    # Clean up the working storage

    my jt_cleanup

    return 0
}
 
# quadcode::transformer method jt_unpackPhis --
#
................................................................................
        return [expr {($u & $IMPURE) == 0}]; # Can't be true
    } elseif {[quadcode::dataType::mightbea $u $v]} {
        return 0
    } else {
        return 1
    }
}


































 
# quadcode::transformer method jt_cleanup --
#
#	Cleans up working storage after the jump threading pass.
#
# Results:
#	None.







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

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

|







 







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







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
....
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
    # Identify which subsets of the conditions are reachable on specific
    # control flow paths, so that blocks can be replicated to have known
    # entry conditions. Also report the (up to two) successors for each
    # variant block.

    my jt_forward

    # Determine whether the division into variants is trying to split
    # anything.







    if {[my jt_has_multiple_variants]} {

        # TODO - IMPLEMENT THE FOLLOWING

        my jt_cleanup; return 0

        # We will be splitting paths.  This is a relatively 'violent'
        # change to the program, and it's insanely difficult to maintain SSA
        # through it. Instead, we deconstruct the SSA form, split the paths
        # in the deconstructed version, and then rebuild SSA. (We then have
        # to solve for ud- and du-chains again.

        
        my ssa_deconstruct

        
        my jt_split_paths

        
        my ssa
        my ud_du_chain


    }
        
    # Clean up the working storage
    
    my jt_cleanup

    return 0
}
 
# quadcode::transformer method jt_unpackPhis --
#
................................................................................
        return [expr {($u & $IMPURE) == 0}]; # Can't be true
    } elseif {[quadcode::dataType::mightbea $u $v]} {
        return 0
    } else {
        return 1
    }
}
 
# quadcode::transformer method jt_has_multiple_variants --
#
#	Determine whether jump threading has found any work to do.
#
# Results:
#	Returns 1 if the program should be rewritten, 0 otherwise.

oo::define quadcode::transformer method jt_has_multiple_variants {} {

    my variable jt_variants

    my debug-jumpthread {
        puts "Variants found:"
        set b -1
        foreach vs $jt_variants {
            incr b
            dict for {m ss} $vs {
                puts [format "  %d (%llx): %s" $b $m $ss]
            }
        }
    }

    set b -1
    foreach vs $jt_variants {
        incr b
        if {[dict size $vs] > 1} {
            return 1
        }
    }

    return 0
}

 
# quadcode::transformer method jt_cleanup --
#
#	Cleans up working storage after the jump threading pass.
#
# Results:
#	None.