1#!/usr/bin/env python 2 3from __future__ import print_function 4 5import sys 6import random 7 8 9class TimingScriptGenerator: 10 """Used to generate a bash script which will invoke the toy and time it""" 11 12 def __init__(self, scriptname, outputname): 13 self.timeFile = outputname 14 self.shfile = open(scriptname, "w") 15 self.shfile.write('echo "" > %s\n' % self.timeFile) 16 17 def writeTimingCall(self, filename, numFuncs, funcsCalled, totalCalls): 18 """Echo some comments and invoke both versions of toy""" 19 rootname = filename 20 if "." in filename: 21 rootname = filename[: filename.rfind(".")] 22 self.shfile.write( 23 'echo "%s: Calls %d of %d functions, %d total" >> %s\n' 24 % (filename, funcsCalled, numFuncs, totalCalls, self.timeFile) 25 ) 26 self.shfile.write('echo "" >> %s\n' % self.timeFile) 27 self.shfile.write('echo "With MCJIT (original)" >> %s\n' % self.timeFile) 28 self.shfile.write( 29 '/usr/bin/time -f "Command %C\\n\\tuser time: %U s\\n\\tsytem time: %S s\\n\\tmax set: %M kb"' 30 ) 31 self.shfile.write(" -o %s -a " % self.timeFile) 32 self.shfile.write( 33 "./toy -suppress-prompts -use-mcjit=true -enable-lazy-compilation=false < %s > %s-mcjit.out 2> %s-mcjit.err\n" 34 % (filename, rootname, rootname) 35 ) 36 self.shfile.write('echo "" >> %s\n' % self.timeFile) 37 self.shfile.write('echo "With MCJIT (lazy)" >> %s\n' % self.timeFile) 38 self.shfile.write( 39 '/usr/bin/time -f "Command %C\\n\\tuser time: %U s\\n\\tsytem time: %S s\\n\\tmax set: %M kb"' 40 ) 41 self.shfile.write(" -o %s -a " % self.timeFile) 42 self.shfile.write( 43 "./toy -suppress-prompts -use-mcjit=true -enable-lazy-compilation=true < %s > %s-mcjit-lazy.out 2> %s-mcjit-lazy.err\n" 44 % (filename, rootname, rootname) 45 ) 46 self.shfile.write('echo "" >> %s\n' % self.timeFile) 47 self.shfile.write('echo "With JIT" >> %s\n' % self.timeFile) 48 self.shfile.write( 49 '/usr/bin/time -f "Command %C\\n\\tuser time: %U s\\n\\tsytem time: %S s\\n\\tmax set: %M kb"' 50 ) 51 self.shfile.write(" -o %s -a " % self.timeFile) 52 self.shfile.write( 53 "./toy -suppress-prompts -use-mcjit=false < %s > %s-jit.out 2> %s-jit.err\n" 54 % (filename, rootname, rootname) 55 ) 56 self.shfile.write('echo "" >> %s\n' % self.timeFile) 57 self.shfile.write('echo "" >> %s\n' % self.timeFile) 58 59 60class KScriptGenerator: 61 """Used to generate random Kaleidoscope code""" 62 63 def __init__(self, filename): 64 self.kfile = open(filename, "w") 65 self.nextFuncNum = 1 66 self.lastFuncNum = None 67 self.callWeighting = 0.1 68 # A mapping of calls within functions with no duplicates 69 self.calledFunctionTable = {} 70 # A list of function calls which will actually be executed 71 self.calledFunctions = [] 72 # A comprehensive mapping of calls within functions 73 # used for computing the total number of calls 74 self.comprehensiveCalledFunctionTable = {} 75 self.totalCallsExecuted = 0 76 77 def updateTotalCallCount(self, callee): 78 # Count this call 79 self.totalCallsExecuted += 1 80 # Then count all the functions it calls 81 if callee in self.comprehensiveCalledFunctionTable: 82 for child in self.comprehensiveCalledFunctionTable[callee]: 83 self.updateTotalCallCount(child) 84 85 def updateFunctionCallMap(self, caller, callee): 86 """Maintains a map of functions that are called from other functions""" 87 if not caller in self.calledFunctionTable: 88 self.calledFunctionTable[caller] = [] 89 if not callee in self.calledFunctionTable[caller]: 90 self.calledFunctionTable[caller].append(callee) 91 if not caller in self.comprehensiveCalledFunctionTable: 92 self.comprehensiveCalledFunctionTable[caller] = [] 93 self.comprehensiveCalledFunctionTable[caller].append(callee) 94 95 def updateCalledFunctionList(self, callee): 96 """Maintains a list of functions that will actually be called""" 97 # Update the total call count 98 self.updateTotalCallCount(callee) 99 # If this function is already in the list, don't do anything else 100 if callee in self.calledFunctions: 101 return 102 # Add this function to the list of those that will be called. 103 self.calledFunctions.append(callee) 104 # If this function calls other functions, add them too 105 if callee in self.calledFunctionTable: 106 for subCallee in self.calledFunctionTable[callee]: 107 self.updateCalledFunctionList(subCallee) 108 109 def setCallWeighting(self, weight): 110 """Sets the probably of generating a function call""" 111 self.callWeighting = weight 112 113 def writeln(self, line): 114 self.kfile.write(line + "\n") 115 116 def writeComment(self, comment): 117 self.writeln("# " + comment) 118 119 def writeEmptyLine(self): 120 self.writeln("") 121 122 def writePredefinedFunctions(self): 123 self.writeComment( 124 "Define ':' for sequencing: as a low-precedence operator that ignores operands" 125 ) 126 self.writeComment("and just returns the RHS.") 127 self.writeln("def binary : 1 (x y) y;") 128 self.writeEmptyLine() 129 self.writeComment("Helper functions defined within toy") 130 self.writeln("extern putchard(x);") 131 self.writeln("extern printd(d);") 132 self.writeln("extern printlf();") 133 self.writeEmptyLine() 134 self.writeComment("Print the result of a function call") 135 self.writeln("def printresult(N Result)") 136 self.writeln(" # 'result('") 137 self.writeln( 138 " putchard(114) : putchard(101) : putchard(115) : putchard(117) : putchard(108) : putchard(116) : putchard(40) :" 139 ) 140 self.writeln(" printd(N) :") 141 self.writeln(" # ') = '") 142 self.writeln(" putchard(41) : putchard(32) : putchard(61) : putchard(32) :") 143 self.writeln(" printd(Result) :") 144 self.writeln(" printlf();") 145 self.writeEmptyLine() 146 147 def writeRandomOperation(self, LValue, LHS, RHS): 148 shouldCallFunc = self.lastFuncNum > 2 and random.random() < self.callWeighting 149 if shouldCallFunc: 150 funcToCall = random.randrange(1, self.lastFuncNum - 1) 151 self.updateFunctionCallMap(self.lastFuncNum, funcToCall) 152 self.writeln(" %s = func%d(%s, %s) :" % (LValue, funcToCall, LHS, RHS)) 153 else: 154 possibleOperations = ["+", "-", "*", "/"] 155 operation = random.choice(possibleOperations) 156 if operation == "-": 157 # Don't let our intermediate value become zero 158 # This is complicated by the fact that '<' is our only comparison operator 159 self.writeln(" if %s < %s then" % (LHS, RHS)) 160 self.writeln(" %s = %s %s %s" % (LValue, LHS, operation, RHS)) 161 self.writeln(" else if %s < %s then" % (RHS, LHS)) 162 self.writeln(" %s = %s %s %s" % (LValue, LHS, operation, RHS)) 163 self.writeln(" else") 164 self.writeln( 165 " %s = %s %s %f :" 166 % (LValue, LHS, operation, random.uniform(1, 100)) 167 ) 168 else: 169 self.writeln(" %s = %s %s %s :" % (LValue, LHS, operation, RHS)) 170 171 def getNextFuncNum(self): 172 result = self.nextFuncNum 173 self.nextFuncNum += 1 174 self.lastFuncNum = result 175 return result 176 177 def writeFunction(self, elements): 178 funcNum = self.getNextFuncNum() 179 self.writeComment("Auto-generated function number %d" % funcNum) 180 self.writeln("def func%d(X Y)" % funcNum) 181 self.writeln(" var temp1 = X,") 182 self.writeln(" temp2 = Y,") 183 self.writeln(" temp3 in") 184 # Initialize the variable names to be rotated 185 first = "temp3" 186 second = "temp1" 187 third = "temp2" 188 # Write some random operations 189 for i in range(elements): 190 self.writeRandomOperation(first, second, third) 191 # Rotate the variables 192 temp = first 193 first = second 194 second = third 195 third = temp 196 self.writeln(" " + third + ";") 197 self.writeEmptyLine() 198 199 def writeFunctionCall(self): 200 self.writeComment("Call the last function") 201 arg1 = random.uniform(1, 100) 202 arg2 = random.uniform(1, 100) 203 self.writeln( 204 "printresult(%d, func%d(%f, %f) )" 205 % (self.lastFuncNum, self.lastFuncNum, arg1, arg2) 206 ) 207 self.writeEmptyLine() 208 self.updateCalledFunctionList(self.lastFuncNum) 209 210 def writeFinalFunctionCounts(self): 211 self.writeComment( 212 "Called %d of %d functions" % (len(self.calledFunctions), self.lastFuncNum) 213 ) 214 215 216def generateKScript( 217 filename, numFuncs, elementsPerFunc, funcsBetweenExec, callWeighting, timingScript 218): 219 """Generate a random Kaleidoscope script based on the given parameters""" 220 print("Generating " + filename) 221 print( 222 " %d functions, %d elements per function, %d functions between execution" 223 % (numFuncs, elementsPerFunc, funcsBetweenExec) 224 ) 225 print(" Call weighting = %f" % callWeighting) 226 script = KScriptGenerator(filename) 227 script.setCallWeighting(callWeighting) 228 script.writeComment( 229 "===========================================================================" 230 ) 231 script.writeComment("Auto-generated script") 232 script.writeComment( 233 " %d functions, %d elements per function, %d functions between execution" 234 % (numFuncs, elementsPerFunc, funcsBetweenExec) 235 ) 236 script.writeComment(" call weighting = %f" % callWeighting) 237 script.writeComment( 238 "===========================================================================" 239 ) 240 script.writeEmptyLine() 241 script.writePredefinedFunctions() 242 funcsSinceLastExec = 0 243 for i in range(numFuncs): 244 script.writeFunction(elementsPerFunc) 245 funcsSinceLastExec += 1 246 if funcsSinceLastExec == funcsBetweenExec: 247 script.writeFunctionCall() 248 funcsSinceLastExec = 0 249 # Always end with a function call 250 if funcsSinceLastExec > 0: 251 script.writeFunctionCall() 252 script.writeEmptyLine() 253 script.writeFinalFunctionCounts() 254 funcsCalled = len(script.calledFunctions) 255 print( 256 " Called %d of %d functions, %d total" 257 % (funcsCalled, numFuncs, script.totalCallsExecuted) 258 ) 259 timingScript.writeTimingCall( 260 filename, numFuncs, funcsCalled, script.totalCallsExecuted 261 ) 262 263 264# Execution begins here 265random.seed() 266 267timingScript = TimingScriptGenerator("time-toy.sh", "timing-data.txt") 268 269dataSets = [ 270 (5000, 3, 50, 0.50), 271 (5000, 10, 100, 0.10), 272 (5000, 10, 5, 0.10), 273 (5000, 10, 1, 0.0), 274 (1000, 3, 10, 0.50), 275 (1000, 10, 100, 0.10), 276 (1000, 10, 5, 0.10), 277 (1000, 10, 1, 0.0), 278 (200, 3, 2, 0.50), 279 (200, 10, 40, 0.10), 280 (200, 10, 2, 0.10), 281 (200, 10, 1, 0.0), 282] 283 284# Generate the code 285for (numFuncs, elementsPerFunc, funcsBetweenExec, callWeighting) in dataSets: 286 filename = "test-%d-%d-%d-%d.k" % ( 287 numFuncs, 288 elementsPerFunc, 289 funcsBetweenExec, 290 int(callWeighting * 100), 291 ) 292 generateKScript( 293 filename, 294 numFuncs, 295 elementsPerFunc, 296 funcsBetweenExec, 297 callWeighting, 298 timingScript, 299 ) 300print("All done!") 301