[WIP] Helper script for analyzing mir dumps

[markus]

Summary

Some ideas for helper scripts for analyzing mir dumps.

The dump files generated by llc -print-after-all tend to be rather large and this results in a number of problems. When comparing two runs simply launching your favorite diff tool on two files in the range of ~100k lines is not ideal. Diffing one pass and a subsequent one requires copy&paste to put the fragments in different files. When searching for e.g. registers it is easy to accidentally get a match outside the current pass of interest.

A more sophisticated approach would be to develop a simple python library that creates an in-memory representation of the dump file. E.g. the dump file is represented by a DumpFile object and then you have Fragment objects that reference an interval of lines of this DumpFile. The Fragment class can then be specialized into Pass, Function and BasicBlock. Defining some operations (like compare, view and diff) on the fragments allows for a rather flexible framework that can be used to build custom tools to ease the task of dump analysis by eliminating cumbersome and error prone manual steps.

Example usage

int dot(int *a, int *b, int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += a[i] * b[i];
  return sum;
}

$ clang --target=riscv32 dot.c -O4 -S -mllvm -print-after-all 2> dump.txt

# Get an overview of where changes occurred
$ utils/dumptool --primary=dump.txt --list-pruned
* 0 riscv-isel
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 ]
* 4 slotindexes
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 ]
* 5 stack-coloring
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 ]
* 10 machine-sink
        *dot [ *bb.0 *bb.4 bb.1 *bb.2 bb.3 ]
