source: proto/Compiler/bitexpr.py @ 452

Last change on this file since 452 was 429, checked in by eamiri, 9 years ago

-simd-carry option added

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