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

[gbedwell]

Summary

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.

[andreadb]

LGTM.

Thanks

llvm/trunk/test/tools/llvm-mca/X86/option-all-stats-1.s

 # FULLREPORT-NEXT:    Total number of mappings created: 0
 # FULLREPORT-NEXT:    Max number of mappings used:      0
 
 # FULLREPORT:      *  Register File #2 -- JIntegerPRF:
 # FULLREPORT-NEXT:    Number of physical registers:     64
 # FULLREPORT-NEXT:    Total number of mappings created: 200
 # FULLREPORT-NEXT:    Max number of mappings used:      44
 
-# FULLREPORT:      Resources:
-# FULLREPORT-NEXT: [0]   - JALU0
-# FULLREPORT-NEXT: [1]   - JALU1
-# FULLREPORT-NEXT: [2]   - JDiv
-# FULLREPORT-NEXT: [3]   - JFPA
-# FULLREPORT-NEXT: [4]   - JFPM
-# FULLREPORT-NEXT: [5]   - JFPU0
-# FULLREPORT-NEXT: [6]   - JFPU1
-# FULLREPORT-NEXT: [7]   - JLAGU
-# FULLREPORT-NEXT: [8]   - JMul
-# FULLREPORT-NEXT: [9]   - JSAGU
-# FULLREPORT-NEXT: [10]  - JSTC
-# FULLREPORT-NEXT: [11]  - JVALU0
-# FULLREPORT-NEXT: [12]  - JVALU1
-# FULLREPORT-NEXT: [13]  - JVIMUL
-
-# FULLREPORT:      Resource pressure per iteration:
-# FULLREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
-# FULLREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
-
-# FULLREPORT:      Resource pressure by instruction:
-# FULLREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
-# FULLREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl %eax, %eax
+# ALL:             Resources:
+# ALL-NEXT:        [0]   - JALU0
+# ALL-NEXT:        [1]   - JALU1
+# ALL-NEXT:        [2]   - JDiv
+# ALL-NEXT:        [3]   - JFPA
+# ALL-NEXT:        [4]   - JFPM
+# ALL-NEXT:        [5]   - JFPU0
+# ALL-NEXT:        [6]   - JFPU1
+# ALL-NEXT:        [7]   - JLAGU
+# ALL-NEXT:        [8]   - JMul
+# ALL-NEXT:        [9]   - JSAGU
+# ALL-NEXT:        [10]  - JSTC
+# ALL-NEXT:        [11]  - JVALU0
+# ALL-NEXT:        [12]  - JVALU1
+# ALL-NEXT:        [13]  - JVIMUL
+
+# ALL:             Resource pressure per iteration:
+# ALL-NEXT:        [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
+# ALL-NEXT:        0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
+
+# ALL:             Resource pressure by instruction:
+# ALL-NEXT:        [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
+# ALL-NEXT:        0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl %eax, %eax

llvm/trunk/test/tools/llvm-mca/X86/option-all-stats-2.s

 # FULL-NEXT: GROUP   - Static restrictions on the dispatch group: 0
 
 # FULL:      Dispatch Logic - number of cycles where we saw N micro opcodes dispatched:
 # FULL-NEXT: [# dispatched], [# cycles]
 # FULL-NEXT:  0,              22  (21.4%)
 # FULL-NEXT:  1,              62  (60.2%)
 # FULL-NEXT:  2,              19  (18.4%)
 
