source: proto/Compiler/basic_block.py @ 365

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

Bit stream initialization support added.
Improvements in inlining.

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