الكود بلا تفرّع في

نبذة عن الكود بلا تفرّع

يقدّم مفهوم الجمل الشرطية التعليمة 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 في غير ذلك. والوجهة دائمًا معامل بحجم 8 بت.

تتبع اللاحقة cc التسمية نفسها المتبعة في jcc و cmovcc. على سبيل المثال، تضبط setz الوجهة على 1 إذا كان ZF == 1، وعلى 0 في غير ذلك.

ولأن الوجهة بحجم 8 بت، فمن الشائع أن تتبع 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 من الأعداد الصحيحة ذات 64 بت بدءًا من 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.

ويكون الكود بلا تفريع مجديًا عندما يصعب توقع التفريع، أو عندما يلزم توقيت ثابت بغض النظر عن المدخلات.