A hierarchical cache with at least a unified cache is used to store both instructions and data values, and a further cache coupled between processing circuitry and a unified cache. The unified cache has a plurality of cache lines identified as an instruction cache line or a data cache line. Each data cache line stores at least one data value and the associated information. Pre-decode circuitry is associated with the unified cache and performs a first pre-decode operation on a received instruction for that instruction cache line in order to generate a corresponding partially pre-decoded instruction for storing in the instruction cache line. Further pre-decode circuitry is associated with the further cache, and, when a partially pre-decoded instruction is routed to the further cache, performs a further pre-decode operation on the partially pre-decoded instruction to generate a corresponding pre-decoded instruction for storage in the further cache.