-# FULL:      Schedulers - number of cycles where we saw N instructions issued:
-# FULL-NEXT: [# issued], [# cycles]
-# FULL-NEXT:  0,          3  (2.9%)
-# FULL-NEXT:  1,          100  (97.1%)
-
-# FULL:      Scheduler's queue usage:
-# FULL-NEXT: [1] Resource name.
-# FULL-NEXT: [2] Average number of used buffer entries.
-# FULL-NEXT: [3] Maximum number of used buffer entries.
-# FULL-NEXT: [4] Total number of buffer entries.
-
-# FULL:       [1]            [2]        [3]        [4]
-# FULL-NEXT: JALU01           15         20         20
-# FULL-NEXT: JFPU01           0          0          18
-# FULL-NEXT: JLSAGU           0          0          12
-
-# FULL:      Retire Control Unit - number of cycles where we saw N instructions retired:
-# FULL-NEXT: [# retired], [# cycles]
-# FULL-NEXT:  0,           3  (2.9%)
-# FULL-NEXT:  1,           100  (97.1%)
-
-# FULL:      Register File statistics:
-# FULL-NEXT: Total number of mappings created:    200
-# FULL-NEXT: Max number of mappings used:         44
-
-# FULL:      *  Register File #1 -- JFpuPRF:
-# FULL-NEXT:    Number of physical registers:     72
-# FULL-NEXT:    Total number of mappings created: 0
-# FULL-NEXT:    Max number of mappings used:      0
-
-# FULL:      *  Register File #2 -- JIntegerPRF:
-# FULL-NEXT:    Number of physical registers:     64
-# FULL-NEXT:    Total number of mappings created: 200
-# FULL-NEXT:    Max number of mappings used:      44
-
-# FULL:      Resources:
-# FULL-NEXT: [0]   - JALU0
-# FULL-NEXT: [1]   - JALU1
-# FULL-NEXT: [2]   - JDiv
-# FULL-NEXT: [3]   - JFPA
-# FULL-NEXT: [4]   - JFPM
-# FULL-NEXT: [5]   - JFPU0
-# FULL-NEXT: [6]   - JFPU1
-# FULL-NEXT: [7]   - JLAGU
-# FULL-NEXT: [8]   - JMul
-# FULL-NEXT: [9]   - JSAGU
-# FULL-NEXT: [10]  - JSTC
-# FULL-NEXT: [11]  - JVALU0
-# FULL-NEXT: [12]  - JVALU1
-# FULL-NEXT: [13]  - JVIMUL
-
-# FULL:      Resource pressure per iteration:
-# FULL-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
-# FULL-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
-
-# FULL:      Resource pressure by instruction:
-# FULL-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
-# FULL-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl %eax, %eax
+# ALL:       Schedulers - number of cycles where we saw N instructions issued:
+# ALL-NEXT:  [# issued], [# cycles]
+# ALL-NEXT:   0,          3  (2.9%)
+# ALL-NEXT:   1,          100  (97.1%)
+
+# ALL:       Scheduler's queue usage:
+# ALL-NEXT:  [1] Resource name.
+# ALL-NEXT:  [2] Average number of used buffer entries.
+# ALL-NEXT:  [3] Maximum number of used buffer entries.
+# ALL-NEXT:  [4] Total number of buffer entries.
+
+# ALL:        [1]            [2]        [3]        [4]
+# ALL-NEXT:  JALU01           15         20         20
+# ALL-NEXT:  JFPU01           0          0          18
+# ALL-NEXT:  JLSAGU           0          0          12
+
+# ALL:       Retire Control Unit - number of cycles where we saw N instructions retired:
+# ALL-NEXT:  [# retired], [# cycles]
+# ALL-NEXT:   0,           3  (2.9%)
+# ALL-NEXT:   1,           100  (97.1%)
+
+# ALL:       Register File statistics:
+# ALL-NEXT:  Total number of mappings created:    200
+# ALL-NEXT:  Max number of mappings used:         44
+
+# ALL:       *  Register File #1 -- JFpuPRF:
+# ALL-NEXT:     Number of physical registers:     72
+# ALL-NEXT:     Total number of mappings created: 0
+# ALL-NEXT:     Max number of mappings used:      0
+
+# ALL:       *  Register File #2 -- JIntegerPRF:
+# ALL-NEXT:     Number of physical registers:     64
+# ALL-NEXT:     Total number of mappings created: 200
+# ALL-NEXT:     Max number of mappings used:      44
+
+# ALL:       Resources:
+# ALL-NEXT:  [0]   - JALU0
+# ALL-NEXT:  [1]   - JALU1
+# ALL-NEXT:  [2]   - JDiv
+# ALL-NEXT:  [3]   - JFPA
+# ALL-NEXT:  [4]   - JFPM
+# ALL-NEXT:  [5]   - JFPU0
+# ALL-NEXT:  [6]   - JFPU1
+# ALL-NEXT:  [7]   - JLAGU
+# ALL-NEXT:  [8]   - JMul
+# ALL-NEXT:  [9]   - JSAGU
+# ALL-NEXT:  [10]  - JSTC
+# ALL-NEXT:  [11]  - JVALU0
+# ALL-NEXT:  [12]  - JVALU1
+# ALL-NEXT:  [13]  - JVIMUL
+
+# ALL:       Resource pressure per iteration:
+# ALL-NEXT:  [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
+# ALL-NEXT:  0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
+
+# ALL:       Resource pressure by instruction:
+# ALL-NEXT:  [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
+# ALL-NEXT:  0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl %eax, %eax

