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