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