{"id":322769,"date":"2021-05-08T15:00:09","date_gmt":"2021-05-08T15:00:09","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=322769"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=322769","title":{"rendered":"\u041a\u0430\u043a LLVM \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u0441\u0443\u043c\u043c\u044b \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">LLVM \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u0441\u0443\u043c\u043c\u044b \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:  <\/p>\n<pre><code class=\"cpp\">int sum(int count) {   int result = 0;    for (int j = 0; j &lt; count; ++j)     result += j*j;    return result; }<\/code><\/pre>\n<p>  \u0432 \u043a\u043e\u0434, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0431\u0435\u0437 \u0446\u0438\u043a\u043b\u0430 (<a href=\"https:\/\/godbolt.org\/z\/ZJhD05\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>):  <\/p>\n<pre><code class=\"cpp\">sum(int):         test    edi, edi         jle     .LBB0_1         lea     eax, [rdi - 1]         lea     ecx, [rdi - 2]         imul    rcx, rax         lea     eax, [rdi - 3]         imul    rax, rcx         shr     rax         imul    eax, eax, 1431655766         add     eax, edi         shr     rcx         lea     ecx, [rcx + 2*rcx]         lea     eax, [rax + rcx]         add     eax, -1         ret .LBB0_1:         xor     eax, eax         ret<\/code><\/pre>\n<p>  \u0422\u0430\u043a\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 (<a href=\"https:\/\/godbolt.org\/z\/mWknyx\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>) \u2013 \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0437\u0434\u0435\u0441\u044c \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u0442 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u044b. \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043a\u0430\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u044d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f.<br \/>  <a name=\"habracut\"><\/a>  <\/p>\n<h3>\u0410\u043d\u0430\u043b\u0438\u0437 \u0446\u0438\u043a\u043b\u043e\u0432 \u2014 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0435 \u0440\u0430\u0437\u0432\u0451\u0440\u0442\u044b\u0432\u0430\u043d\u0438\u0435<\/h3>\n<p>  \u0415\u0441\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u043a\u043e\u0433\u0434\u0430 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0443 \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0441\u043b\u0435\u0436\u0438\u0432\u0430\u0442\u044c, \u043a\u0430\u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432\u043d\u0443\u0442\u0440\u0438 \u0446\u0438\u043a\u043b\u0430. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432\u0435\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0442\u043e\u0440 \u0446\u0438\u043a\u043b\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043d\u0430 \u043d\u043e\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442, \u0447\u0442\u043e \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0435 \u0441\u0441\u044b\u043b\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u0438\u0437\u0438\u0440\u0443\u0435\u043c\u044b\u0439 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d.<\/p>\n<p>  \u0418 GCC, \u0438 LLVM \u0434\u0435\u043b\u0430\u044e\u0442 \u044d\u0442\u043e \u0441\u0445\u043e\u0434\u043d\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c, \u0432 \u043f\u0440\u043e\u0445\u043e\u0434\u0430\u0445 \u00abscalar evolution\u00bb (<i>\u044f \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u0435\u043b \u043d\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0442\u0435\u0440\u043c\u0438\u043d\u044b \u0432\u043e \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u0435 \u043f\u043e\u0442\u0435\u0440\u0438 \u0441\u043c\u044b\u0441\u043b\u0430 \u2014 \u043f\u0440\u0438\u043c \u043f\u0435\u0440\u0435\u0432.<\/i>), \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043a\u0430\u0436\u0434\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043d\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 i (\u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043e\u0442\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0441 0) \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043a\u0430\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c77\/610\/121\/c77610121c22cf9ba7de90b7429e5567.svg\" alt=\"$f_0(i)$\" data-tex=\"inline\"><\/math>, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u0430\u044f \u043a\u0430\u043a \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0430  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5d0\/6e1\/f7f\/5d06e1f7f3196ebb14cbe407434a08dd.svg\" alt=\"$f_j(i)=\\begin{cases}\\phi_j &amp; if &amp; i = 0\\\\f_j(i-1)\\odot_{j+1}f_{j+1}(i-1)&amp; if &amp; x &gt; 0\\end{cases} $\" data-tex=\"display\"><\/math><\/p>\n<p>  \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c8f\/430\/fd3\/c8f430fd38b44d5287d689911067e9d1.svg\" alt=\"$\\odot \\in \\big\\{+, \\ast \\big\\} $\" data-tex=\"inline\"><\/math><br \/>  <b>\u041f\u0440\u0438\u043c\u0435\u0440 1<\/b><br \/>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0446\u0438\u043a\u043b\u0430:  <\/p>\n<pre><code class=\"cpp\">void foo(int m, int *p) {   for (int j = 0; j &lt; m; j++)     *p++ = j; }<\/code><\/pre>\n<p>  \u0426\u0438\u043a\u043b \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 0 \u0432 *p++ \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, 1 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0439, \u0438 \u0442. \u0434. \u0418\u0442\u0430\u043a, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0435 \u043d\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 i \u043a\u0430\u043a    <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/264\/dab\/61f\/264dab61fdc96a1947a7409b047ba317.svg\" alt=\"$f_j(i)=\\begin{cases}0 &amp; if &amp; i = 0\\\\f(j-1)+1&amp; if &amp; x &gt; 0\\end{cases} $\" data-tex=\"display\"><\/math><\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440 2<\/b><br \/>  \u041f\u043e\u043b\u0438\u043d\u043e\u043c\u044b \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u044b \u0432 \u044d\u0442\u043e\u0439 \u0444\u043e\u0440\u043c\u0435.  <\/p>\n<pre><code class=\"cpp\">void foo(int m, int k, int *p) {   for (int j = 0; &lt; m; j++)     *p++ = j*j*j - 2*j*j + k*j + 7; }<\/code><\/pre>\n<p>  \u041c\u044b \u0443\u0432\u0438\u0434\u0438\u043c \u043d\u0438\u0436\u0435, \u043a\u0430\u043a \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0441\u0435\u0439\u0447\u0430\u0441 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u0441\u043e\u0445\u0440\u0430\u043d\u0451\u043d\u043d\u043e\u0433\u043e \u0432 \u0446\u0438\u043a\u043b\u0435:   <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aba\/0bf\/360\/aba0bf3606795780f5d78a975f299ca4.svg\" alt=\"$\\begin{align}f_2(i) &amp; = \\begin{cases} 2\\phantom{f_0(i-1) + f_1(i-1)} &amp; \\text{if $i = 0$} \\\\ f_2(i-1) + 6 &amp; \\text{if $i &gt; 0$} \\end{cases}\\\\ f_1(i) &amp; = \\begin{cases} k-1 &amp; \\text{if $i = 0$} \\\\ f_1(i-1) + f_2(i-1)\\phantom{2} &amp; \\text{if $i &gt; 0$} \\end{cases}\\\\ f(i) = f_0(i) &amp; = \\begin{cases} 7 &amp; \\text{if $i = 0$} \\\\ f_0(i-1) + f_1(i-1)\\phantom{2} &amp; \\text{if $i &gt; 0$} \\end{cases}\\end{align}$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u041e\u0434\u043d\u0443 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u0438\u0434\u0435\u0442\u044c \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0438\u0437 \u044d\u0442\u0438\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439, \u043e\u043d\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043e \u0437\u0430 \u0442\u0440\u0438 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432 \u0446\u0438\u043a\u043b\u0435  <\/p>\n<pre><code class=\"cpp\">void foo(int m, int k, int *p) {   int t0 = 7;   int t1 = k-1;   int t2 = 2;   for (int j = 0; j &lt; m; j++) {     *p++ = t0;     t0 = t0 + t1;     t1 = t1 + t2;     t2 = t2 + 6;   } }<\/code><\/pre>\n<p>  , \u0447\u0442\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u0434\u043b\u044f \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u043c. \u041a\u043e\u0434 \u0442\u0430\u043a\u043e\u0433\u043e \u0432\u0438\u0434\u0430, \u043e\u0434\u043d\u0430\u043a\u043e, \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0431\u0449\u0435\u043f\u0440\u0438\u043d\u044f\u0442\u044b\u043c, \u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u043e\u0432 \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0442\u0430\u043a\u0443\u044e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e, \u043d\u043e \u043e\u043d\u0438 \u0434\u0435\u043b\u0430\u044e\u0442 \u0435\u0451 \u0434\u043b\u044f \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a  <\/p>\n<pre><code class=\"cpp\">void foo(int m, int k, int *p) {   for (int j = 0; &lt; m; j++)     *p++ = k*j + 7; }<\/code><\/pre>\n<p>  \u0442\u0430\u043a \u043a\u0430\u043a \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u0432\u0438\u0434\u0430 k*j+7 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u044b\u043c\u0438 \u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u0430\u0434\u0440\u0435\u0441\u0430.<\/p>\n<h3>\u0420\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0435 \u0446\u0435\u043f\u0438<\/h3>\n<p>  \u0413\u0440\u043e\u043c\u043e\u0437\u0434\u043a\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0438\u0441\u0430\u0442\u044c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u043f\u0438\u0448\u0443\u0442\u0441\u044f \u0432 \u0444\u043e\u0440\u043c\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/91d\/7e3\/489\/91d7e34897b992687f4af02284383958.svg\" alt=\"$\\left\\{ \\phi_j,\\odot_{j+1},f_{j+1}\\right \\}$\" data-tex=\"inline\"><\/math>. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/55a\/ac3\/391\/55aac3391863bec601429f81721f593e.svg\" alt=\"$\\begin{align}f_2(i) &amp; = \\begin{cases} 2\\phantom{f_0(i-1) + f_1(i-1)} &amp; \\text{if $i = 0$} \\\\ f_2(i-1) + 6 &amp; \\text{if $i &gt; 0$} \\end{cases} \\phantom{xx}\\text{is written as $\\{2,+,6\\}$}\\\\ f_1(i) &amp; = \\begin{cases} k-1 &amp; \\text{if $i = 0$} \\\\ f_1(i-1) + f_2(i-1)\\phantom{2} &amp; \\text{if $i &gt; 0$} \\end{cases} \\phantom{xx}\\text{is written as $\\{k-1,+,f_2\\}$}\\\\ f(i) = f_0(i) &amp; = \\begin{cases} 7 &amp; \\text{if $i = 0$} \\\\ f_0(i-1) + f_1(i-1)\\phantom{2} &amp; \\text{if $i &gt; 0$} \\end{cases} \\phantom{xx}\\text{is written as $\\{7,+,f_1\\}$}\\end{align}$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u042d\u0442\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0432 \u0446\u0435\u043f\u043e\u0447\u043a\u0443, \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3a7\/42a\/787\/3a742a7878533886314fae6e4beb5c25.svg\" alt=\"$f(i)$\" data-tex=\"inline\"><\/math> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u043a\u0430\u043a \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0446\u0435\u043f\u044c (chain of recurrences, CR) <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ebb\/766\/3e9\/ebb7663e9448312fa3e67af7acefea5e.svg\" alt=\"$\\{7,+,\\{k-1,+,\\{2,+,6\\}\\}\\}$\" data-tex=\"inline\"><\/math>. \u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u0444\u0438\u0433\u0443\u0440\u043d\u044b\u0435 \u0441\u043a\u043e\u0431\u043a\u0438 \u0438\u0437\u0431\u044b\u0442\u043e\u0447\u043d\u044b, \u0438 CR \u043e\u0431\u044b\u0447\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043a\u043e\u0440\u0442\u0435\u0436 \\{7,+,\\{k-1,+,\\{2,+,6\\}\\}\\}.<\/p>\n<h3>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0440\u0435\u043a\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u044b\u0445 \u0446\u0435\u043f\u0435\u0439<\/h3>\n<p>  \u0420\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0435 \u0446\u0435\u043f\u0438 \u0441\u0442\u0440\u043e\u044f\u0442\u0441\u044f \u043f\u0443\u0442\u0451\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0430\u0434 \u043a\u043e\u0434\u043e\u043c \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0433\u043e CR \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 (\u0438\u043b\u0438 \u043c\u0430\u0440\u043a\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c, \u0435\u0441\u043b\u0438 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e), \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u044f:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f91\/01a\/b96\/f9101ab96be761977837de3c3455501c.svg\" alt=\"$\\begin{align}c * \\{\\phi_0, +, \\phi_1\\} &amp; \\phantom{xx} \\Rightarrow \\phantom{xx} \\{c * \\phi_0, +, c * \\phi_1\\} \\\\ \\{\\phi_0, +, \\phi_1\\} + \\{\\psi_0, +, \\psi_1\\} &amp; \\phantom{xx} \\Rightarrow \\phantom{xx} \\{\\phi_0 + \\psi_0, +, \\phi_1 + \\psi_1\\} \\\\ \\{\\phi_0, +, \\phi_1\\}* \\{\\psi_0, +, \\psi_1\\} &amp; \\phantom{xx} \\Rightarrow \\phantom{xx} \\{\\phi_0 * \\psi_0, +, \\psi_1 * \\{\\phi_0, +, \\phi_1\\} + \\phi_1 * \\{\\psi_0, +, \\psi_1\\} + \\phi_1*\\psi_1\\} \\\\ \\{\\phi_0, +, \\phi_1,+,0\\} &amp; \\phantom{xx} \\Rightarrow \\phantom{xx} \\{\\phi_0, +, \\phi_1\\}\\end{align} $\" data-tex=\"display\"><\/math><\/p>\n<p>  \u0418\u0442\u0430\u043a, \u0434\u043b\u044f \u0446\u0438\u043a\u043b\u0430 \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 sum:  <\/p>\n<pre><code class=\"cpp\">for (int j = 0; j &lt; count; ++j)   result += j*j;<\/code><\/pre>\n<p>  \u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 j \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430 CR <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4f5\/295\/c73\/4f5295c737c77433be7f434fc5cd5480.svg\" alt=\"$\\{0,+,1\\}$\" data-tex=\"inline\"><\/math> \u0438\u0437 \u043f\u0440\u0438\u043c\u0435\u0440\u0430 1. \u0417\u0430\u0442\u0435\u043c \u043e\u043d\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043a\u0430\u043a j*j, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c result, \u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c CR \u0434\u043b\u044f j*j, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u044f:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6ff\/581\/3b9\/6ff5813b908e8226b25f8497bba24bab.svg\" alt=\"$\\begin{align}j*j&amp; = \\{0,+,1\\} * \\{0,+,1\\} \\\\ &amp; = \\{0 * 0, +, 1 * \\{0, +,1\\} + 1 * \\{0, +, 1\\} + 1*1\\} \\\\ &amp; = \\{0, +, 1,+,2\\}\\end{align}$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u0421\u0445\u043e\u0434\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f result \u0434\u0430\u0451\u0442 \u043d\u0430\u043c CR <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/863\/fdc\/a72\/863fdca72ac88ef47b7901d3618eb134.svg\" alt=\"$\\{0,+,0,+,1,+,2\\}$\" data-tex=\"inline\"><\/math> \u043f\u043e\u0441\u043b\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f j*j.  <\/p>\n<h3>\u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438<\/h3>\n<p>  \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0443\u043a\u0446\u0438\u0438 (induction variable simplification), \u0438 LLVM \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0432 \u0444\u043e\u0440\u043c\u0443, \u0443\u0434\u043e\u0431\u043d\u0443\u044e \u0434\u043b\u044f \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438  <\/p>\n<pre><code class=\"cpp\">int sum(int count) {   int result = 0;    if (count &gt; 0) {     int j = 0;     do {       result = result + j*j;       ++j;     } while (j &lt; count);   }    return result; }<\/code><\/pre>\n<p>  \u0438\u043b\u0438, \u043a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 LLVM IR:  <\/p>\n<pre><code class=\"cpp\">define i32 @sum(i32) { %2 = icmp sgt i32 %0, 0 br i1 %2, label %3, label %6 ; &lt;label&gt;:3: br label %8 ; &lt;label&gt;:4: %5 = phi i32 [ %12, %8 ]  br label %6 ; &lt;label&gt;:6: %7 = phi i32 [ 0, %1 ], [ %5, %4 ]  ret i32 %7 ; &lt;label&gt;:8: %9 = phi i32 [ %13, %8 ], [ 0, %3 ]     ; {0,+,1} %10 = phi i32 [ %12, %8 ], [ 0, %3 ]    ; {0,+,0,+,1,+,2} %11 = mul nsw i32 %9, %9                ; {0,+,1,+,2} %12 = add nuw nsw i32 %11, %10          ; {0,+,1,+,3,+,2} %13 = add nuw nsw i32 %9, 1             ; {1,+,1} %14 = icmp slt i32 %13, %0 br i1 %14, label %8, label %4 }<\/code><\/pre>\n<p>  \u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u043c\u043e\u0436\u0435\u0442 \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 0, \u0435\u0441\u043b\u0438 count &lt;= 0, \u0438\u043d\u0430\u0447\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0446\u0438\u043a\u043b\u0430 loop iteration count-1.<br \/>  \u041f\u0440\u0438\u044f\u0442\u043d\u043e\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u043e\u0439 \u0446\u0435\u043f\u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043b\u0435\u0433\u043a\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438: \u0435\u0441\u043b\u0438 \u043c\u044b \u0437\u043d\u0430\u0435\u043c CR:<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf9\/4d1\/c38\/bf94d1c38abc90df0af3a3385ca63f26.svg\" alt=\"$\\{\\phi_0,+,\\phi_1,+,\\ldots,+,\\phi_n\\}$\" data-tex=\"inline\"><\/math>, \u0442\u043e\u0433\u0434\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043e \u043a\u0430\u043a:<br \/>  \\begin{align}f(i) &amp; = \\sum_{j=0}^{n}\\phi_j{i \\choose j} \\\\ &amp; = \\phi_0 + \\phi_1i + \\phi_2{i(i-1)\\over 2!} + \\ldots + \\phi_n{i(i-1)\\cdots(i-n+1)\\over n!}\\end{align}<br \/>  \u041f\u043e\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043b\u044f CR <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8c7\/443\/e2c\/8c7443e2c203ca569b81059978fbac01.svg\" alt=\"$\\{0,+,1,+,3,+,2\\}$\" data-tex=\"inline\"><\/math>, \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0449\u0438\u0435 result, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/545\/c46\/f3f\/545c46f3fed6a75cec087a5e6702ae91.svg\" alt=\"$f(i) = i + {3i(i-1)\\over 2} + {i(i-1)(i-2) \\over 3}$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0443 \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3bb\/8dd\/bb7\/3bb8ddbb7de0cdbbca41e516e2ab01cd.svg\" alt=\"$i =$\" data-tex=\"inline\"><\/math> count-1, \u043f\u043e\u0441\u043b\u0435 \u0446\u0438\u043a\u043b\u0430  <\/p>\n<pre><code class=\"cpp\">result = count-1 + 3*(count-1)*(count-2)\/2 + (count-1)*(count-2)(count-3)\/3; <\/code><\/pre>\n<p>  \u043d\u043e \u043d\u0443\u0436\u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0441\u0442\u043e\u0440\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0435\u0440\u044f\u0442\u044c\u0441\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c (\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u043d\u0435 \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u0432 32-\u0431\u0438\u0442\u043d\u044b\u0435 \u0446\u0435\u043b\u044b\u0435). <a href=\"https:\/\/kristerw.blogspot.com\/2017\/05\/integer-division-is-slow.html\" rel=\"nofollow noopener noreferrer\">\u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u044b\u0445 \u2014 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/a>, \u0438 \u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0440\u044e\u043a \u0441 \u0437\u0430\u043c\u0435\u043d\u043e\u0439 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0441\u0434\u0432\u0438\u0433\u0438. \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 LLVM IR  <\/p>\n<pre><code class=\"cpp\">%4 = add i32 %0, -1   %5 = zext i32 %4 to i33   %6 = add i32 %0, -2   %7 = zext i32 %6 to i33   %8 = mul i33 %5, %7   %9 = add i32 %0, -3   %10 = zext i32 %9 to i33   %11 = mul i33 %8, %10   %12 = lshr i33 %11, 1   %13 = trunc i33 %12 to i32   %14 = mul i32 %13, 1431655766   %15 = add i32 %14, %0   %16 = lshr i33 %8, 1   %17 = trunc i33 %16 to i32   %18 = mul i32 %17, 3   %19 = add i32 %15, %18   %20 = add i32 %19, -1<\/code><\/pre>\n<p>  \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u044d\u0442\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u0434\u0435\u043b\u0430\u0435\u0442 \u0446\u0438\u043a\u043b \u043c\u0451\u0440\u0442\u0432\u044b\u043c, \u0438 \u043f\u043e\u0437\u0436\u0435 \u043e\u043d \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0445\u043e\u0434\u043e\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043c\u0451\u0440\u0442\u0432\u043e\u0433\u043e \u043a\u043e\u0434\u0430 (dead code elimination), \u0438 \u043c\u044b, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043a\u043e\u0434  <\/p>\n<pre><code class=\"cpp\">sum(int):         test    edi, edi         jle     .LBB0_1         lea     eax, [rdi - 1]         lea     ecx, [rdi - 2]         imul    rcx, rax         lea     eax, [rdi - 3]         imul    rax, rcx         shr     rax         imul    eax, eax, 1431655766         add     eax, edi         shr     rcx         lea     ecx, [rcx + 2*rcx]         lea     eax, [rax + rcx]         add     eax, -1         ret .LBB0_1:         xor     eax, eax         ret<\/code><\/pre>\n<p>  <\/p>\n<h3>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h3>\n<p>  \u042d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u0433\u043e\u0434\u043d\u0430. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440,  <\/p>\n<pre><code class=\"cpp\">int sum(int count) {   int result = 0;    for (int j = 0; j &lt; count; ++j)     result += j*j*j*j*j*j;    return result; }<\/code><\/pre>\n<p>  \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0442\u0440\u0438 32-\u0431\u0438\u0442\u043d\u044b\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u043e\u0434\u043d\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0437\u0430 \u0446\u0438\u043a\u043b, \u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0448\u0435\u0441\u0442\u044c 64-\u0431\u0438\u0442\u043d\u044b\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043f\u044f\u0442\u044c 32-\u0431\u0438\u0442\u043d\u044b\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 (<a href=\"https:\/\/godbolt.org\/z\/tV9Rii\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>), \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0441\u0438\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0434\u043b\u044f \u043c\u0430\u043b\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0446\u0438\u043a\u043b\u0430. \u041d\u0430 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 CPU \u0441, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0431\u043e\u043b\u0435\u0435 \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u043c 64-\u0431\u0438\u0442\u043d\u044b\u043c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435\u043c, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0446\u0438\u043a\u043b\u043e\u0432, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u0430, \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u044b\u0445 CPU. \u0414\u043b\u044f CPU, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0438\u043c\u0435\u044e\u0442 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0439 \u0434\u043b\u044f 64-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f, \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0435\u0449\u0451 \u0431\u043e\u043b\u044c\u0448\u0435 (<a href=\"https:\/\/godbolt.org\/z\/KNBl0Z\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>).<br \/>  \u041e\u0434\u043d\u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u0442\u0430\u043a\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0446\u0438\u043a\u043b, \u0435\u0441\u043b\u0438 \u043e\u043d \u0437\u043d\u0430\u0435\u0442, \u0447\u0442\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043c\u0430\u043b\u044b, \u0447\u0442\u043e\u0431\u044b \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u0446\u0438\u043a\u043b\u0430 \u0431\u044b\u043b\u0430 \u043b\u0443\u0447\u0448\u0438\u043c \u0432\u044b\u0431\u043e\u0440\u043e\u043c. GCC, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0435\u0441\u043b\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f.  <\/p>\n<pre><code class=\"cpp\">\/* Do not emit expensive expressions.  The rationale is that    when someone writes a code like     while (n &gt; 45) n -= 45;     he probably knows that n is not large, and does not want it    to be turned into n %= 45.  *\/ || expression_expensive_p (def))<\/code><\/pre>\n<p>  \u0415\u0441\u043b\u0438 GCC \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e, \u044d\u0442\u043e \u043d\u0435 \u0431\u0430\u0433, \u044d\u0442\u043e \u0444\u0438\u0447\u0430.<\/p>\n<h3>\u041b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u0430:<\/h3>\n<p>  \u0420\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0435 \u0446\u0435\u043f\u0438:<br \/>  1. Olaf Bachmann, Paul S. Wang, Eugene V. Zima. \u201c<a href=\"https:\/\/bohr.wlu.ca\/ezima\/papers\/ISSAC94_p242-bachmann.pdf\" rel=\"nofollow noopener noreferrer\">Chains of recurrences \u2013 a method to expedite the evaluation of closed-form functions<\/a>\u201d<br \/>  2. Eugene V. Zima. \u201c<a href=\"https:\/\/bohr.wlu.ca\/ezima\/papers\/ISSAC01_p345-zima.pdf\" rel=\"nofollow noopener noreferrer\">On computational properties of chains of recurrences<\/a>\u201d<br \/>  \u0426\u0438\u043a\u043b\u043e\u0432\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0435 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0435 \u0446\u0435\u043f\u0438:<br \/>  3. Robert A. van Engelen. \u201c<a href=\"https:\/\/www.semanticscholar.org\/paper\/Symbolic-Evaluation-of-Chains-of-Recurrencesfor-OptimizationRobert-van\/d247e00ddea346258916c19b1480048ce0fd20be?p2df\" rel=\"nofollow noopener noreferrer\">Symbolic Evaluation of Chains of Recurrences for Loop Optimization<\/a>\u201d<br \/>  4. Robert A. van Engelen. \u201c<a href=\"https:\/\/www.cs.fsu.edu\/~engelen\/cc01.pdf\" rel=\"nofollow noopener noreferrer\">Efficient Symbolic Analysis for Optimizing Compilers<\/a>\u201d<br \/>  \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0441\u0434\u0432\u0438\u0433\u0430:<br \/>  5. Torbj\u00f6rn Granlund, Peter L. Montgomery. \u201c<a href=\"https:\/\/gmplib.org\/~tege\/divcnst-pldi94.pdf\" rel=\"nofollow noopener noreferrer\">Division by Invariant Integers using Multiplication<\/a>\u201d<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/550900\/\"> https:\/\/habr.com\/ru\/post\/550900\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">LLVM \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u0441\u0443\u043c\u043c\u044b \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:  <\/p>\n<pre><code class=\"cpp\">int sum(int count) {   int result = 0;    for (int j = 0; j &lt; count; ++j)     result += j*j;    return result; }<\/code><\/pre>\n<p>  \u0432 \u043a\u043e\u0434, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0431\u0435\u0437 \u0446\u0438\u043a\u043b\u0430 (<a href=\"https:\/\/godbolt.org\/z\/ZJhD05\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>):  <\/p>\n<pre><code class=\"cpp\">sum(int):         test    edi, edi         jle     .LBB0_1         lea     eax, [rdi - 1]         lea     ecx, [rdi - 2]         imul    rcx, rax         lea     eax, [rdi - 3]         imul    rax, rcx         shr     rax         imul    eax, eax, 1431655766         add     eax, edi         shr     rcx         lea     ecx, [rcx + 2*rcx]         lea     eax, [rax + rcx]         add     eax, -1         ret .LBB0_1:         xor     eax, eax         ret<\/code><\/pre>\n<p>  \u0422\u0430\u043a\u0436\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 (<a href=\"https:\/\/godbolt.org\/z\/mWknyx\" rel=\"nofollow noopener noreferrer\">godbolt<\/a>) \u2013 \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0437\u0434\u0435\u0441\u044c \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u0442 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u044b. \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043a\u0430\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u044d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-322769","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/322769","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=322769"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/322769\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=322769"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=322769"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=322769"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}