CompileDSP

#!/usr/bin/python
import fileinput
import sys

#
#A LISP parser to generate vDSP
#

# The language we parse is a LISP variant that looks like this:
#
#( do
#  (in w0 w1 w3 w3 a x y0 y1 c y2 sy3)
#  (vset output  (vadd (vmul w0 w1) (vsmul w2 w3)))
#  (vset output1 (vadd a (vmul x (vadd y0 y1))))
#  (vset output2 (vadd c (vmul output1 (vsadd y2 sy3))))
#  (out output2)
#)
#
#The whole point of doing this is so that we can keep modifying this
#compiler to take advantage of high level vDSP operations as we find that
#they are necessary
#


##
## Parsing utilities to read char by char with lookahead of 1
##

#Consume a file and allow bytes to be pushed back
class Reader:

  def __init__(self,fname):
    self.pushedChars = []
    self.file = open(fname,'r')
    self.originalText = []

  def __iter__(self):
    return self

  def next(self):
    if len(self.pushedChars)>0:
      c = self.pushedChars.pop()
    else:
      c = self.file.read(1)
      if not c:
        self.file.close()
        raise StopIteration
      else:
        self.originalText.append(c) 
    return c

  def prev(self,c):
    self.pushedChars.append(c)

##
## This is a specific compiler for our LISP variant
##

class InstV3:
  def __init__(self,name,r0,r1,w):
    self.name = name
    self.read = [r0,r1]
    self.scalar    = None
    self.write = w

  def __str__(self):
    return "vDSP_{0}({1},1,{2},1,{3},1,{4});".format(
      self.name,self.read[0],self.read[1],self.write,"index")

#Also used with the cp instruction by reversing r0 and w order(!)
class InstV2:
  def __init__(self,name,r0,w):
    self.name = name
    self.read = [r0]
    self.scalar    = None
    self.write = w

  def __str__(self):
    return "vDSP_{0}({1},1,{2},1,{3});".format(
      self.name,self.read[0],self.write,"index")


class InstS3:
  def __init__(self,name,r0,scalar,w):
    self.name = name
    self.read = [r0]
    self.scalar = scalar
    self.write = w

  def __str__(self):
    return "vDSP_{0}({1},1,&{2},{3},1,{4});".format(
      self.name,self.read[0],self.scalar,self.write,"index")
 
class Register:
  def __init__(self,name):
    self.name = name
    self.isScalar = False
    self.isInput = False
    self.isOutput = False
    self.reads = {}
    self.writes = {}
 
  def __str__(self):
    return self.name


