[MIPS] Adding validator for MIPS architecture.

src/trusted/validator_mips/dgen/dgen_opt.py

Index: src/trusted/validator_mips/dgen/dgen_opt.py
diff --git a/src/trusted/validator_mips/dgen/dgen_opt.py b/src/trusted/validator_mips/dgen/dgen_opt.py
new file mode 100755
index 0000000000000000000000000000000000000000..7efa35b09a21958d1a04feb532efbb00b1ac0aa1
--- /dev/null
+++ b/src/trusted/validator_mips/dgen/dgen_opt.py
@@ -0,0 +1,76 @@
+#!/usr/bin/python
+#
+# Copyright 2012 The Native Client Authors.  All rights reserved.
+# Use of this source code is governed by a BSD-style license that can
+# be found in the LICENSE file.
+# Copyright 2012, Google Inc.
+#
+
+"""
+Table minimization algorithm.
+"""
+
+def optimize_rows(rows):
+    """Breaks rows up into batches, and attempts to minimize each batch,
+    using _optimize_rows_for_single_action.
+    """
+    rows_by_action = dict()
+    for row in rows:
+        if (row.action, row.arch) in rows_by_action:
+            rows_by_action[(row.action, row.arch)].append(row)
+        else:
+            rows_by_action[(row.action, row.arch)] = [row]
+
+    optimized_rows = []
+    for row_group in rows_by_action.itervalues():
+        optimized_rows.extend(_optimize_rows_for_single_action(row_group))
+
+    _remove_unused_columns(optimized_rows)
+    return optimized_rows
+
+def _optimize_rows_for_single_action(rows):
+    """Performs basic automatic minimization on the given rows.
+
+    Repeatedly selects a pair of rows to merge.  Recurses until no suitable pair
+    can be found.  It's not real smart, and is O(n^2).
+
+    A pair of rows is compatible if all columns are equal, or if exactly one
+    row differs but is_strictly_compatible.
+    """
+    for (i, j) in each_index_pair(rows):
+        row_i, row_j = rows[i], rows[j]
+
+        if row_i.can_merge(row_j):
+            new_rows = list(rows)
+            del new_rows[j]
+            del new_rows[i]
+            new_rows.append(row_i + row_j)
+            return _optimize_rows_for_single_action(new_rows)
+
+    # No changes made:
+    return rows
+
+def _remove_unused_columns(rows):
+    num_cols = len(rows[0].patterns)
+    used = [False] * num_cols
+
+    for r in rows:
+        for i in range(0, num_cols):
+            if r.patterns[i].mask != 0:
+                used[i] = True
+
+    if not True in used:
+        # Always preserve at least one column
+        used[0] = True
+
+    for col in range(num_cols - 1, 0 - 1, -1):
+        for r in rows:
+            if not used[col]:
+                del r.patterns[col]
+
+
+def each_index_pair(sequence):
+    """Utility function: Generates each unique index pair in sequence."""
+    for i in range(0, len(sequence)):
+        for j in range(i + 1, len(sequence)):
+            yield (i, j)