* 21 unreachable-mbb-elimination
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 22 livevars
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 23 phi-node-elimination
        *dot [ bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 24 twoaddressinstruction
        *dot [ bb.0 bb.1 bb.2 bb.3 bb.4 ]
* 25 slotindexes
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 26 liveintervals
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 27 register-coalescer
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 30 livedebugvars
        *dot [ bb.0 bb.1 bb.2 bb.3 bb.4 ]
* 35 virtregrewriter
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 38 machine-cp
        *dot [ *bb.0 *bb.1 *bb.2 *bb.3 *bb.4 ]
* 44 shrink-wrap
        *dot [ bb.0 bb.1 bb.2 *bb.3 *bb.4 *bb.5 ]
* 47 branch-folder
        *dot [ *bb.0 *bb.1 *bb.2 ]
* 50 postrapseudos
        *dot [ *bb.0 bb.1 *bb.2 ]
* 64 machine-sanmd
        dot [ bb.0 bb.1 bb.2 ]
* 65 stack-frame-layout
        dot [ bb.0 bb.1 bb.2 ]
* 70 unpack-mi-bundles
        dot [ bb.0 bb.1 bb.2 ]

# Examine bb.4 of function dot after machine-sink

$ utils/dumptool --primary=dump.txt --primary-frag=10/dot/bb.4 --view

# Diff function dot before and after machine sink

$ utils/dumptool --primary=dump.txt --secondary=dump.txt --primary-frag=9/dot --secondary-frag=10/dot --diff

llvm/utils/dumptool

+#!/usr/bin/env python3
+
+import argparse
+import dumputils as du
+
+import pdb
+
+def get_fragment(dump, path):
+  lst = path.split('/')
+  p = dump.passes[int(lst[0])]
+  if len(lst) < 2:
+    return p
+  f = p.functions[lst[1]]
+  if len(lst) < 3:
+    return f
+  b = f.blocks[lst[2]]
+  return b
+
+def cmd_list(dump, prune=False):
+  pprev = None
+  for pidx, p in enumerate(dump.passes):
+    if prune and pprev is not None and p == pprev:
+      continue
+
+    print('{} {} {}'.format('*' if pprev is None or p != pprev else ' ', pidx, p.name))
+    for fkey, f in p.functions.items():
+      fprev = pprev.functions.get(fkey) if pprev is not None else None
+      print('        {}{} ['.format('*' if fprev is None or fprev != f else '', f.name), end='')
+      for bkey, b in f.blocks.items():
+        bprev = fprev.blocks.get(bkey) if fprev is not None else None
+        print(' {}{}'.format('*' if bprev is None or bprev != b else '', b.name), end='')
+      print(' ]')
+
+    pprev = p
+
+def cmd_compare(dump, other):
+  for idx, _ in enumerate(dump.passes):
+    p = dump.passes[idx]
+    pother = other.passes[idx]
+    assert p.name == pother.name
+    if p == pother:
+      continue
+    print('Mismatch in pass: {} {}'.format(idx, p.name))
+    for fkey, f in p.functions.items():
+      fother = pother.functions.get(fkey)
+      if fother is not None and f == fother:
+        continue
+      print('  Mismatch in function: {}'.format(f.name))
+      for bkey, b in f.blocks.items():
+        bother = fother.blocks.get(bkey)
+        if bother is not None and b == bother:
+          continue
+        print('    Mismatch in block: {}'.format(b.name))
+  
+
+parser = argparse.ArgumentParser(description='A "Swizz Army Knife" tool for analyzing llc -print-after-all dumps')
+parser.add_argument('--primary', action='store', required=True, help='Specify the primary dump-file')
+parser.add_argument('--secondary', action='store', help='Specify the secondary dump-file')
+parser.add_argument('--list', action='store_true', help='List contents of the primary dump (\'*\' indicates that the fragment was modified)')
+parser.add_argument('--list-pruned', action='store_true', help='Same as --list but pruning those pass invocations that did not modify')
+parser.add_argument('--compare', action='store_true', help='Compare the primary and secondary dumps')
+parser.add_argument('--primary-frag', action='store', help='Specify the fragment (format is \'passidx/function/block\') inside the primary dump')
+parser.add_argument('--secondary-frag', action='store', help='Specify the fragment (format is \'passidx/function/block\') inside the secondary dump')
+parser.add_argument('--graph', action='store_true', help='View the CFG of the specified primary function fragment')
+parser.add_argument('--view', action='store_true', help='View the specified primary fragment')
+parser.add_argument('--diff', action='store_true', help='Diff the primary and secondary fragment')
+
+args = parser.parse_args()
+
+primary = du.DumpFile(args.primary)
+secondary = du.DumpFile(args.secondary) if args.secondary else None
+
+primary_frag = get_fragment(primary, args.primary_frag) if args.primary_frag else None
+secondary_frag = get_fragment(secondary, args.secondary_frag) if args.secondary_frag else None
+
+if args.list:
+  cmd_list(primary)
+if args.list_pruned:
+  cmd_list(primary, True)
+if args.compare and secondary is not None:
+  cmd_compare(primary, secondary)
+if args.graph and primary_frag:
+  du.graph(primary_frag)
+if args.view and primary_frag:
+  du.view(primary_frag)
+if args.diff and primary_frag and secondary_frag:
+  du.diff(primary_frag, secondary_frag)

llvm/utils/dumputils.py

+import re
+import os
+import tempfile
+import pdb
+
+class DumpFile(object):
+  def __init__(self, path):
+    self.passes = []
+    self.lines = []
+    f = open(path, 'r')
+    for line in f.readlines():
+      self.lines.append(line)
+    f.close()
+    pat_begin = re.compile('^# \*\*\* IR Dump [^\(]+ \(([a-zA-Z0-9\-]+)\) \*\*\*:$')
+    begin = None
+    begin_name = None
+    for idx, line in enumerate(self.lines):
+      if m := pat_begin.match(line):
+        name = m.group(1)
+        if begin:
+          self.passes.append(Pass(self, begin_name, begin+1, idx))
+        begin = idx
+        begin_name = name
+    self.passes.append(Pass(self, begin_name, begin+1, idx))
+
+class Fragment(object):
+  def __init__(self, dump, name, begin, end):
+    self.dump = dump
+    self.name = name
+    self.begin = begin
+    self.end = end
+
+  def __eq__(self, other):
+    return self.dump.lines[self.begin:self.end] == other.dump.lines[other.begin:other.end]
+
+  def write(self, file):
+    for idx in range(self.begin, self.end):
+      file.write(self.dump.lines[idx])
+
+class Pass(Fragment):
+  def __init__(self, dump, name, begin, end):
+    super().__init__(dump, name, begin, end)
+    self.functions = {}
+
+    pat_begin = re.compile('^# Machine code for function ([a-zA-Z_][a-zA-Z0-9_]+).*$')
+    pat_end = re.compile('^# End machine code for function ([a-zA-Z_][a-zA-Z0-9_]+).*$')
+    for idx in range(self.begin, self.end):
+      line = self.dump.lines[idx]
+      if m := pat_begin.match(line):
+        begin = idx
+      elif m := pat_end.match(line):
+        name = m.group(1)
+        self.functions[name] = Function(self.dump, name, begin, idx)
+
+
+class Function(Fragment):
+  def __init__(self, dump, name, begin, end):
+    super().__init__(dump, name, begin, end)
+    self.blocks = {}
+
+    pat_begin = re.compile('^([0-9]+B)?\s*(bb\.[0-9]+)')
+    begin = None
+    begin_name = None
+    for idx in range(self.begin, self.end):
+      line = self.dump.lines[idx]
+      if m := pat_begin.search(line):
+        name = m.group(2)
+        if begin:
+          self.blocks[begin_name] = BasicBlock(self.dump, begin_name, begin, idx)
+        begin = idx
+        begin_name = name
+    self.blocks[begin_name] = BasicBlock(self.dump, begin_name, begin, self.end)
+
+
+class BasicBlock(Fragment):
+  def __init__(self, dump, name, begin, end):
+    super().__init__(dump, name, begin, end)
+
+  def successors(self):
+    pat_succs = re.compile('\s+successors:([^;]+).*$')
+    pat_bb = re.compile('(bb.[0-9]+)')
+    for idx in range(self.begin, self.end):
+      line = self.dump.lines[idx]
+      if m := pat_succs.match(line):
+        return pat_bb.findall(m.group(1))
+    return []
+
+def diff(obj_a, obj_b):
+  with tempfile.TemporaryDirectory() as tmpdirname:
+    path_a = tmpdirname + '/a.txt'
+    path_b = tmpdirname + '/b.txt'
+    file_a = open(path_a, 'w')
+    file_b = open(path_b, 'w')
+    obj_a.write(file_a)
+    obj_b.write(file_b)
+    file_a.close()
+    file_b.close()
+    os.system('vimdiff {} {}'.format(path_a, path_b))
+
+def view(obj_a):
+  with tempfile.TemporaryDirectory() as tmpdirname:
+    path_a = tmpdirname + '/a.txt'
+    file_a = open(path_a, 'w')
+    obj_a.write(file_a)
+    file_a.close()
+    os.system('vim {}'.format(path_a))
+
+def graph(func):
+  with tempfile.TemporaryDirectory() as tmpdirname:
+    path = tmpdirname + '/cfg.dot'
+    file = open(path, 'w')
+    file.write('digraph CFG {\n')
+    for _, b in func.blocks.items():
+      for s in b.successors():
+        file.write('  {} -> {}\n'.format(b.name.replace('.','_'), s.replace('.','_')))
+    file.write('}\n')
+    file.close()
+    if os.system('dot -Tx11 {}'.format(path)) != 0:
+      os.system('cat {}'.format(path))
+
+def prune_passes(dump):
+  mpasses = []
+  mpasses.append(dump.passes[0])
+  for p in dump.passes:
+    if p != mpasses[-1]:
+      mpasses.append(p)
+  return mpasses