Κώδικας χωρίς διακλαδώσεις σε

Σχετικά με την έννοια Κώδικας χωρίς διακλαδώσεις

Η έννοια συνθήκες παρουσιάζει το 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 bit.

Το επίθημα cc ακολουθεί την ίδια ονοματολογία όπως στα jcc και cmovcc. Για παράδειγμα, η setz θέτει τον προορισμό σε 1 αν ZF == 1 και σε 0 διαφορετικά.

Επειδή ο προορισμός είναι 8 bit, συνηθίζεται να ακολουθεί μια 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 bit ξεκινώντας από το 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.

Ο κώδικας χωρίς διακλαδώσεις αξίζει τον κόπο όταν η διακλάδωση είναι δύσκολο να προβλεφθεί, ή όταν απαιτείται σταθερός χρόνος εκτέλεσης ανεξάρτητα από τις εισόδους.