In a data processing system, data representing program instructions is fetched from memory, each instruction being from one of a plurality of sets of instructions including at least first and second sets of instructions and each program instruction within the fetched data comprising one or more blocks to be pre-decoded, each block representing a portion of an instruction. Pre-decoding circuitry is configured to perform pre-decoding operations on the blocks. For at least one portion of an instruction from the first set of instructions and at least one portion of an instruction from the second set of instructions the pre-decoding operation performed on a block fetched from memory is independent of whether the block is identified as representing the at least one portion of an instruction from the first set of instructions or as the at least one portion of an instruction from the second set of instructions.