Latency hiding of traces using block coloring

A program transformer in a compiler for a program module for multiple processing threads comprising:

• a memory to store a program module and colors form blocks of instructions within the program module;
• and
• a processor to implement:
• a color assignor to associate blocks of instructions between start and end of a mutually exclusive critical section with color information, the blocks corresponding to a program trace and containing a wait instruction associated with access to the memory, and to associate the wait instructions with a wait color, wherein the wait color information is not related to the color information;
• a code mover and compensator coupled to the color assignor to sink the wait instruction down the blocks globally across the blocks to the end of the critical section using the color information, the wait color information, and a dependence constraint on the wait instruction;
• and
• an enhanced program module to receive the enhanced program module with the sunk wait instruction.

A system comprising:

• a network processor;
• a host processor coupled to the network processor;
• and
• a memory coupled to the host processor having a program transformer of a compiler to transform a program module to be executed on multiple threads of the network processor, the program transformer comprising:
• a color assignor to associate blocks of instructions between start and end of a mutually exclusive critical section with color information, the blocks corresponding to a program trace and containing a wait instruction associated with access to the memory, and to associate the wait instruction with a wait color, wherein the wait color information is not related to the color information;
• a code mover and compensator coupled to the color assignor to sink the wait instruction down the blocks globally across the blocks to the end of the critical section using the color information, the wait color information, and a dependence constraint on the wait instruction;
• and
• an enhanced program module to receive the enhanced program module with the sunk wait instruction.

An article of manufacture comprising:

• a machine-accessible non-transitory storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising:
• receiving a program module for multiple processing threads;
• identifying blocks of instructions in the received program module;
• identifying critical sections of the program module;
• associating blocks of instructions between a start and an end of a mutually exclusive critical section with color information, the blocks corresponding to a program trace and containing a wait instruction associated with a memory access;
• associating the wait instruction with wait color information, wherein the wait color information is not related to the color information;
• sinking the wait instruction down the blocks globally across the blocks to the end of the critical section using the color information, the wait color information, and a dependence constraint on the wait instruction;
• and
• outputting an enhanced program module with the sunk wait instruction.