9.4 אופטימיזציות של הקומפיילר פתרון

פתרונות

פתרון 1

קטע א - constant folding ו-constant propagation:

ב--O0:

constant_demo:
    movl    $10, -4(%rbp)      ; x = 10
    movl    $20, -8(%rbp)      ; y = 20
    movl    -4(%rbp), %eax
    addl    -8(%rbp), %eax     ; z = x + y
    movl    %eax, -12(%rbp)
    movl    -12(%rbp), %eax
    addl    %eax, %eax         ; z * 2
    ...

ב--O2:

constant_demo:
    movl    $60, %eax          ; 10 + 20 = 30, 30 * 2 = 60
    ret

אופטימיזציות: constant folding (חישוב 10+20=30 ו-302=60 בזמן קומפילציה) ו-constant propagation* (הערכים של x ו-y מוחלפים בקבועים).

קטע ב - dead code elimination:

ב--O2:

dead_demo:
    ; a, b, c נעלמו לחלוטין
    leaq    .LC0(%rip), %rdi   ; "hello"
    call    puts               ; printf("hello\n") -> puts("hello")
    xorl    %eax, %eax         ; return 0
    ret

אופטימיזציות: dead code elimination (a, b, c לא משמשים - נמחקו). גם printf עם מחרוזת פשוטה הוחלף ב-puts (אופטימיזציה של gcc).

קטע ג - function inlining:

ב--O2:

inline_demo:
    ; double_it הוטמע - אין call
    leal    (%rdi,%rdi), %eax   ; n * 2
    leal    2(%rdi,%rdi), %edx  ; (n+1) * 2 = n*2 + 2
    addl    %edx, %eax          ; n*2 + n*2 + 2 = 4n + 2
    ret

אופטימיזציה: function inlining (גוף double_it הועתק ישירות). ואחרי ההטמעה, הקומפיילר יכול גם לפשט את החישוב.

קטע ד - loop-invariant code motion ו-strength reduction:

ב--O2:

loop_demo:
    ; factor * 3 מחושב פעם אחת לפני הלולאה
    leal    (%rdx,%rdx,2), %ecx  ; ecx = factor * 3
    ...
.L2:
    movl    %ecx, (%rdi)          ; arr[i] = factor*3 + i
    addl    $1, %ecx              ; factor*3 + (i+1)
    addq    $4, %rdi              ; pointer arithmetic
    ...

אופטימיזציות: loop-invariant code motion (factor3 חושב מחוץ ללולאה), strength reduction (חיבור מצטבר במקום חישוב factor3+i בכל איטרציה).

---

פתרון 2

1. ב-regular_loop עם -O2, הקומפיילר עלול לזהות שהלולאה פשוט רצה עד שcount מגיע ל-1000000 ולהחליף את כל הפונקציה ב:

regular_loop:
    movl    $1000000, %eax
    ret

הקומפיילר ניתח את הלולאה, הבין שהתוצאה תמיד 1000000, והחליף את כל הקוד בקבוע.

1. ב-volatile_loop, הקומפיילר חייב לקרוא את flag מהזיכרון בכל איטרציה:

volatile_loop:
    movl    $1, -4(%rsp)       ; flag = 1 (על המחסנית)
    xorl    %eax, %eax         ; count = 0
.L2:
    movl    -4(%rsp), %edx     ; קורא flag מהזיכרון בכל פעם!
    testl   %edx, %edx
    je      .L1
    addl    $1, %eax
    cmpl    $1000000, %eax
    jne     .L2
    movl    $0, -4(%rsp)       ; flag = 0
    jmp     .L2
.L1:
    ret

1. בלי volatile, הקומפיילר רואה שבתוך הלולאה אף קוד חיצוני לא יכול לשנות את flag (מנקודת המבט של thread אחד). לכן הוא יכול להניח שהערך לא ישתנה "באורח פלא" ולבצע אופטימיזציות מבוססות על ההנחה הזו. עם volatile, הקומפיילר חייב להניח שהערך יכול להשתנות בכל רגע (על ידי חומרה, signal handler, או thread אחר).

2. הוספת printf בתוך הלולאה מונעת מהקומפיילר לבצע את האופטימיזציה האגרסיבית, כי printf היא קריאה לפונקציה חיצונית שהקומפיילר לא יודע מה היא עושה - אולי היא משנה את flag. לכן הוא חייב לקרוא את flag מחדש אחרי כל printf.

---

פתרון 3

1. תוצאות לדוגמה (משתנות לפי מחשב):

רמה	זמן (שניות)
O0-	0.350
O1-	0.120
O2-	0.080
O3-	0.045

ב--O3 מהיר פי 7-8 מ--O0.

