Trace optimization via fusing operations of a target architecture operation set
View Patent ↗Reference architecture instructions are translated into target architecture operations. Sequences of operations, in a predicted execution order in some embodiments, form traces. In some embodiments, a trace is based on a plurality of basic blocks. In some embodiments, a trace is committed or aborted as a single entity. Sequences of operations are optimized by fusing collections of operations; fused operations specify a same observable function as respective collections, but advantageously enable more efficient processing. In some embodiments, a collection comprises multiple register operations. Fusing a register operation with a branch operation in a trace forms a fused reg-op/branch operation. In some embodiments, branch instructions translate into assert operations. Fusing an assert operation with another operation forms a fused assert operation. In some embodiments, fused operations only set architectural state, such as high-order portions of registers, that is subsequently read before being written.
1. A method comprising:
obtaining an instruction image comprising a plurality of basic blocks (BBs), wherein each of the plurality of BBs ends with one of a plurality of branch instructions;
generating a first trace for a target architecture by translating a first instruction of a first BB, a second instruction of the first BB, and a branch instruction ending the first BB into a first operation, a second operation, and an assertion operation, respectively, compatible with the target architecture, wherein the second instruction is predicted to execute prior to the branch instruction;
searching, within a search window having a span excluding the assertion operation, a plurality of operations including the first operation and the second operation for operations to pair;
moving the search window to include the assertion operation within the span of the search window;
identifying, after moving the search window, the first operation and the assertion operation as a pair within the search window; and
fusing the first operation with the assertion operation to create a first fused operation, wherein the first fused operation is predicted to be executed prior to the second operation,
wherein identifying the pair comprises:
determining a first portion and a second portion within a register written to by the first instruction,
wherein the second instruction writes the second portion of the register, and
wherein the branch instruction reads the first portion of the register to evaluate a condition of the branch instruction.
2. The method of claim 1 , wherein identifying the pair comprises:
determining a flag set by the first instruction and consumed as a condition in the branch instruction, wherein the first fused operation passes the flag from part of the first fused operation corresponding to the first operation as a part of the first fused operation corresponding to the assert operation, and wherein the second instruction executes independently of the flag.
3. The method of claim 1 , further comprising enlarging the search window.
4. The method of claim 1 , further comprising:
translating a third instruction of the first BB into a third operation compatible with the target architecture;
identifying, within the search window, the second operation and the third operation for pairing; and
fusing the second operation with the third operation to create a second fused operation,
wherein the first trace includes the second fused operation.
5. The method of claim 1 , further comprising:
generating a second trace for a target architecture by translating a first instruction of a second BB and a branch instruction ending the second BB into a third operation, and a second assertion operation, respectively, compatible with the target architecture.
6. The method of claim 5 , wherein the second trace is predicted to execute before the first trace.
7. The method of claim 1 , wherein the assertion operation aborts the first trace.
8. The method of claim 1 , wherein predicted execution order adheres to the dependencies within the instruction image.
9. A system comprising:
an instruction image comprising a plurality of basic blocks (BBs), wherein each of the plurality of BBs ends with one of a plurality of branch instructions compatible with a reference architecture;
a translating agent configured to translate a first instruction of a first BB, a second instruction of the first BB, and a branch instruction ending the first BB into a first operation, a second operation, and an assertion operation, respectively, compatible with the target architecture, wherein the second instruction is predicted to execute prior to the branch instruction;
a trace-building unit configured to generate a first trace by:
searching, within the search window having a span excluding the assertion operation, a plurality of operations including the first operation and the second operation for operations to pair;
moving the search window to include the assertion operation within the span of the search window; and
identifying, after moving the search window, the first operation and the assertion operation as a pair within the search window; and
a fusing agent configured to fuse the first operation with the assertion operation to create a first fused operation, wherein the first fused operation is predicted to be executed prior to the second operation,
wherein the pair comprises:
a register having a first portion and a second portion written to by the first instruction,
wherein the second instruction writes the second portion of the register, and
wherein the branch instruction reads the first portion of the register to evaluate a condition of the branch instruction.
10. The system of claim 9 , wherein the pair comprises:
a flag set by the first instruction and consumed as a condition in the branch instruction, wherein the first fused operation passes the flag from part of the first fused operation corresponding to the first operation the a part of the first fused operation corresponding to the assert operation, and wherein the second instruction executes independently of the flag.
11. The system of claim 9 , wherein the pair comprises:
a register having a first portion and a second portion written to by the first instruction,
wherein the second instruction writes the second portion of the register, and
wherein the branch instruction reads the first portion of the register to evaluate a condition of the branch instruction.
12. The system of claim 9 , further comprising:
wherein the translating agent is further configured to:
translate a third instruction of the first BB into a third operation compatible with the target architecture; and
identify, within the search window, the second operation and the third operation for pairing,
wherein the fusing agent is further configured to:
fuse the second operation with the third operation to create a second fused operation,
wherein the first trace includes the second fused operation.
13. The system of claim 9 , further comprising:
wherein the trace-building agent is further configured to:
generate a second trace for a target architecture by translating a first instruction of a second BB and a branch instruction ending the second BB into a third operation, and a second assertion operation, respectively, compatible with the target architecture.
14. The system of claim 13 , wherein the second trace is predicted to execute before the first trace.
15. The system of claim 9 , wherein the assertion operation aborts the first trace.
16. The system of claim 9 , wherein predicted execution order adheres to the dependencies within the instruction image.