{"id":91181,"date":"2015-08-04T07:00:00","date_gmt":"2015-08-04T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/20150804-00\/?p=91181\/"},"modified":"2019-03-13T12:18:04","modified_gmt":"2019-03-13T19:18:04","slug":"20150804-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20150804-00\/?p=91181","title":{"rendered":"The Itanium processor, part 7: Speculative loads"},"content":{"rendered":"

Today we’ll look at speculative loads, which is when you load a value before you even know whether the value should be loaded. (A related but distinct concept is advanced loading, which we’ll look at next time.) <\/p>\n

Consider the following code: <\/p>\n

\nint32_t SomeClass::calculateSomething(int32_t *a, int32_t *b)\n{\n int32_t result;\n if (m_p > m_q + 1) {\n  result = a[*b];\n } else {\n  result = defaultValue;\n }\n return result;\n}\n<\/pre>\n
The naïve way to compile this function would go something like this: <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        \/\/ calculate complex condition, putting the result in p6\n        \/\/ and the opposite of the result in p7.\n\n        addl    r31 = 08h, r32          \/\/ r31 = &this->m_p\n        addl    r30 = 10h, r32 ;;       \/\/ r30 = &this->m_q\n        ld8     r31 = [r31]             \/\/ r31 = this->m_p\n        ld8     r30 = [r30] ;;          \/\/ r30 = this->m_q\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    ld4     r29 = [r34] ;;          \/\/ if true: load *b\n(p6)    shladd  r29 = r29, 2, r33 ;;    \/\/ if true: calculate &a[*b]\n(p6)    ld4     ret0 = [r29]            \/\/ if true: load a[*b]\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return default value\n        br.ret.sptk.many rp             \/\/ return\n<\/pre>\n
First we decide whether the condition is true or not. Once we know whether the branch is taken, we execute the appropriate branch. If the condition is true, then we load *b<\/code>, then use it to index the array a<\/code>. If the condition is false, then we just set the result to the default value. <\/p>\n
Now, in reality, the encoded instructions aren’t that neat due to template restrictions. For example, we cannot put the first three instructions into a bundle because they consist of two arithmetic instructions, a stop, and a memory instruction, but there is no II|M template. The actual encoding would be more like this: <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        \/\/ calculate complex condition, putting the result in p6\n        \/\/ and the opposite of the result in p7.\n\n{      \/\/ MII| template<\/font>\n        nop.m<\/font>\n        addl    r31 = 08h, r32          \/\/ r31 = &this->m_p\n        addl    r30 = 10h, r32 ;;       \/\/ r30 = &this->m_q\n}\n{       \/\/ MM|I| template (M port can also execute integer operations)<\/font>\n        ld8     r31 = [r31]             \/\/ r31 = this->m_p\n        ld8     r30 = [r30] ;;          \/\/ r30 = this->m_q\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n}\n{       \/\/ M|MI| template<\/font>\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    ld4     r29 = [r34]             \/\/ if true: load *b\n        nop.i ;;<\/font>                        \/\/ move the stop here\n}\n{       \/\/  M|MI template<\/font>\n(p6)    shladd  r29 = r29, 2, r33 ;;    \/\/ if true: calculate &a[*b]\n(p6)    ld4     ret0 = [r29]            \/\/ if true: load a[*b]\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return default value\n}\n{       \/\/ BBB template<\/font>\n        br.ret.sptk.many rp             \/\/ return\n        nop.b\n        nop.b<\/font>\n}<\/font>\n<\/pre>\n
Anyway, let’s go back to the original version. What you might notice is that there is a long dependency chain: <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
addl r31 = 08h, r32<\/td>\n<\/td>\naddl r30 = 10h, r32<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
ld8 r31 = [r31]<\/td>\n<\/td>\nld8 r30 = [r30]<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\naddl r30 = 08h, r30<\/td>\n<\/tr>\n
↓<\/td>\n↙︎<\/td>\n<\/td>\n<\/tr>\n
cmp.gt p6, p7 = r30, r31<\/td>\n<\/td>\n<\/tr>\n
↓<\/td>\n↘︎<\/td>\n<\/td>\n<\/tr>\n
(p7) or ret0 = 2Ah, r0<\/td>\n<\/td>\n(p6) ld4 r29 = [r34]<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
↓<\/td>\n(p6) shladd r29 = r29, 2, r33<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n(p6) ld4 ret0 = [r29]<\/td>\n<\/tr>\n
↓<\/td>\n↙︎<\/td>\n<\/td>\n<\/tr>\n
br.ret.sptk.many rp<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/table>\n
It would be great if we could parallelize more of this computation. For example, we could precalculate the true<\/var> branch: <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        ld4     r29 = [r34]             \/\/ assume true: load *b<\/font>\n        addl    r31 = 08h, r32\n        addl    r30 = 10h, r32 ;;\n        shladd  r29 = r29, 2, r33       \/\/ assume true: calculate &a[*b]<\/font>\n        ld8     r31 = [r31]\n        ld8     r30 = [r30] ;;\n        ld4     r29 = [r29]             \/\/ assume true: load a[*b]<\/font>\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    or      ret0 = r0, r29          \/\/ if true: use the value we precalculated\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return the default value\n        br.ret.sptk.many rp             \/\/ return\n<\/pre>\n
After applying template restrictions, the code looks more like this: <\/p>\n
\n{       \/\/ MII| template\n        ld4     r29 = [r34]             \/\/ assume true: load *b<\/font>\n        addl    r31 = 08h, r32\n        addl    r30 = 10h, r32 ;;\n}\n{       \/\/ MMI| template\n        ld8     r31 = [r31]\n        ld8     r30 = [r30]\n        shladd  r29 = r29, 2, r33 ;;    \/\/ assume true: calculate &a[*b]\n}\n{       \/\/ MI|I| template\n        ld4     r29 = [r29]             \/\/ assume true: load a[*b]<\/font>\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n}\n{       \/\/ MIB template (recalling that the M port can also execute integer instructions)\n(p6)    or      ret0 = r0, r29          \/\/ if true: use the value we precalculated\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return the default value\n        br.ret.sptk.many rp             \/\/ return\n}\n<\/pre>\n
Note that we managed to shrink the code because we were able to use the speculative instructions to “fill in the holes” left by the template-mandated nop<\/code> instructions in the original. We managed to squeeze out all the nop<\/code>s! <\/p>\n
Okay, enough with the template restrictions digressions. <\/p>\n
This alternate version assumes that the complex condition is true and speculatively evaluates the true<\/var> branch. If the test turns out to be true, then it just uses the precalculated result. if it turns out to be false, then the precalculated result is thrown away. <\/p>\n
In other words, we rewrote the code like this: <\/p>\n
\nint32_t SomeClass::calculateSomething(int32_t *a, int32_t *b)\n{\n int32_t speculativeResult = a[*b];\n int32_t result;\n if (m_p > m_q + 1) {\n  result = speculativeResult;\n } else {\n  result = defaultValue;\n }\n return result;\n}\n<\/pre>\n
The dependency chain is now much shorter. <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
addl r31 = 08h, r32<\/td>\n<\/td>\naddl r30 = 10h, r32<\/td>\n<\/td>\nld4 r29 = [r34]<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
ld8 r31 = [r31]<\/td>\n<\/td>\nld8 r30 = [r30]<\/td>\n<\/td>\nshladd r29 = r29, 2, r33<\/td>\n<\/tr>\n<\/tr>\n
↓<\/td>\n<\/td>\n↓<\/td>\n<\/td>\n↓<\/td>\n<\/tr>\n
↓<\/td>\n<\/td>\naddl r30 = 08h, r30<\/td>\n<\/td>\nld4 r29 = [r29]<\/td>\n<\/tr>\n
↓<\/td>\n↙︎<\/td>\n<\/td>\n<\/td>\n↙︎<\/td>\n<\/tr>\n
cmp.gt p6, p7 = r30, r31<\/td>\n<\/td>\n↙︎<\/td>\n<\/tr>\n
↓<\/td>\n↘︎<\/td>\n↙︎<\/td>\n<\/tr>\n
(p7) or ret0 = 2ah, r0<\/td>\n<\/td>\n(p6) or ret0 = r0, r29<\/td>\n<\/tr>\n
↓<\/td>\n↙︎<\/td>\n<\/td>\n<\/tr>\n
br.ret.sptk.many rp<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/table>\n
This rewrite is generally beneficial if profiling feedback suggests that the conditional is normally true, since it hides the memory access latency inside the calculation of the conditional. <\/p>\n
Until somebody does this: <\/p>\n
\n    \/\/ Get the default value. We know that m_p == m_q.\n    p->calculateSomething(nullptr, nullptr);\n<\/pre>\n
In this case, the speculative execution will take an access violation because it tries to deference the null pointer as part of calculating the speculative result. <\/p>\n
Well, that sucks. <\/p>\n
To solve this problem, the Itanium lets you explicitly tag memory read operations as speculative. If you try to load a value speculatively, the instruction will read the value if possible, but if doing so would normally raise an exception, the processor says, “Sorry, I couldn’t read it. But since this is part of speculative execution, I shouldn’t raise an exception. Instead, I will set the NaT bit on the value so that you will know that the speculative load failed.” <\/p>\n
The NaT bit (short for Not a Thing<\/i>) is a 65th bit associated with each 64-bit general-purpose integer register that says whether the register holds a valid value. (Floating point registers do not have a NaT bit; instead there is a special value called NaTVal which serves the same purpose.) Arithmetic operations on NaT simply result in another NaT, but if you try to do something interesting with a NaT, you incur a STATUS_REG_NAT_CONSUMPTION<\/code> exception<\/a>. <\/p>\n
So let’s take advantage of explicit speculative execution: <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        ld4.s   r29 = [r34]             \/\/ speculatively load *b<\/font>\n        addl    r31 = 08h, r32\n        addl    r30 = 10h, r32 ;;\n        ld8     r31 = [r31]\n        ld8     r30 = [r30]\n        shladd  r29 = r29, 2, r33 ;;    \/\/ speculatively calculate &a[*b]\n        ld4.s   r29 = [r29]             \/\/ speculatively load a[*b]<\/font>\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    or      ret0 = r0, r29          \/\/ if true: use the value we precalculated\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return the default value\n        br.ret.sptk.many rp             \/\/ return\n<\/pre>\n
We changed the two load operations from ld4<\/code> to ld4.s<\/code>. The trailing .s<\/code> means that the load is being performed speculatively, and that if an error occurs or if the address is itself NaT, then set the result to NaT rather than raising an exception. <\/p>\n
Okay, so this prevents the exception from being raised during the speculative execution, but what if an exception really occurred? How do we turn the NaT back into the original exception? As written, we return NaT back to our caller, which is definitely not what the caller expects! <\/p>\n
You might put on your language lawyer hat at this point and say that dereferencing a null pointer invokes undefined behavior<\/i>, so returning NaT is standard-conforming (because undefined behavior allows anything<\/i> to be standard-conforming). That’s true, if the exception was due to an access violation. But the exception might have been a page not present<\/i> exception because the memory was paged out. In that case, we really do want to raise the exception so that the kernel can handle it by paging the memory back in, and then we want to read the value and resume our calculations. The caller definitely does not expect that passing valid parameters will result in a NaT just because the memory happens to be paged out. <\/p>\n
What we need to do is convert the deferred exception back into the original exception so that it can be raised as if no speculation had occurred. The instruction that lets us know that an exception got converted to a NaT is chk.s<\/code>. This means “Check if the register contains NaT. If so, then jump to recovery code.” The recovery code re-executes the instructions non-speculatively so that all the exceptions can be raised in the standard way, and any exception handlers can do their work in the standard way. Since NaT infects future computations, we don’t need to check every speculative step; we need only check the final speculated result. <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        ld4.s   r29 = [r34]             \/\/ speculatively load *b\n        addl    r31 = 08h, r32\n        addl    r30 = 10h, r32 ;;\n        ld8     r31 = [r31]\n        ld8     r30 = [r30]\n        shladd  r29 = r29, 2, r33 ;;    \/\/ speculatively calculate &a[*b]\n        ld4.s   r29 = [r29]             \/\/ speculatively load a[*b]\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    chk.s   r29, recovery           \/\/ if true: recover r29 if not valid\nrecovered:<\/font>\n(p6)    or      ret0 = r0, r29          \/\/ if true: use the value we precalculated\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return the default value\n        br.ret.sptk.many rp             \/\/ return\n\nrecovery:\n        ld4     r29 = [r34] ;;          \/\/ load *b\n        shladd  r29 = r29, 2, r33 ;;    \/\/ calculate &a[*b]\n        ld4     r29 = [r29]             \/\/ load a[*b]\n        br      recovered               \/\/ resume with recovered value<\/font>\n<\/pre>\n
The chk.s<\/code> instruction checks the specified register to see if the NaT bit is set. If not, the instruction allows execution to continue normally. But if the register is invalid, then control transfers to the specified label. Our recovery code re-executes the instructions that led to the invalid value, but this time we execute them non-speculatively so that exceptions can be raised and handled. Once the value has been recovered, we jump back to the instruction after the chk.s<\/code> so that normal execution can resume. <\/p>\n
In this case, we can make an additional optimization. Since the only things happening after recovery are copying r29<\/code> to ret0<\/code> and returning, we can inline those two instructions then perform peephole optimization to combine the ld4 r29 = [r29]<\/code> and or ret0 = r0, r29<\/code> into ld4 ret0 = [r29]<\/code>. <\/p>\n
Note that optimizing the recovery code is not really that important from an execution speed standpoint, since the recovery code runs only if an exception occurred, and the cost of raising and handling the exception will drown out any cycle squeezing effects. The real benefit of optimizing the recovery code is to avoid the jump back into the mainline code, because that allows the mainline code to be more compact: Recall that all jump targets must be the start of a bundle. If we had the recovery code jump back to the mainline code, we would have to insert some nop<\/code>s so that the recovered<\/code> label is at the start of a bundle. (In practice, what the compiler will do is repeat the trailing instructions in the bundle containing the chk.s<\/code> then jump to the start of the next bundle.) <\/p>\n
The final compiled function now looks like this: <\/p>\n
\n        \/\/ we are a leaf function, so no need to use \"alloc\" or to save rp.\n        \/\/ on entry: r32 = this, r33 = a, r34 = b\n\n        ld4.s   r29 = [r34]             \/\/ speculatively load *b\n        addl    r31 = 08h, r32\n        addl    r30 = 10h, r32 ;;\n        ld8     r31 = [r31]\n        ld8     r30 = [r30]\n        shladd  r29 = r29, 2, r33 ;;    \/\/ speculatively calculate &a[*b]\n        ld4.s   r29 = [r29]             \/\/ speculatively load a[*b]\n        addl    r30 = 08h, r30 ;;       \/\/ r30 = this->m_q + 1\n        cmp.gt  p6, p7 = r30, r31 ;;    \/\/ p6 = m_p > m_q + 1; p7 = !p6\n\n        \/\/ Now take action based on the result.\n\n(p6)    chk.s   r29, recovery           \/\/ if true: recover r29 if not valid\n(p6)    or      ret0 = r0, r29          \/\/ if true: use the value we precalculated\n(p7)    or      ret0 = 2ah, r0          \/\/ if false: return the default value\n        br.ret.sptk.many rp             \/\/ return\n\nrecovery:\n        ld4     r29 = [r34] ;;          \/\/ load *b\n        shladd  r29 = r29, 2, r33 ;;    \/\/ calculate &a[*b]\n        ld4     ret0 = [r29]            \/\/ load a[*b] as return value\n        br.ret.sptk.many rp             \/\/ return<\/font>\n<\/pre>\n
Next time, we’ll look at advanced loading, which is a different type of speculative execution. <\/p>\n","protected":false},"excerpt":{"rendered":"
I knew you were going to say that.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-91181","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"
I knew you were going to say that.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91181","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=91181"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91181\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=91181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=91181"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=91181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}