کد بدون انشعاب در

درباره‌ی کد بدون انشعاب

مفهوم شرط‌ها دستور jcc را معرفی می‌کند؛ خانواده‌ای از دستورها برای «انشعاب» بر اساس یک شرط. دستور jcc فقط در صورتی اجرا را به نقطه‌ی دیگری از برنامه منتقل می‌کند که شرطش برقرار باشد.

با این حال، پردازنده‌های مدرن سریع‌اند و می‌توانند بسیاری از دستورها را به‌صورت موازی اجرا کنند. متوقف کردن همه‌ی کارها تا زمانی که پردازنده منتظر بررسی شرط در زمان اجرا بماند، هزینه‌ی زیادی دارد.

به همین دلیل است که پردازنده در باطن منتظر نمی‌ماند. پردازنده از یک «پیش‌بین انشعاب» استفاده می‌کند تا نتیجه‌ی یک شرط را حدس بزند و اجرای مسیر حدس‌زده را به‌صورت گمانه‌زنانه آغاز می‌کند.

اگر پیش‌بینی درست باشد، اجرا طوری پیش می‌رود که گویی انشعابی وجود نداشته است. اما اگر پیش‌بینی نادرست باشد، پردازنده باید کار انجام‌شده روی مسیر پیش‌بینی‌شده را کنار بگذارد و از مسیر درست دوباره شروع کند.

به این حالت پیش‌بینی نادرست انشعاب می‌گویند و پرهزینه است و تأخیر به همراه دارد.

وقتی پیش‌بینی یک انشعاب دشوار باشد، این پیش‌بینی‌های نادرست روی هم انباشته می‌شوند. در چنین مواردی، گاهی بهتر است از انشعاب به‌کلی پرهیز شود تا دستورهای یکسانی صرف‌نظر از شرط اجرا شوند. به کدی که بدون jcc بین مقدارها انتخاب می‌کند، بدون انشعاب می‌گویند.

راه‌های گوناگونی برای ساختاربندی کد وجود دارد تا کمتر انشعاب بگیرد، یا انشعاب‌هایی که دارد قابل‌پیش‌بینی‌تر باشند. به‌طور خاص، معماری x86-64 دو خانواده‌ی دستور فراهم می‌کند که معمولاً برای نوشتن کد بدون انشعاب به کار می‌روند.

انتقال‌های شرطی

خانواده‌ی دستورهای cmovcc فقط در صورتی «عملوند» مبدأ را در مقصد کپی می‌کنند که شرط خاصی برقرار باشد. در غیر این صورت، مقصد بدون تغییر می‌ماند.

پسوند cc همان نام‌گذاری jcc را دارد و همان معنا را می‌رساند:

قواعد آن مشابه jcc است:

1. از l و g برای مقایسه‌های علامت‌دار استفاده می‌شود؛ از b و a برای مقایسه‌های بدون علامت.
2. افزودن e به یک پسوند، تساوی را نیز شامل می‌شود.
3. افزودن n شرط را نقیض می‌کند.
4. گونه‌هایی هم وجود دارند که به تنظیم بودن «پرچم» اشاره می‌کنند. برای نمونه، cmovz و cmovc.

مقدار قدرمطلق یک عدد صحیح علامت‌دار در rdi را در نظر بگیرید که در rax برگردانده می‌شود. این تابع اگر با jcc نوشته شود، یکی از دو مسیر را انتخاب می‌کند:

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

اگر با cmovcc نوشته شود، هر دو مقدار نامزد به‌صورت بی‌قیدوشرط محاسبه می‌شوند و انتقال شرطی یکی را انتخاب می‌کند:

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

نسخه‌ی بدون انشعاب همیشه دستورهای یکسانی را اجرا می‌کند. هیچ jccی وجود ندارد که پیش‌بین آن را حدس بزند.

مقصد cmovcc باید یک «ثبات» باشد. مبدأ می‌تواند یک ثبات یا یک مکان حافظه باشد، اما نه یک «مقدار فوری».

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

تنظیم شرطی

خانواده‌ی دستورهای setcc در صورت برقرار بودن شرط خاصی، عملوند مقصد را برابر 1 و در غیر این صورت برابر 0 قرار می‌دهند. مقصد همیشه یک عملوند ۸ بیتی است.

پسوند cc همان نام‌گذاری jcc و cmovcc را دارد. برای نمونه، setz مقصد را در صورتی که ZF == 1 باشد برابر 1 و در غیر این صورت برابر 0 قرار می‌دهد.

چون مقصد ۸ بیتی است، معمول است که در صورت نیاز به مقدار پهن‌تر، بعد از setcc از movzx استفاده شود:

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

این روشی رایج برای تبدیل نتیجه‌ی یک مقایسه به عدد صحیح 0 یا 1 است.

چه زمانی از کد بدون انشعاب استفاده کنیم

کد بدون انشعاب همیشه از کد دارای انشعاب سریع‌تر نیست. وقتی انشعابی به‌شدت قابل‌پیش‌بینی باشد، پیش‌بین تقریباً هر بار درست حدس می‌زند و jcc عملاً هیچ هزینه‌ای ندارد. کد بدون انشعابی که جای چنین انشعابی را بگیرد کندتر است، چون همیشه هر دو محاسبه‌ی نامزد را اجرا می‌کند.

شمارنده‌ی حلقه نمونه‌ی کلاسیک این مورد است. تابعی را در نظر بگیرید که rsi عدد صحیح ۶۴ بیتی را که از rdi شروع می‌شوند با هم جمع می‌کند:

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

این دقیقاً همان الگویی است که پیش‌بین‌های انشعاب خوب از عهده‌ی آن برمی‌آیند، پس انشعاب صرف‌نظر از تعداد عناصری که sum_array پردازش می‌کند، عملاً بی‌هزینه است.

کد بدون انشعاب زمانی به‌صرفه است که پیش‌بینی انشعاب دشوار باشد، یا زمانی که زمان‌بندی یکنواخت صرف‌نظر از ورودی‌ها لازم باشد.