source: proto/Compiler/bitexpr.py @ 604

Last change on this file since 604 was 545, checked in by eamiri, 9 years ago

If statement introduced

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