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

הקדמה¶

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

למה זה חשוב?
- הנדסה הפוכה (פרק 7) - כשקוראים אסמבלי של תוכנית מקומפלת, האסמבלי לא תמיד נראה כמו הקוד המקורי. הקומפיילר שינה אותו. אם מבינים אילו אופטימיזציות הקומפיילר עושה, קל יותר לשחזר את הכוונה המקורית.
- דיבוג - לפעמים באג "נעלם" ברמת אופטימיזציה מסוימת. הבנת האופטימיזציות עוזרת להבין למה.
- כתיבת קוד - הבנת מה הקומפיילר יודע לעשות מאפשרת לכתוב קוד ברור ולתת לקומפיילר לטפל בביצועים.

קיפול קבועים - constant folding¶

הקומפיילר מחשב ביטויים קבועים בזמן קומפילציה במקום בזמן ריצה:

int x = 3 + 4;          // הקומפיילר שם 7 ישירות
int y = 60 * 60 * 24;   // הקומפיילר שם 86400
int z = sizeof(int) * 8; // הקומפיילר שם 32

באסמבלי של -O0:

movl    $3, -4(%rbp)
addl    $4, -4(%rbp)    ; חישוב בזמן ריצה

באסמבלי של -O2:

movl    $7, -4(%rbp)    ; התוצאה מחושבת מראש

גם ביטויים מורכבים יותר:

if (sizeof(long) == 8) {
    // קוד ל-64 ביט
} else {
    // קוד ל-32 ביט
}

הקומפיילר יודע ש-sizeof(long) הוא קבוע (8 ב-64 ביט), אז הוא מסיר את ה-if לחלוטין ומשאיר רק את הענף הנכון.

הפצת קבועים - constant propagation¶

אם הקומפיילר יודע שמשתנה מקבל ערך קבוע, הוא יכול להחליף את כל השימושים בו בערך עצמו:

int x = 5;
int y = x * 3;    // הקומפיילר יודע ש-x = 5, אז y = 15
int z = y + x;    // y = 15, x = 5, אז z = 20

ב--O2, כל המשתנים יוחלפו בקבועים. אם x, y ו-z לא משתנים אחר כך, הקומפיילר אפילו ימחק את ההשמות המקוריות.

הסרת קוד מת - dead code elimination¶

הקומפיילר מסיר קוד שלעולם לא ירוץ, או שהתוצאה שלו לא משמשת:

int dead_code() {
    int x = compute_something();  // נמחק ב-O2
    int y = x * 2;                // נמחק ב-O2
    return 42;                    // רק זה נשאר
}

המשתנים x ו-y מחושבים אבל התוצאה שלהם לא משמשת (הפונקציה מחזירה 42 בלי קשר). ב--O2 הקומפיילר מסיר את החישובים. הפונקציה הופכת ל:

dead_code:
    movl    $42, %eax
    ret

שימו לב: אם ל-compute_something יש תופעות לוואי (side effects) כמו כתיבה לקובץ או שינוי משתנה גלובלי, הקומפיילר לא יסיר את הקריאה - כי ההסרה תשנה את ההתנהגות.

גם קוד שלא ניתן להגיע אליו מוסר:

void f() {
    return;
    printf("This never runs\n");  // dead code - מוסר
}

הטמעת פונקציות - function inlining¶

במקום לבצע call לפונקציה, הקומפיילר מעתיק את גוף הפונקציה למקום הקריאה:

static int square(int x) {
    return x * x;
}

int main() {
    int a = square(5);   // במקום call, ישים: a = 5 * 5 = 25
    int b = square(a);
}

ב--O2, הקומפיילר ישתול את גוף square ישירות, ואז עם constant folding ו-constant propagation:

main:
    ; a = 25 (קבוע, חושב בזמן קומפילציה)
    ; b = 25 * 25 = 625 (גם קבוע!)
    movl    $625, %eax
    ...

מילת המפתח inline¶

inline int add(int a, int b) {
    return a + b;
}

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

הכפייה - always_inline¶

__attribute__((always_inline))
static inline int critical_add(int a, int b) {
    return a + b;
}

ה-__attribute__((always_inline)) מכריח את הקומפיילר להטמיע את הפונקציה תמיד, גם ב--O0.

אופטימיזציות לולאות - loop optimizations¶

פריסת לולאה - loop unrolling¶

