A control-flow graph (CFG) is a fundamental structure used in computer science and engineering for describing and analyzing the structure of an algorithm or program. A dynamic control-flow graph (DCFG) is a specialized CFG that adds data from a specific execution of a program. We provide a tool for generating a DCFG based on the Pin binary-instrumentation package. We also provide an application-programmer interface (API) to access the DCFG data from within another Pin tool or a standalone program. More details follow.
We start with a classical control-flow graph (CFG) definition as described by Frances Allen in a 1970 ACM SIGPLAN article:
Typically, a CFG is defined statically, i.e., there is exactly one CFG for a given binary, it contains no information about the execution path of any particular workload, and the nodes and edges are determined by all the possible reachable code paths in the binary. It does not typically include edges created by unexpected exceptions and other non-control-flow instructions.
We define a DCFG as a CFG with the following differences:
The blocks in a DCFG can be combined into higher-level constructs such as loops, routines, and binary images. Dynamic data such as loop iteration counts can be deduced from the underlying edge counts.
Even though a DCFG contains dynamic information such as edge counts, in general, it does not allow one to recreate the order in which edges were executed. This additional information is needed for many types of dynamic analysis. So, in addition to the DCFG, we define a DCFG-Trace as the sequence of edges taken during execution of the workload. The exact sequence of basic blocks, routines, and loops taken by a workload can then be recreated from the combination of its DCFG and DCFG-Trace.
A DCFG and/or a DCFG-Trace can be created using a PinPlay tool that is linked with the DCFG PinPlay library “dcfg-pinplay.so” (for Linux). Linking with this library provides a number of command-line knobs. The “-dcfg” knob creates a DCFG datafile and adding the “-dcfg:write_trace” knob creates a DCFG-Trace datafile. Both of these files are in JSON format. See the help messages for other knobs beginning with “-dcfg:” for other options.
A DCFG and/or a DCFG-Trace can be used in a variety of ways. For example:
Documentation is available for the following:
DCFG library/example-tools are distributed with the PinPlay kit for PLDI2016 (pinplay-drdebug-pldi2016-*).
Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.
Notice revision #20110804