Trace circuitry 22, 6 forms trace objects 34 representing a sequence of executed program instructions and comprising a start address indicator indicating a start address of a sequence of executed program instructions, a branch outcome indicator indicating a sequence of branch outcomes within the sequence of executed program instructions starting from the start address and a count indicator indicating a count of times the sequence of branch outcomes was detected. The trace circuitry may be on-chip 22 or off-chip 6. A trace object may include an indicator of a start address of a next sequence of program instructions to be followed following the sequence of program instructions represented by the trace object concerned.