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