Check-in [c388c8737b]

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.433
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
Unified Diff Ignore Whitespace Patch
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
    # 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 --
#







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

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

|

|







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


































1115
1116
1117
1118
1119
1120
1121
        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.







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







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