source: proto/Compiler/basic_block.py @ 817

Last change on this file since 817 was 676, checked in by ksherdy, 9 years ago

Add JSON character class definitions.

File size: 14.0 KB
RevLine 
[676]1# -*- coding: utf-8 -*-
[344]2import bitexpr
[365]3import copy
[344]4
5def expr2simd(genobj, expr):
6    """Translate a Boolean expression into three-address simd code
7       using code generator object genobj.
8    """
9    if isinstance(expr, bitexpr.TrueLiteral): return expr
10    elif isinstance(expr, bitexpr.FalseLiteral): return expr
[365]11    elif isinstance(expr, bitexpr.Const): return expr
[344]12    elif isinstance(expr, bitexpr.Var):
[365]13        #print expr.show()
[344]14        genobj.common_expression_map[expr.show()] = expr
15        return expr
16    elif isinstance(expr, bitexpr.Not):
17       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
18       return bitexpr.Andc(bitexpr.TrueLiteral(), e)
19    elif isinstance(expr, bitexpr.Or):
20       if isinstance(expr.operand1, bitexpr.FalseLiteral):
21           return expr.operand2
22       elif isinstance(expr.operand1, bitexpr.TrueLiteral):
23           return bitexpr.TrueLiteral()
24       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
25           return expr.operand1
26       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
27           return bitexpr.TrueLiteral()
28       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
29       i = expr2simd(genobj, expr.operand2)
30       e2 = genobj.expr_string_to_variable(i)
31       return bitexpr.Or(e1, e2)
32    elif isinstance(expr, bitexpr.Xor):
33       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
34       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
35       return bitexpr.Xor(e1,e2)
36    elif isinstance(expr, bitexpr.And):
37       if isinstance(expr.operand1, bitexpr.Not):
38           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand1))
39           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
40           return bitexpr.Andc(e2, e1)
41       elif isinstance(expr.operand2, bitexpr.Not):
42           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
43           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand1))
44           return bitexpr.Andc(e1,e2)
45       elif isinstance(expr.operand1, bitexpr.FalseLiteral):
46           return bitexpr.FalseLiteral()
47       elif isinstance(expr.operand1, bitexpr.TrueLiteral):
48           return expr.operand2
49       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
50           return bitexpr.FalseLiteral()
51       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
52           return expr.operand1
53       else:
54           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
55           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
56           return bitexpr.And(e1, e2)
57    elif isinstance(expr, bitexpr.Sel):
58       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
59       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
60       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
61       return bitexpr.Sel(sel,e1,e2)
62    elif isinstance(expr, bitexpr.Add):
63       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
64       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
65       carry = "carry%i"%BasicBlock.carry_counter
66       return bitexpr.Add(e1, e2, carry)
67    elif isinstance(expr, bitexpr.Sub):
68       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
69       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
[363]70       brw = "carry_brw%i"%BasicBlock.brw_counter
[344]71       return bitexpr.Sub(e1, e2, brw)
72    elif isinstance(expr, bitexpr.Andc):
73       if isinstance(expr.operand2, bitexpr.Not):
74           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
75           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand1))
76           return bitexpr.And(e1,e2)
77       elif isinstance(expr.operand1, bitexpr.FalseLiteral):
78           return bitexpr.FalseLiteral()
79       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
80           return expr.operand1
81       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
82           return bitexpr.FalseLiteral()
83       else:
84           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
85           j = expr2simd(genobj, expr.operand2)
86           e2 = genobj.expr_string_to_variable(j)
87           return bitexpr.Andc(e1, e2)
88
89
90################################################################
91# New version of the class BasicBlock
92################################################################
93class BasicBlock:
94    gensym_counter = 0
95    carry_counter = 0
96    brw_counter = 0
97    def __init__(self, predeclared={}):
98        self.gensym_template = 'Temp%i'
99        self.code = []
100        self.common_expression_map = {}
101        self.new_vars = []
102        self.vars = {}
103        self.ceelim = True
104        #for sym in predeclared: self.common_expression_map[sym] =sym
105        self.common_expression_map.update(predeclared)
106
107    def add_stmt(self, varname, expr):
108        assert(not isinstance(varname, str))
[365]109        if isinstance(expr, bitexpr.FalseLiteral):
110            self.code.append(bitexpr.BitAssign(varname, expr))
111        elif self.common_expression_map.has_key(expr.show()) and self.ceelim:
[344]112            self.code.append(bitexpr.BitAssign(varname, self.common_expression_map[expr.show()]))
113        else:
114            self.common_expression_map[expr.show()] = varname
115            self.code.append(bitexpr.BitAssign(varname, expr))
116        if isinstance(expr, bitexpr.Add):
117                BasicBlock.carry_counter += 1
118        if isinstance(expr, bitexpr.Sub):
119                BasicBlock.brw_counter += 1
120
121    def expr_string_to_variable(self, expr_string):
122        if self.common_expression_map.has_key(expr_string.show()) and self.ceelim:
123            return self.common_expression_map[expr_string.show()]
124        else:
125            BasicBlock.gensym_counter += 1
126            sym = bitexpr.Var(self.gensym_template % BasicBlock.gensym_counter)
127            self.add_stmt(sym, expr_string)
128            return sym
129
130    def showcode(self, indent, line_no = False):
131        s=""
132        for index, stmt in enumerate(self.code): 
133                if line_no:
134                        s+= "%i %s%s;\n"%(index, " "*indent,stmt.show())
135                else:
136                        s += " "*indent + stmt.show() + ";\n"
137        return s
138
139    def get_code(self):
140        return self.code
141
142    def normalize(self, stmts, ceelim = True):
143        self.ceelim = ceelim
144        for s in stmts:
145            self.add_stmt(s.LHS, expr2simd(self, s.RHS))
146        return self.common_expression_map
147
148################################################################################################
149################################################################################################
150
151def simplify_expr(expr):
152    """
153       simplifies a logical expression due to replacement of variables by constants
154    """
155    if isinstance(expr, bitexpr.TrueLiteral): return expr
156    elif isinstance(expr, bitexpr.FalseLiteral): return expr
[365]157    elif isinstance(expr, bitexpr.Const): return expr
[344]158    elif isinstance(expr, bitexpr.Var): return expr
159    elif isinstance(expr, bitexpr.Not): return make_not(simplify(expr.operand1))
160    elif isinstance(expr, bitexpr.Or):
161       if isinstance(expr.operand1, bitexpr.FalseLiteral):
162           return expr.operand2
163       elif isinstance(expr.operand1, bitexpr.TrueLiteral):
164           return bitexpr.TrueLiteral()
165       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
166           return expr.operand1
167       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
168           return bitexpr.TrueLiteral()
169       else:
170           return expr
171    elif isinstance(expr, bitexpr.Xor):
172       if isinstance(expr.operand1, bitexpr.FalseLiteral):
173           return expr.operand2
174       elif isinstance(expr.operand1, bitexpr.TrueLiteral):
175           return bitexpr.Andc(bitexpr.TrueLiteral() ,expr.operand2)
176       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
177           return expr.operand1
178       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
179           return bitexpr.Andc(bitexpr.TrueLiteral() ,expr.operand1)
180       else:
181           return expr
182    elif isinstance(expr, bitexpr.And):
183       if isinstance(expr.operand1, bitexpr.FalseLiteral):
184           return bitexpr.FalseLiteral()
185       elif isinstance(expr.operand1, bitexpr.TrueLiteral):
186           return expr.operand2
187       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
188           return bitexpr.FalseLiteral()
189       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
190           return expr.operand1
191       else:
192            return expr
193    elif isinstance(expr, bitexpr.Sel):
194       if isinstance(expr.sel, bitexpr.FalseLiteral):
195           return expr.false_branch
196       elif isinstance(expr.sel, bitexpr.TrueLiteral):
197           return expr.true_branch
198       elif isinstance(expr.true_branch, bitexpr.FalseLiteral):
199           return bitexpr.Andc(expr.false_branch, expr.sel)
200       elif isinstance(expr.true_branch, bitexpr.TrueLiteral):
201           return bitexpr.Or(expr.false_branch, expr.sel)
202       elif isinstance(expr.false_branch, bitexpr.FalseLiteral):
203           return bitexpr.And(expr.true_branch, expr.sel)
204       elif isinstance(expr.false_branch, bitexpr.TrueLiteral):
205           return expr #SIMPLIFICATION IS POSSIBLE BUT ACCESS TO BASIC BLOCK IS NEEDED
206       else:
207            return expr
208    elif isinstance(expr, bitexpr.Add):
209            return expr
210    elif isinstance(expr, bitexpr.Sub):
211        return expr
212    elif isinstance(expr, bitexpr.Andc):
213       if isinstance(expr.operand1, bitexpr.FalseLiteral):
214           return bitexpr.FalseLiteral()
215       elif isinstance(expr.operand2, bitexpr.FalseLiteral):
216           return expr.operand1
217       elif isinstance(expr.operand2, bitexpr.TrueLiteral):
218           return bitexpr.FalseLiteral()
219       else:
220           return expr
221
222def propagate_constant(code, previous):
223    #propagate from right to left
224    changed = False
225    fixed = previous
226    for s in code:
227        if isinstance(s.RHS, bitexpr.FalseLiteral):
228            fixed[s.LHS.varname] = bitexpr.FalseLiteral()
229            continue
230        if isinstance(s.RHS, bitexpr.TrueLiteral):
231            fixed[s.LHS.varname] = bitexpr.TrueLiteral()
232            continue
[365]233        if isinstance(s.RHS, bitexpr.Const):
234            #fixed[s.LHS.varname] = copy.copy(s.RHS)
235            continue
[344]236        if isinstance(s.RHS, bitexpr.Var):
237            if s.RHS.varname in fixed:
238                s.RHS = fixed[s.RHS.varname]
239            #print "$$$$$$$$$$$$$$$$111", s.LHS.varname, s.RHS, s.RHS.varname
240            fixed[s.LHS.varname] = s.RHS
241            continue
242        if isinstance(s.RHS, bitexpr.Not):
243            if s.RHS.operand.varname in fixed:
244                s.RHS.operand = fixed[s.RHS.operand.varname]
245            continue
246        if s.RHS.operand1.varname in fixed:
247            changed = True
248            #if isinstance(fixed[s.RHS.operand1.varname], bitexpr.Var):
249            #    print "\t\t", s.RHS.operand1.varname, fixed[s.RHS.operand1.varname].varname
250            s.RHS.operand1 = fixed[s.RHS.operand1.varname]
251        if s.RHS.operand2.varname in fixed:
252            s.RHS.operand2 = fixed[s.RHS.operand2.varname]
253            changed = True
254
255    return fixed, changed
256
257
258def transform(code):
259    for loc in code:
260        loc.RHS = simplify_expr(loc.RHS)
261
262def simplify(code, previous):
[363]263    #for i in previous:
264        #print i, previous[i].varname
[344]265    changed = True
266    while changed:
267        #if len(code) > 100:
268        #    print "\t",code[61].RHS.operand1.varname
269        transform(code)
270        fixed, changed = propagate_constant(code, previous)
271    return fixed
272
273def calc_implications(code, assumptions):
274    #Left to right propagation
275    #changed = False
276    notchecked = [x for x in assumptions]
277    lhs = [x.LHS.varname for x in code]
278    while True:
279        if len(notchecked) == 0:
280            break
281        var = notchecked.pop(0)
282        if var in lhs:
283            index = lhs.index(var)
284            s = code[index]
285        else:
286            continue
287        if var in assumptions:
288            if isinstance(assumptions[s.LHS.varname], bitexpr.FalseLiteral):
289                if isinstance(s.RHS, bitexpr.Not):
290                    assumptions[s.RHS.operand1.varname] = bitexpr.TrueLiteral()
291                    notchecked.append(s.RHS.operand.varname)
292                elif isinstance(s.RHS, bitexpr.Var):
293                    assumptions[s.RHS.varname] = bitexpr.FalseLiteral()
294                    notchecked.append(s.RHS.operand.varname)
295                elif isinstance(s.RHS, bitexpr.Or):
296                    assumptions[s.RHS.operand1.varname] = bitexpr.FalseLiteral()
297                    assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
298                    notchecked.append(s.RHS.operand1.varname)
299                    notchecked.append(s.RHS.operand2.varname)
300                elif isinstance(s.RHS, bitexpr.Xor):
301                    pass
302            if isinstance(assumptions[s.LHS.varname], bitexpr.TrueLiteral):
303                if isinstance(s.RHS, bitexpr.Not):
304                    assumptions[s.RHS.operand1.varname] = bitexpr.FalseLiteral()
305                    notchecked.append(s.RHS.operand.varname)
306                elif isinstance(s.RHS, bitexpr.Var):
307                    assumptions[s.RHS.varname] = bitexpr.TrueLiteral()
308                    notchecked.append(s.RHS.operand.varname)
309                elif isinstance(s.RHS, bitexpr.And):
310                    assumptions[s.RHS.operand1.varname] = bitexpr.TrueLiteral()
311                    assumptions[s.RHS.operand2.varname] = bitexpr.TrueLiteral()
312                    notchecked.append(s.RHS.operand1.varname)
313                    notchecked.append(s.RHS.operand2.varname)
314                elif isinstance(s.RHS, bitexpr.Andc):
315                    if isinstance(s.RHS.operand1, bitexpr.TrueLiteral):
316                        assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
317                        notchecked.append(s.RHS.operand2.varname)
318                    else:
319                        assumptions[s.RHS.operand1.varname] = bitexpr.TrueLiteral()
320                        assumptions[s.RHS.operand2.varname] = bitexpr.FalseLiteral()
321                        notchecked.append(s.RHS.operand1.varname)
322                        notchecked.append(s.RHS.operand2.varname)
323    return assumptions
Note: See TracBrowser for help on using the repository browser.