mole – static search for critical and uniproc cycles

We extended our earlier tool chain to perform efficient enumeration of cycles in programs at large scale. Details of our approach can by found in the accompanying paper. The main change to the earlier implementation is support for programs without a defined entry point, such as libraries. This enables static analysis at object level, rather than relying on fully linked programs.

We distribute the changes to previous code as source patch and as a binary (goto-instrument-git, for Linux/amd64) contained in the full distribution of mole, described below. The new code adds the option --static-cycles to goto-instrument.

The full distribution of mole contains the full tool chain built around this static search in order to analyse archives of goto binaries to provide the information discussed in the paper. The following tool chain was used to obtain the data:

• idiom-search.sh: Invokes idiom-search-one.sh on all Debian packages containing references to POSIX threads or Linux kernel threads; idiom-search-one.sh in turn processes an archive of goto binaries, as available from our experimental results, to invoke goto-instrument-git --static-cycles on each object file. Each object file yields one log file of output.
• classify-wrapper.sh: Filters the above result logs (using filter-critical-cycles.pl) to extract all critical or uniproc cycles from the output, and then passes these to either classify (for critical cycles, via classify-critical.pl) or classify-uniproc.pl (for uniproc cycles) to identify the idiom corresponding to each cycle.
• to-axiom.sh (via cycle-to-axiom.pl) identifies, for each critical or uniproc cycle, the axiom that covers this cycle.

Based on the data, we generate two kinds of reports:

• Our detailed per-package reports as LaTeX, and then HTML, using mole-to-latex-full.sh (via mole.sh and mole-to-latex.sh, using mole-latex-transform.pl and mole-source-transform.pl).
• The results presented in the paper using summaries.sh.

Once mole-0.2.tar.gz is unpacked, we use this tool kit as follows (no command line arguments required, but some of the shell scripts make assumptions about our local directory structure; this needs to be adjusted as needed, in particular the location of the goto binary archives):

• Run idiom-search.sh
• Run classify-wrapper.sh
• Run to-axiom.sh

These three tools can safely be run in parallel, or even multiple instances of each of them. As idiom-search.sh may have to run for several days or weeks, results will be complete for the Debian packages fully processed so far. For any of the packages classify-wrapper.sh and to-axiom.sh are done with, the reports can be generated accordingly. This is achieved by running mole-to-latex-full.sh.

This document was translated from L^AT_EX by H^EV^EA.