source: proto/Compiler/pablo.py @ 2690

Last change on this file since 2690 was 2690, checked in by cameron, 6 years ago

Restructure CarryInfoSetVisitor?, add block child info.

File size: 56.1 KB
RevLine 
[753]1#
2# Pablo.py - parallel bitstream to bitblock
3#  2nd generation compiler
4#
[903]5# Copyright 2010, 2011, Robert D. Cameron, Kenneth S. Herdy
[753]6# All rights reserved.
7#
8import ast, copy, sys
9import Cgen
10
[1271]11name_substitution_map = {}
[1997]12do_block_inline_decorator = 'IDISA_INLINE '
13do_final_block_inline_decorator = ''
[2099]14error_routine = 'raise_assert'
[2612]15experimentalMode=False
[1271]16
[2606]17def isCarryGenerating(builtin_fn):
[2636]18   return builtin_fn in ['ScanThru', 'ScanTo', 'AdvanceThenScanThru', 'AdvanceThenScanTo', 'SpanUpTo', 'InclusiveSpan', 'ExclusiveSpan', 'ScanToFirst']
[2606]19def usesCarryInit1(builtin_fn):
20   return builtin_fn in ['ScanToFirst']
[2636]21def isAdvance(builtin_fn):
[2606]22   return builtin_fn in ['Advance']
23
[2636]24
25def CheckForBuiltin(fncall, builtin_fnmod_noprefix='pablo'):
[2612]26  if not isinstance(fncall, ast.Call): return None
27  if isinstance(fncall.func, ast.Name): fn_name = fncall.func.id
28  elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
29    if fncall.func.value.id == builtin_fnmod_noprefix: fn_name = fncall.func.attr
30    else: return None
31  else: return None
[2636]32  if isCarryGenerating(fn_name) or isAdvance(fn_name): return fn_name
[2612]33  else: return None
34
[2606]35def CarryCountOfFn(fncall, builtin_fnmod_noprefix='pablo'):
36  if not isinstance(fncall, ast.Call): return 0
37  if isinstance(fncall.func, ast.Name): fn_name = fncall.func.id
38  elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
39    if fncall.func.value.id == builtin_fnmod_noprefix: fn_name = fncall.func.attr
40    else: return 0
41  else: return 0
[2636]42  if isAdvance(fn_name):
[2606]43    if len(fncall.args) == 1: return 1
44    else: return 0 #  return fncall.args[1].n  # Possibly count Advance(m, n) as generating n carries.
45  elif isCarryGenerating(fn_name): return 1
46  else: return 0
47   
[1440]48def is_BuiltIn_Call(fncall, builtin_fnname, builtin_arg_cnt, builtin_fnmod_noprefix='pablo'):
[813]49        if isinstance(fncall.func, ast.Name): iscall = fncall.func.id == builtin_fnname
50        elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
51                 iscall = fncall.func.value.id == builtin_fnmod_noprefix and fncall.func.attr == builtin_fnname
[1864]52        return iscall and len(fncall.args) == builtin_arg_cnt
[753]53
[1864]54def dump_Call(fncall):
55        if isinstance(fncall.func, ast.Name): print "fn_name = %s\n" % fncall.func.id
56        elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
57                print "fn_name = %s.%s\n" % (fncall.func.value.id, fncall.func.attr)
58        print "len(fncall.args) = %s\n" % len(fncall.args)
59
[770]60def is_simd_not(e):
61  return isinstance(e, ast.Call) and isinstance(e.func, ast.Name) and e.func.id == 'simd_not'
62
[753]63def mkQname(obj, field):
64  return ast.Attribute(ast.Name(obj, ast.Load()), field, ast.Load())
65
66def mkCall(fn_name, args):
[1271]67  if isinstance(fn_name, str): 
68        if name_substitution_map.has_key(fn_name): fn_name = name_substitution_map[fn_name]
69        fn_name = ast.Name(fn_name, ast.Load())
[753]70  return ast.Call(fn_name, args, [], None, None)
71
72def mkCallStmt(fn_name, args):
73  if isinstance(fn_name, str): fn_name = ast.Name(fn_name, ast.Load())
74  return ast.Expr(ast.Call(fn_name, args, [], None, None))
[2636]75 
76 
77#
78# Carry Info Set
79#
80class CarryInfoSetVisitor(ast.NodeVisitor):
[2690]81  def __init__(self, streamFunctionNode):
82    (self.operation_count, self.block_count) = (0, 0)
83    (self.block_first_op, self.block_op_count, self.advance_amount) = ({}, {}, {})
[2636]84    self.init_one_list = []
[2690]85    (self.parent_block, self.children) = ({}, {})
86    (self.carry_count, self.adv_n_count, self.adv_1_count) = (0, 0, 0)
87    (self.total_advance, self.max_advance) = (0, 0)
[2688]88
[2690]89    # Initialize for the main block
90    self.block_no = 0
91    self.block_count += 1
92    self.children[0] = []
93    self.block_first_op[0] = 0
94    # Recursively process all blocks
95    self.generic_visit(streamFunctionNode)
96    self.block_op_count[0] = self.operation_count
97
[2636]98  def visit_Call(self, callnode):
99    self.generic_visit(callnode)
100    builtin = CheckForBuiltin(callnode)
101    if builtin == None: return
102    if isCarryGenerating(builtin): 
[2690]103      if usesCarryInit1(builtin): self.init_one_list.append(self.operation_count)
104      self.operation_count += 1
[2688]105      self.carry_count += 1
[2636]106    elif isAdvance(builtin):
107      if len(callnode.args) > 1:
108        adv_amount = callnode.args[1].n
[2688]109        self.adv_n_count += 1
110      else: 
111        adv_amount = 1
112        self.adv_1_count += 1
[2690]113      self.advance_amount[self.operation_count] = adv_amount
[2688]114      self.total_advance += adv_amount
115      if adv_amount > self.max_advance: self.max_advance = adv_amount
[2690]116      self.operation_count += 1
[2636]117    else: return
[753]118
[2690]119  def block_visit(self, blkNode):
120    prnt = self.block_no
121    this_block_no = self.block_count
122    self.block_count += 1
123    self.parent_block[this_block_no] = prnt
124    self.children[prnt].append(this_block_no)
[2636]125    self.block_no = this_block_no
[2690]126    self.block_first_op[this_block_no] = self.operation_count
127    self.children[this_block_no] = []
128    self.generic_visit(blkNode)
129    self.block_op_count[this_block_no] = self.operation_count - self.block_first_op[this_block_no]
[2688]130    # reset for processing remainder of parent
[2636]131    self.block_no = self.parent_block[this_block_no]
[2690]132
133
134  def visit_If(self, ifNode): 
135    self.block_visit(ifNode)
[2636]136 
[2690]137  def visit_While(self, whileNode):   
138    self.block_visit(whileNode)
[2636]139
140  def countBlockCarrysWithAdv1(self, blk):
141    op_count = self.block_op_count[blk]
142    if op_count == 0: return 0
143    carries = 0
144    for op in range(self.block_first_op[blk], self.block_first_op[blk] + op_count):
145      if op not in self.advance_amount.keys(): carries += 1
146      elif self.advance_amount[op] == 1: carries += 1
147    return carries
148
[753]149#
[863]150# Reducing AugAssign, e.g.  x |= y becomes x = x | y
[771]151#
152class AugAssignRemoval(ast.NodeTransformer):
153  def xfrm(self, t):
154    return self.generic_visit(t)
155  def visit_AugAssign(self, e):
156    self.generic_visit(e)
157    return ast.Assign([e.target], ast.BinOp(e.target, e.op, e.value))
[2208]158#
159# pablo.Advance(pablo.Advance(x, n)) => pablo.Advance(x, n+1)
160#
161class AdvanceCombiner(ast.NodeTransformer):
162  def xfrm(self, t):
163    return self.generic_visit(t)
164  def visit_if(self, ifNode):
165    return IfNode
166  def visit_While(self, whileNode):
167    return whileNode
168  def visit_Call(self, callnode):
169    self.generic_visit(callnode)
[2262]170    if len(callnode.args) == 0: return callnode
[2208]171    if not isinstance(callnode.args[0], ast.Call): return callnode
172    if is_BuiltIn_Call(callnode,'Advance', 1):
173        if is_BuiltIn_Call(callnode.args[0],'Advance', 1):
174          callnode.args = [callnode.args[0].args[0], ast.Num(2)]
175        elif is_BuiltIn_Call(callnode.args[0], 'Advance', 2):
176          if isinstance(callnode.args[0].args[1], ast.Num):
177            callnode.args = [callnode.args[0].args[0], ast.Num(callnode.args[0].args[1].n + 1)]
178          else:
179            callnode.args = [callnode.args[0].args[0], ast.BinOp(callnode.args[0].args[1], ast.Add(), ast.Num(1))]
180    return callnode
[771]181
[2009]182
[771]183#
[2009]184#  Translating pablo.match(marker, str)
185#  Incremental character match with lookahead
186#
187CharNameMap = {'[' : 'LBrak', ']' : 'RBrak', '{' : 'LBrace', '}' : 'LBrace', '(' : 'LParen', ')' : 'RParen', \
188              '!' : 'Exclam', '"' : 'DQuote', '#' : 'Hash', '$' : 'Dollar', '%' : 'PerCent', '&': 'RefStart', \
189              "'" : 'SQuote', '*': 'Star', '+' : 'Plus', ',' : 'Comma', '-' : 'Hyphen', '.' : 'Dot', '/' : 'Slash', \
190              ':' : 'Colon', ';' : 'Semicolon', '=' : 'Equals', '?' : 'QMark', '@' : 'AtSign', '\\' : 'BackSlash', \
191              '^' : 'Caret', '_' : 'Underscore', '|' : 'VBar', '~' : 'Tilde', ' ' : 'SP', '\t' : 'HT', '\m' : 'CR', '\n' : 'LF'}
192
193def GetCharName(char):
194        if char >= 'a' and char <= 'z' or char >= 'A' and char <= 'Z': return 'letter_' + char
195        elif char >= '0' and char <= '9': return 'digit_' + char
196        else: return CharNameMap[char]
197
198def MkCharStream(char):
199        return mkQname('lex', GetCharName(char))
200
201def MkLookAheadExpr(v, i):
202        return mkCall(mkQname('pablo', 'LookAhead'), [v, ast.Num(i)])
203
204def CompileMatch(match_var, string_to_match):
205        expr = mkCall('simd_and', [match_var, MkCharStream(string_to_match[0])])
206        for i in range(1, len(string_to_match)):
207                expr = mkCall('simd_and', [expr, MkLookAheadExpr(MkCharStream(string_to_match[i]), i)])
208        return expr
209
210class StringMatchCompiler(ast.NodeTransformer):
211  def xfrm(self, t):
212    return self.generic_visit(t)
213  def visit_Call(self, callnode):
214    if is_BuiltIn_Call(callnode,'match', 2):
215        ast.dump(callnode)
216        assert isinstance(callnode.args[0], ast.Str)
217        string_to_match = callnode.args[0].s
218        match_var = callnode.args[1]
219        expr = mkCall('simd_and', [match_var, MkCharStream(string_to_match[0])])
220        for i in range(1, len(string_to_match)):
221                expr = mkCall('simd_and', [expr, MkLookAheadExpr(MkCharStream(string_to_match[i]), i)])
222        return expr
223    else: return callnode
224
225
226
227#
[2606]228#  Converting expressions involving built-ins to compiled form. 
[2631]229#  Apply before carry variable insertion.
[2606]230#
231class TempifyBuiltins(ast.NodeTransformer):
232    def __init__(self, tempVarpfx = "tempvar"):
233      self.tempVarCount = 0
234      self.newTempList = []
235      self.tempVarPrefix = tempVarpfx
236    def genVar(self):
237      newTemp = self.tempVarPrefix + repr(self.tempVarCount)
238      self.newTempList.append(newTemp)
239      self.tempVarCount += 1
240      return newTemp
241    def tempVars(self):
242      return self.newTempList
243    def xfrm(self, t):
244      self.setUpStmts = []
245      self.assigNode = None
246      return self.generic_visit(t)
247    def is_Assign_value(self, node):
248      return self.assigNode != None and self.assigNode.value == node
249    def visit_If(self, ifNode):
250      self.setUpStmts = []
[2630]251      self.generic_visit(ifNode.test)
252      ifSetUpStmts = self.setUpStmts
[2606]253      self.generic_visit(ifNode)
254      if ifSetUpStmts == []: return ifNode
255      else: return ifSetUpStmts + [ifNode]
256    def visit_While(self, whileNode):
257      self.setUpStmts = []
[2630]258      self.generic_visit(whileNode.test)
259      whileSetUpStmts = self.setUpStmts
[2606]260      self.generic_visit(whileNode)
261      whileNode.body = whileNode.body + whileSetUpStmts
262      return whileSetUpStmts + [whileNode]
263    def visit_Assign(self, node):
264      self.assigNode = node
265      self.setUpStmts = []
266      self.generic_visit(node)
[2630]267      return self.setUpStmts + [node]
[2631]268    def visit_AugAssign(self, node):
269      self.setUpStmts = []
270      self.generic_visit(node)
271      return self.setUpStmts + [node]
[2606]272    def visit_Call(self, callnode):     
273        self.generic_visit(callnode)
274        if CarryCountOfFn(callnode) > 0 and not self.is_Assign_value(callnode):
275        #if not self.is_Assign_value(callnode):
276            tempVar = ast.Name(self.genVar(), ast.Load())
277            self.setUpStmts.append(ast.Assign([tempVar], callnode))
278            return tempVar
279        else: return callnode
280
281
282
283
284
285#
[753]286# Introducing BitBlock logical operations
287#
288class Bitwise_to_SIMD(ast.NodeTransformer):
289  """
290  Make the following substitutions:
291     x & y => simd_and(x, y)
[770]292     x & ~y => simd_andc(x, y)
[753]293     x | y => simd_or(x, y)
294     x ^ y => simd_xor(x, y)
295     ~x    => simd_not(x)
296     0     => simd_const_1(0)
297     -1    => simd_const_1(1)
[1916]298     if x: => if bitblock::any(x):
299  while x: => while bitblock::any(x):
[753]300  >>> ast_show(Bitwise_to_SIMD().xfrm(ast.parse("pfx = bit0 & bit1; sfx = bit0 &~ bit1")))
301 
302  pfx = simd_and(bit0, bit1)
303  sfx = simd_and(bit0, simd_not(bit1))
304  >>>
305  """
306  def xfrm(self, t):
307    return self.generic_visit(t)
308  def visit_UnaryOp(self, t):
309    self.generic_visit(t)
310    if isinstance(t.op, ast.Invert):
311      return mkCall('simd_not', [t.operand])
312    else: return t
313  def visit_BinOp(self, t):
314    self.generic_visit(t)
315    if isinstance(t.op, ast.BitOr):
316      return mkCall('simd_or', [t.left, t.right])
317    elif isinstance(t.op, ast.BitAnd):
[770]318      if is_simd_not(t.right): return mkCall('simd_andc', [t.left, t.right.args[0]])
319      elif is_simd_not(t.left): return mkCall('simd_andc', [t.right, t.left.args[0]])
320      else: return mkCall('simd_and', [t.left, t.right])
[753]321    elif isinstance(t.op, ast.BitXor):
322      return mkCall('simd_xor', [t.left, t.right])
323    else: return t
324  def visit_Num(self, numnode):
325    n = numnode.n
[1916]326    if n == 0: return mkCall('simd<1>::constant<0>', [])
327    elif n == -1: return mkCall('simd<1>::constant<1>', [])
[753]328    else: return numnode
329  def visit_If(self, ifNode):
330    self.generic_visit(ifNode)
[1916]331    ifNode.test = mkCall('bitblock::any', [ifNode.test])
[753]332    return ifNode
333  def visit_While(self, whileNode):
334    self.generic_visit(whileNode)
[1916]335    whileNode.test = mkCall('bitblock::any', [whileNode.test])
[753]336    return whileNode
337  def visit_Subscript(self, numnode):
338    return numnode  # no recursive modifications of index expressions
339
340#
341#  Generating BitBlock declarations for Local Variables
342#
[880]343class FunctionVars(ast.NodeVisitor):
344  def __init__(self,node):
345        self.params = []
346        self.stores = []
347        self.generic_visit(node)
[753]348  def visit_Name(self, nm):
349    if isinstance(nm.ctx, ast.Param):
350      self.params.append(nm.id)
351    if isinstance(nm.ctx, ast.Store):
352      if nm.id not in self.stores: self.stores.append(nm.id)
[880]353  def getLocals(self): 
[753]354    return [v for v in self.stores if not v in self.params]
355
356MAX_LINE_LENGTH = 80
357
358def BitBlock_decls_from_vars(varlist):
359  global MAX_LINE_LENGTH
[880]360  decls =  ""
361  if not len(varlist) == 0:
362          decls = "             BitBlock"
363          pending = ""
364          linelgth = 10
365          for v in varlist:
366            if linelgth + len(v) + 2 <= MAX_LINE_LENGTH:
367              decls += pending + " " + v
368              linelgth += len(pending + v) + 1
369            else:
370              decls += ";\n             BitBlock " + v
371              linelgth = 11 + len(v)
372            pending = ","
373          decls += ";"
[753]374  return decls
375
376def BitBlock_decls_of_fn(fndef):
[880]377  return BitBlock_decls_from_vars(FunctionVars(fndef).getLocals())
[753]378
379def BitBlock_header_of_fn(fndef):
380  Ccode = "static inline void " + fndef.name + "("
381  pending = ""
382  for arg in fndef.args.args:
383    if isinstance(arg, ast.Name):
384      Ccode += pending + arg.id.upper()[0] + arg.id[1:] + " & " + arg.id
385      pending = ", "
[863]386  if CarryCounter().count(fndef) > 0:
387    Ccode += pending + " CarryQtype & carryQ"
[753]388  Ccode += ")"
389  return Ccode
390
391
[760]392
393#
394#  Stream Initialization Statement Extraction
395#
396#  streamvar = 1 ==> streamvar = sisd_from_int(1) initially.
397class StreamInitializations(ast.NodeTransformer):
398  def xfrm(self, node):
399    self.stream_stmts = []
400    self.loop_post_inits = []
401    self.generic_visit(node)
402    return Cgen.py2C().gen(self.stream_stmts)
403  def visit_Assign(self, node):
404    if isinstance(node.value, ast.Num):
405      if node.value.n == 0: return node
406      elif node.value.n == -1: return node
407      else: 
408        stream_init = copy.deepcopy(node)
409        stream_init.value = mkCall('sisd_from_int', [node.value])
410        loop_init = copy.deepcopy(node)
411        loop_init.value.n = 0
412        self.stream_stmts.append(stream_init)
413        self.loop_post_inits.append(loop_init)
414        return None
415    else: return node
416  def visit_FunctionDef(self, node):
417    self.generic_visit(node)
418    node.body = node.body + self.loop_post_inits
419    return node
420
[2041]421
422
[753]423#
424# Carry Introduction Transformation
425#
426class CarryCounter(ast.NodeVisitor):
427  def visit_Call(self, callnode):
428    self.generic_visit(callnode)
[2606]429    self.carry_count += CarryCountOfFn(callnode)
[769]430  def visit_BinOp(self, exprnode):
[753]431    self.generic_visit(exprnode)
432    if isinstance(exprnode.op, ast.Sub):
433      self.carry_count += 1
[769]434    if isinstance(exprnode.op, ast.Add):
435      self.carry_count += 1
[753]436  def count(self, nodeToVisit):
437    self.carry_count = 0
438    self.generic_visit(nodeToVisit)
439    return self.carry_count
440
[2260]441#
442# Carry Initialization:  Aug. 4, 2012
443# - Carry variables are initialized to 0 by default
444# - However, the scan_to_first routine should ideally use
445#   initialization with 1.
446
447#
448class CarryInitToOneList(ast.NodeVisitor):
449  def visit_Call(self, callnode):
450    self.generic_visit(callnode)
451    if is_BuiltIn_Call(callnode,'Advance', 1) or is_BuiltIn_Call(callnode,'ScanThru', 2) or is_BuiltIn_Call(callnode,'ScanTo', 2) or is_BuiltIn_Call(callnode,'AdvanceThenScanThru', 2) or is_BuiltIn_Call(callnode,'AdvanceThenScanTo', 2) or is_BuiltIn_Call(callnode,'SpanUpTo', 2) or  is_BuiltIn_Call(callnode,'InclusiveSpan', 2) or is_BuiltIn_Call(callnode,'ExclusiveSpan', 2):       
452      self.carry_count += 1
453    elif is_BuiltIn_Call(callnode,'ScanToFirst', 1):
454      self.init_to_one_list.append(self.carry_count)
455      self.carry_count += 1
456  def visit_BinOp(self, exprnode):
457    self.generic_visit(exprnode)
458    if isinstance(exprnode.op, ast.Sub):
459      self.carry_count += 1
460    if isinstance(exprnode.op, ast.Add):
461      self.carry_count += 1
462  def count(self, nodeToVisit):
463    self.carry_count = 0
464    self.init_to_one_list = []
465    self.generic_visit(nodeToVisit)
466    return self.init_to_one_list
467
[2206]468class adv_nCounter(ast.NodeVisitor):
[1211]469  def visit_Call(self, callnode):
470    self.generic_visit(callnode)
471    if is_BuiltIn_Call(callnode,'Advance32', 1):       
[2206]472      self.adv_n_count += 1
473    if is_BuiltIn_Call(callnode,'Advance', 2):         
474      self.adv_n_count += 1
[1211]475  def count(self, nodeToVisit):
[2206]476    self.adv_n_count = 0
[1211]477    self.generic_visit(nodeToVisit)
[2206]478    return self.adv_n_count
[1211]479
[2689]480#
481# Base CCGO Class is also the null class, suitable for stream
482# functions that have no carry-generating operations.
483#
484class CCGO:
485    def __init__(self): pass
486    def GenerateCarryDecls(self): return ""
487    def GenerateInitializations(self): return ""
488    def GenerateStreamFunctionDecls(self):  return ""
489    def GenerateCarryInAccess(self, operation_no): return None
490    def GenerateCarryOutStore(self, operation_no, carry_out_expr): return []
491    def GenerateCarryIfTest(self, block_no, ifTest): return ifTest
492    def GenerateCarryElseFinalization(self, block_no): return []
493    def GenerateLocalDeclare(self, block_no): return []
494    def GenerateCarryWhileTest(self, block_no, testExpr): return testExpr
495    def EnterLocalWhileBlock(self, operation_offset):  pass
496    def ExitLocalWhileBlock(self):  pass
497    def GenerateCarryWhileFinalization(self, block_no): return []
498    def GenerateStreamFunctionFinalization(self): return []
[2612]499
[2689]500class testCCGO(CCGO):
[2638]501    def __init__(self, carryInfoSet, carryGroupVarName='carryQ'):
[2636]502        self.carryInfoSet = carryInfoSet
[2638]503        self.carryGroupVar = carryGroupVarName
[2636]504        self.carryIndex = {}
505        self.operation_offset = 0
506        carry_counter = 0
[2690]507        for op_no in range(carryInfoSet.operation_count):
[2636]508          self.carryIndex[op_no] = carry_counter
509          if not op_no in carryInfoSet.advance_amount.keys(): carry_counter += 1
510          elif carryInfoSet.advance_amount[op_no] == 1: carry_counter += 1
511        # Add a dummy entry for any possible final block that is empty.
[2690]512        self.carryIndex[carryInfoSet.operation_count] = carry_counter
[2640]513    # Helper
[2638]514    def CarryGroupAtt(self, attname, CarryGroupVarName=""):
515        if CarryGroupVarName == '': CarryGroupVarName = self.carryGroupVar
516        return ast.Attribute(ast.Name(CarryGroupVarName, ast.Load()), attname, ast.Load())
[2640]517    def GenerateCarryDecls(self):
518        carry_counter = 0
519        adv_n_counter = 0
520        for op_no in range(self.carryInfoSet.block_op_count[0]):
521          if not op_no in self.carryInfoSet.advance_amount.keys(): carry_counter += 1
522          elif self.carryInfoSet.advance_amount[op_no] == 1: carry_counter += 1
523          else: adv_n_counter += 1
524        return "CarryArray<%i, %i> %s;" % (carry_counter, adv_n_counter, self.carryGroupVar)
[2688]525    def GenerateInitializations(self):
526        carry_counter = 0
527        adv_n_counter = 0
528        inits = ""
529        for op_no in range(self.carryInfoSet.block_op_count[0]):
530          if op_no in self.carryInfoSet.init_one_list: inits += "carryQ.cq[%s] = carryQ.carry_flip(carryQ.cq[%s]);\n" % (carry_counter, carry_counter)
531          if not op_no in self.carryInfoSet.advance_amount.keys(): carry_counter += 1
532          elif self.carryInfoSet.advance_amount[op_no] == 1: carry_counter += 1
533          else: adv_n_counter += 1
534        return inits
535    def GenerateStreamFunctionDecls(self):  return ""
[2636]536    def GenerateCarryInAccess(self, operation_no):
537        carry_index = self.carryIndex[operation_no - self.operation_offset]
538        return mkCall(self.carryGroupVar + "." + 'get_carry_in', [ast.Num(carry_index)])
539    def GenerateCarryOutStore(self, operation_no, carry_out_expr):
540        carry_index = self.carryIndex[operation_no - self.operation_offset]
[2689]541        return [ast.Assign([ast.Subscript(self.CarryGroupAtt('cq'), ast.Index(ast.Num(carry_index)), ast.Store())], 
542                          mkCall("bitblock::srli<127>", [carry_out_expr]))]
[2636]543    def GenerateCarryIfTest(self, block_no, ifTest):
544        carry_count = self.carryInfoSet.block_op_count[block_no]
545        if carry_count == 0: return ifTest
546        ifIndex = self.carryIndex[self.carryInfoSet.block_first_op[block_no]]       
[2638]547        return ast.BoolOp(ast.Or(), [ifTest, mkCall(self.CarryGroupAtt('CarryTest'), [ast.Num(ifIndex), ast.Num(carry_count)])])
[2637]548    def GenerateCarryElseFinalization(self, block_no): 
549        carry_count = self.carryInfoSet.block_op_count[block_no]
550        if carry_count == 0: return []
551        ifIndex = self.carryIndex[self.carryInfoSet.block_first_op[block_no]]       
[2638]552        return [mkCallStmt(self.CarryGroupAtt('CarryDequeueEnqueue'), [ast.Num(ifIndex), ast.Num(carry_count)])]
[2640]553    def GenerateLocalDeclare(self, block_no):
554        local_carryvar = ast.Name("sub" + self.carryGroupVar, ast.Load())
[2689]555        return [mkCallStmt('LocalCarryDeclare', [local_carryvar, ast.Num(self.carryInfoSet.block_op_count[block_no])])]
[2640]556    def GenerateCarryWhileTest(self, block_no, testExpr):
557        carry_count = self.carryInfoSet.block_op_count[block_no]
558        if carry_count == 0: return testExpr
559        carry0 = self.carryIndex[self.carryInfoSet.block_first_op[block_no]]       
560        return ast.BoolOp(ast.Or(), [testExpr, mkCall(self.CarryGroupAtt('CarryTest'), [ast.Num(carry0), ast.Num(carry_count)])])
[2636]561    def EnterLocalWhileBlock(self, operation_offset): 
562        self.carryGroupVar = "sub" + self.carryGroupVar
563        self.operation_offset = operation_offset
564    def ExitLocalWhileBlock(self): 
565        self.operation_offset = 0
566        self.carryGroupVar = self.carryGroupVar[3:]
[2638]567    def GenerateCarryWhileFinalization(self, block_no): 
568        carry_count = self.carryInfoSet.block_op_count[block_no]
569        if carry_count == 0: return []
570        loopIndex = self.carryIndex[self.carryInfoSet.block_first_op[block_no]]       
[2689]571        return [mkCallStmt(self.CarryGroupAtt('CarryCombine'), [self.CarryGroupAtt('cq', "sub" + self.carryGroupVar), ast.Num(loopIndex), ast.Num(carry_count)])]
[2636]572    def GenerateStreamFunctionFinalization(self):
573        carry_count = self.carryInfoSet.countBlockCarrysWithAdv1(0)
574        if carry_count == 0: return []
[2638]575        else: return [mkCallStmt(self.CarryGroupAtt('CarryQ_Adjust'), [ast.Num(carry_count)])]
[2612]576
[2689]577
[2636]578def Strategic_CCGO_Factory(carryInfoSet):
579    ccgo = testCCGO(carryInfoSet, 'carryQ')
580    return ccgo
[2612]581
[2636]582
[753]583class CarryIntro(ast.NodeTransformer):
[2636]584  def __init__(self, ccgo, carryvar="carryQ", carryin = "_ci", carryout = "_co"):
[753]585    self.carryvar = ast.Name(carryvar, ast.Load())
[921]586    self.carryin = carryin
587    self.carryout = carryout
[2636]588    self.ccgo = ccgo
[753]589  def xfrm_fndef(self, fndef):
[2636]590    self.block_no = 0
[2690]591    self.operation_count = 0
[753]592    self.current_carry = 0
[2206]593    self.current_adv_n = 0
[753]594    carry_count = CarryCounter().count(fndef)
595    if carry_count == 0: return fndef
596    self.generic_visit(fndef)
[2628]597  def xfrm_fndef_final(self, fndef):
[2636]598    self.block_no = 0
[2690]599    self.operation_count = 0
[2628]600    self.carryout = ""
601    self.current_carry = 0
602    self.current_adv_n = 0
603    carry_count = CarryCounter().count(fndef)
604    if carry_count == 0: return fndef
605    self.generic_visit(fndef)
[762]606#   
607#    fndef.body.insert(0, mkCallStmt('CarryDeclare', [self.carryvar, ast.Num(carry_count)]))
[753]608    return fndef
609  def generic_xfrm(self, node):
[2636]610    self.block_no = 0
[2690]611    self.operation_count = 0
[753]612    self.current_carry = 0
[2206]613    self.current_adv_n = 0
[2264]614    self.last_stmt = None
[2265]615    self.last_stmt_carries = 0
[753]616    carry_count = CarryCounter().count(node)
[2206]617    adv_n_count = adv_nCounter().count(node)
618    if carry_count == 0 and adv_n_count == 0: return node
[753]619    self.generic_visit(node)
620    return node
[2631]621   
622  def local_while_xfrm(self, local_carryvar, whileNode):
[2690]623    saved_state = (self.block_no, self.operation_count, self.carryvar, self.carryin, self.carryout, self.current_carry, self.current_adv_n)
[2636]624    (self.carryvar, self.carryin, self.current_carry, self.current_adv_n) = (local_carryvar, '', 0, 0)
[2690]625    self.ccgo.EnterLocalWhileBlock(self.operation_count);
[2631]626    inner_while = self.generic_visit(whileNode)
[2636]627    self.ccgo.ExitLocalWhileBlock();
[2690]628    (self.block_no, self.operation_count, self.carryvar, self.carryin, self.carryout, self.current_carry, self.current_adv_n) = saved_state
[2631]629    return inner_while
630   
[753]631  def visit_Call(self, callnode):
632    self.generic_visit(callnode)
[1571]633    #CARRYSET
[1997]634    #carry_args = [ast.Num(self.current_carry)]
[2206]635    #adv_n_args = [ast.Subscript(ast.Name(self.carryvar.id + '.pending64', ast.Load()), ast.Num(self.current_adv_n), ast.Load())]
[2221]636    #adv_n_pending = ast.Subscript(ast.Name(self.carryvar.id + '.pending64', ast.Load()), ast.Num(self.current_adv_n), ast.Load())
[1997]637    if self.carryin == "_ci":
638        carry_args = [mkCall(self.carryvar.id + "." + 'get_carry_in', [ast.Num(self.current_carry)]), ast.Num(self.current_carry)]
[2221]639        adv_n_args = [mkCall(self.carryvar.id + "." + 'get_pending64', [ast.Num(self.current_adv_n)]), ast.Num(self.current_adv_n)]
[1997]640    else: 
641        carry_args = [mkCall('simd<1>::constant<0>', []), ast.Num(self.current_carry)]
[2206]642        adv_n_args = [mkCall('simd<1>::constant<0>', []), ast.Num(self.current_adv_n)]
[1997]643
[2206]644    if is_BuiltIn_Call(callnode, 'Advance', 2):         
645      #CARRYSET
646      rtn = self.carryvar.id + "." + "BitBlock_advance_n_<%i>" % callnode.args[1].n
647      c = mkCall(rtn, [callnode.args[0]] + adv_n_args)
648      self.current_adv_n += 1
649      return c
[813]650    if is_BuiltIn_Call(callnode, 'Advance', 1):         
[1571]651      #CARRYSET
[1997]652      rtn = self.carryvar.id + "." + "BitBlock_advance_ci_co"
[924]653      c = mkCall(rtn, callnode.args + carry_args)
[753]654      self.current_carry += 1
655      return c
[1211]656    elif is_BuiltIn_Call(callnode, 'Advance32', 1):     
[1571]657      #CARRYSET
[2206]658      rtn = self.carryvar.id + "." + "BitBlock_advance_n_<32>"
659      c = mkCall(rtn, callnode.args + adv_n_args)
660      self.current_adv_n += 1
[1211]661      return c
[813]662    elif is_BuiltIn_Call(callnode, 'ScanThru', 2):
[1571]663      #CARRYSET
[1997]664      rtn = self.carryvar.id + "." + "BitBlock_scanthru_ci_co"
[924]665      c = mkCall(rtn, callnode.args + carry_args)
[753]666      self.current_carry += 1
667      return c
[2041]668    elif is_BuiltIn_Call(callnode, 'AdvanceThenScanThru', 2):
669      #CARRYSET
670      rtn = self.carryvar.id + "." + "BitBlock_advance_then_scanthru"
671      c = mkCall(rtn, callnode.args + carry_args)
672      self.current_carry += 1
673      return c
674    elif is_BuiltIn_Call(callnode, 'AdvanceThenScanTo', 2):
675      #CARRYSET
676      rtn = self.carryvar.id + "." + "BitBlock_advance_then_scanthru" 
677      if self.carryout == "":  scanclass = mkCall('simd_andc', [ast.Name('EOF_mask', ast.Load()), callnode.args[1]])
678      else: scanclass = mkCall('simd_not', [callnode.args[1]])
[2049]679      c = mkCall(rtn, [callnode.args[0], scanclass] + carry_args)
[2041]680      self.current_carry += 1
681      return c
682    elif is_BuiltIn_Call(callnode, 'SpanUpTo', 2):
683      #CARRYSET
684      rtn = self.carryvar.id + "." + "BitBlock_span_upto"
685      c = mkCall(rtn, callnode.args + carry_args)
686      self.current_carry += 1
687      return c
688    elif is_BuiltIn_Call(callnode, 'InclusiveSpan', 2):
689      #CARRYSET
[2049]690#      rtn = self.carryvar.id + "." + "BitBlock_span_upto"
691#      c = mkCall('simd_or', [mkCall(rtn, callnode.args + carry_args), callnode.args[1]])
692      rtn = self.carryvar.id + "." + "BitBlock_inclusive_span"
693      c = mkCall(rtn, callnode.args + carry_args)
[2041]694      self.current_carry += 1
695      return c
696    elif is_BuiltIn_Call(callnode, 'ExclusiveSpan', 2):
697      #CARRYSET
[2049]698#      rtn = self.carryvar.id + "." + "BitBlock_span_upto"
699#      c = mkCall('simd_andc', [mkCall(rtn, callnode.args + carry_args), callnode.args[0]])
700      rtn = self.carryvar.id + "." + "BitBlock_exclusive_span"
701      c = mkCall(rtn, callnode.args + carry_args)
[2041]702      self.current_carry += 1
703      return c
[902]704    elif is_BuiltIn_Call(callnode, 'ScanTo', 2):
[1520]705      # Modified Oct. 9, 2011 to directly use BitBlock_scanthru, eliminating duplication
706      # in having a separate BitBlock_scanto routine.
[1571]707      #CARRYSET
[1997]708      rtn = self.carryvar.id + "." + "BitBlock_scanthru_ci_co" 
[1520]709      if self.carryout == "":  scanclass = mkCall('simd_andc', [ast.Name('EOF_mask', ast.Load()), callnode.args[1]])
710      else: scanclass = mkCall('simd_not', [callnode.args[1]])
711      c = mkCall(rtn, [callnode.args[0], scanclass] + carry_args)
[902]712      self.current_carry += 1
713      return c
[1074]714    elif is_BuiltIn_Call(callnode, 'ScanToFirst', 1):
[1571]715      #CARRYSET
716      rtn = self.carryvar.id + "." + "BitBlock_scantofirst"
[1074]717      #if self.carryout == "":  carry_args = [ast.Name('EOF_mask', ast.Load())] + carry_args
718      c = mkCall(rtn, callnode.args + carry_args)
719      self.current_carry += 1
720      return c
[1439]721    elif is_BuiltIn_Call(callnode, 'atEOF', 1):
722      if self.carryout != "": 
723        # Non final block: atEOF(x) = 0.
[1916]724        return mkCall('simd<1>::constant<0>', [])
[1439]725      else: return mkCall('simd_andc', [callnode.args[0], ast.Name('EOF_mask', ast.Load())])
726    elif is_BuiltIn_Call(callnode, 'inFile', 1):
727      if self.carryout != "": 
728        # Non final block: inFile(x) = x.
729        return callnode.args[0]
730      else: return mkCall('simd_and', [callnode.args[0], ast.Name('EOF_mask', ast.Load())])
[822]731    elif is_BuiltIn_Call(callnode, 'StreamScan', 2):
732      rtn = "StreamScan"           
733      c = mkCall(rtn, [ast.Name('(ScanBlock *) &' + callnode.args[0].id, ast.Load()), 
734                                           ast.Name('sizeof(BitBlock)/sizeof(ScanBlock)', ast.Load()),
735                                           ast.Name(callnode.args[1].id, ast.Load())])
736      return c
[1864]737    else:
[1865]738      #dump_Call(callnode)
[1864]739      return callnode
[765]740  def visit_BinOp(self, exprnode):
[753]741    self.generic_visit(exprnode)
[1571]742    carry_args = [ast.Num(self.current_carry)]
[2003]743    if self.carryin == "_ci":
744        carry_args = [mkCall(self.carryvar.id + "." + 'get_carry_in', [ast.Num(self.current_carry)]), ast.Num(self.current_carry)]
745    else: 
746        carry_args = [mkCall('simd<1>::constant<0>', []), ast.Num(self.current_carry)]
[753]747    if isinstance(exprnode.op, ast.Sub):
[1571]748      #CARRYSET
[2003]749      rtn = self.carryvar.id + "." + "BitBlock_sub_ci_co"
[924]750      c = mkCall(rtn, [exprnode.left, exprnode.right] + carry_args)
[753]751      self.current_carry += 1
752      return c
753    elif isinstance(exprnode.op, ast.Add):
[1571]754      #CARRYSET
[2004]755      rtn = self.carryvar.id + "." + "BitBlock_add_ci_co"
[924]756      c = mkCall(rtn, [exprnode.left, exprnode.right] + carry_args)
[753]757      self.current_carry += 1
758      return c
759    else: return exprnode
[2612]760  def visit_Assign(self, assigNode):
761    self.last_stmt_carries = CarryCounter().count(assigNode)
[2636]762    f = CheckForBuiltin(assigNode.value)
763    if f == None or not experimentalMode: 
[2612]764            self.generic_visit(assigNode)
765            self.last_stmt = assigNode
766            return assigNode
[2636]767    elif isCarryGenerating(f) or (isAdvance(f) and ((len(assigNode.value.args) == 1) or (assigNode.value.args[1].n==1))):
[2612]768    # We have an assignment v = pablo.SomeCarryGeneratingFunction()
769    #elif f == 'ScanThru':
770            if self.carryin == "_ci":
[2690]771                carry_in_expr = self.ccgo.GenerateCarryInAccess(self.operation_count)
[2612]772            else: 
773                carry_in_expr = mkCall('simd<1>::constant<0>', [])
774            callnode = assigNode.value
[2636]775            if isAdvance(f):
776               pablo_routine_call = mkCall('pablo_blk_' + f, [assigNode.value.args[0], carry_in_expr, assigNode.targets[0]])
777            elif f in ['ScanTo', 'AdvanceThenScanTo']:
[2612]778               if self.carryout == "":  scanclass = mkCall('simd_andc', [ast.Name('EOF_mask', ast.Load()), callnode.args[1]])
779               else: scanclass = mkCall('simd_not', [callnode.args[1]])
780               pablo_routine_call = mkCall('pablo_blk_' +f[:-2] + 'Thru', [callnode.args[0], scanclass, carry_in_expr, assigNode.targets[0]])
781            else:
782               pablo_routine_call = mkCall('pablo_blk_' + f, assigNode.value.args + [carry_in_expr, assigNode.targets[0]])
783            self.last_stmt = pablo_routine_call
[2690]784            compiled = self.ccgo.GenerateCarryOutStore(self.operation_count, pablo_routine_call)
785            self.operation_count += 1
[2612]786            self.current_carry += 1
787            return compiled
788    else:
789            self.generic_visit(assigNode)
790            self.last_stmt = assigNode
[2690]791            self.operation_count += 1
[2612]792            return assigNode
[2636]793           
794           
[753]795  def visit_If(self, ifNode):
[2636]796    self.block_no += 1
[2637]797    this_block = self.block_no
[753]798    carry_base = self.current_carry
799    carries = CarryCounter().count(ifNode)
[2206]800    assert adv_nCounter().count(ifNode) == 0, "Advance(x,n) within if: illegal\n"
[753]801    self.generic_visit(ifNode)
[2264]802    if carries == 0 or self.carryin == "": 
803      self.last_stmt = ifNode
804      return ifNode
[1571]805    #CARRYSET
806    carry_arglist = [ast.Num(carry_base), ast.Num(carries)]
[2636]807    #new_test = ast.BoolOp(ast.Or(), [ifNode.test, mkCall(ast.Attribute(self.carryvar, 'CarryTest', ast.Load()), carry_arglist)])
[2637]808    #new_else_part = ifNode.orelse + [mkCallStmt(ast.Attribute(self.carryvar, 'CarryDequeueEnqueue', ast.Load()), carry_arglist)]
809    new_test = self.ccgo.GenerateCarryIfTest(this_block, ifNode.test)
810    new_else_part = ifNode.orelse + self.ccgo.GenerateCarryElseFinalization(this_block)
[2264]811    newIf = ast.If(new_test, ifNode.body, new_else_part)
812    self.last_stmt = newIf
[2265]813    self.last_stmt_carries = carries
[2264]814    return newIf
815
[2265]816
817  def is_while_special_case(self, whileNode):
818    #
819    # Special case optimization for pattern:
820    #   m=pablo.scan...()
821    #   while m:
822    #      S
823    #      m=pablo.scan...()
824    #
825    # Determine the original test expression, now encloded in bitblock::any()
826    original_test_expr = whileNode.test.args[0]
827    if not isinstance(original_test_expr, ast.Name): return False
828    test_var = original_test_expr.id
829    if not isinstance(self.last_stmt, ast.Assign): return False
830    if not isinstance(whileNode.body[-1], ast.Assign): return False
831    if len(self.last_stmt.targets) != 1: return False
832    if len(whileNode.body[-1].targets) != 1: return False
833    if not isinstance(self.last_stmt.targets[0], ast.Name): return False
834    if not isinstance(whileNode.body[-1].targets[0], ast.Name): return False
835    if self.last_stmt.targets[0].id != test_var: return False
836    if whileNode.body[-1].targets[0].id != test_var: return False
[2269]837    if self.last_stmt_carries != 1: return False
[2265]838    if CarryCounter().count(whileNode.body[-1]) != 1: return False
839    return True
840
[753]841  def visit_While(self, whileNode):
[2265]842    # Determine the original test expression, now encloded in bitblock::any()
[2636]843    self.block_no += 1
[2638]844    this_block = self.block_no
[2265]845    original_test_expr = whileNode.test.args[0]
[941]846    if self.carryout == '':
[2265]847      whileNode.test.args[0] = mkCall("simd_and", [original_test_expr, ast.Name('EOF_mask', ast.Load())])
[753]848    carry_base = self.current_carry
[2206]849    assert adv_nCounter().count(whileNode) == 0, "Advance(x,n) within while: illegal\n"
[753]850    carries = CarryCounter().count(whileNode)
[2269]851#   Special Case Recognition
852    is_special = self.is_while_special_case(whileNode)
[1571]853    #CARRYSET
[753]854    if carries == 0: return whileNode
[2628]855    local_carryvar = ast.Name('sub' + self.carryvar.id, ast.Load())
[2631]856    inner_while = self.local_while_xfrm(local_carryvar, copy.deepcopy(whileNode))
[753]857    self.generic_visit(whileNode)
[2640]858    local_carry_decl = self.ccgo.GenerateLocalDeclare(this_block)
859    #local_carry_decl = mkCallStmt('LocalCarryDeclare', [local_carryvar, ast.Num(carries)])
[2689]860    inner_while.body = local_carry_decl + inner_while.body
[2638]861    #final_combine = mkCallStmt(ast.Attribute(self.carryvar, 'CarryCombine', ast.Load()), [ast.Attribute(local_carryvar, 'cq', ast.Load()),ast.Num(carry_base), ast.Num(carries)])
862    final_combine = self.ccgo.GenerateCarryWhileFinalization(this_block)
[2689]863    inner_while.body += final_combine
[1571]864    #CARRYSET
[2269]865
866#   Special Case Optimization
867    if is_special:
868      # We combine the final carry into the one preceeding the loop.
869      combine1 = mkCallStmt(ast.Attribute(self.carryvar, 'CarryCombine1', ast.Load()), [ast.Num(carry_base-1), ast.Num(carry_base+carries-1)])
870      while_body_extend = [inner_while, combine1]
871      # The carry test can skip the final case.
872      carry_test_arglist = [ast.Num(carry_base), ast.Num(carries-1)]
873    else: 
874      carry_test_arglist = [ast.Num(carry_base), ast.Num(carries)]
875      while_body_extend = [inner_while]
876
[921]877    if self.carryin == '': new_test = whileNode.test
[2640]878    else: new_test = self.ccgo.GenerateCarryWhileTest(this_block, whileNode.test)
879    else_part = [self.ccgo.GenerateCarryElseFinalization(this_block)]   
[2269]880    newIf = ast.If(new_test, whileNode.body + while_body_extend, else_part)
[2264]881    self.last_stmt = newIf
[2265]882    self.last_stmt_carries = carries
[2264]883    return newIf
[753]884
885class StreamStructGen(ast.NodeVisitor):
886  """
887  Given a BitStreamSet subclass, generate the equivalent C struct.
888  >>> obj = ast.parse(r'''
889  ... class S1(BitStreamSet):
890  ...   a1 = 0
891  ...   a2 = 0
892  ...   a3 = 0
893  ...
894  ... class S2(BitStreamSet):
895  ...   x1 = 0
896  ...   x2 = 0
897  ... ''')
898  >>> print StreamStructGen().gen(obj)
899  struct S1 {
900    BitBlock a1;
901    BitBlock a2;
902    BitBlock a3;
[2206]903  }    self.current_adv_n = 0
[1211]904
[753]905 
906  struct S2 {
907    BitBlock x1;
908    BitBlock x2;
909  }
910  """
[857]911  def __init__(self, asType=False):
912    self.asType = asType
[753]913  def gen(self, tree):
914    self.Ccode=""
915    self.generic_visit(tree)
916    return self.Ccode
[865]917  def gen_struct_types(self, tree):
918    self.asType = True
919    self.Ccode=""
920    self.generic_visit(tree)
921    return self.Ccode
922  def gen_struct_vars(self, tree):
923    self.asType = False
924    self.Ccode=""
925    self.generic_visit(tree)
926    return self.Ccode
[753]927  def visit_ClassDef(self, node):
[857]928    class_name = node.name[0].upper() + node.name[1:]
929    instance_name = node.name[0].lower() + node.name[1:]
[880]930    self.Ccode += "  struct " + class_name
[865]931    if self.asType:
932            self.Ccode += " {\n"
933            for stmt in node.body:
934              if isinstance(stmt, ast.Assign):
935                for v in stmt.targets:
936                  if isinstance(v, ast.Name):
937                    self.Ccode += "  BitBlock " + v.id + ";\n"
938            self.Ccode += "}" 
939    else: self.Ccode += " " + instance_name
[857]940    self.Ccode += ";\n\n"
[753]941 
942class StreamFunctionDecl(ast.NodeVisitor):
943  def __init__(self):
944    pass
945  def gen(self, tree):
946    self.Ccode=""
947    self.generic_visit(tree)
948    return self.Ccode
949  def visit_FunctionDef(self, node):
950    self.Ccode += "static inline void " + node.name + "("
951    pending = ""
952    for arg in node.args.args:
953      if isinstance(arg, ast.Name):
954        self.Ccode += pending + arg.id.upper()[0] + arg.id[1:] + " & " + arg.id
955        pending = ", "
956    self.Ccode += ");\n"
957
[2099]958class AssertCompiler(ast.NodeTransformer):
959  def __init__(self):
960    self.assert_routine = ast.parse(error_routine).body[0].value
961  def xfrm(self, t):
962    return self.generic_visit(t)
963  def visit_Expr(self, node):
964    if isinstance(node.value, ast.Call):
965        if is_BuiltIn_Call(node.value, "assert_0", 2):
966                err_stream = node.value.args[0]
967                err_code = node.value.args[1]
[2640]968                return ast.If(mkCall('bitblock::any', [err_stream]),
[2100]969                              [ast.Expr(mkCall(self.assert_routine, [err_code, err_stream]))],
[2099]970                              [])
971        else: return node
972    else: return node
973       
[810]974#
975# Adding Debugging Statements
976#
977class Add_SIMD_Register_Dump(ast.NodeTransformer):
978  def xfrm(self, t):
979    return self.generic_visit(t)
980  def visit_Assign(self, t):
981    self.generic_visit(t)
982    v = t.targets[0]
[1843]983    dump_stmt = mkCallStmt(' print_register<BitBlock>', [ast.Str(Cgen.py2C().gen(v)), v])
[810]984    return [t, dump_stmt]
[880]985
[1901]986#
987# Adding ASSERT_BITBLOCK_ALIGN macros
988#
989class Add_Assert_BitBlock_Align(ast.NodeTransformer):
990    def xfrm(self, t):
991      return self.generic_visit(t)
992    def visit_Assign(self, t):
993      self.generic_visit(t)
994      v = t.targets[0]
995      dump_stmt = mkCallStmt(' ASSERT_BITBLOCK_ALIGN', [v])
996      return [t, dump_stmt]
997
[880]998class StreamFunctionCarryCounter(ast.NodeVisitor):
999  def __init__(self):
1000        self.carry_count = {}
1001       
1002  def count(self, node):
1003        self.generic_visit(node)
1004        return self.carry_count
1005                                   
1006  def visit_FunctionDef(self, node):   
1007        type_name = node.name[0].upper() + node.name[1:]                       
1008        self.carry_count[type_name] = CarryCounter().count(node)
1009     
1010class StreamFunctionCallXlator(ast.NodeTransformer):
[937]1011  def __init__(self, xlate_type="normal"):
[880]1012        self.stream_function_type_names = []
[937]1013        self.xlate_type = xlate_type
1014
[1195]1015  def xfrm(self, node, stream_function_type_names, C_syntax):
[880]1016        self.stream_function_type_names = stream_function_type_names
[1195]1017        self.C_syntax = C_syntax
[880]1018        self.generic_visit(node)
1019       
1020  def visit_Call(self, node):   
1021        self.generic_visit(node)
1022
[1957]1023        if isinstance(node, ast.Call) and isinstance(node.func, ast.Name):# and node.func.id in self.stream_function_type_names:
[1195]1024             name = lower1(node.func.id)
1025             node.func.id = name + ("_" if self.C_syntax else ".") + ("do_final_block" if self.xlate_type == "final" else "do_block")
1026             if self.C_syntax:
[1196]1027                     node.args = [ast.Name(lower1(name), ast.Load())] + node.args
[937]1028             if self.xlate_type == "final":
1029                   node.args = node.args + [ast.Name("EOF_mask", ast.Load())]
[1195]1030                     
[880]1031        return node     
1032               
1033class StreamFunctionVisitor(ast.NodeVisitor):
1034        def __init__(self,node):
1035                self.stream_function_node = {}
1036                self.generic_visit(node)
1037                                                             
1038        def visit_FunctionDef(self, node):                     
1039                key = node.name[0].upper() + node.name[1:]
1040                self.stream_function_node[key] = node
[2260]1041
1042
[880]1043               
1044class StreamFunction():
1045        def __init__(self):
1046                self.carry_count = 0 
[2260]1047                self.init_to_one_list = [] 
[2206]1048                self.adv_n_count = 0 
[880]1049                self.type_name = ""
1050                self.instance_name = "" 
1051                self.parameters = ""
1052                self.declarations = "" 
1053                self.initializations = "" 
[2393]1054       
1055        def dump(self):
[2408]1056                print "%s" % (self.type_name)
1057                print "%s=%s" % ("Carry Count", str(self.carry_count))
1058                print "%s=[%s]" % ("Init to One List" , ','.join(map(str,self.init_to_one_list)))
1059                print "%s=%s" % ("Adv n Count", str(self.adv_n_count)) 
1060        #print "Instance Name:"     #+ self.instance_name = ""
1061        #print "Parameters:"        #+ self.parameters = ""
1062        #print "Declarations:"           #+ self.declarations = ""
1063        #print "Initializations:"   # + self.initializations = ""
1064   
[813]1065#
[903]1066# TODO Consolidate *all* C code generation into the Emitter class.   Medium priority.
1067# TODO Implement 'pretty print' indentation.   Low priority.
1068# TODO Migrate Emiter() class to Emitter module.  Medium priority.
[908]1069
1070def lower1(name):
1071    return name[0].lower() + name[1:]
1072def upper1(name):
1073    return name[0].upper() + name[1:]
1074
[1196]1075def escape_newlines(str):
1076  return str.replace('\n', '\\\n')
1077
[880]1078class Emitter():
[2640]1079        def __init__(self, use_C_syntax, ccgo):
[1195]1080                self.use_C_syntax = use_C_syntax
[2640]1081                self.ccgo = ccgo
[753]1082
[880]1083        def definition(self, stream_function, icount=0):
1084               
1085                constructor = ""
1086                carry_declaration = ""
[1195]1087                self.type_name = stream_function.type_name
[880]1088               
[2206]1089                if stream_function.carry_count > 0 or stream_function.adv_n_count > 0:
[2260]1090                        constructor = self.constructor(stream_function.type_name, stream_function.carry_count, stream_function.init_to_one_list, stream_function.adv_n_count)
[2206]1091                        carry_declaration = self.carry_declare('carryQ', stream_function.carry_count, stream_function.adv_n_count)
[753]1092
[880]1093                do_block_function = self.do_block(self.do_block_parameters(stream_function.parameters), 
1094                                                stream_function.declarations, 
1095                                                stream_function.initializations, 
1096                                                stream_function.statements)             
[906]1097
[922]1098                do_final_block_function = self.do_final_block(self.do_final_block_parameters(stream_function.parameters), 
1099                                                stream_function.declarations, 
1100                                                stream_function.initializations, 
1101                                                stream_function.final_block_statements)                 
1102
[906]1103                do_segment_function = self.do_segment(self.do_segment_parameters(stream_function.parameters), 
1104                                                self.do_segment_args(stream_function.parameters))       
1105
[1195]1106                if self.use_C_syntax:
[1196]1107                        return self.indent(icount) + "struct " + stream_function.type_name + " {" \
[1195]1108                               + "\n" + self.indent(icount) + carry_declaration \
1109                               + "\n" + self.indent(icount) + "};\n" \
1110                               + "\n" + self.indent(icount) + do_block_function \
1111                               + "\n" + self.indent(icount) + do_final_block_function \
1112                               + "\n" + self.indent(icount) + do_segment_function + "\n\n"
1113                               
[880]1114                return self.indent(icount) + "struct " + stream_function.type_name + " {" \
1115                + "\n" + self.indent(icount) + constructor \
1116                + "\n" + self.indent(icount) + do_block_function \
[922]1117                + "\n" + self.indent(icount) + do_final_block_function \
[906]1118                + "\n" + self.indent(icount) + do_segment_function \
[880]1119                + "\n" + self.indent(icount) + carry_declaration \
1120                + "\n" + self.indent(icount) + "};\n\n"
1121
[2260]1122        def constructor(self, type_name, carry_count, init_to_one_list, adv_n_count, icount=0):
[2688]1123                one_inits = self.ccgo.GenerateInitializations()
1124                #one_inits = ""
1125                #for v in init_to_one_list:
1126                #       one_inits += "  carryQ.cq[%s] = carryQ.carry_flip(carryQ.cq[%s]);\n" % (v, v)
[2206]1127                adv_n_decl = ""
1128                #for i in range(adv_n_count): adv_n_decl += self.indent(icount+2) + "pending64[%s] = simd<1>::constant<0>();\n" % i     
[2260]1129                return self.indent(icount) + "%s() { ""\n" % (type_name) + adv_n_decl + self.carry_init(carry_count) + one_inits + " }" 
[880]1130                       
1131        def do_block(self, parameters, declarations, initializations, statements, icount=0):
[1195]1132                pfx = (lower1(self.type_name) + "_" if self.use_C_syntax else "")
[1196]1133                if self.use_C_syntax:
1134                        return "#define " + pfx + "do_block(" + parameters + ")\\\n do {" \
1135                        + "\\\n" + self.indent(icount) + escape_newlines(declarations) \
1136                        + "\\\n" + self.indent(icount) + escape_newlines(initializations) \
1137                        + "\\\n" + self.indent(icount) + escape_newlines(statements) \
1138                        + "\\\n" + self.indent(icount + 2) + "} while (0)" 
[1997]1139                return self.indent(icount) + do_block_inline_decorator + "void " + pfx + "do_block(" + parameters + ") {" \
[1195]1140                + "\n" + self.indent(icount) + declarations \
[880]1141                + "\n" + self.indent(icount) + initializations \
1142                + "\n" + self.indent(icount) + statements \
1143                + "\n" + self.indent(icount + 2) + "}" 
1144
[1196]1145
1146
1147
[922]1148        def do_final_block(self, parameters, declarations, initializations, statements, icount=0):
[1195]1149                pfx = (lower1(self.type_name) + "_" if self.use_C_syntax else "")
[1196]1150                if self.use_C_syntax:
1151                        return "#define " + pfx + "do_final_block(" + parameters + ")\\\n do {" \
1152                        + "\\\n" + self.indent(icount) + escape_newlines(declarations) \
1153                        + "\\\n" + self.indent(icount) + escape_newlines(initializations) \
1154                        + "\\\n" + self.indent(icount) + escape_newlines(statements) \
1155                        + "\\\n" + self.indent(icount + 2) + "} while (0)" 
[1997]1156                return self.indent(icount) + do_final_block_inline_decorator + "void " + pfx + "do_final_block(" + parameters + ") {" \
[1195]1157                + "\n" + self.indent(icount) + declarations \
[922]1158                + "\n" + self.indent(icount) + initializations \
1159                + "\n" + self.indent(icount) + statements \
1160                + "\n" + self.indent(icount + 2) + "}" 
1161
[906]1162        def do_segment(self, parameters, do_block_call_args, icount=0):
[1195]1163                pfx = (lower1(self.type_name) + "_" if self.use_C_syntax else "")
[1196]1164                if self.use_C_syntax:
1165                        return "#define " + pfx + "do_segment(" + parameters + ")\\\n do {" \
1166                        + "\\\n" + self.indent(icount) + "  int i;" \
[1882]1167                        + "\\\n" + self.indent(icount) + "  for (i = 0; i < segment_blocks; i++)" \
[1196]1168                        + "\\\n" + self.indent(icount) + "    " + pfx + "do_block(" + do_block_call_args + ");" \
1169                        + "\\\n" + self.indent(icount + 2) + "} while (0)" 
[1195]1170                return self.indent(icount) + "void " + pfx + "do_segment(" + parameters + ") {" \
[1196]1171                + "\n" + self.indent(icount) + "  int i;" \
[1882]1172                + "\n" + self.indent(icount) + "  for (i = 0; i < segment_blocks; i++)" \
[1195]1173                + "\n" + self.indent(icount) + "    " + pfx + "do_block(" + do_block_call_args + ");" \
[906]1174                + "\n" + self.indent(icount + 2) + "}" 
1175
[1198]1176        def declaration(self, type_name, instance_name, icount=0):
1177                if self.use_C_syntax: return self.indent(icount) + "struct " + type_name + " " + instance_name + ";\n"
[880]1178                return self.indent(icount) + type_name + " " + instance_name + ";\n"
1179               
1180        def carry_init(self, carry_count, icount=0):   
[1571]1181                #CARRY SET
1182                return ""
1183               
[2206]1184        def carry_declare(self, carry_variable, carry_count, adv_n_count=0, icount=0):
1185                adv_n_decl = ""
1186                #if adv_n_count > 0:
1187                #       adv_n_decl = "\n" + self.indent(icount) + "BitBlock pending64[%s];" % adv_n_count
[1571]1188                #CARRY SET
[2640]1189                return self.indent(icount) + self.ccgo.GenerateCarryDecls()
[880]1190
1191        def carry_test(self, carry_variable, carry_count, icount=0):
[1571]1192                #CARRY SET
1193                return self.indent(icount) + "carryQ.CarryTest(0, %i)" % (carry_count)         
[880]1194               
1195        def indent(self, icount):
1196                s = ""
1197                for i in range(0,icount): s += " "
1198                return s       
1199               
1200        def do_block_parameters(self, parameters):
[1195]1201                if self.use_C_syntax:
[1196]1202                        #return ", ".join([self.type_name + " * " + self.instance_name] + [upper1(p) + " * " + lower1(p) for p in parameters])
1203                        return ", ".join([lower1(self.type_name)] + [lower1(p) for p in parameters])
[1195]1204                else: return ", ".join([upper1(p) + " & " + lower1(p) for p in parameters])
[880]1205               
[922]1206        def do_final_block_parameters(self, parameters):
[1195]1207                if self.use_C_syntax:
[1196]1208                        #return ", ".join([self.type_name + " * " + self.instance_name] + [upper1(p) + " * " + lower1(p) for p in parameters]+ ["BitBlock EOF_mask"])
1209                        return ", ".join([lower1(self.type_name)] + [lower1(p) for p in parameters]+ ["EOF_mask"])
[1195]1210                else: return ", ".join([upper1(p) + " & " + lower1(p) for p in parameters]+ ["BitBlock EOF_mask"])
[922]1211               
[906]1212        def do_segment_parameters(self, parameters):
[1195]1213                if self.use_C_syntax:
[1196]1214                        #return ", ".join([self.type_name + " * " + + self.instance_name] + [upper1(p) + " " + lower1(p) + "[]" for p in parameters])
[2218]1215                        return ", ".join([lower1(self.type_name)] + [lower1(p) for p in parameters] + ["segment_blocks"])
[1882]1216                else: return ", ".join([upper1(p) + " " + lower1(p) + "[]" for p in parameters] + ["int segment_blocks"])
[906]1217
1218        def do_segment_args(self, parameters):
[1195]1219                if self.use_C_syntax:
1220                        return ", ".join([lower1(self.type_name)] + [lower1(p) + "[i]" for p in parameters])
1221                else: return ", ".join([lower1(p) + "[i]" for p in parameters])
[908]1222
[753]1223def main(infilename, outfile = sys.stdout):
1224  t = ast.parse(file(infilename).read())
[865]1225  outfile.write(StreamStructGen(True).gen(t))
[753]1226  outfile.write(FunctionXlator().xlat(t))
1227
1228#
1229#  Routines for compatibility with the old compiler/template.
1230#  Quick and dirty hacks for now - Dec. 2010.
1231#
1232
[777]1233class MainLoopTransformer:
[2627]1234  def __init__(self, main_module, C_syntax=False, add_dump_stmts=False, add_assert_bitblock_align=False, dump_func_data=False, main_node_id='Main'):
[889]1235       
[777]1236    self.main_module = main_module
[880]1237    self.main_node_id = main_node_id
[1195]1238    self.use_C_syntax = C_syntax
[889]1239    self.add_dump_stmts = add_dump_stmts
[1901]1240    self.add_assert_bitblock_align = add_assert_bitblock_align
[2393]1241    self.dump_func_data = dump_func_data
[880]1242   
1243        # Gather and partition function definition nodes.
1244    stream_function_visitor = StreamFunctionVisitor(self.main_module)
1245    self.stream_function_node = stream_function_visitor.stream_function_node
[2215]1246    for key, node in self.stream_function_node.iteritems():
1247                AdvanceCombiner().xfrm(node)
[880]1248    self.main_node = self.stream_function_node[main_node_id]
1249    self.main_carry_count = CarryCounter().count(self.main_node)
[2206]1250    self.main_adv_n_count = adv_nCounter().count(self.main_node)
[2690]1251    self.main_carry_info_set = CarryInfoSetVisitor(self.main_node)
[2640]1252    self.main_ccgo = Strategic_CCGO_Factory(self.main_carry_info_set)
[2206]1253    assert self.main_adv_n_count == 0, "Advance32() in main not supported.\n"
[880]1254    del self.stream_function_node[self.main_node_id]
1255   
1256    self.stream_functions = {}
1257    for key, node in self.stream_function_node.iteritems():
1258                stream_function = StreamFunction()
1259                stream_function.carry_count = CarryCounter().count(node)
[2260]1260                stream_function.init_to_one_list = CarryInitToOneList().count(node)
[2206]1261                stream_function.adv_n_count = adv_nCounter().count(node)
[2690]1262                carry_info_set = CarryInfoSetVisitor(node)
[2640]1263                stream_function.ccgo = Strategic_CCGO_Factory(carry_info_set)
[880]1264                stream_function.type_name = node.name[0].upper() + node.name[1:]
1265                stream_function.instance_name = node.name[0].lower() + node.name[1:]
1266                stream_function.parameters = FunctionVars(node).params
1267                stream_function.declarations = BitBlock_decls_of_fn(node)
[2688]1268                stream_function.declarations += stream_function.ccgo.GenerateStreamFunctionDecls()
[880]1269                stream_function.initializations = StreamInitializations().xfrm(node) 
1270               
[2631]1271                t = TempifyBuiltins()
1272                t.xfrm(node)
1273                stream_function.declarations += "\n" + BitBlock_decls_from_vars(t.tempVars())
1274
[2630]1275                StringMatchCompiler().xfrm(node)
1276                AugAssignRemoval().xfrm(node)
1277
[2606]1278               
[880]1279                Bitwise_to_SIMD().xfrm(node)
[922]1280                final_block_node = copy.deepcopy(node)
[1195]1281                if self.use_C_syntax:
[1196]1282                        carryQname = stream_function.instance_name + ".carryQ"
[1195]1283                else: carryQname = "carryQ"
[2640]1284                CarryIntroVisitor = CarryIntro(stream_function.ccgo, carryQname)
[2628]1285                CarryIntroVisitor.xfrm_fndef(node)
1286                CarryIntroVisitor.xfrm_fndef_final(final_block_node)
[2640]1287                #
1288                # Compile asserts after carry intro so that generated if-statements
1289                # are ignored.
1290                AssertCompiler().xfrm(node)
1291                AssertCompiler().xfrm(final_block_node)
[889]1292                if self.add_dump_stmts: 
1293                        Add_SIMD_Register_Dump().xfrm(node)
[1849]1294                        Add_SIMD_Register_Dump().xfrm(final_block_node)
[1901]1295
1296                if self.add_assert_bitblock_align:
1297                        Add_Assert_BitBlock_Align().xfrm(node)
1298                        Add_Assert_BitBlock_Align().xfrm(final_block_node)
1299
[2636]1300                #if stream_function.carry_count > 0:
1301                #       node.body += [mkCallStmt('carryQ.CarryQ_Adjust', [ast.Num(stream_function.carry_count)])]
[2640]1302                node.body += stream_function.ccgo.GenerateStreamFunctionFinalization()
[2636]1303
[889]1304               
[880]1305                stream_function.statements = Cgen.py2C(4).gen(node.body)
[922]1306                stream_function.final_block_statements = Cgen.py2C(4).gen(final_block_node.body)
[880]1307                self.stream_functions[stream_function.type_name] = stream_function
[2393]1308               
1309    if self.dump_func_data:     
1310        for key, value in self.stream_functions.iteritems():
1311                        value.dump()
[2409]1312        sys.exit()
[2393]1313               
[2640]1314    self.emitter = Emitter(self.use_C_syntax, stream_function.ccgo)
[880]1315   
[777]1316  def any_carry_expr(self):
[880]1317       
1318        carry_test = []
1319       
1320        if self.main_carry_count > 0:
[1571]1321                        carry_test.append(self.emitter.carry_test('carryQ', self.main_carry_count)) 
[880]1322                        carry_test.append(" || ")
1323
1324        for key in self.stream_functions.keys():               
1325                if self.stream_functions[key].carry_count > 0:
[1571]1326                        carry_test.append(self.stream_functions[key].instance_name + "." + self.emitter.carry_test('carryQ',self.stream_functions[key].carry_count))# TODO Update self.emitter.carry_test
[880]1327                        carry_test.append(" || ")
1328
1329        if len(carry_test) > 0:
1330                carry_test.pop()
[1195]1331                return "".join(carry_test)
[880]1332        return "1"
1333
1334  def gen_globals(self):
[865]1335    self.Cglobals = StreamStructGen().gen_struct_types(self.main_module)
[880]1336    for key in self.stream_functions.keys():
[2640]1337                sf = self.stream_functions[key]
1338                self.Cglobals += Emitter(self.use_C_syntax, sf.ccgo).definition(sf, 2)     
[880]1339                       
1340  def gen_declarations(self): 
[865]1341    self.Cdecls = StreamStructGen().gen_struct_vars(self.main_module)
[880]1342    self.Cdecls += BitBlock_decls_of_fn(self.main_node)
1343    if self.main_carry_count > 0: 
[1571]1344        self.Cdecls += self.emitter.carry_declare('carryQ', self.main_carry_count)
[880]1345               
[777]1346  def gen_initializations(self):
1347    self.Cinits = ""
[880]1348    if self.main_carry_count > 0: 
1349        self.Cinits += self.emitter.carry_init(self.main_carry_count)
[777]1350    self.Cinits += StreamInitializations().xfrm(self.main_module)
[1195]1351    if self.use_C_syntax:
1352                for key in self.stream_functions.keys():
[1196]1353                        if self.stream_functions[key].carry_count == 0: continue
1354                        self.Cinits += self.emitter.declaration(self.stream_functions[key].type_name, self.stream_functions[key].instance_name, 2)
1355                        self.Cinits += "CarryInit(" + self.stream_functions[key].instance_name + ".carryQ, %i);\n" % (self.stream_functions[key].carry_count)
1356    else:
1357                for key in self.stream_functions.keys():
1358                        self.Cinits += self.emitter.declaration(self.stream_functions[key].type_name, self.stream_functions[key].instance_name, 2)
[1195]1359
[880]1360                       
[889]1361  def xfrm_block_stmts(self):
[2009]1362    StringMatchCompiler().xfrm(self.main_node)
[880]1363    AugAssignRemoval().xfrm(self.main_node)
1364    Bitwise_to_SIMD().xfrm(self.main_node)
[2099]1365    Bitwise_to_SIMD().xfrm(self.main_node)
[937]1366    final_block_main = copy.deepcopy(self.main_node)
[2690]1367    carry_info_set = CarryInfoSetVisitor(self.main_node)
[2636]1368    ccgo = Strategic_CCGO_Factory(carry_info_set)
1369    CarryIntroVisitor = CarryIntro(ccgo)
[2628]1370    CarryIntroVisitor.xfrm_fndef(self.main_node)
1371    CarryIntroVisitor.xfrm_fndef_final(final_block_main)
[2636]1372    AssertCompiler().xfrm(self.main_node)
[889]1373    if self.add_dump_stmts: 
[880]1374        Add_SIMD_Register_Dump().xfrm(self.main_node)
[939]1375        Add_SIMD_Register_Dump().xfrm(final_block_main)
[880]1376               
[1901]1377    if self.add_assert_bitblock_align:
[1917]1378        print "add_assert_bitblock_align"
[1901]1379        Add_Assert_BitBlock_Align().xfrm(self.main_node)
1380        Add_Assert_BitBlock_Align().xfrm(final_block_main)
1381
[1195]1382    StreamFunctionCallXlator().xfrm(self.main_node, self.stream_function_node.keys(), self.use_C_syntax)
1383    StreamFunctionCallXlator('final').xfrm(final_block_main, self.stream_function_node.keys(), self.use_C_syntax)
[889]1384   
[2636]1385    #if self.main_carry_count > 0:
[1571]1386                #self.main_node.body += [mkCallStmt('CarryQ_Adjust', [ast.Name('carryQ', ast.Load()), ast.Num(self.main_carry_count)])]
[2636]1387    self.main_node.body += ccgo.GenerateStreamFunctionFinalization()
1388   
[889]1389   
1390       
[880]1391    self.Cstmts = Cgen.py2C().gen(self.main_node.body)
[937]1392    self.Cfinal_stmts = Cgen.py2C().gen(final_block_main.body)
[880]1393   
[753]1394if __name__ == "__main__":
1395                import doctest
[902]1396                doctest.testmod()
Note: See TracBrowser for help on using the repository browser.