source: proto/charsetcompiler/pablo_expr.py @ 4892

Last change on this file since 4892 was 4359, checked in by cameron, 5 years ago

Sel -> Xor optimization; implement Pablo Xor in printer, compiler

File size: 8.9 KB
Line 
1#
2#  Pablo Expressions:  bitwise Boolean Expressions + Advance.
3#
4import ast
5
6class BitwiseExpr:
7   """The BitwiseExpr class and its subclasses provide a symbolic
8      representation of bitwise Boolean expressions.
9   """
10   pass
11
12class Var(BitwiseExpr):
13    def __init__(self, varname):
14        self.varname = varname
15    def __str__(self): return 'Var("' + self.varname + '")'
16    def toAST(self): return ast.Name(id=self.varname, ctx=ast.Load())
17
18class TrueLiteral(BitwiseExpr):
19    def __init__(self):
20        self.value = True
21    def __str__(self): return 'T'
22    def toAST(self): return ast.Name(id='True', ctx=ast.Load())
23
24class FalseLiteral(BitwiseExpr):
25    def __init__(self):
26        self.value = False
27    def __str__(self): return 'F'
28    def toAST(self): return ast.Name(id='False', ctx=ast.Load())
29
30class Not(BitwiseExpr):
31    def __init__(self, expr):
32        self.operand = expr
33    def __str__(self): return 'Not(%s)' % (self.operand.__str__())
34    def toAST(self): return ast.UnaryOp(ast.Not(), self.operand.toAST())
35
36class And(BitwiseExpr):
37    def __init__(self, expr1, expr2):
38        self.operand1 = expr1
39        self.operand2 = expr2
40    def __str__(self): return 'And(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
41    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitAnd(), self.operand2.toAST())
42
43class Or(BitwiseExpr):
44    def __init__(self, expr1, expr2):
45        self.operand1 = expr1
46        self.operand2 = expr2
47    def __str__(self): return 'Or(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
48    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitOr(), self.operand2.toAST())
49
50class Xor(BitwiseExpr):
51    def __init__(self, expr1, expr2):
52        self.operand1 = expr1
53        self.operand2 = expr2
54    def __str__(self): return 'Xor(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
55    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitXor(), self.operand2.toAST())
56
57class Sel(BitwiseExpr):
58    def __init__(self, expr1, expr2, expr3):
59        self.sel = expr1
60        self.true_branch = expr2
61        self.false_branch = expr3
62    def __str__(self): return 'Sel(%s, %s, %s)' % (self.sel.__str__(), self.true_branch.__str__(), self.false_branch.__str__())
63    def toAST(self): return ast.IfExpr(self.sel.toAST(), self.true_branch.toAST(), self.false_branch.toAST())
64
65class Adv(BitwiseExpr):
66    def __init__(self, expr, n):
67        self.operand = expr
68        self.offset = n
69    def __str__(self): 
70       if self.offset == 1: return 'Advance(%s)' % (self.operand.__str__()) 
71       else: return 'Advance(%s, %i)' % (self.operand.__str__(), self.offset)
72    def toAST(self): return ast.Call(ast.Attribute(ast.Name('pablo', ast.Load()), 'Advance', ast.Load()), [self.operand.toAST(), ast.Num(self.offset)])
73
74#
75# Optimizing Constructors for Boolean Expressions
76# - Maintaining Assembler Instruction Form:
77#   - All boolean algebraic rules involving true/false applied.
78#   - Negations restricted:
79#       - no negations within or (DeMorgan's to nand)
80#       - at most one negation within and
81#
82
83def make_not(expr):
84    if isinstance(expr, TrueLiteral):
85        return FalseLiteral()
86    elif isinstance(expr, FalseLiteral):
87        return TrueLiteral()
88    elif isinstance(expr, Not):
89        return expr.operand
90    else: return Not(expr)
91
92def make_and(expr1, expr2):
93    if isinstance(expr1, TrueLiteral):
94        return expr2
95    elif isinstance(expr2, TrueLiteral):
96        return expr1
97    elif isinstance(expr1, FalseLiteral):
98        return FalseLiteral()
99    elif isinstance(expr2, FalseLiteral):
100        return FalseLiteral()
101    elif equal_exprs(expr1, expr2): return expr1
102    elif isinstance(expr1, Not):
103        if isinstance(expr2, Not):
104            return make_not(make_or(expr1.operand, expr2.operand))
105        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
106        else: return And(expr1, expr2)
107    elif isinstance(expr2, Not):
108        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
109        else: return And(expr1, expr2)
110    else: return And(expr1, expr2)
111
112def make_or(expr1, expr2):
113    if isinstance(expr1, FalseLiteral):
114        return expr2
115    elif isinstance(expr2, FalseLiteral):
116        return expr1
117    elif isinstance(expr1, TrueLiteral):
118        return TrueLiteral()
119    elif isinstance(expr2, TrueLiteral):
120        return TrueLiteral()
121    elif isinstance(expr1, Not):
122        return make_not(make_and(expr1.operand, make_not(expr2)))
123    elif isinstance(expr2, Not):
124        return make_not(make_and(make_not(expr1), expr2.operand))
125    elif equal_exprs(expr1, expr2): return expr1
126    elif isinstance(expr1, And) and isinstance(expr2, And):
127        # These optimizations factor out common components that
128        # can occur when sets are formed by union (e.g., union of
129        # [a-z] and [A-Z].
130        if equal_exprs(expr1.operand1, expr2.operand1):
131            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
132        elif equal_exprs(expr1.operand2, expr2.operand2):
133            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
134        elif equal_exprs(expr1.operand1, expr2.operand2):
135            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
136        elif equal_exprs(expr1.operand2, expr2.operand1):
137            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
138        else: return Or(expr1, expr2)
139    else: return Or(expr1, expr2)
140
141def make_sel(if_expr, T_expr, F_expr):
142    if isinstance(if_expr, TrueLiteral):
143        return T_expr
144    elif isinstance(if_expr, FalseLiteral):
145        return F_expr
146    elif isinstance(T_expr, TrueLiteral):
147        # if x then T else y = x or y
148        return make_or(if_expr, F_expr) 
149    elif isinstance(T_expr, FalseLiteral):
150        # if x then F else y = not(x) and y
151        return make_and(make_not(if_expr), F_expr) 
152    elif isinstance(F_expr, FalseLiteral):
153        # if x then y else F = x and y
154        return make_and(if_expr, T_expr) 
155    elif isinstance(F_expr, TrueLiteral):
156        # if x then y else T = not(x) or y
157        return make_or(make_not(if_expr), T_expr)
158    elif equal_exprs(T_expr, F_expr):
159        return T_expr
160    elif isinstance(T_expr, Not) and equal_exprs(T_expr.operand, F_expr):
161        return make_xor(if_expr, F_expr)
162    elif isinstance(F_expr, Not) and equal_exprs(F_expr.operand, T_expr):
163        return make_xor(if_expr, F_expr)
164    else: return Sel(if_expr, T_expr, F_expr)
165
166
167def make_xor(expr1, expr2):
168    if isinstance(expr1, FalseLiteral):
169        return expr2
170    elif isinstance(expr2, FalseLiteral):
171        return expr1
172    elif isinstance(expr1, TrueLiteral):
173        return make_not(expr2)
174    elif isinstance(expr2, TrueLiteral):
175        return make_not(expr1)
176    elif isinstance(expr1, Not) and isinstance(expr2, Not):
177        return make_xor(expr1.operand, expr2.operand)
178    else: return Xor(expr1, expr2)
179
180# Return True if e1 and e2 can be proven equivalent according
181# to some rules, False otherwise.   Note that False may
182# be returned in some cases when the exprs are equivalent.
183def equal_exprs(e1, e2):
184    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
185    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
186    elif isinstance(e1, Var) and isinstance(e2, Var):
187        return e1.varname == e2.varname
188    elif isinstance(e1, Not) and isinstance(e2, Not):
189        return equal_exprs(e1.operand, e2.operand)
190    elif isinstance(e1, And) and isinstance(e2, And):
191        if equal_exprs(e1.operand1, e2.operand1):
192            return equal_exprs(e1.operand2, e2.operand2)
193        elif equal_exprs(e1.operand1, e2.operand2):
194            return equal_exprs(e1.operand2, e2.operand1)
195        else: return False
196    elif isinstance(e1, Or) and isinstance(e2, Or):
197        if equal_exprs(e1.operand1, e2.operand1):
198            return equal_exprs(e1.operand2, e2.operand2)
199        elif equal_exprs(e1.operand1, e2.operand2):
200            return equal_exprs(e1.operand2, e2.operand1)
201        else: return False
202    elif isinstance(e1, Xor) and isinstance(e2, Xor):
203        if equal_exprs(e1.operand1, e2.operand1):
204            return equal_exprs(e1.operand2, e2.operand2)
205        elif equal_exprs(e1.operand1, e2.operand2):
206            return equal_exprs(e1.operand2, e2.operand1)
207        else: return False
208    elif isinstance(e1, Sel) and isinstance(e2, Sel):
209        if equal_exprs(e1.sel, e2.sel):
210             if equal_exprs(e1.true_branch, e2.true_branch):
211                 return equal_exprs(e1.false_branch, e2.false_branch)
212             else: return False
213        else: return False
214    elif isinstance(e1, Adv) and isinstance(e2, Adv):
215        if e1.offset == e2.offset: return equal_exprs(e1.operand(), e2.operand())
216        else: return False
217    else: return False
218
219def make_shift_forward(expr, n):
220    if isinstance(expr, FalseLiteral):
221        return expr
222    elif n == 0:
223        return expr
224    elif isinstance(expr, Adv):
225        return Adv(expr.operand, n + expr.offset)
226    else: return Adv(expr, n)
227
228
Note: See TracBrowser for help on using the repository browser.