#
# A trivial LISP compiler to generate vDSP/vecLib code snippets
#
class Compiler:

  def findOrCreateRegister(self,name):
    if name in self.allRegisters:
      register = self.allRegisters[name]
    else:
      self.allRegisters[name] = Register(name)
      register = self.allRegisters[name]
    return register
 
  def __init__(self,reader):
    self.reader = reader
    self.tokens = []
    self.STARTSTATEMENT=1
    self.STOPSTATEMENT=2
    self.FINDSTATEMENT=0
    self.FINDTOKEN=1
    self.assembler = []
    self.instructions = []
    self.nextAccumulator = 0
    self.idx = "index"
    self.v2 = ["vfrac","vset"]
    self.v3 = ["vadd","vsub","vmul"]
    self.s3 = ["vsadd","vssub","vsmul"]
    self.scalars = []
    self.allRegisters = {}

  #This is what is legal in an identifier
  def isTokenChar(self,c):
    return (c=='_') or ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9')

  #Eat the input character by character
  def consume(self,state,chars):
    more = True
    if state == self.FINDSTATEMENT:
      try:
        c = self.reader.next()
      except StopIteration:
        more = False
      if more:
        if   c=='(':
          self.tokens.append(self.STARTSTATEMENT)
        elif c==')':
          self.tokens.append(self.STOPSTATEMENT)
        elif self.isTokenChar(c):
          state = self.FINDTOKEN
          self.reader.prev(c)
    elif state == self.FINDTOKEN:
      c = self.reader.next()
      if self.isTokenChar(c):
        chars.append(c)
      else:
        token = "".join(chars)
        self.tokens.append(token)
        chars = []
        self.reader.prev(c)
        state = self.FINDSTATEMENT

    return more,state,chars

  #This drives the loop that turns a char string into tokens
  #LISP tokenization is trivial because it is just identifiers and parens
  def tokenize(self):
    more = True
    state = self.FINDSTATEMENT
    chars = []
    while more:
      more,state,chars = self.consume(state,chars)
    self.comment = "/*" + "".join(self.reader.originalText) + "*/"

  #This builds a bidirectional graph of register dependencies, with
  #counts do that we can determine uniqueness of reads, etc
  def linkRegisters(self,r,w):
    if r and w:
      if not w in r.writes:
        r.writes[w] = 0
      if not r in w.reads:
        w.reads[r] = 0
      r.writes[w] = r.writes[w] + 1
      w.reads[r] = w.reads[r] + 1
  
  #Given the parameters, turn the string of items into 
  #a real instruction with all the metadata it needs for later 
  def createInstruction(self,matched,n):
    R = self.findOrCreateRegister
    name = matched[0]
    r0 = None
    r1 = None
    w0 = None
    if   name in self.v3:
      r0 = R(matched[1])
      r1 = R(matched[2])
      w0 = R(matched[3])
      instr = InstV3(name,r0,r0,w0)
    elif name == "vset":
      r0 = R(matched[2])
      w0 = R(matched[1])
      instr = InstV2(name,r0,w0)
    elif name in self.v2:
      r0 = R(matched[1])
      w0 = R(matched[2])
      instr = InstV2(name,r0,w0)
    elif name in self.s3:
      r0 = R(matched[1])
      r1 = R(matched[2])
      w0 = R(matched[3])
      r1.scalar = True
      instr = InstS3(name,r0,r1,w0)
    else:
      raise Exception(str(matched))
    #generate a register dependency graph
    self.linkRegisters(r0, w0)
    self.linkRegisters(r1, w0)
    return instr

  #When we have a string of statements for a subexpression
  #Then deal with it here
  #It corresponds to an instruction
  def parseMatched(self,lastStart,lastStop,n):
    R = self.findOrCreateRegister
    matched = self.tokens[lastStart+1:lastStop]
    front = self.tokens[0:lastStart]
    back = self.tokens[lastStop+1:]
    accumulatorName = "reg{0}".format(self.nextAccumulator)
    self.nextAccumulator = self.nextAccumulator + 1
    accumulator = Register(accumulatorName) 
    matched.append(accumulatorName)
    front.append(accumulatorName)
    self.tokens = front+back
    self.assembler.append(matched)
    if   matched[0] == "in":
      self.inputs = map(Register,matched[1:-1])
      for registerName in self.inputs:
        R(registerName).isInput = True
    elif matched[0] == "out":
      self.outputs = map(Register,matched[1:-1])
      for registerName in self.outputs:
        R(registerName).isOutput = True
    else:
      instr = self.createInstruction(matched,n)
      if instr:
        self.instructions.append(instr)


  #LISP syntax here is trivial because it is nothing but identifiers
  # and parenthesis.  Let the code that this gets embedded in assign
  # the identifiers.  This is the WHOLE parse!    
  def parseContinue(self):
    n=0
    while(True):
      if n >= len(self.tokens):
        return False
      elif self.tokens[n]==self.STARTSTATEMENT:
        lastStart=n
      elif self.tokens[n]==self.STOPSTATEMENT:
        lastStop=n
        self.parseMatched(lastStart,lastStop,n)
        return True
      n=n+1
    return True,lastStart

  def findScalars(self):
    for instr in self.instructions:
      if instr.scalar:
        self.scalars.append(instr.scalar)

  def parse(self):
    more=True
    while more:
      more = self.parseContinue()
    self.findScalars()

  def optimize(self):
    pass
    #todo: given that we have a dependency graph with count,
    #we should be able to minimize register usage easily
      
      

  def compile(self):
    self.tokenize()
    self.parse()
    self.optimize()

#Open up the file to be parsed and compile it
compiler=Compiler(Reader(sys.argv[1]))
compiler.compile()

#The parsed content is found in the compiler
#List the instructions and the text that generated it in a comment
print compiler.comment
for instr in compiler.instructions:
  print instr