OLD | NEW |
---|---|
(Empty) | |
1 #!/usr/bin/python | |
Nick Bray (chromium)
2012/04/13 20:25:26
Putting the dgen_* files into a module might help
| |
2 # | |
Nick Bray (chromium)
2012/04/13 20:25:26
No empty line. The file you're copying this from
| |
3 # Copyright 2009 The Native Client Authors. All rights reserved. | |
Nick Bray (chromium)
2012/04/13 20:25:26
Update all copyrights to 2012 in the files you've
| |
4 # Use of this source code is governed by a BSD-style license that can | |
5 # be found in the LICENSE file. | |
6 # Copyright 2009, Google Inc. | |
7 # | |
8 | |
9 """ | |
10 The core object model for the Decoder Generator. The dg_input and dg_output | |
11 modules both operate in terms of these classes. | |
12 """ | |
13 | |
14 import re | |
15 | |
16 def _popcount(int): | |
17 """Returns the number of 1 bits in the input.""" | |
18 count = 0 | |
19 for bit in range(0, 32): | |
20 count = count + ((int >> bit) & 1) | |
21 return count | |
22 | |
23 | |
24 class BitPattern(object): | |
25 """A pattern for matching strings of bits. See parse() for syntax.""" | |
26 | |
27 @staticmethod | |
28 def parse(pattern, hi_bit, lo_bit): | |
29 """ Parses a string pattern describing some bits. The string can | |
30 consist of '1' and '0' to match bits explicitly, 'x' or 'X' to ignore | |
31 bits, '_' as an ignored separator, and an optional leading '~' to | |
32 negate the entire pattern. Examples: | |
33 10xx0 | |
34 1111_xxxx | |
35 ~111x | |
36 | |
37 The pattern may also optionally be '-', which is equivalent to a | |
38 sequence of 'xxx...xxx' of the requested width. | |
39 | |
40 Args: | |
41 pattern: a string in the format described above. | |
42 hi_bit: the top of the range matched by this pattern, inclusive. | |
43 lo_bit: the bottom of the range matched by this pattern, inclusive. | |
44 Returns: | |
45 A BitPattern instance that describes the match, and is capable of | |
46 transforming itself to a C expression. | |
47 Raises: | |
48 Exception: the input didn't meet the rules described above. | |
49 """ | |
50 num_bits = hi_bit - lo_bit + 1 | |
51 # Convert - into a full-width don't-care pattern. | |
52 if pattern == '-': | |
53 return BitPattern.parse('x' * num_bits, hi_bit, lo_bit) | |
54 | |
55 # Derive the operation type from the presence of a leading tilde. | |
56 if pattern.startswith('~'): | |
57 op = '!=' | |
58 pattern = pattern[1:] | |
59 else: | |
60 op = '==' | |
61 | |
62 # Allow use of underscores anywhere in the pattern, as a separator. | |
63 pattern = pattern.replace('_', '') | |
64 | |
65 if len(pattern) != num_bits: | |
66 raise Exception('Pattern %s is wrong length for %d:%u' | |
67 % (pattern, hi_bit, lo_bit)) | |
68 | |
69 mask = 0 | |
70 value = 0 | |
71 for c in pattern: | |
72 if c == '1': | |
73 mask = (mask << 1) | 1 | |
74 value = (value << 1) | 1 | |
75 elif c == '0': | |
76 mask = (mask << 1) | 1 | |
77 value = value << 1 | |
78 elif c == 'x' or c == 'X': | |
79 mask = mask << 1 | |
80 value = value << 1 | |
81 else: | |
82 raise Exception('Invalid characters in pattern %s' % pattern) | |
83 | |
84 mask = mask << lo_bit | |
85 value = value << lo_bit | |
86 return BitPattern(mask, value, op) | |
87 | |
88 def __init__(self, mask, value, op): | |
89 """Initializes a BitPattern. | |
90 | |
91 Args: | |
92 mask: an integer with 1s in the bit positions we care about (e.g. | |
93 those that are not X) | |
94 value: an integer that would match our pattern, subject to the mask. | |
95 op: either '==' or '!=', if the pattern is positive or negative, | |
96 respectively. | |
97 """ | |
98 self.mask = mask | |
99 self.value = value | |
100 self.op = op | |
101 self.significant_bits = _popcount(mask) | |
102 | |
103 def conflicts(self, other): | |
104 """Returns an integer with a 1 in each bit position that conflicts | |
105 between the two patterns, and 0s elsewhere. Note that this is only | |
106 useful if the masks and ops match. | |
107 """ | |
108 return (self.mask & self.value) ^ (other.mask & other.value) | |
109 | |
110 def is_complement(self, other): | |
111 """Checks if two patterns are complements of each other. This means | |
112 they have the same mask and pattern bits, but one is negative. | |
113 """ | |
114 return (self.op != other.op | |
115 and self.mask == other.mask | |
116 and self.value == other.value) | |
117 | |
118 def is_strictly_compatible(self, other): | |
119 """Checks if two patterns are safe to merge using +, but are not ==.""" | |
120 if self.is_complement(other): | |
121 return True | |
122 elif self.op == other.op: | |
123 return (self.mask == other.mask | |
124 and _popcount(self.conflicts(other)) == 1) | |
125 return False | |
126 | |
127 def __add__(self, other): | |
128 """Merges two compatible patterns into a single pattern that matches | |
129 everything either pattern would have matched. | |
130 """ | |
131 assert (self == other) or self.is_strictly_compatible(other) | |
132 | |
133 if self.op == other.op: | |
134 c = self.conflicts(other) | |
135 return BitPattern((self.mask | other.mask) ^ c, | |
136 (self.value | other.value) ^ c, self.op) | |
137 else: | |
138 return BitPattern(0, 0, '==') # matches anything | |
139 | |
140 def to_c_expr(self, input): | |
141 """Converts this pattern to a C expression. | |
142 Args: | |
143 input: the name (string) of the C variable to be tested by the | |
144 expression. | |
145 Returns: | |
146 A string containing a C expression. | |
147 """ | |
148 if self.mask == 0: | |
149 return 'true' | |
150 else: | |
151 return ('(%s & 0x%08X) %s 0x%08X' | |
152 % (input, self.mask, self.op, self.value)) | |
153 | |
154 def __cmp__(self, other): | |
155 """Compares two patterns for sorting purposes. We sort by | |
156 - # of significant bits, DESCENDING, | |
157 - then mask value, numerically, | |
158 - then value, numerically, | |
159 - and finally op. | |
160 | |
161 This is also used for equality comparison using ==. | |
162 """ | |
163 return (cmp(other.significant_bits, self.significant_bits) | |
164 or cmp(self.mask, other.mask) | |
165 or cmp(self.value, other.value) | |
166 or cmp(self.op, other.op)) | |
167 | |
168 def __repr__(self): | |
169 pat = [] | |
170 for i in range(0, 32): | |
171 if (self.mask >> i) & 1: | |
172 pat.append(`(self.value >> i) & 1`) | |
173 else: | |
174 pat.append('x') | |
175 if self.op == '!=': | |
176 pat.append('~') | |
177 return ''.join(reversed(pat)) | |
178 | |
179 | |
180 class Table(object): | |
181 """A table in the instruction set definition. Each table contains 1+ | |
182 columns, and 1+ rows. Each row contains a bit pattern for each column, plus | |
183 the action to be taken if the row matches.""" | |
184 | |
185 def __init__(self, name, citation): | |
186 """Initializes a new Table. | |
187 Args: | |
188 name: a name for the table, used to reference it from other tables. | |
189 citation: the section in the ISA spec this table was derived from. | |
190 """ | |
191 self.name = name | |
192 self.citation = citation | |
193 self.rows = [] | |
194 self._columns = [] | |
195 | |
196 def add_column(self, name, hi_bit, lo_bit): | |
197 """Adds a column to the table. | |
198 | |
199 Because we don't use the column information for very much, we don't give | |
200 it a type -- we store it as a list of tuples. | |
201 | |
202 Args: | |
203 name: the name of the column (for diagnostic purposes only). | |
204 hi_bit: the leftmost bit included. | |
205 lo_bit: the rightmost bit included. | |
206 """ | |
207 self._columns.append( (name, hi_bit, lo_bit) ) | |
208 | |
209 def add_row(self, col_patterns, action_string): | |
210 """Adds a row to the table. | |
211 Args: | |
212 col_patterns: a list containing a BitPattern for every column in the | |
213 table. | |
214 action_string: a string indicating the action to take; must begin | |
215 with '=' for a terminal instruction class, or '->' for a | |
216 table-change. The action may end with an arch revision in | |
217 parentheses. | |
218 """ | |
219 arch = None | |
220 m = re.match(r'^(=[A-Za-z0-9_]+)\(([^)]+)\)$', action_string) | |
221 if m: | |
222 action_string = m.group(1) | |
223 arch = m.group(2) | |
224 | |
225 parsed = [] | |
226 for i in range(0, len(col_patterns)): | |
227 col = self._columns[i] | |
228 parsed.append(BitPattern.parse(col_patterns[i], col[1], col[2])) | |
229 self.rows.append(Row(parsed, action_string, arch)) | |
230 | |
231 | |
232 class Row(object): | |
233 """ A row in a Table.""" | |
234 def __init__(self, patterns, action, arch): | |
235 """Initializes a Row. | |
236 Args: | |
237 patterns: a list of BitPatterns that must match for this Row to | |
238 match. | |
239 action: the action to be taken if this Row matches. | |
240 arch: the minimum architecture that this Row can match. | |
241 """ | |
242 self.patterns = patterns | |
243 self.action = action | |
244 self.arch = arch | |
245 | |
246 self.significant_bits = 0 | |
247 for p in patterns: | |
248 self.significant_bits += p.significant_bits | |
249 | |
250 def can_merge(self, other): | |
251 """Determines if we can merge two Rows.""" | |
252 if self.action != other.action or self.arch != other.arch: | |
253 return False | |
254 | |
255 equal_columns = 0 | |
256 compat_columns = 0 | |
257 for (a, b) in zip(self.patterns, other.patterns): | |
258 if a == b: | |
259 equal_columns += 1 | |
260 if a.is_strictly_compatible(b): | |
261 compat_columns += 1 | |
262 | |
263 cols = len(self.patterns) | |
264 return (equal_columns == cols | |
265 or (equal_columns == cols - 1 and compat_columns == 1)) | |
266 | |
267 def __add__(self, other): | |
268 assert self.can_merge(other) # Caller is expected to check! | |
269 return Row([a + b for (a, b) in zip(self.patterns, other.patterns)], | |
270 self.action, self.arch) | |
271 | |
272 def __cmp__(self, other): | |
273 """Compares two rows, so we can order pattern matches by specificity. | |
274 """ | |
275 return (cmp(self.patterns, other.patterns) | |
276 or cmp(self.action, other.action)) | |
277 | |
278 def __repr__(self): | |
279 return 'Row(%s, %s)' % (repr(self.patterns), repr(self.action)) | |
OLD | NEW |