Processing circuitry performs data processing operations in response to instructions fetched from a cache or memory or micro-operations decoded from the instructions. Sampling circuitry selects a subset of instructions or micro-operations as sampled operations to be profiled. Profiling circuitry captures, in response to processing of an instruction or micro-operation selected as a sampled operation, a sample record specifying an operation type of the sampled operation and information about behaviour of the sampled operation which is directly attributed to the sampled operation. The profiling circuitry can include, in the sample record for a sampled operation corresponding to a given instruction, a reference instruction address indicator indicative of an address of a reference instruction appearing earlier or later in program order than the given instruction, for which control flow is sequential between any instructions occurring between the reference instruction and the given instruction in program order.