[utils] Allow better identification of matching blocks in update_mca_test_checks.py

Insert empty blocks to cause the positions of matching blocks to match
across lists where possible so that later stages of the algorithm can
actually identify them as being identical.

Regenerated all tests with this change.

Differential Revision: https://reviews.llvm.org/D52560

llvm-svn: 343331

1 files changed, 67 insertions, 0 deletions

diff --git a/llvm/utils/update_mca_test_checks.py b/llvm/utils/update_mca_test_checks.py
index 18de299f1ce..88853bfe306 100755
--- a/llvm/utils/update_mca_test_checks.py
+++ b/llvm/utils/update_mca_test_checks.py
@@ -222,6 +222,64 @@ def _get_useful_prefix_info(run_infos):
   return common_to_all, longest_prefix_len
 
 
+def _align_matching_blocks(all_blocks, farthest_indexes):
+  """ Some sub-sequences of blocks may be common to multiple lists of blocks,
+      but at different indexes in each one.
+
+      For example, in the following case, A,B,E,F, and H are common to both
+      sets, but only A and B would be identified as such due to the indexes
+      matching:
+
+      index | 0 1 2 3 4 5 6
+      ------+--------------
+      setA  | A B C D E F H
+      setB  | A B E F G H
+
+      This function attempts to align the indexes of matching blocks by
+      inserting empty blocks into the block list. With this approach, A, B, E,
+      F, and H would now be able to be identified as matching blocks:
+
+      index | 0 1 2 3 4 5 6 7
+      ------+----------------
+      setA  | A B C D E F   H
+      setB  | A B     E F G H
+  """
+
+  # "Farthest block analysis": essentially, iterate over all blocks and find
+  # the highest index into a block list for the first instance of each block.
+  # This is relatively expensive, but we're dealing with small numbers of
+  # blocks so it doesn't make a perceivable difference to user time.
+  for blocks in all_blocks.values():
+    for block in blocks:
+      if not block:
+        continue
+
+      index = blocks.index(block)
+
+      if index > farthest_indexes[block]:
+        farthest_indexes[block] = index
+
+  # Use the results of the above analysis to identify any blocks that can be
+  # shunted along to match the farthest index value.
+  for blocks in all_blocks.values():
+    for index, block in enumerate(blocks):
+      if not block:
+        continue
+
+      changed = False
+      while(index < farthest_indexes[block]):
+        blocks.insert(index, '')
+        index += 1
+        changed = True
+
+      if changed:
+        # Bail out.  We'll need to re-do the farthest block analysis now that
+        # we've inserted some blocks.
+        return True
+
+  return False
+
+
 def _get_block_infos(run_infos, test_path, args, common_prefix):  # noqa
   """ For each run line, run the tool with the specified args and collect the
       output. We use the concept of 'blocks' for uniquing, where a block is
@@ -253,6 +311,10 @@ def _get_block_infos(run_infos, test_path, args, common_prefix):  # noqa
   all_blocks = {}
   max_block_len = 0
 
+  # A cache of the furthest-back position in any block list of the first
+  # instance of each block, indexed by the block itself.
+  farthest_indexes = defaultdict(int)
+
   # Run the tool for each run line to generate all of the blocks.
   for prefixes, tool_args in run_infos:
     key = _block_key(tool_args, prefixes)
@@ -270,6 +332,11 @@ def _get_block_infos(run_infos, test_path, args, common_prefix):  # noqa
                        for b in raw_tool_output.split('\n\n')]
     max_block_len = max(max_block_len, len(all_blocks[key]))
 
+    # Attempt to align matching blocks until no more changes can be made.
+    made_changes = True
+    while made_changes:
+      made_changes = _align_matching_blocks(all_blocks, farthest_indexes)
+
   # If necessary, pad the lists of blocks with empty blocks so that they are
   # all the same length.
   for key in all_blocks: