An apparatus in a microprocessor that has an instruction set architecture in which instructions may include a length-modifying prefix used to select an address/operand size other than a default address/operand size, wherein the apparatus marks the start byte and the end byte of each instruction in a stream of instruction bytes. Decode logic decodes each instruction byte of a predetermined number of instruction bytes to determine whether the instruction byte specifies a length-modifying prefix and generates a start mark and an end mark for each of the instruction bytes based on an address/operand size. Operand/address size logic provides the default operand/address size to the decode logic to use to generate the start and end marks during a first clock cycle during which the decode logic decodes the predetermined number of instruction bytes. If during the first clock cycle and any of N subsequent clock cycles the decode logic indicates that one of the predetermined number of instruction bytes specifies a length-modifying prefix, the operand/address size logic provides to the decode logic on the next clock cycle the address/operand size specified by the length-modifying prefix to use to generate the start and end marks.