הקומפיילר מכפיל את גוף הלולאה כדי להפחית את מספר הסתעפויות:

// לפני:
for (int i = 0; i < 8; i++) {
    arr[i] = 0;
}

// אחרי unrolling (מה שהקומפיילר עושה ב-O3):
arr[0] = 0; arr[1] = 0; arr[2] = 0; arr[3] = 0;
arr[4] = 0; arr[5] = 0; arr[6] = 0; arr[7] = 0;

למה זה מהיר יותר? כי כל איטרציה של לולאה דורשת:
- הגדלת מונה (i++)
- בדיקת תנאי (i < 8)
- הסתעפות מותנית (branch)

אם "נפרוש" את הלולאה, חוסכים את ה-overhead הזה.

הוצאת חישוב מחוץ ללולאה - loop-invariant code motion¶

// לפני:
for (int i = 0; i < n; i++) {
    arr[i] = x * y + i;  // x * y מחושב שוב ושוב!
}

// אחרי (מה שהקומפיילר עושה):
int temp = x * y;  // חושב פעם אחת מחוץ ללולאה
for (int i = 0; i < n; i++) {
    arr[i] = temp + i;
}

הקומפיילר מזהה ש-x * y לא משתנה בתוך הלולאה ומוציא את החישוב החוצה.

הפחתת עוצמה - strength reduction¶

החלפת פעולה יקרה בפעולה זולה:

// לפני:
for (int i = 0; i < n; i++) {
    arr[i * 4] = i;  // כפל בכל איטרציה
}

// אחרי:
int offset = 0;
for (int i = 0; i < n; i++) {
    arr[offset] = i;
    offset += 4;      // חיבור במקום כפל
}

חיבור מהיר יותר מכפל במעבד, אז הקומפיילר מחליף i * 4 בחיבור מצטבר של 4.

וקטוריזציה אוטומטית - auto-vectorization¶

הקומפיילר משתמש בהוראות SIMD (כמו SSE/AVX) כדי לעבד מספר אלמנטים במקביל:

// לפני:
for (int i = 0; i < 1024; i++) {
    c[i] = a[i] + b[i];
}

// מה שהקומפיילר עושה (קונספטואלית):
// עם AVX2, מעבד 8 ערכי int בו זמנית:
for (int i = 0; i < 1024; i += 8) {
    __m256i va = _mm256_load_si256(&a[i]);
    __m256i vb = _mm256_load_si256(&b[i]);
    __m256i vc = _mm256_add_epi32(va, vb);
    _mm256_store_si256(&c[i], vc);
}

ב--O3 או עם -ftree-vectorize, הקומפיילר מנסה לבצע וקטוריזציה אוטומטית. אפשר לראות אם הצליח:

gcc -O3 -ftree-vectorize -fopt-info-vec-optimized code.c

אופטימיזציית קריאה זנבית - tail call optimization¶

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

int factorial(int n, int acc) {
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);  // tail call - הקריאה היא הדבר האחרון
}

ב--O2, הקומפיילר מזהה שזו קריאה זנבית והופך את הרקורסיה ללולאה:

factorial:
.L2:
    cmpl    $1, %edi
    jle     .L1
    imull   %edi, %esi
    subl    $1, %edi
    jmp     .L2          ; jmp במקום call - לא צורך frame חדש!
.L1:
    movl    %esi, %eax
    ret

זה מונע stack overflow ברקורסיה עמוקה.

אופטימיזציית ערך חזרה - RVO/NRVO¶

כש-C מחזיר struct, בדרך כלל הוא מועתק. אבל הקומפיילר יכול לבנות את הstruct ישירות במקום הקריאה:

struct Point {
    double x, y, z;
};

struct Point create_point(double x, double y, double z) {
    struct Point p;
    p.x = x;
    p.y = y;
    p.z = z;
    return p;  // בלי אופטימיזציה: מעתיק 24 bytes
}

int main() {
    struct Point pt = create_point(1.0, 2.0, 3.0);
    // עם RVO: הקומפיילר בונה את pt ישירות, בלי העתקה
}

מילת המפתח volatile¶

מילת המפתח volatile אומרת לקומפיילר: אל תבצע אופטימיזציה על הגישה למשתנה הזה.

volatile int *hardware_reg = (volatile int *)0xFFFF0000;

while (*hardware_reg == 0) {
    // ממתינים שהחומרה תשנה את הערך
}

