source: proto/Compiler/carryInfo.py @ 3009

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

Support for pablo.MatchStar?

File size: 7.2 KB
Line 
1#
2# carryInfo.py
3#
4# Copyright 2012, Robert D. Cameron, Kenneth S. Herdy
5# All rights reserved.
6#
7# Information Gathering for Carry Processing in Pablo
8
9import ast
10
11def isCarryGenerating(builtin_fn):
12   return builtin_fn in ['ScanThru', 'ScanTo', 'AdvanceThenScanThru', 'AdvanceThenScanTo', 'SpanUpTo', 'InclusiveSpan', 'ExclusiveSpan', 'ScanToFirst', 'MatchStar']
13def usesCarryInit1(builtin_fn):
14   return builtin_fn in ['ScanToFirst']
15def isAdvance(builtin_fn):
16   return builtin_fn in ['Advance']
17
18
19def CheckForBuiltin(fncall, builtin_fnmod_noprefix='pablo'):
20  if not isinstance(fncall, ast.Call): return None
21  if isinstance(fncall.func, ast.Name): fn_name = fncall.func.id
22  elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
23    if fncall.func.value.id == builtin_fnmod_noprefix: fn_name = fncall.func.attr
24    else: return None
25  else: return None
26  if isCarryGenerating(fn_name) or isAdvance(fn_name): return fn_name
27  else: return None
28
29def CarryCountOfFn(fncall, builtin_fnmod_noprefix='pablo'):
30  if not isinstance(fncall, ast.Call): return 0
31  if isinstance(fncall.func, ast.Name): fn_name = fncall.func.id
32  elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
33    if fncall.func.value.id == builtin_fnmod_noprefix: fn_name = fncall.func.attr
34    else: return 0
35  else: return 0
36  if isAdvance(fn_name):
37    if len(fncall.args) == 1: return 1
38    else: return 0 #  return fncall.args[1].n  # Possibly count Advance(m, n) as generating n carries.
39  elif isCarryGenerating(fn_name): return 1
40  else: return 0
41 
42def is_BuiltIn_Call(fncall, builtin_fnname, builtin_arg_cnt, builtin_fnmod_noprefix='pablo'):
43        if isinstance(fncall.func, ast.Name): iscall = fncall.func.id == builtin_fnname
44        elif isinstance(fncall.func, ast.Attribute) and isinstance(fncall.func.value, ast.Name):
45                 iscall = fncall.func.value.id == builtin_fnmod_noprefix and fncall.func.attr == builtin_fnname
46        return iscall and len(fncall.args) == builtin_arg_cnt
47
48#
49# Carry Info Set
50#
51class CarryInfoSetVisitor(ast.NodeVisitor):
52  def __init__(self, streamFunctionNode):
53    (self.operation_count, self.block_count) = (0, 0)
54    (self.block_first_op, self.block_op_count, self.advance_amount) = ({}, {}, {})
55    self.init_one_list = []
56    (self.parent_block, self.children, self.whileblock) = ({}, {}, {})
57    self.containing_block = {}
58    (self.carry_count, self.adv_n_count, self.adv_1_count) = (0, 0, 0)
59    (self.total_advance, self.max_advance) = (0, 0)
60
61    # Initialize for the main block
62    self.block_no = 0
63    self.block_count += 1
64    self.children[0] = []
65    self.block_first_op[0] = 0
66    # Recursively process all blocks
67    self.generic_visit(streamFunctionNode)
68    self.block_op_count[0] = self.operation_count
69    self.whileblock[0] = False
70
71  def visit_Call(self, callnode):
72    self.generic_visit(callnode)
73    builtin = CheckForBuiltin(callnode)
74    if builtin == None: return
75    if isCarryGenerating(builtin): 
76      if usesCarryInit1(builtin): self.init_one_list.append(self.operation_count)
77      self.containing_block[self.operation_count] = self.block_no
78      self.operation_count += 1
79      self.carry_count += 1
80    elif isAdvance(builtin):
81      if len(callnode.args) > 1:
82        adv_amount = callnode.args[1].n
83        self.adv_n_count += 1
84      else: 
85        adv_amount = 1
86        self.adv_1_count += 1
87      self.advance_amount[self.operation_count] = adv_amount
88      self.total_advance += adv_amount
89      if adv_amount > self.max_advance: self.max_advance = adv_amount
90      self.containing_block[self.operation_count] = self.block_no
91      self.operation_count += 1
92    else: return
93
94  def block_visit(self, blkNode):
95    prnt = self.block_no
96    this_block_no = self.block_count
97    self.block_count += 1
98    self.parent_block[this_block_no] = prnt
99    self.children[prnt].append(this_block_no)
100    self.whileblock[this_block_no] = isinstance(blkNode, ast.While)
101    self.block_no = this_block_no
102    self.block_first_op[this_block_no] = self.operation_count
103    self.children[this_block_no] = []
104    self.generic_visit(blkNode)
105    self.block_op_count[this_block_no] = self.operation_count - self.block_first_op[this_block_no]
106    # reset for processing remainder of parent
107    self.block_no = self.parent_block[this_block_no]
108
109
110  def visit_If(self, ifNode): 
111    self.block_visit(ifNode)
112 
113  def visit_While(self, whileNode):   
114    self.block_visit(whileNode)
115
116
117
118
119#
120#
121# Determine the number of carries directly within each block.
122#
123def direct_block_carries(carryInfoSet, count_advance_1_as_carry = True, count_advance_n_as_n = False):
124    carries = [0 for i in range(carryInfoSet.block_count)]
125    for op in range(carryInfoSet.operation_count):
126        b = carryInfoSet.containing_block[op]
127        if op not in carryInfoSet.advance_amount.keys():
128          carries[b] += 1
129        elif carryInfoSet.advance_amount[op] == 1 and count_advance_1_as_carry: 
130          carries[b] += 1
131        elif count_advance_n_as_n:
132          carries[b] += carryInfoSet.advance_amount[op]
133    return carries
134
135
136#
137#####################################
138#
139# DEPRECATED - made redundant by CarryInfoSet
140#
141   
142   
143   
144   
145class CarryCounter(ast.NodeVisitor):
146  def visit_Call(self, callnode):
147    self.generic_visit(callnode)
148    self.carry_count += CarryCountOfFn(callnode)
149  def visit_BinOp(self, exprnode):
150    self.generic_visit(exprnode)
151    if isinstance(exprnode.op, ast.Sub):
152      self.carry_count += 1
153    if isinstance(exprnode.op, ast.Add):
154      self.carry_count += 1
155  def count(self, nodeToVisit):
156    self.carry_count = 0
157    self.generic_visit(nodeToVisit)
158    return self.carry_count
159
160#
161# Carry Initialization:  Aug. 4, 2012
162# - Carry variables are initialized to 0 by default
163# - However, the scan_to_first routine should ideally use
164#   initialization with 1.
165
166#
167class CarryInitToOneList(ast.NodeVisitor):
168  def visit_Call(self, callnode):
169    self.generic_visit(callnode)
170    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)  or is_BuiltIn_Call(callnode,'MatchStar', 2):           
171      self.carry_count += 1
172    elif is_BuiltIn_Call(callnode,'ScanToFirst', 1):
173      self.init_to_one_list.append(self.carry_count)
174      self.carry_count += 1
175  def visit_BinOp(self, exprnode):
176    self.generic_visit(exprnode)
177    if isinstance(exprnode.op, ast.Sub):
178      self.carry_count += 1
179    if isinstance(exprnode.op, ast.Add):
180      self.carry_count += 1
181  def count(self, nodeToVisit):
182    self.carry_count = 0
183    self.init_to_one_list = []
184    self.generic_visit(nodeToVisit)
185    return self.init_to_one_list
186
187class adv_nCounter(ast.NodeVisitor):
188  def visit_Call(self, callnode):
189    self.generic_visit(callnode)
190    if is_BuiltIn_Call(callnode,'Advance32', 1):       
191      self.adv_n_count += 1
192    if is_BuiltIn_Call(callnode,'Advance', 2):         
193      self.adv_n_count += 1
194  def count(self, nodeToVisit):
195    self.adv_n_count = 0
196    self.generic_visit(nodeToVisit)
197    return self.adv_n_count
198
199
200
201
202if __name__ == "__main__":
203                import doctest
204                doctest.testmod()
Note: See TracBrowser for help on using the repository browser.