source: proto/charsetcompiler/CC_compiler.py @ 3960

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

Eliminating some common subexpressions

File size: 10.7 KB
RevLine 
[3943]1#
2#  Character Class Compiler - callable CharClassCompiler object.
3#
4import charset_input_parser
5
6import UTF_encoding
7Encoding_Type = UTF_encoding.UTF_Encoding_Type
8
[3947]9from pablo_expr import *
[3943]10
11class CC_compiler():
12    def __init__(self, encoding, gensym_pattern, little_endian_bit_numbering = True, typedecl = 'BitBlock '):
13        self.mEncoding = encoding
14        self.little_endian = little_endian_bit_numbering
15        self.gensym_template = gensym_pattern
16        self.gensym_counter = 0
17        self.generated_code = []
18        self.common_expression_map = {}
[3950]19        self.typedecl = typedecl
20        predeclared = [self.bit_var(i) for i in range(0, self.mEncoding.bits)]
21        for sym in predeclared: self.common_expression_map[sym] = sym
[3943]22
[3960]23    def add_symbol_to_map(self, sym): 
24        self.common_expression_map[sym] = sym
25
26    def add_common_expressions(self, enclosing_cgo):
27        for sym in enclosing_cgo.common_expression_map.keys():
28            self.common_expression_map[sym] = enclosing_cgo.common_expression_map[sym]
29
[3943]30    def bit_var(self, n):
31
32            if len(self.mEncoding.basis_pattern) == 1:
33                return self.mEncoding.basis_pattern[0] % n
34           
35            if self.mEncoding.name == UTF_encoding.UTF16.name:
36                if options.little_endian == True:
37                    if n >= 8:
38                        return self.mEncoding.basis_pattern[0] % (n - 8)
39                    else:
40                        return self.mEncoding.basis_pattern[1] % n
41                else:
42                    if n <= 7:
43                        return self.mEncoding.basis_pattern[0] % n
44                    else:
45                        return self.mEncoding.basis_pattern[1] % (n - 8)
46
47            if self.mEncoding.name == UTF_encoding.UTF32.name:
48                if options.little_endian == True:
49                    if n >= 21:
50                        return "unused_bit%i" % (n - 21)
51                    elif n < 21 and n >= 16:
52                        return self.mEncoding.basis_pattern[0] % (n - 16)
53                    elif n < 16 and n >= 8:
54                        return self.mEncoding.basis_pattern[1] % (n - 8)
55                    elif n < 8:
56                        return self.mEncoding.basis_pattern[2] % n
57                else:
58                    if n <= 10:
59                        return "unused_bit%i" % n
60                    elif n > 10 and n <= 15:
61                        return self.mEncoding.basis_pattern[0] % (n - 8)
62                    elif n > 15 and n <= 23:
63                        return self.mEncoding.basis_pattern[1] % (n - 16)
64                    elif n > 23:
65                        return self.mEncoding.basis_pattern[2] % (n - 24)
66
67    def make_bitv(self, n):
68               
69            if self.little_endian == True:
70                return Var(self.bit_var(n))
71            else:
72                return Var(self.bit_var((self.mEncoding.bits - 1) -n)) 
73               
74    def make_bit_test(self, pattern, bit_count):
75            if bit_count == 0: return TrueLiteral()
76            bit_terms = []
77            test_bit = 2**(bit_count - 1)
78            for i in range(0, bit_count):
79                if (pattern & test_bit) == 0:
80                    bit_terms.append(make_not(self.make_bitv((self.mEncoding.bits - 1)-i)))   
81                else: bit_terms.append(self.make_bitv((self.mEncoding.bits - 1)-i))           
82                test_bit >>= 1
83            while len(bit_terms) > 1:
84                new_terms = []
85                for i in range(0, len(bit_terms)/ 2):
86                    new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
87                if len(bit_terms) % 2 == 1:
88                    new_terms.append(bit_terms[-1])
89                bit_terms = new_terms
90            return bit_terms[0]
91
92    def bit_pattern_expr(self, pattern, selected_bits):
93            if selected_bits == 0: return TrueLiteral()
94            bit_terms = []
95            bit_no = 0
96            while selected_bits:
97              test_bit = 1 << bit_no
98              if selected_bits & test_bit:
99                if (pattern & test_bit) == 0:
100                    bit_terms = [make_not(self.make_bitv(bit_no))] + bit_terms
101                else: bit_terms = [self.make_bitv(bit_no)] + bit_terms
102              else: bit_terms = [TrueLiteral()] + bit_terms
103              # Appending TrueLiteral() for nonselected bits is intended
104              # to keep consistent grouping of variables in the next loop.
105              selected_bits &= ~test_bit
106              bit_no += 1
107             
108            while len(bit_terms) > 1:
109                new_terms = []
110                for i in range(0, len(bit_terms)/ 2):
111                    new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
112                if len(bit_terms) % 2 == 1:
113                    new_terms.append(bit_terms[-1])
114                bit_terms = new_terms
115           
116            return bit_terms[0]
117   
118
[3944]119    def char_test_expr(self, chval):
120            return self.bit_pattern_expr(chval, self.mEncoding.mask) 
[3943]121
122    def GE_Range(self, N, n):
123            if N == 0: return TrueLiteral()
124            elif N % 2 == 0 and (n >> (N - 2)) == 0:
125                return make_or(make_or(self.make_bitv(N-1), self.make_bitv(N-2)),
126                                self.GE_Range(N - 2, n))
127            elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
128                return make_and(make_and(self.make_bitv(N-1), self.make_bitv(N-2)),
129                                self.GE_Range(N - 2, n - (3 << (N-2))))
130            elif N >= 1:
131                hi_bit = n & (1 << (N-1))
132                lo_bits = n - hi_bit
133                lo_range = self.GE_Range(N-1, lo_bits)
134                if hi_bit == 0:
135                    # If the hi_bit of n is not set, then whenever the corresponding bit
136                    # is set in the target, the target will certainly be >=.  Otherwise,
137                    # the value of GE_range(N-1, lo_bits) is required.
138                    return make_or(self.make_bitv(N-1), lo_range)
139                else: 
140                    # If the hi_bit of n is set, then the corresponding bit must be set
141                    # in the target for >= and GE_range(N-1, lo_bits) must also be true.
142                    return make_and(self.make_bitv(N-1), lo_range)
143
144    def LE_Range(self, N, n):
145            # If an N-bit pattern is all ones, then it is always
146            # true that any n-bit value is LE this pattern.
147            # Handling this as a special case avoids an overflow
148            # issue with n+1 requiring more than N bits.
149            if n+1 == 2 ** N:
150                return TrueLiteral()
151            else:
152                return make_not(self.GE_Range(N, n+1))
153
154    def Make_Range(self, n1, n2):  # require n2 >= n1
155            diff_bits = n1 ^ n2
156            diff_count = 0
157            while diff_bits > 0:
158                diff_count += 1
159                diff_bits >>= 1
[3959]160            if n2 < n1 or diff_count > self.mEncoding.bits: raise Exception("Bad range: (%x, %x)." % (n1, n2))
[3943]161            mask = 2**(diff_count) - 1
162            #common = make_bit_test(n1 >> diff_count, 8 - diff_count)
163            common = self.bit_pattern_expr(n1 & ~mask, self.mEncoding.mask^mask)   
164            if diff_count == 0: return common
165            mask = 2**(diff_count-1) - 1
166            lo_test = self.GE_Range(diff_count-1, n1 & mask)
167            hi_test = self.LE_Range(diff_count-1, n2 & mask)
168            return make_and(common, make_sel(self.make_bitv(diff_count-1), hi_test, lo_test))
169
170
171    def char_or_range_expr(self, charset_item):
[3944]172            (lo, hi) = charset_item
173            if lo == hi:
174                return self.char_test_expr(lo)
175            else:
176                return self.Make_Range(lo, hi)
[3943]177
178    def charset_expr(self, chardef):
179            if chardef.items == []: return FalseLiteral()
180            if len(chardef.items) > 2:
181                combine = True
182                #If all of the charset items are single codepoints
183                #such that X0 == Y0, X1 == Y1 etc.
[3944]184                for item in chardef.items:
185                    if item[0] != item[1]:
[3943]186                        combine = False
187                        break
188                if combine == True:
189                    #If charset items are all of the form X1 = X0 + 2.
190                    for i in range(1 , len(chardef.items) - 1):
191                        curr_item = chardef.items[i]
192                        next_item = chardef.items[i+1]
[3944]193                        if curr_item[0] != next_item[0] - 2:
[3943]194                            combine = False
195                            break
196                if combine == True:
[3944]197                    lo = chardef.items[0][0]
198                    hi = chardef.items[-1][0]
[3943]199                    utf_temp = self.mEncoding.mask - 1
[3944]200                    lo &= utf_temp
201                    hi |= (self.mEncoding.mask ^ utf_temp)
202                    return self.char_or_range_expr((lo, hi))
[3943]203            e1 = self.char_or_range_expr(chardef.items[0])
204            for i in range(1, len(chardef.items)):   
205                e1 = make_or(e1, self.char_or_range_expr(chardef.items[i]))
206            if chardef.complemented: return make_not(e1)
207            else: return e1
208
209    def add_assignment(self, varname, expr):
210        self.common_expression_map[expr] = varname
211        #self.generated_code.append('%s%s = %s;\n' % (self.typedecl, varname, expr))
212        self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, varname, expr))
213
[3952]214    def add_if_stmt(self, test_expr, generated_subcode):
215        test_line = 'if %s:\n' % (self.expr_string_to_variable(self.expr2py(test_expr)))
216        self.generated_code.append('\t' + test_line)
217        self.generated_code += ['\t' + line for line in generated_subcode]
218        self.generated_code.append('\t#end' + test_line)
219       
220
[3943]221    def expr_string_to_variable(self, expr_string):
222        if self.common_expression_map.has_key(expr_string):
223            return self.common_expression_map[expr_string]
224        else:
225            self.gensym_counter += 1                           
226            sym = self.gensym_template % self.gensym_counter 
227            self.add_assignment(sym, expr_string) 
228            return sym
229
230    def showcode(self):
231        s = ''
232        for stmt in self.generated_code: s += stmt
233        return s
234
235    def expr2py(self, expr):
236            """Translate a Boolean expression into three-address python code.
237            """
238            if isinstance(expr, TrueLiteral): return '-1'
239            elif isinstance(expr, FalseLiteral): return '0'
[3960]240            elif isinstance(expr, Var): 
241               # This is a hack.
242               self.common_expression_map[expr.varname] = expr.varname
243               return expr.varname
[3943]244            elif isinstance(expr, Not):
245               e = self.expr_string_to_variable(self.expr2py(expr.operand))
246               return '(~%s)' % (e)
247            elif isinstance(expr, Or):
248               e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
249               e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
250               return '(%s | %s)' % (e1, e2)
251            elif isinstance(expr, Xor):
252               e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
253               e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
254               return '(%s ^ %s)' % (e1, e2)
255            elif isinstance(expr, And):
256               if isinstance(expr.operand1, Not):
257                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1.operand))
258                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
259                   return '(%s &~ %s)' % (e2, e1)
260               elif isinstance(expr.operand2, Not):
261                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
262                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2.operand))
263                   return '(%s &~ %s)' % (e1, e2)
264               else:
265                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
266                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
267                   return '(%s & %s)' % (e1, e2)
268            elif isinstance(expr, Sel):
269               sel = self.expr_string_to_variable(self.expr2py(expr.sel))
270               e1 = self.expr_string_to_variable(self.expr2py(expr.true_branch))
271               e2 = self.expr_string_to_variable(self.expr2py(expr.false_branch))
272               return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
[3948]273            elif isinstance(expr, Adv):
[3950]274               e = self.expr_string_to_variable(self.expr2py(expr.operand))
275               return 'Advance(%s, %i)' % (e, expr.offset)
276            else: raise Exception("Bad expression: %s" % repr(e))
[3943]277
278    def chardef2py(self, chardef):
279            self.add_assignment(chardef.name, self.expr2py(self.charset_expr(chardef)))
280   
281    def chardeflist2py(self, chardeflist):
282            for d in chardeflist:
283                self.chardef2py(d) 
284            return self.showcode()
285
286
Note: See TracBrowser for help on using the repository browser.