Instruction Trace: Funnels, Packet Formats, and Reconstructing Execution

A breakpoint shows one moment. Trace shows the sequence, and the difference in hardware is large: instead of comparators, an on-chip unit watches every instruction the core retires and emits a compressed description of where execution went. The compression is the interesting part. Trace bandwidth is limited by the pins or the buffer, and the ratio between instructions executed and bytes emitted determines how long a capture can be.

What the trace unit can and cannot see

The trace source sits inside the core and observes the instruction pipeline. It can see the address of every instruction executed, whether a branch was taken, whether the core entered an exception, and whether a data access occurred at an approximate address. It cannot see register values, memory contents, or the result of a comparison; those are inferred by the decoder from the program image, which is why a decoder needs the exact ELF file that produced the trace.

That dependency is absolute. If the image is rebuilt, addresses shift and the decoder reconstructs a plausible but wrong instruction stream. Trace and image must be tied together, which is why trace captures are stored with the build identifier and why a trace decoded against the wrong image produces a sequence that looks like a valid program.

The core’s own capability is reported in a set of registers: which packet types it can emit, how many address comparators it has for filtering, and whether it can emit timestamps. A trace tool that assumes a capability the source does not have will configure a mode that silently produces no data.

Compression by exception

The fundamental observation is that most instructions execute sequentially, so their addresses are predictable. The trace unit emits an address only when execution departs from the expected path: a taken branch, a return, an exception entry or exit, or a change of instruction set state.

The expected path is maintained by a small state machine. For a branch, the unit knows the target from the program image if the branch is direct, so it emits only a single bit saying whether the branch was taken. For an indirect branch, the target is not derivable, so a full address must be emitted. For a return, the target is on the stack, which the trace unit does not read, so a return packet carries either a full address or a compressed value derived from the call depth.

This is why the ratio between executed instructions and trace bytes is workload-dependent rather than fixed. Straight-line code with direct branches compresses extremely well: a loop of twenty instructions with one backward branch emits one bit per iteration. Code full of indirect calls, computed jumps from a state machine, or returns from varying depths compresses poorly. A switch statement compiled to a jump table emits a full address per dispatch; the same switch compiled to a chain of comparisons emits one bit each. The compiler’s choice changes the trace volume, which is why trace bandwidth planning has to consider the code shape and not only the clock rate.

Packet framing and the funnel

Packets are grouped into frames. Each frame begins with a header identifying the source that produced it, followed by a length or a set of flags, followed by the packet bytes, and terminated by a flag byte marking the end. The header’s source field is what allows multiple trace sources to share one output.

That sharing is done by a funnel: a component with several inputs and one output, which arbitrates between sources and tags each frame with its origin. The arbitration is not simultaneous; only one source feeds the output at a time, and a source that is producing faster than the output can drain will lose data. The loss is reported in the frame header as an overflow flag, which the decoder must surface rather than silently skip.

Downstream of the funnel the trace goes to one of several sinks: a set of pins carrying a parallel or serial protocol to an external probe, or an on-chip SRAM buffer that the probe reads out afterwards. The buffer avoids pins entirely and is limited by size — a few kilobytes to a few hundred kilobytes — which converts directly into capture duration. A buffer of 64 KiB at an average of one byte per ten instructions holds roughly 650,000 instructions, which at about one instruction per cycle and a core clock in the tens of megahertz is on the order of ten milliseconds of execution.

The buffered arrangement has one property worth noting: because the buffer is written by hardware and read afterwards, the capture is not affected by the probe’s speed, and the timing of the program is not affected by the readout. Streaming to pins is the opposite: the program’s timing is unaffected but the probe must keep up, and the capture length is limited only by disk.

Decoding, and the reconstruction problem

A decoder does three things in sequence. It parses frames and packets, producing a stream of events: an address, a branch taken or not taken, an exception entry, a timestamp. It then walks the program image starting from a known address, applying each event at the instruction it corresponds to, and emitting the sequence of executed addresses. Finally it maps addresses to source lines using the DWARF line table described in reading ELF sections and debug information.

The second step is where ambiguity lives. A taken-branch bit applies to the next branch instruction encountered while walking, not to the branch at a fixed offset, so the decoder must simulate instruction decoding exactly as the core would. Getting this wrong by a single instruction desynchronises the entire stream from that point onward, and the output remains syntactically plausible: a valid sequence of instructions that the program never executed.

Returns are the hardest case. A return address is on the stack, and the decoder cannot read the stack from a trace that does not contain data. The protocol provides a compressed return encoding that expresses the target relative to the call depth, and it works only when the call depth is within the encodable range. Beyond that range the unit emits a full address, which is larger but unambiguous. A decoder that mis-tracks call depth — because an exception entry or exit was not counted, or because a tail call was not recognised — produces returns to the wrong address, and the resulting trace shows execution jumping into unrelated functions.

Overflow is the other systematic failure. When the sink cannot accept a packet, the frame is marked and the data is gone. The decoder must emit an explicit discontinuity, not guess at the missing instructions, and a trace tool that renders the gap as continuous execution is misreporting. The correct output says that an unknown number of instructions executed between two known points.

Timestamps and the resolution question

Timestamps are optional and their resolution is a hardware property, often a divider from the core clock. Their purpose is to attribute execution to time rather than to order, which matters for interrupt latency measurement and for correlating trace with an external event.

Two costs follow. A timestamp packet consumes bandwidth, and emitting one per frame rather than per instruction means the timestamps mark frame boundaries rather than individual instructions. Interpolating between them gives a range, not a value, and a latency figure derived from interpolated timestamps carries an error of the same magnitude as the frame duration.

The second cost is clock domain crossing. The trace unit runs on the core clock; the sink may run on a different one. Timestamps are generated in the core domain and must be converted, and the conversion is exact only if the ratio is known and stable. A part that changes its core clock at run time — a power-management transition, a frequency scaling step — makes the timestamps discontinuous in a way that no packet records unless the trace unit emits a timestamp on the transition.

For interrupt latency specifically, the trace is often supplemented by a separate mechanism: a counter that the hardware starts on exception entry and stops on the first instruction of the handler. That measurement is exact and does not depend on trace bandwidth, and it is why latency figures from such a unit and from a decoded trace can differ. The relationship between trace and the events it is meant to explain is the same one that makes breakpoints insufficient on their own; the comparator limits are covered in hardware breakpoints and watchpoints.