llvm/trunk/test/tools/llvm-mca/X86/option-all-views-1.s

 # FULLREPORT-NEXT:       Total number of mappings created: 0
 # FULLREPORT-NEXT:       Max number of mappings used:      0
 
 # FULLREPORT:         *  Register File #2 -- JIntegerPRF:
 # FULLREPORT-NEXT:       Number of physical registers:     64
 # FULLREPORT-NEXT:       Total number of mappings created: 200
 # FULLREPORT-NEXT:       Max number of mappings used:      44
 
-# FULLREPORT:         Resources:
-# FULLREPORT-NEXT:    [0]   - JALU0
-# FULLREPORT-NEXT:    [1]   - JALU1
-# FULLREPORT-NEXT:    [2]   - JDiv
-# FULLREPORT-NEXT:    [3]   - JFPA
-# FULLREPORT-NEXT:    [4]   - JFPM
-# FULLREPORT-NEXT:    [5]   - JFPU0
-# FULLREPORT-NEXT:    [6]   - JFPU1
-# FULLREPORT-NEXT:    [7]   - JLAGU
-# FULLREPORT-NEXT:    [8]   - JMul
-# FULLREPORT-NEXT:    [9]   - JSAGU
-# FULLREPORT-NEXT:    [10]  - JSTC
-# FULLREPORT-NEXT:    [11]  - JVALU0
-# FULLREPORT-NEXT:    [12]  - JVALU1
-# FULLREPORT-NEXT:    [13]  - JVIMUL
-
-# FULLREPORT:         Resource pressure per iteration:
-# FULLREPORT-NEXT:    [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
-# FULLREPORT-NEXT:    0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
-
-# FULLREPORT:         Resource pressure by instruction:
-# FULLREPORT-NEXT:    [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
-# FULLREPORT-NEXT:    0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl  %eax, %eax
+# DEFAULTREPORT:      Resources:
+# DEFAULTREPORT-NEXT: [0]   - JALU0
+# DEFAULTREPORT-NEXT: [1]   - JALU1
+# DEFAULTREPORT-NEXT: [2]   - JDiv
+# DEFAULTREPORT-NEXT: [3]   - JFPA
+# DEFAULTREPORT-NEXT: [4]   - JFPM
+# DEFAULTREPORT-NEXT: [5]   - JFPU0
+# DEFAULTREPORT-NEXT: [6]   - JFPU1
+# DEFAULTREPORT-NEXT: [7]   - JLAGU
+# DEFAULTREPORT-NEXT: [8]   - JMul
+# DEFAULTREPORT-NEXT: [9]   - JSAGU
+# DEFAULTREPORT-NEXT: [10]  - JSTC
+# DEFAULTREPORT-NEXT: [11]  - JVALU0
+# DEFAULTREPORT-NEXT: [12]  - JVALU1
+# DEFAULTREPORT-NEXT: [13]  - JVIMUL
+
+# DEFAULTREPORT:      Resource pressure per iteration:
+# DEFAULTREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
+# DEFAULTREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
+
+# DEFAULTREPORT:      Resource pressure by instruction:
+# DEFAULTREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
+# DEFAULTREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl  %eax, %eax
 
 # FULLREPORT:         Timeline view:
 # FULLREPORT-NEXT:                        012
 # FULLREPORT-NEXT:    Index     0123456789
 
 # FULLREPORT:         [0,0]     DeER .    . .   addl  %eax, %eax
 # FULLREPORT-NEXT:    [1,0]     D=eER.    . .   addl  %eax, %eax
 # FULLREPORT-NEXT:    [2,0]     .D=eER    . .   addl  %eax, %eax

