From WikiChip
Difference between revisions of "macro-operation fusion"

(→‎Mechanism)
Line 18: Line 18:
  
 
* Two instructions must be right next to each other, with no other instruction in between
 
* Two instructions must be right next to each other, with no other instruction in between
−
* First instruction must be one of the following: <code>{{x86|CMP}}</code>, <code>{{x86|TEST}}</code>, <code>{{x86|ADD}}</code>, <code>{{x86|SUB}}</code>, <code>{{x86|INC}}</code>, <code>{{x86|DEC}}</code>, or <code>{{x86|AND}}</code>. (Note: prior to {{intel|Nehalem|l=arch}}, this was limited to only CMP/TEST)
+
* First instruction must be one of the following: <code>{{x86|CMP}}</code>, <code>{{x86|TEST}}</code>, <code>{{x86|ADD}}</code>, <code>{{x86|SUB}}</code>, <code>{{x86|INC}}</code>, <code>{{x86|DEC}}</code>, or <code>{{x86|AND}}</code>.
 
* Second instruction must be a conditional jump (e.g., <code>{{x86|JA}}</code>, <code>{{x86|JAE}}</code>, <code>{{x86|JE}}</code>, <code>{{x86|JNE}}</code>)
 
* Second instruction must be a conditional jump (e.g., <code>{{x86|JA}}</code>, <code>{{x86|JAE}}</code>, <code>{{x86|JE}}</code>, <code>{{x86|JNE}}</code>)
 +
* Fusion cannot take place if the first instruction ends on byte 63 of a cache line and the second instruction starts at byte 0 of the next line.
  
