1. A computer system that is configured to perform the following: dividing a set of computer instructions arranged in a sequential program order into a plurality of instruction sequences, wherein instructions within each sequence are arranged and executed according to the program order, but executed out-of-order relative to instructions in other sequences; assigning increment values to individual program-ordered (PO) instructions in each sequence, wherein each increment value is equal to a difference between a program order value of a subsequent PO instruction in the sequence and a program order value of the PO instruction, and wherein the increment value is encoded into the PO instruction; and at a processor of the system, reconstructing the program order of instructions in each sequence relative to the program order of instructions in the other sequences by: calculating the program order value of PO instructions based on the program order value and the increment value of a preceding PO instruction in the same sequence, wherein the calculating is repeated for each sequence, and setting the program order value of non-PO instructions to the calculated program order value of a next PO instruction.