llvm/trunk/test/tools/llvm-mca/X86/option-all-views-2.s

 # FULLREPORT-NEXT: [7]   - JLAGU
 # FULLREPORT-NEXT: [8]   - JMul
 # FULLREPORT-NEXT: [9]   - JSAGU
 # FULLREPORT-NEXT: [10]  - JSTC
 # FULLREPORT-NEXT: [11]  - JVALU0
 # FULLREPORT-NEXT: [12]  - JVALU1
 # FULLREPORT-NEXT: [13]  - JVIMUL
 
-# NORPV:           Timeline view:
-# NORPV-NEXT:                          012
-# NORPV-NEXT:      Index     0123456789
-
 # FULLREPORT:      Resource pressure per iteration:
 # FULLREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]
 # FULLREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -
 
-# NORPV:           [0,0]     DeER .    . .   addl %eax, %eax
-# NORPV-NEXT:      [1,0]     D=eER.    . .   addl %eax, %eax
-# NORPV-NEXT:      [2,0]     .D=eER    . .   addl %eax, %eax
-# NORPV-NEXT:      [3,0]     .D==eER   . .   addl %eax, %eax
-# NORPV-NEXT:      [4,0]     . D==eER  . .   addl %eax, %eax
-# NORPV-NEXT:      [5,0]     . D===eER . .   addl %eax, %eax
-# NORPV-NEXT:      [6,0]     .  D===eER. .   addl %eax, %eax
-# NORPV-NEXT:      [7,0]     .  D====eER .   addl %eax, %eax
-# NORPV-NEXT:      [8,0]     .   D====eER.   addl %eax, %eax
-# NORPV-NEXT:      [9,0]     .   D=====eER   addl %eax, %eax
-
-# NORPV:           Average Wait times (based on the timeline view):
-# NORPV-NEXT:      [0]: Executions
-# NORPV-NEXT:      [1]: Average time spent waiting in a scheduler's queue
-# NORPV-NEXT:      [2]: Average time spent waiting in a scheduler's queue while ready
-# NORPV-NEXT:      [3]: Average time elapsed from WB until retire stage
-
 # FULLREPORT:      Resource pressure by instruction:
 # FULLREPORT-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]   [11]   [12]   [13]   Instructions:
 # FULLREPORT-NEXT: 0.50   0.50    -      -      -      -      -      -      -      -      -      -      -      -     addl %eax, %eax
 
