3 # Copyright 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 # Copyright 2012, Google Inc.
10 Table minimization algorithm.
13 def optimize_rows(rows):
14 """Breaks rows up into batches, and attempts to minimize each batch,
15 using _optimize_rows_for_single_action.
17 rows_by_action = dict()
19 if (row.action, row.arch) in rows_by_action:
20 rows_by_action[(row.action, row.arch)].append(row)
22 rows_by_action[(row.action, row.arch)] = [row]
25 for row_group in rows_by_action.itervalues():
26 optimized_rows.extend(_optimize_rows_for_single_action(row_group))
28 _remove_unused_columns(optimized_rows)
31 def _optimize_rows_for_single_action(rows):
32 """Performs basic automatic minimization on the given rows.
34 Repeatedly selects a pair of rows to merge. Recurses until no suitable pair
35 can be found. It's not real smart, and is O(n^2).
37 A pair of rows is compatible if all columns are equal, or if exactly one
38 row differs but is_strictly_compatible.
40 for (i, j) in each_index_pair(rows):
41 row_i, row_j = rows[i], rows[j]
43 if row_i.can_merge(row_j):
47 new_rows.append(row_i + row_j)
48 return _optimize_rows_for_single_action(new_rows)
53 def _remove_unused_columns(rows):
54 num_cols = len(rows[0].patterns)
55 used = [False] * num_cols
58 for i in range(0, num_cols):
59 if r.patterns[i].mask != 0:
63 # Always preserve at least one column
66 for col in range(num_cols - 1, 0 - 1, -1):
72 def each_index_pair(sequence):
73 """Utility function: Generates each unique index pair in sequence."""
74 for i in range(0, len(sequence)):
75 for j in range(i + 1, len(sequence)):