בלי volatile, הקומפיילר עלול להוציא את הקריאה מהלולאה:

// מה שהקומפיילר עלול לעשות בלי volatile:
int temp = *hardware_reg;  // קורא פעם אחת
while (temp == 0) {
    // לולאה אינסופית! temp לעולם לא ישתנה
}

עם volatile, הקומפיילר חייב לקרוא מהזיכרון בכל פעם מחדש.

שימושים ל-volatile:
- Memory-mapped I/O - רגיסטרים של חומרה שמשתנים מבחוץ
- מטפלי סיגנלים - signal handlers - משתנה שמשתנה בhandler
- משתנים משותפים - בין threads (אם כי atomic עדיף)

מילת המפתח restrict¶

מילת המפתח restrict אומרת לקומפיילר: שני הפוינטרים האלה לא מצביעים על אותו זיכרון (no aliasing).

void add_arrays(int *restrict dest, const int *restrict src, int n) {
    for (int i = 0; i < n; i++) {
        dest[i] += src[i];
    }
}

בלי restrict, הקומפיילר חייב להניח ש-dest ו-src עלולים להצביע על אותו זיכרון (או על זיכרון חופף). זה מונע ממנו לבצע אופטימיזציות מסוימות כמו וקטוריזציה.

עם restrict, הקומפיילר יודע שהם נפרדים ויכול לבצע אופטימיזציות אגרסיביות - למשל לקרוא כמה ערכים מ-src מראש לפני שכותב ל-dest.

הפונקציה memcpy מוגדרת עם restrict (לכן אסור שהזיכרון יחפוף). הפונקציה memmove לא - ולכן היא איטית יותר אבל בטוחה גם עם חפיפה.

תכונות פונקציה - function attributes¶

// pure - הפונקציה לא משנה שום state חוץ מערך ההחזרה
// (יכולה לקרוא משתנים גלובליים)
__attribute__((pure))
int compute_hash(const char *str);

// const - כמו pure, אבל לא קוראת אפילו משתנים גלובליים
// (תלויה רק בארגומנטים)
__attribute__((const))
int square(int x);

אם פונקציה מסומנת כ-pure או const, הקומפיילר יכול:
- לא לקרוא לה שוב עם אותם ארגומנטים (caching)
- להוציא קריאה מלולאה אם הארגומנטים לא משתנים
- למחוק קריאה אם התוצאה לא בשימוש

השמטת frame pointer - omit frame pointer¶

gcc -fomit-frame-pointer code.c

בדרך כלל, כל פונקציה משתמשת ב-rbp כ-frame pointer (מצביע לתחתית ה-stack frame). עם -fomit-frame-pointer, הקומפיילר לא שומר את rbp ומשתמש בו כרגיסטר רגיל - מה שנותן רגיסטר נוסף לשימוש.

החיסרון: דיבוג קשה יותר, כי בלי frame pointer קשה ל-GDB ולכלי profiling לעקוב אחרי מחסנית הקריאות (stack unwinding).

ב--O2 ומעלה, זה בדרך כלל מופעל אוטומטית.

אופטימיזציה מונחית פרופיל - PGO - profile-guided optimization¶

רעיון חכם: לתת לקומפיילר נתונים אמיתיים על ההתנהגות של התוכנית כדי שיקבל החלטות טובות יותר.

# שלב 1: קימפול עם איסוף נתונים
gcc -fprofile-generate -O2 program.c -o program

# שלב 2: הרצת התוכנית (נוצרים קבצי .gcda עם סטטיסטיקות)
./program

# שלב 3: קימפול מחדש עם שימוש בנתונים
gcc -fprofile-use -O2 program.c -o program_optimized

מה הקומפיילר לומד מהנתונים:
- אילו ענפי if נלקחים לעתים קרובות (branch prediction hints)
- אילו פונקציות "חמות" ושווה להטמיע
- כמה פעמים כל לולאה רצה (האם שווה לעשות unrolling)
- אילו ערכים נפוצים בswitch

PGO יכול לשפר ביצועים ב-10-30% בתוכניות אמיתיות.

אופטימיזציית זמן לינקוג' - LTO - link-time optimization¶

בדרך כלל, הקומפיילר מבצע אופטימיזציות על כל קובץ בנפרד. עם LTO, האופטימיזציות קורות בזמן הלינקוג' - כשהלינקר רואה את כל הקוד ביחד:

