{"id":99495,"date":"2018-08-15T07:00:00","date_gmt":"2018-08-15T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=99495"},"modified":"2019-03-13T00:38:22","modified_gmt":"2019-03-13T07:38:22","slug":"20180815-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20180815-00\/?p=99495","title":{"rendered":"The PowerPC 600 series, part 8: Control transfer"},"content":{"rendered":"

The PowerPC 600 series has a few types of control transfer instructions. Let’s look at direct branches first. <\/p>\n

\n    b       target          ; branch to target\n    bl      target          ; branch to target and link\n<\/pre>\n
The direct branch instructions perform an unconditional relative branch to the target. It has a reach of ±32MB<\/a>. All the “… and link” instructions  set the lr<\/var> register to the return address (the instruction after the branch). This happens even for conditional branches when the branch is not taken. <\/p>\n
There are also absolute versions of these instructions: <\/p>\n
\n    ba      target          ; branch to target (absolute form)\n    bla     target          ; branch to target and link (absolute form)\n<\/pre>\n
The absolute versions treat the displacement as an absolute address rather than as a displacement from the current instruction pointer. These are not useful in Windows NT, but could be useful in embedded systems. <\/p>\n
Things get exciting when you look at the conditional branches. Formally, they are written as <\/p>\n
\n    bc      BO, BI, target  ; branch conditional\n    bcl     BO, BI, target  ; branch conditional and link\n<\/pre>\n
Conditional branch instructions have a reach of only ±32KB<\/a>. There are also absolute variants bca<\/code> and bcla<\/code> which treat the displacement as an absolute address, allowing conditional branches to the top and bottom 32KB of address space. Again, absolute addressing is not that useful in Windows NT. <\/p>\n
The magical BO<\/var> and BI<\/var> parameters describe the condition to be tested. You can optionally decrement the ctr<\/var> register and check if the result is zero or nonzero.¹ You can also optionally check if a specific bit in the cr<\/var> register is set (true) or clear (false), and sometimes you can provide a static prediction hint. The following combinations are valid: <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Decrement ctr<\/var>?<\/th>\nTest a bit in cr<\/var>?<\/th>\nPrediction hint<\/th>\nBO<\/var><\/th>\nMnemonic<\/th>\n<\/tr>\n
Yes, test for nonzero<\/td>\nNo<\/td>\n<\/td>\n16<\/td>\ndnz<\/code><\/td>\n<\/tr>\n
Yes, test for nonzero<\/td>\nNo<\/td>\nNot taken<\/td>\n24<\/td>\ndnz-<\/code><\/td>\n<\/tr>\n
Yes, test for nonzero<\/td>\nNo<\/td>\nTaken<\/td>\n25<\/td>\ndnz+<\/code><\/td>\n<\/tr>\n
Yes, test for nonzero<\/td>\nTest for false<\/td>\n<\/td>\n0<\/td>\ndnzf<\/code><\/td>\n<\/tr>\n
Yes, test for nonzero<\/td>\nTest for true<\/td>\n<\/td>\n8<\/td>\ndnzt<\/code><\/td>\n<\/tr>\n
Yes, test for zero<\/td>\nNo<\/td>\n<\/td>\n18<\/td>\ndz<\/code><\/td>\n<\/tr>\n
Yes, test for zero<\/td>\nNo<\/td>\nNot taken<\/td>\n26<\/td>\ndz-<\/code><\/td>\n<\/tr>\n
Yes, test for zero<\/td>\nNo<\/td>\nTaken<\/td>\n27<\/td>\ndz+<\/code><\/td>\n<\/tr>\n
Yes, test for zero<\/td>\nTest for true<\/td>\n<\/td>\n10<\/td>\ndzt<\/code><\/td>\n<\/tr>\n
Yes, test for zero<\/td>\nTest for false<\/td>\n<\/td>\n2<\/td>\ndzf<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for false<\/td>\n<\/td>\n4<\/td>\nf<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for false<\/td>\nNot taken<\/td>\n6<\/td>\nf-<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for false<\/td>\nTaken<\/td>\n7<\/td>\nf+<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for true<\/td>\n<\/td>\n12<\/td>\nt<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for true<\/td>\nNot taken<\/td>\n14<\/td>\nt-<\/code><\/td>\n<\/tr>\n
No<\/td>\nTest for true<\/td>\nTaken<\/td>\n15<\/td>\nt+<\/code><\/td>\n<\/tr>\n
Unconditional<\/td>\nTaken<\/td>\n20<\/td>\n<\/td>\n<\/tr>\n<\/table>\n
Any BO<\/var> values not in the above table are reserved for future use and should be avoided if you know what’s good for you. <\/p>\n
A static prediction hint overrides any internal branch prediction algorithm, so you’d better have very high confidence that your hint is correct. <\/p>\n
These mnemonics save you from having to memorize the BO<\/var> numbers. <\/p>\n
\n    bxx<\/u>     BI, target  ; branch conditional\n    bxx<\/u>l    BI, target  ; branch conditional and link\n<\/pre>\n
Except that if the mnemonic ends in a +<\/code> or -<\/code>, then the prediction hint goes at the very end. For example, “branch if false and link, predict not taken” is bfl-<\/code>. <\/p>\n
The bit index BI<\/var> can be written as a number, but as we saw when we learned about condition registers, you can combine the condition register bit mnemonics with with the cr#<\/var> mnemonics to produce a reference to a condition bit. For example, 4*cr2+gt<\/code> means “The gt<\/var> bit in the cr2<\/var> condition register.” And since the numeric value of cr0<\/var> is zero, you can omit 4*cr0+<\/code>, which results in some surprisingly readable results like <\/p>\n
\n    bt       eq, target  ; branch if eq is set in cr0\n<\/pre>\n
The assembler goes one step further and provides a few combination mnemonics:² <\/p>\n\n\n\n\n\n\n\n\n\n\n
Branch and condition<\/th>\nMnemonic<\/th>\nMeaning<\/th>\n<\/tr>\n
bt lt<\/code><\/td>\nblt<\/code><\/td>\nBranch if less than<\/td>\n<\/tr>\n
bt gt<\/code><\/td>\nbgt<\/code><\/td>\nBranch if greater than<\/td>\n<\/tr>\n
bt eq<\/code><\/td>\nbeq<\/code><\/td>\nBranch if equal<\/td>\n<\/tr>\n
bt so<\/code><\/td>\nbso<\/code><\/td>\nBranch if summary overflow<\/td>\n<\/tr>\n
bf lt<\/code><\/td>\nbnl<\/code><\/td>\nBranch if not less than<\/td>\n<\/tr>\n
bf gt<\/code><\/td>\nbng<\/code><\/td>\nBranch if not greater than<\/td>\n<\/tr>\n
bf eq<\/code><\/td>\nbne<\/code><\/td>\nBranch if not equal<\/td>\n<\/tr>\n
bf so<\/code><\/td>\nbns<\/code><\/td>\nBranch if not summary overflow<\/td>\n<\/tr>\n<\/table>\n
The mnemonics can separate the condition bit from the condition register, so you can get <\/p>\n
\n    beq      cr4, target  ; branch if eq is set in cr4\n<\/pre>\n
Okay, the next type of branch instruction is the computed jump. <\/p>\n
 \n    bcctr    BO, BI, BH   ; branch conditional to address in ctr\n    bcctrl   BO, BI, BH   ; branch conditional to address in ctr and link\n\n    bclr     BO, BI, BH   ; branch conditional to address in lr\n    bclrl    BO, BI, BH   ; branch conditional to address in lr and link\n<\/pre>\n
You are not allowed to use any of the “decrement ctr<\/var>” branch operations with the bcctr<\/code> or bcctrl<\/code> instructions because shame on you for even thinking about trying it. <\/p>\n
The BO<\/var> and BI<\/var> codes follow the same rules as above, and the assembler provides mnemonics for various combinations. If you go to PowerPC reference materials, you’ll see horrid tables<\/a> that look like some sort of dystopian declension table from a long-forgotten Slavic language. In this hypothetical language, bdnztlrl<\/code> means something like “branch on odd-numbered Thursdays,” I guess. (Okay, it actually means “b<\/u>ranch, after d<\/u>ecrementing ctr<\/code>, if the result is n<\/u>onz<\/u>ero, and if the condition bit is t<\/u>rue, to the address in the lr<\/u><\/code> register, and l<\/u>ink.”) <\/p>\n
The BH<\/var> field provides a hint for branch prediction, primarily whether the branch target is likely to be the same as the previous time the branch was encountered. Branches through an import table are likely to be the same each time. Branches through a vtable could also use this hint if the method is being dispatched from the same object in a loop. (The vtable is unlikely to change during the loop.) <\/p>\n
The processor optimizes on the assumption that bctr<\/code> is a computed jump and blr<\/code> is a subroutine return,³ although the BH<\/var> hints can tweak those assumptions. Furthermore, Windows NT requires<\/i> that non-leaf subroutine returns be encoded exclusively as blr<\/code>. You are not allowed to pull fancy tricks like beqlr<\/code> to perform a conditional subroutine return. This is not a significant problem in practice because there’s usually other stuff that needs to be done as part of the function epilogue. Adding this rule makes the exception unwinding code easier. <\/p>\n
For the same reason, the conditional versions of the “and link” branches are mostly useless in practice because even if you can conditionalize the link, you still prepared the function call unconditionally. You might have been better off just branching over the function call entirely. <\/p>\n
Okay, so great, you have these instructions that operate on the lr<\/var> and ctr<\/var> registers, but how do you actually get values in and out of them? <\/p>\n
\n    mflr    rt           ; rt = lr\n    mfctr   rt           ; rt = ctr\n\n    mtlr    rs           ; lr = rs\n    mtctr   rs           ; ctr = rs\n<\/pre>\n
The “move from\/to lr<\/var>\/ctr<\/var>” instructions let you move values into and out of the lr<\/var> and ctr<\/var> registers. (Like mfxer<\/code> and mtxer<\/code>, these are actually shorthand for mfspr<\/code> and mtspr<\/code> with the appropriate magic number for lr<\/var> or ctr<\/var>.) <\/p>\n
In practice, the first instruction of a non-leaf function is mflr r0<\/code> to save the return address, and when it’s ready to return, it will do a mtlr r0<\/code> to load up the return address in preparation for the blr<\/code>. This is pretty much the only thing the Microsoft compiler uses the r0<\/var> register for: Transferring the return address in and out of lr<\/var>. <\/p>\n
But wait, I’m getting ahead of myself. I promised to talk about the table of contents, so let’s do that next time<\/a>. <\/p>\n
Bonus chatter<\/b>: PowerPC mnemonics are so absurd that there was even a short-lived parody twitter account for them<\/a>. Now that you’ve learned most of the instructions, you may understand some of the more insidey jokes, like <\/p>\n
\n
mscdfr – Means Something Completely Different For r0<\/p>\n
— PowerPC Instructions (@ppcinstructions) January 21, 2015<\/a><\/p><\/blockquote>\n
¹ Note that even if you loaded a 64-bit value into the ctr<\/var> register (because you detected that you had a 64-bit-capable processor), the test for zero or non-zero is performed only against the least-significant 32 bits of the ctr<\/var> register when the processor is in 32-bit mode (which is what Windows NT uses). <\/p>\n
² The assembler also provides bge<\/code> (branch if greater than or equal to) as an alias for bnl<\/code> (branch if not less than). I think that’s misleading, because bge<\/code> suggests that the test checks two bits (gt<\/var> and eq<\/var>) and branches if either is set. But in fact it checks whether lt<\/var> is clear. Now, if the condition register was set by a comparison, then the two cases are equivalent, but if you have been playing games with condition register flags, you can get into states where the trichotomy of numbers breaks down. <\/p>\n
³ The return address predictor gives the processor the ability to start speculating instructions at the return address even before you move the return address into the lr<\/var> register! <\/p>\n","protected":false},"excerpt":{"rendered":"
Jump around.<\/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":[2],"class_list":["post-99495","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-history"],"acf":[],"blog_post_summary":"
Jump around.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/99495","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=99495"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/99495\/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=99495"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=99495"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=99495"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}