source: proto/Compiler/carryInfo.py

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

Factor out AST helpers to mkast.py

File size: 7.5 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  def whileDepth(self, block_no):
117    if block_no == 0: return 0
118    elif self.whileblock[block_no]: 
119      return 1 + self.whileDepth(self.parent_block[block_no])
120    else: return self.whileDepth(self.parent_block[block_no])
121
122
123
124#
125#
126# Determine the number of carries directly within each block.
127#
128def direct_block_carries(carryInfoSet, count_advance_1_as_carry = True, count_advance_n_as_n = False):
129    carries = [0 for i in range(carryInfoSet.block_count)]
130    for op in range(carryInfoSet.operation_count):
131        b = carryInfoSet.containing_block[op]
132        if op not in carryInfoSet.advance_amount.keys():
133          carries[b] += 1
134        elif carryInfoSet.advance_amount[op] == 1 and count_advance_1_as_carry: 
135          carries[b] += 1
136        elif count_advance_n_as_n:
137          carries[b] += carryInfoSet.advance_amount[op]
138    return carries
139
140
141#
142#####################################
143#
144# DEPRECATED - made redundant by CarryInfoSet
145#
146   
147   
148   
149   
150class CarryCounter(ast.NodeVisitor):
151  def visit_Call(self, callnode):
152    self.generic_visit(callnode)
153    self.carry_count += CarryCountOfFn(callnode)
154  def visit_BinOp(self, exprnode):
155    self.generic_visit(exprnode)
156    if isinstance(exprnode.op, ast.Sub):
157      self.carry_count += 1
158    if isinstance(exprnode.op, ast.Add):
159      self.carry_count += 1
160  def count(self, nodeToVisit):
161    self.carry_count = 0
162    self.generic_visit(nodeToVisit)
163    return self.carry_count
164
165#
166# Carry Initialization:  Aug. 4, 2012
167# - Carry variables are initialized to 0 by default
168# - However, the scan_to_first routine should ideally use
169#   initialization with 1.
170
171#
172class CarryInitToOneList(ast.NodeVisitor):
173  def visit_Call(self, callnode):
174    self.generic_visit(callnode)
175    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):           
176      self.carry_count += 1
177    elif is_BuiltIn_Call(callnode,'ScanToFirst', 1):
178      self.init_to_one_list.append(self.carry_count)
179      self.carry_count += 1
180  def visit_BinOp(self, exprnode):
181    self.generic_visit(exprnode)
182    if isinstance(exprnode.op, ast.Sub):
183      self.carry_count += 1
184    if isinstance(exprnode.op, ast.Add):
185      self.carry_count += 1
186  def count(self, nodeToVisit):
187    self.carry_count = 0
188    self.init_to_one_list = []
189    self.generic_visit(nodeToVisit)
190    return self.init_to_one_list
191
192class adv_nCounter(ast.NodeVisitor):
193  def visit_Call(self, callnode):
194    self.generic_visit(callnode)
195    if is_BuiltIn_Call(callnode,'Advance32', 1):       
196      self.adv_n_count += 1
197    if is_BuiltIn_Call(callnode,'Advance', 2):         
198      self.adv_n_count += 1
199  def count(self, nodeToVisit):
200    self.adv_n_count = 0
201    self.generic_visit(nodeToVisit)
202    return self.adv_n_count
203
204
205
206
207if __name__ == "__main__":
208                import doctest
209                doctest.testmod()
Note: See TracBrowser for help on using the repository browser.