An apparatus comprises processing circuitry, an instruction cache, decoding circuitry to decode program instructions fetched from the cache to generate macro-operations to be processed by the processing circuitry, and predecoding circuitry to perform a predecoding operation on a block of program instructions fetched from a data store to generate predecode information to be stored to the cache with the block of instructions. In one example the predecoding operation comprises generating information on how many macro-operations are to generated by the decoding circuitry for a group of one or more program instructions. In another example the predecoding operation comprises generating information indicating whether at least one of a given subset of program instructions within the prefetched block is a branch instruction.