-# NORPV:                 [0]    [1]    [2]    [3]
-# NORPV-NEXT:      0.     10    3.5    0.1    0.0       addl  %eax, %eax
-
-# FULLREPORT:      Timeline view:
-# FULLREPORT-NEXT:                     012
-# FULLREPORT-NEXT: Index     0123456789
-
-# FULLREPORT:      [0,0]     DeER .    . .   addl %eax, %eax
-# FULLREPORT-NEXT: [1,0]     D=eER.    . .   addl %eax, %eax
-# FULLREPORT-NEXT: [2,0]     .D=eER    . .   addl %eax, %eax
-# FULLREPORT-NEXT: [3,0]     .D==eER   . .   addl %eax, %eax
-# FULLREPORT-NEXT: [4,0]     . D==eER  . .   addl %eax, %eax
-# FULLREPORT-NEXT: [5,0]     . D===eER . .   addl %eax, %eax
-# FULLREPORT-NEXT: [6,0]     .  D===eER. .   addl %eax, %eax
-# FULLREPORT-NEXT: [7,0]     .  D====eER .   addl %eax, %eax
-# FULLREPORT-NEXT: [8,0]     .   D====eER.   addl %eax, %eax
-# FULLREPORT-NEXT: [9,0]     .   D=====eER   addl %eax, %eax
-
-# FULLREPORT:      Average Wait times (based on the timeline view):
-# FULLREPORT-NEXT: [0]: Executions
-# FULLREPORT-NEXT: [1]: Average time spent waiting in a scheduler's queue
-# FULLREPORT-NEXT: [2]: Average time spent waiting in a scheduler's queue while ready
-# FULLREPORT-NEXT: [3]: Average time elapsed from WB until retire stage
+# ALL:             Timeline view:
+# ALL-NEXT:                            012
+# ALL-NEXT:        Index     0123456789
+
+# ALL:             [0,0]     DeER .    . .   addl %eax, %eax
+# ALL-NEXT:        [1,0]     D=eER.    . .   addl %eax, %eax
+# ALL-NEXT:        [2,0]     .D=eER    . .   addl %eax, %eax
+# ALL-NEXT:        [3,0]     .D==eER   . .   addl %eax, %eax
+# ALL-NEXT:        [4,0]     . D==eER  . .   addl %eax, %eax
+# ALL-NEXT:        [5,0]     . D===eER . .   addl %eax, %eax
+# ALL-NEXT:        [6,0]     .  D===eER. .   addl %eax, %eax
+# ALL-NEXT:        [7,0]     .  D====eER .   addl %eax, %eax
+# ALL-NEXT:        [8,0]     .   D====eER.   addl %eax, %eax
+# ALL-NEXT:        [9,0]     .   D=====eER   addl %eax, %eax
+
+# ALL:             Average Wait times (based on the timeline view):
+# ALL-NEXT:        [0]: Executions
+# ALL-NEXT:        [1]: Average time spent waiting in a scheduler's queue
+# ALL-NEXT:        [2]: Average time spent waiting in a scheduler's queue while ready
+# ALL-NEXT:        [3]: Average time elapsed from WB until retire stage
 
-# FULLREPORT:            [0]    [1]    [2]    [3]
-# FULLREPORT-NEXT: 0.     10    3.5    0.1    0.0       addl  %eax, %eax
+# ALL:                   [0]    [1]    [2]    [3]
+# ALL-NEXT:        0.     10    3.5    0.1    0.0       addl  %eax, %eax

llvm/trunk/utils/update_mca_test_checks.py

else:
     if len(common_to_all) > 1:
       _warn('Multiple prefixes common to all RUN lines: {}'.format(
           common_to_all))
     if common_to_all:
       common_to_all = sorted(common_to_all)[0]
   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
       a series of lines of text with no more than one newline character between
       each one.  For example:
 
       This
       is
def _get_block_infos(run_infos, test_path, args, common_prefix):  # noqa
   def _block_key(tool_args, prefixes):
     """ Get a hashable key based on the current tool_args and prefixes.
     """
     return ' '.join([tool_args] + prefixes)
 
   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)
     raw_tool_output = common.invoke_tool(args.llvm_mca_binary,
                                          tool_args,
                                          test_path)
 
     # Replace any lines consisting of purely whitespace with empty lines.
     raw_tool_output = '\n'.join(line if line.strip() else ''
                                 for line in raw_tool_output.splitlines())
 
     # Split blocks, stripping all trailing whitespace, but keeping preceding
     # whitespace except for newlines so that columns will line up visually.
     all_blocks[key] = [b.lstrip('\n').rstrip()
                        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:
     len_to_pad = max_block_len - len(all_blocks[key])
     all_blocks[key] += [''] * len_to_pad
 
   # Create the block_infos structure where it is a nested dict in the form of:
   # block number -> block text -> list of prefix sets