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