1. ההבדלים באסמבלי:
2. ב-O0: כל הגישות דרך המחסנית, חישוב i * i בכל איטרציה

3. ב-O3: רגיסטרים בלבד, ייתכן loop unrolling ואפילו vectorization (עם הוראות SIMD שמחשבות 4 ריבועים בו זמנית)

4. עם -Os:

5. הזמן בין O1 ל-O2 (אופטימיזציות שלא מגדילות קוד)

6. הקובץ קטן יותר מ-O3 (כי אין loop unrolling וכו')

7. עם -march=native:

8. ייתכן שיפור נוסף כי הקומפיילר ישתמש בהוראות AVX2 או AVX-512 אם המעבד תומך

---

פתרון 4

1. קימפול ובדיקת אסמבלי:

gcc -O2 -S tail.c -o tail.s

1. ב-factorial_tail עם -O2:

factorial_tail:
.L2:
    cmpl    $1, %edi
    jle     .L1
    imull   %edi, %esi     ; acc = n * acc
    subl    $1, %edi       ; n = n - 1
    jmp     .L2            ; jmp! לא call! - tail call optimization
.L1:
    movl    %esi, %eax
    ret

הרקורסיה הפכה ללולאה. יש jmp לתחילת הפונקציה במקום call - אין frame חדש על המחסנית.

1. ב-factorial_regular:

factorial_regular:
    cmpl    $1, %edi
    jle     .L1
    ; הקומפיילר עלול לבצע TCO גם כאן (gcc חכם)
    ; אבל במקרים מורכבים יותר, הכפל אחרי הקריאה ימנע TCO
    ...

gcc חכם מספיק כדי לפעמים לזהות שאפשר לשנות את הרקורסיה הלא-tail לרקורסיה tail, אבל זה לא מובטח. במקרים מורכבים יותר, הקומפיילר לא יצליח.

1. בדיקת stack overflow:

int main() {
    // factorial_regular(1000000) - stack overflow!
    // כל קריאה רקורסיבית צורכת frame על המחסנית
    // 1000000 frames * ~16 bytes = ~16MB - יותר מגודל המחסנית הרגיל

    // factorial_tail(1000000, 1) עם -O2:
    // הקומפיילר הפך ללולאה - frame אחד בלבד!
    // לא יהיה stack overflow
    printf("%d\n", factorial_tail(1000000, 1));
}

factorial_regular(1000000) יגרום ל-Segmentation Fault (stack overflow). factorial_tail(1000000, 1) עם -O2 ירוץ בסדר כי הרקורסיה הפכה ללולאה (התוצאה תהיה 0 בגלל overflow של int, אבל לא תהיה קריסה).

---

פתרון 5

1. בלי LTO:

gcc -O2 -c math_ops.c -o math_ops.o
gcc -O2 -c main.c -o main.o
gcc -O2 math_ops.o main.o -o no_lto
nm no_lto | grep -E "square|cube|unused"

0000000000401130 T cube
0000000000401110 T square
0000000000401150 T unused_function

כל שלוש הפונקציות נמצאות בקובץ, כולל unused_function שאף אחד לא קורא לה. הלינקר לא מסיר פונקציות שלא בשימוש (ב-default). גם square ו-cube לא הוטמעו ב-main כי הקומפיילר קימפל כל קובץ בנפרד ולא ראה את הגדרת הפונקציות כשקימפל את main.c.

1. עם LTO:

gcc -O2 -flto -c math_ops.c -o math_ops_lto.o
gcc -O2 -flto -c main.c -o main_lto.o
gcc -O2 -flto math_ops_lto.o main_lto.o -o with_lto
nm with_lto | grep -E "square|cube|unused"

ייתכן ש:
- unused_function נעלמה (הוסרה כי אף אחד לא קורא לה)
- square ו-cube נעלמו (הוטמעו ב-main)

1. גודל:

ls -la no_lto with_lto

with_lto יהיה קטן יותר כי קוד מיותר הוסר.

1. באסמבלי של main:

בלי LTO:

main:
    ...
    movl    $5, %edi
    call    square          ; קריאה לפונקציה
    ...
    movl    $3, %edi
    call    cube            ; קריאה לפונקציה
    ...

עם LTO:

main:
    ...
    ; square(5) = 25, cube(3) = 27 - מחושב בקומפילציה!
    movl    $25, %esi
    movl    $27, %edx
    leaq    .LC0(%rip), %rdi
    call    printf
    ...

עם LTO, הקומפיילר ראה את ההגדרה של square ו-cube, הטמיע אותן, ואז ביצע constant folding - כל החישוב נעשה בזמן קומפילציה. ב-main לא נשאר שום חישוב חוץ מהקריאה ל-printf עם הקבועים 25 ו-27.