Home | History | Annotate | Download | only in lazy
      1 #!/usr/bin/env python
      2 
      3 import sys
      4 import random
      5 
      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)
     12 
     13     def writeTimingCall(self, filename, numFuncs, funcsCalled, totalCalls):
     14         """Echo some comments and invoke both versions of toy"""
     15         rootname = filename
     16         if '.' in filename:
     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)
     31 
     32 class KScriptGenerator:
     33     """Used to generate random Kaleidoscope code"""
     34     def __init__(self, filename):
     35         self.kfile = open(filename, 'w')
     36         self.nextFuncNum = 1
     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
     47 
     48     def updateTotalCallCount(self, callee):
     49         # Count this call
     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)
     55 
     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)
     65 
     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:
     72             return
     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)
     79 
     80     def setCallWeighting(self, weight):
     81         """ Sets the probably of generating a function call"""
     82         self.callWeighting = weight
     83 
     84     def writeln(self, line):
     85         self.kfile.write(line + '\n')
     86 
     87     def writeComment(self, comment):
     88         self.writeln('# ' + comment)
     89 
     90     def writeEmptyLine(self):
     91         self.writeln("")
     92 
     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;")
     97         self.writeEmptyLine()
     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()
    113 
    114     def writeRandomOperation(self, LValue, LHS, RHS):
    115         shouldCallFunc = (self.lastFuncNum > 2 and random.random() < self.callWeighting)
    116         if shouldCallFunc:
    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))
    120         else:
    121             possibleOperations = ["+", "-", "*", "/"]
    122             operation = random.choice(possibleOperations)
    123             if operation == "-":
    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)))
    132             else:
    133                 self.writeln("  %s = %s %s %s :" % (LValue, LHS, operation, RHS))
    134 
    135     def getNextFuncNum(self):
    136         result = self.nextFuncNum
    137         self.nextFuncNum += 1
    138         self.lastFuncNum = result
    139         return result
    140 
    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
    149         first = "temp3"
    150         second = "temp1"
    151         third = "temp2"
    152         # Write some random operations
    153         for i in range(elements):
    154             self.writeRandomOperation(first, second, third)
    155             # Rotate the variables
    156             temp = first
    157             first = second
    158             second = third
    159             third = temp
    160         self.writeln("  " + third + ";")
    161         self.writeEmptyLine()
    162 
    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)
    170 
    171     def writeFinalFunctionCounts(self):
    172         self.writeComment("Called %d of %d functions" % (len(self.calledFunctions), self.lastFuncNum))
    173 
    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)
    205 
    206 # Execution begins here
    207 random.seed()
    208 
    209 timingScript = TimingScriptGenerator("time-toy.sh", "timing-data.txt")
    210 
    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)]
    214 
    215 # Generate the code
    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)
    219 print "All done!"
    220