CSI Output: Metadata

Path Tracing Details

Path Tracing metadata is stored as text in the debug section .debug_PT of the object file or executable. Note that in the case of multiple object files linked into a single executable, the executable contains the complete metadata consolidated from all object files. To extract this data, use a command similar to
Tools/extract-section --require .debug_PT myexe

The extracted information will contain entries for each instrumented function in any object file linked into the executable. Each entry gives a description of the control-flow graph of the function, augmented by line number information and Ball/Larus instrumentation information (see [4]). A complete example (from the unit test loop) is:

#
rand
1|EXIT
0|ENTRY|5|5|5|5|5|5|5|5|-1|5
$
0->1|0$0
#
main
3|EXIT
2|ENTRY|9|9|9|9|9|9|9
4|10|10|10
5|11|11|12|12|12|12|13|13|13
6|-1|20|20|21|21
7|14
8|17
9|18|18|18|-1
$
2->4|0$0
4->5|0$0
4->6|2$2
5->7|0$0
5->8|1$1
6->3|0$0
7->9|0$0
8->9|0$0
9~>4|3$3

This metadata format obeys the following grammar. Non-terminals are distinguished from terminals by capitalization, color, and italics.

Each Function entry lists the function’s name, line number information for the function’s basic blocks, and instrumentation information for the control-flow graph edges (between basic blocks).

The function’s name is followed by N Block entries for the N basic blocks in the function. Each block has a block-id, which is unique within the function (though not necessarily globally, though this is the case in the given example). This id is followed by the list of line numbers for statements within that basic block. The special value ENTRY preceeds this list of Block_Lines for the unique function entry block. The unique exit block is not allowed line numbers, and simply has the special value EXIT. If the basic block has no statements with line number information, the block has the special value NULL. This is not an error, and occurs often in real software both naturally and due to instrumentation requirements. If the list of line numbers contains the sentinel value -1, this basic block marks the completion of acyclic paths and writes the unqiue completed path value into the tracing array.

The blocks are followed by a representation of the control-flow graph of the function. Each Edge entry (from one source block-id to the target block-id) contains edge details and information about instrumentation along the edge. If the arrow for the edge is straight (->), the edge is a standard edge; if the arrow is formed from a tilde (~>), it is a backedge. The entry also contains the edge increment (for instrumentation and partial path reconstruction) and the edge weight (for complete acyclic path reconstruction). If the edge is a backedge, these numbers represent the reinitialization of the path sum. For details, see the papers [2, 3], and the original discussion of this instrumentation scheme in [4].

In the example above, then, the basic block in function main labeled 5 contains statements on lines 11, 12, and 13. It is not the end of acyclic paths (it has no -1 in its line numbers), and has two outgoing edges. One edge is to block 7 with an increment (and weight) of 0, and the other is to block 8 with an increment (and weight) of 1. The entire graph thus looks something like this: