1. A processor, comprising: instruction storage in which instructions are stored; fetch logic coupled to the instruction storage to fetch instructions from the instruction storage; decode logic coupled to the fetch logic to decode instructions fetched by the fetch logic; and pre-decode logic associated with the decode logic; wherein at least some of the instructions comprise a prefix, and in parallel with the decode logic decoding a current instruction, the pre-decode logic determines whether a subsequent instruction comprise a prefix, in which case the decode logic causes a program counter to skip the prefix and changes behavior of the decode logic during decoding of the subsequent instruction.