−
Note that prior to {{intel|Nehalem|l=arch}} Macro Fusion was restricted to {{x86|x86-32|32-bit mode}} only. It has since been extended to {{x86|x86-64|64-bit mode}} as well.
+
Additionally, only up to 1 macrofusion can take place each cycle. If there it's possible to perform 2 macrofusions, only the first pair will be fused. The second pair will continue unfused.
 +
 
 +
{| class="wikitable tc2 tc3 tc4 tc5 tc6 tc7"
 +
! colspan="8" | Macro-Fusibility
 +
|-
 +
! [[Instruction]] !! {{x86|TEST}} !! {{x86|CMP}} !! {{x86|AND}} !! {{x86|ADD}} !! {{x86|SUB}} !! {{x86|INC}} !! {{x86|DEC}}
 +
|-
 +
| {{x86|JO}}/{{x86|JNO}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘
 +
|-
 +
| {{x86|JC}}/{{x86|JB}}/{{x86|JAE}}/{{x86|JNB}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘
 +
|-
 +
| {{x86|JE}}/{{x86|JZ}}/{{x86|JNE}}/{{x86|JNZ}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔  || style="background-color: #d6ffd8;" | ✔
 +
|-
 +
| {{x86|JNA}}/{{x86|JBE}}/{{x86|JA}}/{{x86|JNBE}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘
 +
|-
 +
| {{x86|JS}}/{{x86|JNS}}/{{x86|JP}}/{{x86|JPE}}/{{x86|JNP}}/{{x86|JPO}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘ || style="background-color: #ffdad6;" | ✘
 +
|-
 +
| {{x86|JL}}/{{x86|JNGE}}/{{x86|JGE}}/{{x86|JNL}}/{{x86|JLE}}/{{x86|JNG}}/{{x86|JG}}/{{x86|JNLE}} || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔ || style="background-color: #d6ffd8;" | ✔
 +
|}
 +
 
 +
=== Prior limitations ===
 +
 
 +
==== Nehalem µarch limitations ====
 +
In {{intel|Nehalem|l=arch}}, Intel introduced a number of enhancements:
 +
 
 +
* <code>{{x86|CMP}}</code> can be fused with: <code>{{x86|JL}}</code>, <code>{{x86|JNGE}}</code>, <code>{{x86|JGE}}</code>, <code>{{x86|JNL}}</code>, <code>{{x86|JLE}}</code>, <code>{{x86|JNG}}</code>, <code>{{x86|JG}}</code>, <code>{{x86|JNLE}}</code>
 +
* Supported on {{x86|x86-64}} mode
 +
 
 +
==== Core µarch limitations ====
 +
The original implementation in the {{intel|Core|l=arch}} microarchitecture was much more limited than in recent processors.
 +
 
 +
* First instruction must be one of the following: <code>{{x86|CMP}}</code> and <code>{{x86|TEST}}</code>
 +
* Macro Fusion is restricted to {{x86|x86-16|16-bit}} and {{x86|x86-32|32-bit mode}} only (including 32-bit compatibility sub-mode in {{x86|x86-64}}).
 +
* <code>{{x86|CMP}}</code> and <code>{{x86|TEST}}</code> can fuse when comparing:
 +
** REG-REG. For example: CMP EAX,ECX; JZ label
 +
** REG-IMM. For example: CMP EAX,0x80; JZ label
 +
** REG-MEM. For example: CMP EAX,[ECX]; JZ label
 +
** MEM-REG. For example: CMP [EAX],ECX; JZ label
 +
* <code>{{x86|CMP}}</code> and <code>{{x86|TEST}}</code> can not be fused when comparing MEM-IMM (e.g. CMP [EAX],0x80; JZ label)
 +
* <code>{{x86|TEST}}</code> can fused with all conditional jumps
 +
* <code>{{x86|CMP}}</code> can only be fused with {{x86|Carry Flag}} ({{x86|CF}}) / {{x86|Zero Flag}} ({{x86|ZF}}) conditional jumps: <code>{{x86|JA}}</code>, <code>{{x86|JNBE}}</code>, <code>{{x86|JAE}}</code>, <code>{{x86|JNB}}</code>, <code>{{x86|JNC}}</code>, <code>{{x86|JE}}</code>, <code>{{x86|JZ}}</code>, <code>{{x86|JNA}}</code>, <code>{{x86|JBE}}</code>, <code>{{x86|JNAE}}</code>, <code>{{x86|JC}}</code>, <code>{{x86|JB}}</code>, <code>{{x86|JNE}}</code>, <code>{{x86|JNZ}}</code>

Revision as of 16:50, 30 April 2017

Not to be confused with micro-operation fusion.

Macro-Operation Fusion (also Macro-Op Fusion, MOP Fusion, or Macrofusion) is a hardware optimization technique found in Intel's x86 microarchitectures whereby a pair of macro-operations are merged into a single macro-operation.

History

The technique for fusing instructions is owned by Intel under Patent US6675376 ("System and method for fusing instructions") originally filed in December 2000. MOP Fusion was first introduced in the Core microarchitecture and has been featured in every Intel microarch since.

Motivation

A fused instruction remains fused throughout its lifetime. Therefore fused instructions can represent more work with less bits, free up execution units, tracking information (e.g. in the rename unit), save pipeline bandwidth in all stages from decode to retire, and consequently save power. Note that this is done before decoding, therefore even decoding bandwidth is save.

Conditional branching are a very common operation in almost all workloads. Macro-op fusion also helps workloads that are not compiled such as in the case of many interpreted programming languages (e.g. PHP, the software running WikiChip). In those programs, conditional branching is seldomly fused as they would by a static compiler.

Mechanism

After the boundaries of macro-ops are found and marked, they are delivered to the instruction queue before being fed to the decoders. At that stage of the pipeline, macro-operation fusion opportunities can be identified and exploited.

A pair of two dependent instructions are first compared against a set of criteria. For example, if the second instruction is commutative (i.e., the order of operands does not affect the result) or if the destination of the operand of the first instruction is used as the source operand of the second instruction than the instruction may qualify for fusion. Additionally either the first source or destination operand must be a register and the second source operand (if one exists) must be an immediate value or a non-RIP-relative memory. Fusion replaces the two instructions with a single instruction representing both operations behaviorally.

Fusion is done on compare flag-modifying instruction (e.g., CMP or ADD) with a subsequent conditional jump instruction. The produced output is a single single compare-and-branch instruction. The final fused instruction remains as such for its remaining lifetime; that is the fused instruction will stay fused throughout the pipeline and execute on a single port in the back-end that can handle both operations.

  • Two instructions must be right next to each other, with no other instruction in between
  • First instruction must be one of the following: CMP, TEST, ADD, SUB, INC, DEC, or AND.
  • Second instruction must be a conditional jump (e.g., JA, JAE, JE, JNE)
  • Fusion cannot take place if the first instruction ends on byte 63 of a cache line and the second instruction starts at byte 0 of the next line.

Additionally, only up to 1 macrofusion can take place each cycle. If there it's possible to perform 2 macrofusions, only the first pair will be fused. The second pair will continue unfused.

Macro-Fusibility
Instruction TEST CMP AND ADD SUB INC DEC
JO/JNO ✔ ✘ ✔ ✘ ✘ ✘ ✘
JC/JB/JAE/JNB ✔ ✔ ✔ ✔ ✔ ✘ ✘
JE/JZ/JNE/JNZ ✔ ✔ ✔ ✔ ✔ ✔ ✔
JNA/JBE/JA/JNBE ✔ ✔ ✔ ✔ ✔ ✘ ✘
JS/JNS/JP/JPE/JNP/JPO ✔ ✘ ✔ ✘ ✘ ✘ ✘
JL/JNGE/JGE/JNL/JLE/JNG/JG/JNLE ✔ ✔ ✔ ✔ ✔ ✔ ✔

Prior limitations

Nehalem µarch limitations

In Nehalem, Intel introduced a number of enhancements:

Core µarch limitations

The original implementation in the Core microarchitecture was much more limited than in recent processors.

  • First instruction must be one of the following: CMP and TEST
  • Macro Fusion is restricted to 16-bit and 32-bit mode only (including 32-bit compatibility sub-mode in x86-64).
  • CMP and TEST can fuse when comparing:
    • REG-REG. For example: CMP EAX,ECX; JZ label
    • REG-IMM. For example: CMP EAX,0x80; JZ label
    • REG-MEM. For example: CMP EAX,[ECX]; JZ label
    • MEM-REG. For example: CMP [EAX],ECX; JZ label
  • CMP and TEST can not be fused when comparing MEM-IMM (e.g. CMP [EAX],0x80; JZ label)
  • TEST can fused with all conditional jumps
  • CMP can only be fused with Carry Flag (CF) / Zero Flag (ZF) conditional jumps: JA, JNBE, JAE, JNB, JNC, JE, JZ, JNA, JBE, JNAE, JC, JB, JNE, JNZ
Retrieved from "https://en.wikichip.org/w/index.php?title=macro-operation_fusion&oldid=42098"