| OLD | NEW |
|---|
| (Empty) |
| 1 #!/usr/bin/python | |
| 2 # | |
| 3 # Copyright (c) 2012 The Native Client Authors. All rights reserved. | |
| 4 # Use of this source code is governed by a BSD-style license that can be | |
| 5 # found in the LICENSE file. | |
| 6 # | |
| 7 | |
| 8 """ | |
| 9 The core object model for the Decoder Generator. The dg_input and dg_output | |
| 10 modules both operate in terms of these classes. | |
| 11 """ | |
| 12 | |
| 13 def _popcount(int): | |
| 14 """Returns the number of 1 bits in the input.""" | |
| 15 count = 0 | |
| 16 for bit in range(0, 32): | |
| 17 count = count + ((int >> bit) & 1) | |
| 18 return count | |
| 19 | |
| 20 | |
| 21 class BitPattern(object): | |
| 22 """A pattern for matching strings of bits. See parse() for syntax.""" | |
| 23 | |
| 24 @staticmethod | |
| 25 def parse(pattern, hi_bit, lo_bit): | |
| 26 """ Parses a string pattern describing some bits. The string can | |
| 27 consist of '1' and '0' to match bits explicitly, 'x' or 'X' to ignore | |
| 28 bits, '_' as an ignored separator, and an optional leading '~' to | |
| 29 negate the entire pattern. Examples: | |
| 30 10xx0 | |
| 31 1111_xxxx | |
| 32 ~111x | |
| 33 | |
| 34 The pattern may also optionally be '-', which is equivalent to a | |
| 35 sequence of 'xxx...xxx' of the requested width. | |
| 36 | |
| 37 Args: | |
| 38 pattern: a string in the format described above. | |
| 39 hi_bit: the top of the range matched by this pattern, inclusive. | |
| 40 lo_bit: the bottom of the range matched by this pattern, inclusive. | |
| 41 Returns: | |
| 42 A BitPattern instance that describes the match, and is capable of | |
| 43 transforming itself to a C expression. | |
| 44 Raises: | |
| 45 Exception: the input didn't meet the rules described above. | |
| 46 """ | |
| 47 num_bits = hi_bit - lo_bit + 1 | |
| 48 # Convert - into a full-width don't-care pattern. | |
| 49 if pattern == '-': | |
| 50 return BitPattern.parse('x' * num_bits, hi_bit, lo_bit) | |
| 51 | |
| 52 # Derive the operation type from the presence of a leading tilde. | |
| 53 if pattern.startswith('~'): | |
| 54 op = '!=' | |
| 55 pattern = pattern[1:] | |
| 56 else: | |
| 57 op = '==' | |
| 58 | |
| 59 # Allow use of underscores anywhere in the pattern, as a separator. | |
| 60 pattern = pattern.replace('_', '') | |
| 61 | |
| 62 if len(pattern) != num_bits: | |
| 63 raise Exception('Pattern %s is wrong length for %d:%u' | |
| 64 % (pattern, hi_bit, lo_bit)) | |
| 65 | |
| 66 mask = 0 | |
| 67 value = 0 | |
| 68 for c in pattern: | |
| 69 if c == '1': | |
| 70 mask = (mask << 1) | 1 | |
| 71 value = (value << 1) | 1 | |
| 72 elif c == '0': | |
| 73 mask = (mask << 1) | 1 | |
| 74 value = value << 1 | |
| 75 elif c == 'x' or c == 'X': | |
| 76 mask = mask << 1 | |
| 77 value = value << 1 | |
| 78 else: | |
| 79 raise Exception('Invalid characters in pattern %s' % pattern) | |
| 80 | |
| 81 mask = mask << lo_bit | |
| 82 value = value << lo_bit | |
| 83 return BitPattern(mask, value, op) | |
| 84 | |
| 85 @staticmethod | |
| 86 def parse_catch(pattern, hi_bit, lo_bit): | |
| 87 """"Calls parse with given arguments, and catches exceptions | |
| 88 raised. Prints raised exceptions and returns None. | |
| 89 """ | |
| 90 try: | |
| 91 return BitPattern.parse(pattern, hi_bit, lo_bit); | |
| 92 except Exception as ex: | |
| 93 print "Error: %s" % ex | |
| 94 return None | |
| 95 | |
| 96 def __init__(self, mask, value, op): | |
| 97 """Initializes a BitPattern. | |
| 98 | |
| 99 Args: | |
| 100 mask: an integer with 1s in the bit positions we care about (e.g. | |
| 101 those that are not X) | |
| 102 value: an integer that would match our pattern, subject to the mask. | |
| 103 op: either '==' or '!=', if the pattern is positive or negative, | |
| 104 respectively. | |
| 105 """ | |
| 106 self.mask = mask | |
| 107 self.value = value | |
| 108 self.op = op | |
| 109 self.significant_bits = _popcount(mask) | |
| 110 | |
| 111 def conflicts(self, other): | |
| 112 """Returns an integer with a 1 in each bit position that conflicts | |
| 113 between the two patterns, and 0s elsewhere. Note that this is only | |
| 114 useful if the masks and ops match. | |
| 115 """ | |
| 116 return (self.mask & self.value) ^ (other.mask & other.value) | |
| 117 | |
| 118 def is_complement(self, other): | |
| 119 """Checks if two patterns are complements of each other. This means | |
| 120 they have the same mask and pattern bits, but one is negative. | |
| 121 """ | |
| 122 return (self.op != other.op | |
| 123 and self.mask == other.mask | |
| 124 and self.value == other.value) | |
| 125 | |
| 126 def is_strictly_compatible(self, other): | |
| 127 """Checks if two patterns are safe to merge using +, but are not ==.""" | |
| 128 if self.is_complement(other): | |
| 129 return True | |
| 130 elif self.op == other.op: | |
| 131 return (self.mask == other.mask | |
| 132 and _popcount(self.conflicts(other)) == 1) | |
| 133 return False | |
| 134 | |
| 135 def __add__(self, other): | |
| 136 """Merges two compatible patterns into a single pattern that matches | |
| 137 everything either pattern would have matched. | |
| 138 """ | |
| 139 assert (self == other) or self.is_strictly_compatible(other) | |
| 140 | |
| 141 if self.op == other.op: | |
| 142 c = self.conflicts(other) | |
| 143 return BitPattern((self.mask | other.mask) ^ c, | |
| 144 (self.value | other.value) ^ c, self.op) | |
| 145 else: | |
| 146 return BitPattern(0, 0, '==') # matches anything | |
| 147 | |
| 148 def to_c_expr(self, input): | |
| 149 """Converts this pattern to a C expression. | |
| 150 Args: | |
| 151 input: the name (string) of the C variable to be tested by the | |
| 152 expression. | |
| 153 Returns: | |
| 154 A string containing a C expression. | |
| 155 """ | |
| 156 if self.mask == 0: | |
| 157 return 'true' | |
| 158 else: | |
| 159 return ('(%s & 0x%08X) %s 0x%08X' | |
| 160 % (input, self.mask, self.op, self.value)) | |
| 161 | |
| 162 def __cmp__(self, other): | |
| 163 """Compares two patterns for sorting purposes. We sort by | |
| 164 - # of significant bits, DESCENDING, | |
| 165 - then mask value, numerically, | |
| 166 - then value, numerically, | |
| 167 - and finally op. | |
| 168 | |
| 169 This is also used for equality comparison using ==. | |
| 170 """ | |
| 171 return (cmp(other.significant_bits, self.significant_bits) | |
| 172 or cmp(self.mask, other.mask) | |
| 173 or cmp(self.value, other.value) | |
| 174 or cmp(self.op, other.op)) | |
| 175 | |
| 176 def __repr__(self): | |
| 177 pat = [] | |
| 178 for i in range(0, 32): | |
| 179 if (self.mask >> i) & 1: | |
| 180 pat.append(`(self.value >> i) & 1`) | |
| 181 else: | |
| 182 pat.append('x') | |
| 183 if self.op == '!=': | |
| 184 pat.append('~') | |
| 185 return ''.join(reversed(pat)) | |
| 186 | |
| 187 | |
| 188 class Table(object): | |
| 189 """A table in the instruction set definition. Each table contains 1+ | |
| 190 columns, and 1+ rows. Each row contains a bit pattern for each column, plus | |
| 191 the action to be taken if the row matches.""" | |
| 192 | |
| 193 def __init__(self, name, citation): | |
| 194 """Initializes a new Table. | |
| 195 Args: | |
| 196 name: a name for the table, used to reference it from other tables. | |
| 197 citation: the section in the ISA spec this table was derived from. | |
| 198 """ | |
| 199 self.name = name | |
| 200 self.citation = citation | |
| 201 self.rows = [] | |
| 202 self._columns = [] | |
| 203 | |
| 204 def add_column(self, name, hi_bit, lo_bit): | |
| 205 """Adds a column to the table. | |
| 206 | |
| 207 Because we don't use the column information for very much, we don't give | |
| 208 it a type -- we store it as a list of tuples. | |
| 209 | |
| 210 Args: | |
| 211 name: the name of the column (for diagnostic purposes only). | |
| 212 hi_bit: the leftmost bit included. | |
| 213 lo_bit: the rightmost bit included. | |
| 214 """ | |
| 215 self._columns.append( (name, hi_bit, lo_bit) ) | |
| 216 | |
| 217 def add_row(self, patterns, action, arch): | |
| 218 """Adds a row to the table. | |
| 219 Args: | |
| 220 patterns: a list containing a BitPattern for every column in the | |
| 221 table. | |
| 222 action: The action associated with the row. Must either be | |
| 223 a DecoderAction or a DecoderMethod. | |
| 224 arch: a string defining the architectures it applies to. None | |
| 225 implies all. | |
| 226 """ | |
| 227 self.rows.append(Row(patterns, action, arch)) | |
| 228 | |
| 229 def define_pattern(self, pattern, column): | |
| 230 """Converts the given input pattern (for the given column) to the | |
| 231 internal form. Returns None if pattern is bad. | |
| 232 """ | |
| 233 if column >= len(self._columns): return None | |
| 234 col = self._columns[column] | |
| 235 return BitPattern.parse_catch(pattern, col[1], col[2]) | |
| 236 | |
| 237 def action_filter(self, names): | |
| 238 """Returns a table with DecoderActions reduced to the given field names. | |
| 239 Used to optimize out duplicates, depending on context. | |
| 240 """ | |
| 241 table = Table(self.name, self.citation) | |
| 242 table._columns = self._columns | |
| 243 for r in self.rows: | |
| 244 table.add_row(r.patterns, r.action.action_filter(names), r.arch) | |
| 245 return table | |
| 246 | |
| 247 class DecoderAction: | |
| 248 """An action defining a class decoder to apply. | |
| 249 | |
| 250 Corresponds to the parsed decoder action: | |
| 251 decoder_action ::= id (id (word (id)?)?)? | |
| 252 | |
| 253 Fields are: | |
| 254 name - Name of class decoder selected. | |
| 255 rule - Name of the rule in ARM manual that defines | |
| 256 the decoder action. | |
| 257 pattern - The placement of 0/1's within any instruction | |
| 258 that is matched by the corresponding rule. | |
| 259 constraints - Additional constraints that apply to the rule. | |
| 260 """ | |
| 261 def __init__(self, name, rule, pattern, constraints): | |
| 262 self.name = name | |
| 263 self.rule = rule | |
| 264 self.pattern = pattern | |
| 265 self.constraints = constraints | |
| 266 | |
| 267 def action_filter(self, names): | |
| 268 return DecoderAction( | |
| 269 self.name if 'name' in names else None, | |
| 270 self.rule if 'rule' in names else None, | |
| 271 self.pattern if 'pattern' in names else None, | |
| 272 self.constraints if 'constraints' in names else None) | |
| 273 | |
| 274 def __eq__(self, other): | |
| 275 return (other.__class__.__name__ == 'DecoderAction' | |
| 276 and self.name == other.name | |
| 277 and self.rule == other.rule | |
| 278 and self.pattern == other.pattern | |
| 279 and self.constraints == other.constraints) | |
| 280 | |
| 281 def __cmp__(self, other): | |
| 282 # Order lexicographically on type/fields. | |
| 283 value = cmp(other.__class__.__name__, 'DecoderAction') | |
| 284 if value != 0: return value | |
| 285 value = cmp(self.name, other.name) | |
| 286 if value != 0: return value | |
| 287 value = cmp(self.rule, other.rule) | |
| 288 if value != 0: return value | |
| 289 value = cmp(self.pattern, other.pattern) | |
| 290 if value != 0: return value | |
| 291 return cmp(self.constraints, other.constraints) | |
| 292 | |
| 293 def __hash__(self): | |
| 294 return (hash('DecoderAction') + hash(self.name) + hash(self.rule) + | |
| 295 hash(self.pattern) + hash(self.constraints)) | |
| 296 | |
| 297 def __repr__(self): | |
| 298 return '=%s %s %s %s' % (self.name, self.rule, | |
| 299 self.pattern, self.constraints) | |
| 300 | |
| 301 class DecoderMethod(object): | |
| 302 """An action defining a parse method to call. | |
| 303 | |
| 304 Corresponds to the parsed decoder method: | |
| 305 decoder_method ::= '->' id | |
| 306 | |
| 307 Fields are: | |
| 308 name - The name of the corresponding table (i.e. method) that | |
| 309 should be used to continue searching for a matching class | |
| 310 decoder. | |
| 311 """ | |
| 312 def __init__(self, name): | |
| 313 self.name = name | |
| 314 | |
| 315 def action_filter(self, unused_names): | |
| 316 return self | |
| 317 | |
| 318 def __eq__(self, other): | |
| 319 return (self.__class__.__name__ == 'DecoderMethod' | |
| 320 and self.name == other.name) | |
| 321 | |
| 322 def __cmp__(self, other): | |
| 323 # Lexicographically compare types/fields. | |
| 324 value = cmp(other.__class__.__name__, 'DecoderMethod') | |
| 325 if value != 0: return value | |
| 326 return cmp(self.name, other.name) | |
| 327 | |
| 328 def __hash__(self): | |
| 329 return hash('DecoderMethod') + hash(self.name) | |
| 330 | |
| 331 def __repr__(self): | |
| 332 return '->%s' % self.name | |
| 333 | |
| 334 class Row(object): | |
| 335 """ A row in a Table.""" | |
| 336 def __init__(self, patterns, action, arch): | |
| 337 """Initializes a Row. | |
| 338 Args: | |
| 339 patterns: a list of BitPatterns that must match for this Row to | |
| 340 match. | |
| 341 action: the action to be taken if this Row matches. | |
| 342 arch: the minimum architecture that this Row can match. | |
| 343 """ | |
| 344 self.patterns = patterns | |
| 345 self.action = action | |
| 346 self.arch = arch | |
| 347 | |
| 348 self.significant_bits = 0 | |
| 349 for p in patterns: | |
| 350 self.significant_bits += p.significant_bits | |
| 351 | |
| 352 def can_merge(self, other): | |
| 353 """Determines if we can merge two Rows.""" | |
| 354 if self.action != other.action or self.arch != other.arch: | |
| 355 return False | |
| 356 | |
| 357 equal_columns = 0 | |
| 358 compat_columns = 0 | |
| 359 for (a, b) in zip(self.patterns, other.patterns): | |
| 360 if a == b: | |
| 361 equal_columns += 1 | |
| 362 if a.is_strictly_compatible(b): | |
| 363 compat_columns += 1 | |
| 364 | |
| 365 cols = len(self.patterns) | |
| 366 return (equal_columns == cols | |
| 367 or (equal_columns == cols - 1 and compat_columns == 1)) | |
| 368 | |
| 369 def __add__(self, other): | |
| 370 assert self.can_merge(other) # Caller is expected to check! | |
| 371 return Row([a + b for (a, b) in zip(self.patterns, other.patterns)], | |
| 372 self.action, self.arch) | |
| 373 | |
| 374 def __cmp__(self, other): | |
| 375 """Compares two rows, so we can order pattern matches by specificity. | |
| 376 """ | |
| 377 return (cmp(self.patterns, other.patterns) | |
| 378 or cmp(self.action, other.action)) | |
| 379 | |
| 380 def __repr__(self): | |
| 381 return 'Row(%s, %s)' % (repr(self.patterns), repr(self.action)) | |
| 382 | |
| 383 class Decoder(object): | |
| 384 """Defines a class decoder which consists of set of tables. | |
| 385 | |
| 386 A decoder has a primary (i.e. start) table to parse intructions (and | |
| 387 select the proper ClassDecoder), as well as a set of additional | |
| 388 tables to complete the selection of a class decoder. Instances of | |
| 389 this class correspond to the internal representation of parsed | |
| 390 decoder tables recognized by dgen_input.py (see that file for | |
| 391 details). | |
| 392 | |
| 393 Fields are: | |
| 394 primary - The entry parse table to find a class decoder. | |
| 395 tables - The (sorted) set of tables defined by a decoder. | |
| 396 | |
| 397 Note: maintains restriction that tables have unique names. | |
| 398 """ | |
| 399 | |
| 400 def __init__(self): | |
| 401 self.primary = None | |
| 402 self._is_sorted = False | |
| 403 self._tables = [] | |
| 404 | |
| 405 def add(self, table): | |
| 406 """Adds the table to the set of tables. Returns true if successful. | |
| 407 """ | |
| 408 if filter(lambda(t): t.name == table.name, self._tables): | |
| 409 # Table with name already defined, report error. | |
| 410 return False | |
| 411 else: | |
| 412 if not self._tables: | |
| 413 self.primary = table | |
| 414 self._tables.append(table) | |
| 415 self.is_sorted = False | |
| 416 return True | |
| 417 | |
| 418 def tables(self): | |
| 419 """Returns the sorted (by table name) list of tables""" | |
| 420 if self._is_sorted: return self._tables | |
| 421 self._tables = sorted(self._tables, key=lambda(tbl): tbl.name) | |
| 422 self._is_sorted = True | |
| 423 return self._tables | |
| 424 | |
| 425 def action_filter(self, names): | |
| 426 """Returns a new set of tables with actions reduced to the set of | |
| 427 field names. | |
| 428 """ | |
| 429 decoder = Decoder() | |
| 430 decoder._tables = sorted([ t.action_filter(names) for t in self._tables ], | |
| 431 key=lambda(tbl): tbl.name) | |
| 432 decoder.primary = filter( | |
| 433 lambda(t): t.name == self.primary.name, self._tables)[0] | |
| 434 return decoder | |
| 435 | |
| 436 def decoders(self): | |
| 437 """Returns the sorted sequence of DecoderAction's defined in the tables.""" | |
| 438 decoders = set() | |
| 439 for t in self._tables: | |
| 440 for r in t.rows: | |
| 441 if r.action.__class__.__name__ == 'DecoderAction': | |
| 442 decoders.add(r.action) | |
| 443 return sorted(decoders) | |
| 444 | |
| 445 def rules(self): | |
| 446 """Returns the sorted sequence of DecoderActions that define | |
| 447 the rule field. | |
| 448 """ | |
| 449 return sorted(filter(lambda (r): r.rule, self.decoders())) | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 10191011:
Moving dgen_ scripts out of validator_arm into a common directory. (Closed)