gcc -flto -O2 file1.c file2.c file3.c -o program

מה LTO מאפשר:
- הטמעת פונקציות בין קבצים שונים
- הסרת פונקציות שלא נקראות מאף מקום
- אופטימיזציות שדורשות ראיה גלובלית

החיסרון: הקימפול איטי יותר (הקומפיילר צריך לעבד את כל הקוד ביחד).

כלי Godbolt - Compiler Explorer¶

האתר https://godbolt.org הוא כלי מעולה להבנת אופטימיזציות. אפשר:
- לכתוב קוד C בצד שמאל
- לראות את האסמבלי בצד ימין
- להחליף בין רמות אופטימיזציה בזמן אמת
- להשוות בין קומפיילרים שונים (gcc, clang, MSVC)

מומלץ מאוד להשתמש בו כשלומדים את הנושא.

השוואה מעשית - O0 מול O2¶

ניקח דוגמה ונראה את ההבדל:

int sum_array(int *arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

באסמבלי של -O0 (ללא אופטימיזציה):

.L

href="#__codelineno-28-1">sum_array: pushq %rbp movq %rsp, %rbp movq %rdi, -24(%rbp) ; שומר arr על המחסנית movl %esi, -28(%rbp) ; שומר n על המחסנית movl $0, -4(%rbp) ; sum = 0 movl $0, -8(%rbp) ; i = 0 2: movl -8(%rbp), %eax ; טוען i cmpl -28(%rbp), %eax ; i < n jge .L3 movl -8(%rbp), %eax ; טוען i שוב cltq leaq 0(,%rax,4), %rdx ; חישוב offset movq -24(%rbp), %rax ; טוען arr addq %rdx, %rax movl (%rax), %eax ; טוען arr[i] addl %eax, -4(%rbp) ; sum += arr[i] addl $1, -8(%rbp) ; i++ jmp .L2 >.L3: movl -4(%rbp), %eax ; return sum popq %rbp ret

באסמבלי של -O2 (עם אופטימיזציה):

sum_array:
    testl   %esi, %esi         ; n == 0?
    jle     .L1
    leal    -1(%rsi), %eax
    leaq    4(%rdi,%rax,4), %rdx
    xorl    %eax, %eax         ; sum = 0
.L2:
    addl    (%rdi), %eax       ; sum += *arr
    addq    $4, %rdi           ; arr++
    cmpq    %rdx, %rdi
    jne     .L2
    ret
.L1:
    xorl    %eax, %eax
    ret

ההבדלים:
- אין frame pointer - rbp לא בשימוש
- רגיסטרים במקום מחסנית - sum ו-i נשמרים ברגיסטרים, לא על המחסנית
- פחות גישות לזיכרון - אין load/store מיותרים
- pointer arithmetic - במקום לחשב arr + i*4 בכל איטרציה, פשוט מקדם את הpointer
- פחות הוראות - 10 הוראות בלולאה במקום 15

סיכום¶

אופטימיזציה	מה עושה	דגל
קיפול קבועים - constant folding	מחשב ביטויים קבועים בקומפילציה	O1 ומעלה
הפצת קבועים - constant propagation	מחליף משתנים בערכם הקבוע	O1 ומעלה
הסרת קוד מת - dead code elimination	מסיר קוד שלא משפיע	O1 ומעלה
הטמעת פונקציות - function inlining	מעתיק גוף פונקציה במקום call	O2 ומעלה
פריסת לולאה - loop unrolling	מכפיל גוף לולאה	O3
הוצאת חישוב מלולאה - LICM	מוציא חישוב קבוע מחוץ ללולאה	O2 ומעלה
הפחתת עוצמה - strength reduction	כפל -> חיבור	O2 ומעלה
וקטוריזציה - auto-vectorization	שימוש ב-SIMD	O3
קריאה זנבית - tail call optimization	רקורסיה -> לולאה	O2 ומעלה
פרופיל - PGO	אופטימיזציה מבוססת נתוני ריצה	ידני
זמן לינקוג' - LTO	אופטימיזציה בין קבצים	-flto

הקומפיילר הוא כלי חכם מאוד. ברוב המקרים, עדיף לכתוב קוד ברור וקריא ולתת לקומפיילר לטפל בביצועים. אופטימיזציה ידנית בקוד C צריכה להגיע רק אחרי מדידה שמוכיחה שיש צוואר בקבוק.