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