source: proto/Compiler/bitexpr.py @ 370

Last change on this file since 370 was 370, checked in by eamiri, 10 years ago

bugfix

File size: 13.0 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        BitExpr.__init__(self, expr1, expr2, "Add")
104    def show(self): return 'Add(%s, %s)' % (self.operand1.show(), self.operand2.show())
105    def show_C(self): return 'adc128(%s, %s, %s)' % (self.operand1.show_C(), self.operand2.show_C(), self.carry)
106
107class Sub(BitExpr):
108    def __init__(self, expr1, expr2, brw = None):
109        self.op_C = "sbb128"
110        self.brw = brw
111        BitExpr.__init__(self, expr1, expr2, "Sub")
112    def show(self): return 'Sub(%s, %s)' % (self.operand1.show(), self.operand2.show())
113    def show_C(self): return 'sbb128(%s, %s)' % (self.operand1.show_C(), self.operand2.show_C())
114
115
116#
117#  Class BitStmt is used for sequential modification of a set of
118#  bitstream variables
119#
120class BitStmt:
121    pass
122
123class BitAssign(BitStmt):
124    def __init__(self, var, expr):
125        self.LHS = var
126        self.RHS = expr
127    def show(self): 
128            if self.LHS is None:
129                return "%s"%self.RHS.show_C()
130            else:
131                return '%s = %s' % (self.LHS.show_C(), self.RHS.show_C())
132
133class StmtList(BitStmt):
134    def __init__(self, stmts):
135        self.stmts = stmts
136    def show(self): 
137        rslt = ''
138        for s in self.stmts: rslt += s.show() + '\n'
139        return rslt
140
141
142#
143# A PyBit WhileLoop of the form while B: S
144# will execute statements S repeatedly while bitstream expression
145# B evaluates to a nonzero bitstream (i.e., has any bits)
146#
147
148class WhileLoop(StmtList):
149    def __init__(self, expr, stmts):
150        self.control_expr = expr
151        self.carry_expr = None
152        StmtList.__init__(self, stmts)
153        #self.stmt = stmts
154    def show(self): 
155        rslt = ''
156        for s in self.loop_body: rslt += s.show() + '\n'
157        return 'while (%s) {%s}' % (self.control_expr.show(), rslt)
158
159
160
161class If(StmtList):
162    def __init__(self, expr, true_branch, false_branch):
163        self.control_expr = expr
164        self.true_branch = true_branch
165        self.false_branch = false_branch
166
167
168class BitCondition:
169    def __init__(self, var, val = ""):
170        if isinstance(var, Var):
171            self.var = var
172        elif isinstance(var, str):
173            self.var = Var(var)
174        else:
175            print var
176            assert(1==0)
177       
178        self.val = val
179
180class isNoneZero(BitCondition):
181    def __init__(self, var):
182        BitCondition.__init__(self, var)
183    def show(self):
184        return '%s > 0'%self.var.show()
185
186class isAllZero(BitCondition):
187    def __init__(self, var):
188        BitCondition.__init__(self, var, "AllZero")
189    def show(self):
190        return '%s == 0'%self.var.show()
191
192class isAllOne(BitCondition):
193    def __init__(self, var):
194        BitCondition.__init__(self, var, "AllOne")
195    def show(self):
196        return '%s  == -1'%self.var.show()
197
198
199#
200# Optimizing Constructors for Boolean Expressions
201# - Maintaining Assembler Instruction Form:
202#   - All boolean algebraic rules involving true/false applied.
203#   - Negations restricted:
204#       - no negations within or (DeMorgan's to nand)
205#       - at most one negation within and
206#
207
208def make_not(expr):
209    if isinstance(expr, TrueLiteral):
210        return FalseLiteral()
211    elif isinstance(expr, FalseLiteral):
212        return TrueLiteral()
213    elif isinstance(expr, Not):
214        return expr.operand1
215    else: return Not(expr)
216
217def make_and(expr1, expr2):
218    if isinstance(expr1, TrueLiteral):
219        return expr2
220    elif isinstance(expr2, TrueLiteral):
221        return expr1
222    elif isinstance(expr1, FalseLiteral):
223        return FalseLiteral()
224    elif isinstance(expr2, FalseLiteral):
225        return FalseLiteral()
226    elif equal_exprs(expr1, expr2): return expr1
227    elif isinstance(expr1, Not):
228        if isinstance(expr2, Not):
229            return make_not(make_or(expr1.operand1, expr2.operand1))
230        elif equal_exprs(expr1.operand1, expr2): return FalseLiteral()
231        else: return And(expr1, expr2)
232    elif isinstance(expr2, Not):
233        if equal_exprs(expr1, expr2.operand1): return FalseLiteral()
234        else: return And(expr1, expr2)
235    else: return And(expr1, expr2)
236
237def make_or(expr1, expr2):
238    if isinstance(expr1, FalseLiteral):
239        return expr2
240    elif isinstance(expr2, FalseLiteral):
241        return expr1
242    elif isinstance(expr1, TrueLiteral):
243        return TrueLiteral()
244    elif isinstance(expr2, TrueLiteral):
245        return TrueLiteral()
246    elif isinstance(expr1, Not):
247        return make_not(make_and(expr1.operand, make_not(expr2)))
248    elif isinstance(expr2, Not):
249        return make_not(make_and(make_not(expr1), expr2.operand))
250    elif equal_exprs(expr1, expr2): return expr1
251    elif isinstance(expr1, And) and isinstance(expr2, And):
252        # These optimizations factor out common components that
253        # can occur when sets are formed by union (e.g., union of
254        # [a-z] and [A-Z].
255        if equal_exprs(expr1.operand1, expr2.operand1):
256            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
257        elif equal_exprs(expr1.operand2, expr2.operand2):
258            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
259        elif equal_exprs(expr1.operand1, expr2.operand2):
260            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
261        elif equal_exprs(expr1.operand2, expr2.operand1):
262            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
263        else: return Or(expr1, expr2)
264    else: return Or(expr1, expr2)
265
266def make_sel(if_expr, T_expr, F_expr):
267    if isinstance(if_expr, TrueLiteral):
268        return T_expr
269    elif isinstance(if_expr, FalseLiteral):
270        return F_expr
271    elif isinstance(T_expr, TrueLiteral):
272        # if x then T else y = x or y
273        return make_or(if_expr, F_expr) 
274    elif isinstance(T_expr, FalseLiteral):
275        # if x then F else y = not(x) and y
276        return make_and(make_not(if_expr), F_expr) 
277    elif isinstance(F_expr, FalseLiteral):
278        # if x then y else F = x and y
279        return make_and(if_expr, T_expr) 
280    elif isinstance(F_expr, TrueLiteral):
281        # if x then y else T = not(x) or y
282        return make_or(make_not(if_expr), T_expr)
283    elif equal_exprs(T_expr, F_expr):
284        return T_expr
285    else: return Sel(if_expr, T_expr, F_expr)
286
287
288def make_xor(expr1, expr2):
289    if isinstance(expr1, FalseLiteral):
290        return expr2
291    elif isinstance(expr1, FalseLiteral):
292        return expr1
293    elif isinstance(expr1, TrueLiteral):
294        return make_not(expr2)
295    elif isinstance(expr2, TrueLiteral):
296        return make_not(expr1)
297    elif isinstance(expr1, Not) and isinstance(expr2, Not):
298        return make_xor(expr1.operand, expr2.operand)
299    else: return Xor(expr1, expr2)
300
301def equal_exprs(e1, e2):
302    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
303    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
304    elif isinstance(e1, Var) and isinstance(e2, Var):
305        return e1.varname == e2.varname
306    elif isinstance(e1, Not) and isinstance(e2, Not):
307        return equal_exprs(e1.operand1, e2.operand1)
308    elif isinstance(e1, And) and isinstance(e2, And):
309        if equal_exprs(e1.operand1, e2.operand1):
310            return equal_exprs(e1.operand2, e2.operand2)
311        elif equal_exprs(e1.operand1, e2.operand2):
312            return equal_exprs(e1.operand2, e2.operand1)
313        else: return False
314    elif isinstance(e1, Or) and isinstance(e2, Or):
315        if equal_exprs(e1.operand1, e2.operand1):
316            return equal_exprs(e1.operand2, e2.operand2)
317        elif equal_exprs(e1.operand1, e2.operand2):
318            return equal_exprs(e1.operand2, e2.operand1)
319        else: return False
320    elif isinstance(e1, Xor) and isinstance(e2, Xor):
321        if equal_exprs(e1.operand1, e2.operand1):
322            return equal_exprs(e1.operand2, e2.operand2)
323        elif equal_exprs(e1.operand1, e2.operand2):
324            return equal_exprs(e1.operand2, e2.operand1)
325        else: return False
326    elif isinstance(e1, Sel) and isinstance(e2, Sel):
327        if equal_exprs(e1.sel, e2.sel):
328             if equal_exprs(e1.true_branch, e2.true_branch):
329                 return equal_exprs(e1.false_branch, e2.false_branch)
330             else: return False
331        else: return False
332
333def make_add(expr1, expr2):
334    return Add(expr1, expr2)
335
336def make_sub(expr1, expr2):
337    return Sub(expr1, expr2)
338
339
340#
341# Recursive expression simplification using the simplifying constructors.
342# Apply the inside-out simplification method to guarantee systematic
343# simplification (assuming constructors always leave results in simplified
344# form given arguments in simplified form).
345#
346def simplify_expr(expr):
347    """
348       simplifies a logical expression due to replacement of variables by constants
349    """
350    if isinstance(expr, TrueLiteral): return expr
351    elif isinstance(expr, FalseLiteral): return expr
352    elif isinstance(expr, Var): return expr
353    elif isinstance(expr, Not): return make_not(simplify_expr(expr.operand))
354    elif isinstance(expr, Or):
355        return make_or(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
356    elif isinstance(expr, Xor):
357        return make_xor(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
358    elif isinstance(expr, And):
359        return make_and(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
360    elif isinstance(expr, Sel):
361        return make_sel(simplify_expr(expr.sel), simplify_expr(expr.false_branch), simplify_expr(expr.true_branch))
362    elif isinstance(expr, Add):
363        return make_add(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
364    elif isinstance(expr, Sub):
365        return make_sub(simplify_expr(expr.operand1), simplify_expr(expr.operand2))
366    elif isinstance(expr, Andc):
367        return make_and(simplify_expr(expr.operand1), make_not(simplify_expr(expr.operand2)))
Note: See TracBrowser for help on using the repository browser.