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