source: proto/Compiler/bitexpr.py @ 508

Last change on this file since 508 was 454, checked in by cameron, 9 years ago

Generate advance_with_carry in all modes

File size: 13.1 KB
Line 
1
2class Pragma:
3    pass
4
5class Reduce(Pragma):
6    def __init__(self, target, replace):
7        self.target = target
8        self.replace = replace
9
10class BitExpr:
11    """The BitExpr class and its subclasses provide a symbolic
12      representation of Bitwise logical expressions.
13    """
14    def __init__(self, op1, op2, op = "", data_type="vector"):
15        self.op = op
16        self.operand1 = op1
17        self.operand2 = op2
18        self.data_type = data_type
19class Var(BitExpr):
20    def __init__(self, varname):
21        self.varname = varname
22        BitExpr.__init__(self, self, self)
23    def show(self): return 'Var("' + self.varname + '")'
24    def show_C(self):
25        return self.varname
26
27class TrueLiteral(BitExpr):
28    def __init__(self):
29        self.value = True
30        self.varname = 'AllOne'
31        BitExpr.__init__(self, self, self)
32    def show(self): return 'T'
33    def show_C(self): return 'AllOne'
34
35class FalseLiteral(BitExpr):
36    def __init__(self, data_type="vector"):
37        self.value = False
38        self.varname = 'AllZero'
39        BitExpr.__init__(self, self, self, data_type=data_type)
40    def show(self): return 'F'
41    def show_C(self):return 'AllZero'
42
43class Not(BitExpr):
44    def __init__(self, expr):
45        #self.operand = expr
46        BitExpr.__init__(self, expr, expr, "Not")
47    def show(self): return 'Not(%s)' % (self.operand1.show())
48    def show_C(self): return "NOT IMPLEMENTED"
49
50class And(BitExpr):
51    def __init__(self, expr1, expr2):
52        self.operand1 = expr1
53        self.operand2 = expr2
54        self.op_C = "simd_and"
55        BitExpr.__init__(self, expr1, expr2, "And")
56    def show(self): 
57        return 'And(%s, %s)' % (self.operand1.show(), self.operand2.show())
58    def show_C(self): return 'simd_and(%s, %s)'%(self.operand1.show_C(), self.operand2.show_C())
59
60class Andc(BitExpr):
61    def __init__(self, expr1, expr2):
62        self.op_C = "simd_andc"
63        BitExpr.__init__(self, expr1, expr2, "Andc")
64
65    def show(self): return 'Andc(%s, %s)' % (self.operand1.show(), self.operand2.show())
66    def show_C(self): return 'simd_andc(%s, %s)' % (self.operand1.show_C(), self.operand2.show_C())
67
68class Or(BitExpr):
69    def __init__(self, expr1, expr2, data_type="vector"):
70        self.op_C = "simd_or"
71        BitExpr.__init__(self, expr1, expr2, "Or", data_type)
72    def show(self): return 'Or(%s, %s)' % (self.operand1.show(), self.operand2.show())
73    def show_C(self): return 'simd_or(%s, %s)' % (self.operand1.show_C(), self.operand2.show_C())
74
75class Xor(BitExpr):
76    def __init__(self, expr1, expr2):
77        self.op_C = "simd_xor"
78        BitExpr.__init__(self, expr1, expr2, "Xor")
79
80    def show(self): return 'Xor(%s, %s)' % (self.operand1.show(), self.operand2.show())
81    def show_C(self): return 'simd_xor(%s, %s)' % (self.operand1.show_C(), self.operand2.show_C())
82
83class Const(BitExpr):
84    def __init__(self, n):
85        self.n = n
86        BitExpr.__init__(self, self, self, data_type = "int")
87    def show(self): return "%i", self.n
88
89class Sel(BitExpr):
90    def __init__(self, expr1, expr2, expr3):
91        self.sel = expr1
92        self.true_branch = expr2
93        self.false_branch = expr3
94        self.vars = [self.operand1, self.operand2]
95        BitExpr.__init__(self, "Sel")
96    def show(self): return 'Sel(%s, %s, %s)' % (self.sel.show(), self.true_branch.show(), self.false_branch.show())
97    def show_C(self): return 'Sel(%s, %s, %s)' % (self.sel.show_C(), self.true_branch.show_C(), self.false_branch.show_C())
98
99class Add(BitExpr):
100    def __init__(self, expr1, expr2, carry = None):
101        self.op_C = "adc128"
102        self.carry = carry
103        self.op_advance = "advance_with_carry"
104        BitExpr.__init__(self, expr1, expr2, "Add")
105    def show(self): return 'Add(%s, %s)' % (self.operand1.show(), self.operand2.show())
106    def show_C(self): return 'adc128(%s, %s, %s)' % (self.operand1.show_C(), self.operand2.show_C(), self.carry)
107
108class Sub(BitExpr):
109    def __init__(self, expr1, expr2, brw = None):
110        self.op_C = "sbb128"
111        self.brw = brw
112        BitExpr.__init__(self, expr1, expr2, "Sub")
113    def show(self): return 'Sub(%s, %s)' % (self.operand1.show(), self.operand2.show())
114    def show_C(self): return 'sbb128(%s, %s)' % (self.operand1.show_C(), self.operand2.show_C())
115
116
117#
118#  Class BitStmt is used for sequential modification of a set of
119#  bitstream variables
120#
121class BitStmt:
122    pass
123
124class BitAssign(BitStmt):
125    def __init__(self, var, expr):
126        self.LHS = var
127        self.RHS = expr
128    def show(self): 
129            if self.LHS is None:
130                return "%s"%self.RHS.show_C()
131            else:
132                return '%s = %s' % (self.LHS.show_C(), self.RHS.show_C())
133
134class StmtList(BitStmt):
135    def __init__(self, stmts):
136        self.stmts = stmts
137    def show(self): 
138        rslt = ''
139        for s in self.stmts: rslt += s.show() + '\n'
140        return rslt
141
142
143#
144# A PyBit WhileLoop of the form while B: S
145# will execute statements S repeatedly while bitstream expression
146# B evaluates to a nonzero bitstream (i.e., has any bits)
147#
148
149class WhileLoop(StmtList):
150    def __init__(self, expr, stmts):
151        self.control_expr = expr
152        self.carry_expr = None
153        StmtList.__init__(self, stmts)
154        #self.stmt = stmts
155    def show(self): 
156        rslt = ''
157        for s in self.loop_body: rslt += s.show() + '\n'
158        return 'while (%s) {%s}' % (self.control_expr.show(), rslt)
159
160
161
162class If(StmtList):
163    def __init__(self, expr, true_branch, false_branch):
164        self.control_expr = expr
165        self.true_branch = true_branch
166        self.false_branch = false_branch
167
168
169class BitCondition:
170    def __init__(self, var, val = ""):
171        if isinstance(var, Var):
172            self.var = var
173        elif isinstance(var, str):
174            self.var = Var(var)
175        else:
176            print var
177            assert(1==0)
178       
179        self.val = val
180
181class isNoneZero(BitCondition):
182    def __init__(self, var):
183        BitCondition.__init__(self, var)
184    def show(self):
185        return '%s > 0'%self.var.show()
186
187class isAllZero(BitCondition):
188    def __init__(self, var):
189        BitCondition.__init__(self, var, "AllZero")
190    def show(self):
191        return '%s == 0'%self.var.show()
192
193class isAllOne(BitCondition):
194    def __init__(self, var):
195        BitCondition.__init__(self, var, "AllOne")
196    def show(self):
197        return '%s  == -1'%self.var.show()
198
199
200#
201# Optimizing Constructors for Boolean Expressions
202# - Maintaining Assembler Instruction Form:
203#   - All boolean algebraic rules involving true/false applied.
204#   - Negations restricted:
205#       - no negations within or (DeMorgan's to nand)
206#       - at most one negation within and
207#
208
209def make_not(expr):
210    if isinstance(expr, TrueLiteral):
211        return FalseLiteral()
212    elif isinstance(expr, FalseLiteral):
213        return TrueLiteral()
214    elif isinstance(expr, Not):
215        return expr.operand1
216    else: return Not(expr)
217
218def make_and(expr1, expr2):
219    if isinstance(expr1, TrueLiteral):
220        return expr2
221    elif isinstance(expr2, TrueLiteral):
222        return expr1
223    elif isinstance(expr1, FalseLiteral):
224        return FalseLiteral()
225    elif isinstance(expr2, FalseLiteral):
226        return FalseLiteral()
227    elif equal_exprs(expr1, expr2): return expr1
228    elif isinstance(expr1, Not):
229        if isinstance(expr2, Not):
230            return make_not(make_or(expr1.operand1, expr2.operand1))
231        elif equal_exprs(expr1.operand1, expr2): return FalseLiteral()
232        else: return And(expr1, expr2)
233    elif isinstance(expr2, Not):
234        if equal_exprs(expr1, expr2.operand1): return FalseLiteral()
235        else: return And(expr1, expr2)
236    else: return And(expr1, expr2)
237
238def make_or(expr1, expr2):
239    if isinstance(expr1, FalseLiteral):
240        return expr2
241    elif isinstance(expr2, FalseLiteral):
242        return expr1
243    elif isinstance(expr1, TrueLiteral):
244        return TrueLiteral()
245    elif isinstance(expr2, TrueLiteral):
246        return TrueLiteral()
247    elif isinstance(expr1, Not):
248        return make_not(make_and(expr1.operand, make_not(expr2)))
249    elif isinstance(expr2, Not):
250        return make_not(make_and(make_not(expr1), expr2.operand))
251    elif equal_exprs(expr1, expr2): return expr1
252    elif isinstance(expr1, And) and isinstance(expr2, And):
253        # These optimizations factor out common components that
254        # can occur when sets are formed by union (e.g., union of
255        # [a-z] and [A-Z].
256        if equal_exprs(expr1.operand1, expr2.operand1):
257            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
258        elif equal_exprs(expr1.operand2, expr2.operand2):
259            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
260        elif equal_exprs(expr1.operand1, expr2.operand2):
261            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
262        elif equal_exprs(expr1.operand2, expr2.operand1):
263            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
264        else: return Or(expr1, expr2)
265    else: return Or(expr1, expr2)
266
267def make_sel(if_expr, T_expr, F_expr):
268    if isinstance(if_expr, TrueLiteral):
269        return T_expr
270    elif isinstance(if_expr, FalseLiteral):
271        return F_expr
272    elif isinstance(T_expr, TrueLiteral):
273        # if x then T else y = x or y
274        return make_or(if_expr, F_expr) 
275    elif isinstance(T_expr, FalseLiteral):
276        # if x then F else y = not(x) and y
277        return make_and(make_not(if_expr), F_expr) 
278    elif isinstance(F_expr, FalseLiteral):
279        # if x then y else F = x and y
280        return make_and(if_expr, T_expr) 
281    elif isinstance(F_expr, TrueLiteral):
282        # if x then y else T = not(x) or y
283        return make_or(make_not(if_expr), T_expr)
284    elif equal_exprs(T_expr, F_expr):
285        return T_expr
286    else: return Sel(if_expr, T_expr, F_expr)
287
288
289def make_xor(expr1, expr2):
290    if isinstance(expr1, FalseLiteral):
291        return expr2
292    elif isinstance(expr1, FalseLiteral):
293        return expr1
294    elif isinstance(expr1, TrueLiteral):
295        return make_not(expr2)
296    elif isinstance(expr2, TrueLiteral):
297        return make_not(expr1)
298    elif isinstance(expr1, Not) and isinstance(expr2, Not):
299        return make_xor(expr1.operand, expr2.operand)
300    else: return Xor(expr1, expr2)
301
302def equal_exprs(e1, e2):
303    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
304    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
305    elif isinstance(e1, Var) and isinstance(e2, Var):
306        return e1.varname == e2.varname
307    elif isinstance(e1, Not) and isinstance(e2, Not):
308        return equal_exprs(e1.operand1, e2.operand1)
309    elif isinstance(e1, And) and isinstance(e2, And):
310        if equal_exprs(e1.operand1, e2.operand1):
311            return equal_exprs(e1.operand2, e2.operand2)
312        elif equal_exprs(e1.operand1, e2.operand2):
313            return equal_exprs(e1.operand2, e2.operand1)
314        else: return False
315    elif isinstance(e1, Or) and isinstance(e2, Or):
316        if equal_exprs(e1.operand1, e2.operand1):
317            return equal_exprs(e1.operand2, e2.operand2)
318        elif equal_exprs(e1.operand1, e2.operand2):
319            return equal_exprs(e1.operand2, e2.operand1)
320        else: return False
321    elif isinstance(e1, Xor) and isinstance(e2, Xor):
322        if equal_exprs(e1.operand1, e2.operand1):
323            return equal_exprs(e1.operand2, e2.operand2)
324        elif equal_exprs(e1.operand1, e2.operand2):
325            return equal_exprs(e1.operand2, e2.operand1)
326        else: return False
327    elif isinstance(e1, Sel) and isinstance(e2, Sel):
328        if equal_exprs(e1.sel, e2.sel):
329             if equal_exprs(e1.true_branch, e2.true_branch):
330                 return equal_exprs(e1.false_branch, e2.false_branch)
331             else: return False
332        else: return False
333
334def make_add(expr1, expr2):
335    return Add(expr1, expr2)
336
337def make_sub(expr1, expr2):
338    return Sub(expr1, expr2)
339
340
341#
342# Recursive expression simplification using the simplifying constructors.
343# Apply the inside-out simplification method to guarantee systematic
344# simplification (assuming constructors always leave results in simplified
345# form given arguments in simplified form).
346#
347def simplify_expr(expr):
348    """
349       simplifies a logical expression due to replacement of variables by constants
350    """
351    if isinstance(expr, TrueLiteral): return expr
352    elif isinstance(expr, FalseLiteral): return expr
353    elif isinstance(expr, Var): return expr
354    elif isinstance(expr, Not): return make_not(simplify_expr(expr.operand))
355    elif isinstance(expr, Or):
356        return make_or(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
357    elif isinstance(expr, Xor):
358        return make_xor(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
359    elif isinstance(expr, And):
360        return make_and(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
361    elif isinstance(expr, Sel):
362        return make_sel(simplify_expr(expr.sel), simplify_expr(expr.false_branch), simplify_expr(expr.true_branch))
363    elif isinstance(expr, Add):
364        return make_add(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
365    elif isinstance(expr, Sub):
366        return make_sub(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
367    elif isinstance(expr, Andc):
368        return make_and(simplify_expr(expr.operand1), make_not(simplify_expr(expr.operand2)))
Note: See TracBrowser for help on using the repository browser.