{"id":91191,"date":"2015-08-03T07:00:00","date_gmt":"2015-08-03T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/20150803-00\/?p=91191\/"},"modified":"2019-03-13T12:18:01","modified_gmt":"2019-03-13T19:18:01","slug":"20150803-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20150803-00\/?p=91191","title":{"rendered":"The Itanium processor, part 6: Calculating conditionals"},"content":{"rendered":"<p>The Itanium does not have a flags register. A flags register creates implicit dependencies between instructions, which runs contrary to the highly parallel model the Itanium was designed for. Instead of implicitly setting a register after computations, the Itanium has explicit comparison operations that put the comparison result into dedicated predicate registers. <\/p>\n<p>Here&#8217;s a simple fragment that performs some operation if two registers are equal. <\/p>\n<pre>\n        cmp.eq p6, p7 = r32, r33 ;;\n(p6)    something\n<\/pre>\n<p>The <var>cmp<\/var> instruction compares two values and sets the two specified predicate registers as follows: <\/p>\n<ul>\n<li><var>p6<\/var> is <var>true<\/var> if the     values satisfy the condition, or <var>false<\/var>     if they do not satisfy the condition. \n<li><var>p7<\/var> is set to the opposite of <var>p6<\/var> <\/ul>\n<p>The comparison operation generates two results, one which holds the nominal result and one which holds the opposite. This lets you conditionalize both sides of a branch. <\/p>\n<pre>\n        cmp.eq p6, p7 = r32, r33 ;;\n(p6)    something \/\/ executes if they are equal\n(p7)    something \/\/ executes if they are not equal\n<\/pre>\n<p>There is also a <var>cmp4<\/var> instruction which compares two 32-bit values, in which case only the least-significant 32 bits participate in the comparison. <\/p>\n<p>The comparands can be either two registers or an immediate and a register. The immediate is an 8-bit sign-extended value, though the final value may be interpreted as unsigned depending on the comparison type. <\/p>\n<p>There are three comparison types: <\/p>\n<table CLASS=\"cp3\" BORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"3\" STYLE=\"border-collapse: collapse\">\n<tr>\n<th>type<\/th>\n<th>meaning<\/th>\n<\/tr>\n<tr>\n<td>eq<\/td>\n<td>equality<\/td>\n<\/tr>\n<tr>\n<td>lt<\/td>\n<td>signed less than<\/td>\n<\/tr>\n<tr>\n<td>ltu<\/td>\n<td>unsigned less than<\/td>\n<\/tr>\n<\/table>\n<p>The first destination predicate register receives result of the test, and the second gets the opposite of the result. <\/p>\n<p>These are the only comparisons you will see in disassembly, but the compiler can manufacture other types of comparisons. For example, if the compiler wants to perform a <var>ge<\/var> comparison, it can just do a <var>lt<\/var> comparison and flip the order of the two predicates. <\/p>\n<p>More generally, the compiler can synthesize the other integer comparisons as follows: <\/p>\n<table CLASS=\"cp3\" BORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"3\" STYLE=\"border-collapse: collapse\">\n<tr>\n<th>imaginary opcode<\/th>\n<th>meaning<\/th>\n<th COLSPAN=\"2\">synthesized as<\/th>\n<\/tr>\n<tr>\n<td><var>cmp.ne p, q = a, b<\/var><\/td>\n<td>not equal<\/td>\n<td COLSPAN=\"2\"><var>cmp.eq q, p = a, b<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.ge p, q = a, b<\/var><\/td>\n<td>signed greater than or equal<\/td>\n<td COLSPAN=\"2\"><var>cmp.lt q, p = a, b<\/var><\/td>\n<\/tr>\n<tr>\n<td ROWSPAN=\"2\"><var>cmp.gt p, q = a, b<\/var><\/td>\n<td ROWSPAN=\"2\">signed greater than<\/td>\n<td><var>cmp.lt p, q = b, a<\/var><\/td>\n<td>if <var>a<\/var> is a register<\/td>\n<\/tr>\n<tr>\n<td><var>cmp.lt q, p = a &minus; 1, b<\/var><\/td>\n<td>if <var>a<\/var> is an immediate<\/td>\n<\/tr>\n<tr>\n<td ROWSPAN=\"2\"><var>cmp.le p, q = a, b<\/var><\/td>\n<td ROWSPAN=\"2\">signed less than or equal<\/td>\n<td><var>cmp.lt q, p = b, a<\/var><\/td>\n<td>if <var>a<\/var> is a register<\/td>\n<\/tr>\n<tr>\n<td><var>cmp.lt p, q = a &minus; 1, b<\/var><\/td>\n<td>if <var>a<\/var> is an immediate<\/td>\n<\/tr>\n<tr>\n<td><var>cmp.geu p, q = a, b<\/var><\/td>\n<td>unsigned greater than or equal<\/td>\n<td COLSPAN=\"2\"><var>cmp.ltu q, p = a, b<\/var><\/td>\n<\/tr>\n<tr>\n<td ROWSPAN=\"2\"><var>cmp.gtu p, q = a, b<\/var><\/td>\n<td ROWSPAN=\"2\">unsigned greater than<\/td>\n<td><var>cmp.ltu p, q = b, a<\/var><\/td>\n<td>if <var>a<\/var> is a register<\/td>\n<\/tr>\n<tr>\n<td><var>cmp.ltu q, p = a &minus; 1, b<\/var><\/td>\n<td>if <var>a<\/var> is an immediate<\/td>\n<\/tr>\n<tr>\n<td ROWSPAN=\"2\"><var>cmp.leu p, q = a, b<\/var><\/td>\n<td ROWSPAN=\"2\">unsigned less than or equal<\/td>\n<td><var>cmp.ltu q, p = b, a<\/var><\/td>\n<td>if <var>a<\/var> is a register<\/td>\n<\/tr>\n<tr>\n<td><var>cmp.ltu p, q = a &minus; 1, b<\/var><\/td>\n<td>if <var>a<\/var> is an immediate<\/td>\n<\/tr>\n<\/table>\n<p>These syntheses rely on the identities <\/p>\n<table CLASS=\"cp3\" BORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"3\" STYLE=\"border-collapse: collapse\">\n<tr>\n<td><var>x<\/var> &gt; <var>y<\/var><\/td>\n<td>&nbsp;&hArr;&nbsp;<\/td>\n<td><var>y<\/var> &lt; <var>x<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>x<\/var> &le; <var>y<\/var><\/td>\n<td>&nbsp;&hArr;&nbsp;<\/td>\n<td>&not;(<var>x<\/var> &gt; <var>y<\/var>)<\/td>\n<\/tr>\n<tr>\n<td><var>x<\/var> &le; <var>y<\/var><\/td>\n<td>&nbsp;&hArr;&nbsp;<\/td>\n<td><var>x<\/var> &minus; 1 &lt; <var>y<\/var><\/td>\n<td>for integers <var>x<\/var> and <var>y<\/var>, assuming no overflow<\/td>\n<\/tr>\n<tr>\n<td><var>x<\/var> &ge; <var>y<\/var><\/td>\n<td>&nbsp;&hArr;&nbsp;<\/td>\n<td><var>y<\/var> &le; <var>x<\/var><\/td>\n<\/tr>\n<\/table>\n<p>The next level of complexity is the parallel comparisons. These perform a comparison and combine the result with the values already in the destination predicates. <\/p>\n<table CLASS=\"cp3\" BORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"3\" STYLE=\"border-collapse: collapse\">\n<tr>\n<th>opcode<\/th>\n<th>meaning<\/th>\n<th>really<\/th>\n<\/tr>\n<tr>\n<td><var>cmp.xx.or p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> || (<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> || (<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if (<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>q<\/var> = <var>true<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.xx.orcm p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> || &not;(<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> || &not;(<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if &not;(<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>q<\/var> = <var>true<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.xx.and p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> &amp;&amp; (<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> &amp;&amp; (<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if &not;(<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>q<\/var> = <var>false<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.xx.andcm p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> &amp;&amp; &not;(<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> &amp;&amp; &not;(<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if (<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>q<\/var> = <var>false<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.xx.or.andcm p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> || (<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> &amp;&amp; &not;(<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if (<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>true<\/var>,         <var>q<\/var> = <var>false<\/var><\/td>\n<\/tr>\n<tr>\n<td><var>cmp.xx.and.orcm p, q = a, b<\/var><\/td>\n<td><var>p<\/var> = <var>p<\/var> &amp;&amp; (<var>a<\/var> xx <var>b<\/var>)<br>        <var>q<\/var> = <var>q<\/var> || &not;(<var>a<\/var> xx <var>b<\/var>)<\/td>\n<td>if &not;(<var>a<\/var> xx <var>b<\/var>) then         <var>p<\/var> = <var>false<\/var>,         <var>q<\/var> = <var>true<\/var><\/td>\n<\/tr>\n<\/table>\n<p>The <i>meaning<\/i> column describes how it is convenient to think of the operations, but the <i>really<\/i> column describes how they actually work. <\/p>\n<p>The <code>orcm<\/code> and <code>andcm<\/code> versions take the complement of the comparison, which is handy because some of the synthesized comparisons involve taking the opposite of the specified result. <\/p>\n<p>These parallel comparisons get their name because they are designed to have multiple copies executed in parallel. Consequently, they are an exception to the general rule that you can write to a register only once per instruction group. If all writes to a predicate register are AND-like (i.e., <code>and<\/code> or <code>andcm<\/code>) or all writes are OR-like (i.e., <code>or<\/code> or <code>orcm<\/code>), then the writes are allowed to coexist within a single instruction group. (This is where the <i>actually<\/i> column comes in handy. You can see that all AND-like operations either do nothing or set the predicate to <var>false<\/var>, and that all OR-like operations either do nothing or set the predicate to <var>true<\/var>. That&#8217;s why they can run in parallel: If multiple conditions pass, they all do the same thing, so it doesn&#8217;t matter which one goes first.) <\/p>\n<p>Executing them in parallel lets you perform multiple tests in a single cycle. For example: <\/p>\n<pre>\n x =  ... calculate x ...;\n y =  ... calculate y ...;\n z =  ... calculate z ...;\n if (x == 0 || y == 0 || z == 0) {\n   something_is_zero;\n } else {\n   all_are_nonzero;\n }\n<\/pre>\n<p>could be compiled as <\/p>\n<pre>\n        ... calculate x in r29 ...\n        ... calculate y in r30 ...\n        ... calculate z in r31 ...\n        cmp.eq p6, p7 = +1, r0 ;; \/\/ set p6 = false, p7 = true\n\n        cmp.eq.or.andcm p6, p7 = r29, r0 \/\/ p6 = p6 || x == 0\n                                         \/\/ p7 = p7 &amp;&amp; x != 0\n        cmp.eq.or.andcm p6, p7 = r30, r0 \/\/ p6 = p6 || y == 0\n                                         \/\/ p7 = p7 &amp;&amp; y != 0\n        cmp.eq.or.andcm p6, p7 = r31, r0 ;; \/\/ p6 = p6 || z == 0\n                                         \/\/ p7 = p7 &amp;&amp; z != 0\n\n(p6)    something_is_zero\n(p7)    all_are_nonzero\n<\/pre>\n<p>First, we calculate the values of <var>x<\/var>, <var>y<\/var> and <var>z<\/var>. At the same time, we prime the parallel comparison: we compare the constant +1 against register <var>r0<\/var>, which is the hard-coded zero register. This comparison always fails, so we set <var>p6<\/var> to <var>false<\/var> and <var>p7<\/var> to <var>true<\/var>. <\/p>\n<p>Now we perform the three comparisons in parallel. We check if <var>r29<\/var>, <var>r30<\/var>, and <var>r31<\/var> are zero. If any of them is zero, then <var>p6<\/var> becomes <var>true<\/var> and <var>p7<\/var> becomes <var>false<\/var>. If all are nonzero, then nothing changes, so <var>p6<\/var> stays <var>false<\/var> and <var>p7<\/var> stays <var>true<\/var>. <\/p>\n<p>Finally, we act on the calculated predicates. <\/p>\n<p>Notice that the parallel comparison lets us calculate and combine all the parts of the test in a single cycle. In a flags-based architecture, we would have to perform a comparison, test the result, then perform another comparison, test the result, then perform the last comparison, and test the result one last time. That&#8217;s a sequence of six dependent operations, which is difficult to parallelize. (And most likely consume three branch prediction slots instead of just one.) <\/p>\n<p>The last wrinkle in the comparison instructions is the so-called unconditional<\/i> comparison. This special instruction violates the rule that a predicated instruction has no effect if the predicate is false. <\/p>\n<pre>\n(qp)    cmp.xx.unc p, q = r, s\n<\/pre>\n<p>Even though there is a qualifying predicate, this comparison is executed unconditionally (as indicated by the <code>unc<\/code> suffix). The behavior of an unconditional comparison is <\/p>\n<table CLASS=\"cp3\" BORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"3\" STYLE=\"border-collapse: collapse\">\n<tr>\n<td><var>p<\/var> = <var>qp<\/var> &amp;&amp; (<var>r<\/var> xx <var>s<\/var>)<\/td>\n<\/tr>\n<tr>\n<td><var>p<\/var> = <var>qp<\/var> &amp;&amp; &not;(<var>r<\/var> xx <var>s<\/var>)<\/td>\n<\/tr>\n<\/table>\n<p>In other words, if the qualifying predicate is <var>true<\/var>, then the instruction behaves as normal. But if the qualifying predicate is <var>false<\/var>, then the result of the comparison is considered <var>false<\/var> for all branches, regardless of the actual test. <\/p>\n<p>This formulation is handy when you are nesting predicates. Consider: <\/p>\n<pre>\n x =  ... calculate x ...;\n y =  ... calculate y ...;\n if (x == 0) {\n  x_is_zero;\n } else {\n  x_is_nonzero;\n  if (y == 0) {\n   x_is_nonzero_and_y_is_zero;\n  } else {\n   both_are_nonzero;\n  }\n }\n<\/pre>\n<p>This can be compiled like this: <\/p>\n<pre>\n        ... calculate x in r30 ...\n        ... calculate y in r31 ...\n\n        cmp.eq p6, p7 = r30, r0 ;;\n(p6)    x_is_zero\n(p7)    x_is_nonzero\n(p7)    cmp.eq.unc p8, p9 = r31, r0 ;;\n(p8)    x_is_nonzero_and_y_is_zero\n(p9)    both_are_nonzero\n<\/pre>\n<p>After calculating <var>x<\/var> and <var>y<\/var>, we check whether <var>x<\/var> is zero. If it is, then we execute <var>x_is_zero<\/var>. If not, then we execute <var>x_is_nonzero<\/var>. Next, we check whether <var>y<\/var> is zero, and we do so via an unconditional comparison. That way, if we are in the case that <var>x<\/var> is zero, then both <var>p8<\/var> and <var>p9<\/var> are set to <var>false<\/var>. Now we can use <var>p8<\/var> and <var>p9<\/var> to select between the final two branches. (Or if <var>x<\/var> is zero, neither gets selected.) <\/p>\n<p>We&#8217;ll see later that the unconditional comparison is also useful in register rotation. <\/p>\n<p>So that&#8217;s a quick tour of the Itanium conditional instructions. Next time, we&#8217;ll start looking at speculation. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Deciding what to do next.<\/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-91191","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"<p>Deciding what to do next.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91191","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=91191"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/91191\/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=91191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=91191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=91191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}