LLVM מנקודת מבט של Go

פיתוח מהדר היא משימה קשה מאוד. אבל, למרבה המזל, עם הפיתוח של פרויקטים כמו LLVM, הפתרון לבעיה זו מפושט מאוד, מה שמאפשר אפילו למתכנת יחיד ליצור שפה חדשה שקרובה בביצועים ל-C. העבודה עם LLVM מסובכת בגלל העובדה שזה המערכת מיוצגת על ידי כמות עצומה של קוד, מצוידת בתיעוד מועט. כדי לנסות לתקן את החיסרון הזה, מחבר החומר, שאת תרגומו אנו מפרסמים היום, עומד להדגים דוגמאות לקוד שנכתב ב-Go ולהראות כיצד הם מתורגמים לראשונה ל לך SSA, ולאחר מכן ב-LLVM IR באמצעות המהדר tinyGO. קוד ה-Go SSA ו-LLVM IR עבר עריכה קלה כדי להסיר דברים שאינם רלוונטיים להסברים שניתנו כאן, על מנת להפוך את ההסברים למובנים יותר.

דוגמה ראשונה

הפונקציה הראשונה שאני הולך להסתכל עליה היא מנגנון פשוט להוספת מספרים:

func myAdd(a, b int) int{
    return a + b
}

פונקציה זו פשוטה מאוד, ואולי שום דבר לא יכול להיות פשוט יותר. זה מתורגם לקוד Go SSA הבא:

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

בתצוגה זו, הרמזים לסוג הנתונים ממוקמים בצד ימין וניתן להתעלם מהם ברוב המקרים.

דוגמה קטנה זו כבר מאפשרת לך לראות את המהות של היבט אחד של SSA. כלומר, בעת המרת קוד לצורת SSA, כל ביטוי מפורק לחלקים הבסיסיים ביותר מהם הוא מורכב. במקרה שלנו, הפקודה return a + b, למעשה, מייצג שתי פעולות: הוספת שני מספרים והחזרת התוצאה.

בנוסף, כאן אתה יכול לראות את הבלוקים הבסיסיים של התוכנית, בקוד זה יש רק בלוק אחד - בלוק הכניסה. נדבר יותר על בלוקים בהמשך.

קוד Go SSA ממיר בקלות ל-LLVM IR:

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

מה שאתה יכול לשים לב הוא שלמרות שמבנים תחביריים שונים משמשים כאן, מבנה הפונקציה הוא בעצם ללא שינוי. קוד LLVM IR קצת יותר חזק מקוד Go SSA, בדומה ל-C. כאן, בהצהרת הפונקציה, ראשית יש תיאור של סוג הנתונים שהוא מחזיר, סוג הארגומנט מצוין לפני שם הארגומנט. בנוסף, כדי לפשט את ניתוח ה-IR, לפני השמות של ישויות גלובליות מופיע הסמל @, ולפני שמות מקומיים יש סמל % (פונקציה נחשבת גם לישות גלובלית).

דבר אחד שיש לשים לב לקוד זה הוא שהחלטת הסוג של Go int, שיכול להיות מיוצג כערך של 32 סיביות או 64 סיביות, בהתאם למהדר ולמטרת ההידור, מתקבל כאשר LLVM מייצר את קוד ה-IR. זו אחת הסיבות הרבות לכך שקוד IR של LLVM אינו, כפי שאנשים רבים חושבים, בלתי תלוי בפלטפורמה. קוד כזה, שנוצר עבור פלטפורמה אחת, לא ניתן פשוט לקחת ולהרכיב עבור פלטפורמה אחרת (אלא אם כן אתה מתאים לפתרון בעיה זו בזהירות יתרה).

נקודה מעניינת נוספת שכדאי לציין היא שהסוג i64 אינו מספר שלם בסימן: הוא ניטרלי מבחינת ייצוג הסימן של המספר. בהתאם להוראה, זה יכול לייצג גם מספרים חתומים וגם לא חתומים. במקרה של ייצוג פעולת החיבור, זה לא משנה, ולכן אין הבדל בעבודה עם מספרים חתומים או לא חתומים. כאן אני רוצה לציין שבשפת C, הצפת משתנה של מספר שלם בסימן מובילה להתנהגות לא מוגדרת, ולכן ה-frontend Clang מוסיף דגל לפעולה nsw (ללא עטיפה חתומה), מה שאומר ל-LLVM שהיא יכולה להניח שהתוספת לעולם אינה עולה על גדותיה.

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

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

דוגמה שניה

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

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

קוד זה ממיר לקוד Go SSA הבא:

func sum(numbers []int) int:
entry:
    jump for.loop
for.loop:
    t0 = phi [entry: 0:int, for.body: t6] #n                       int
    t1 = phi [entry: 0:int, for.body: t7] #i                       int
    t2 = len(numbers)                                              int
    t3 = t1 < t2                                                  bool
    if t3 goto for.body else for.done
for.body:
    t4 = &numbers[t1]                                             *int
    t5 = *t4                                                       int
    t6 = t0 + t5                                                   int
    t7 = t1 + 1:int                                                int
    jump for.loop
for.done:
    return t0

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

למעשה, כאן ניתן לשים לב לעובדה שהתוכנה אינה מחולקת לבלוקים באמצעות פלטה מתולתלת (כמו במשפחת השפות C). הוא מחולק על ידי תוויות, המזכירות שפות אסמבלינג, ומוצג בצורה של בלוקים בסיסיים. ב-SSA, בלוקים בסיסיים מוגדרים כרצפים רציפים של קוד שמתחילים בתווית ומסתיימים בהוראות השלמת בלוק בסיסיות, כגון - return и jump.

פרט מעניין נוסף של קוד זה מיוצג על ידי ההוראה phi. ההוראות די חריגות ועשויות לקחת קצת זמן להבין. זכור את זה SSA הוא קיצור של Static Single Assignment. זהו ייצוג ביניים של הקוד המשמש את המהדרים, שבו לכל משתנה מוקצה ערך פעם אחת בלבד. זה נהדר לביטוי פונקציות פשוטות כמו הפונקציה שלנו myAddמוצג לעיל, אך אינו מתאים לפונקציות מורכבות יותר כגון הפונקציה הנדונה בסעיף זה sum. במיוחד משתנים משתנים במהלך ביצוע הלולאה i и n.

SSA עוקף את ההגבלה על הקצאת ערכי משתנים פעם אחת באמצעות מה שנקרא הוראה phi (שמו נלקח מהאלפבית היווני). העובדה היא שכדי שייצוג SSA של קוד יופק עבור שפות כמו C, אתה צריך לנקוט בכמה טריקים. התוצאה של קריאת הוראה זו היא הערך הנוכחי של המשתנה (i או n), ורשימת בלוקים בסיסיים משמשת כפרמטרים שלה. לדוגמה, שקול הוראה זו:

t0 = phi [entry: 0:int, for.body: t6] #n

המשמעות שלו היא כדלקמן: אם הבלוק הבסיסי הקודם היה בלוק entry (קלט), אז t0 הוא קבוע 0, ואם הבלוק הבסיסי הקודם היה for.body, אז אתה צריך לקחת את הערך t6 מהגוש הזה. כל זה אולי נראה די מסתורי, אבל המנגנון הזה הוא מה שגורם ל-SSA לעבוד. מנקודת מבט אנושית, כל זה מקשה על הבנת הקוד, אך העובדה שכל ערך מוקצה רק פעם אחת מקלה בהרבה על אופטימיזציות רבות.

שים לב שאם אתה כותב מהדר משלך, בדרך כלל לא תצטרך להתמודד עם דברים מהסוג הזה. אפילו קלאנג לא מייצר את כל ההוראות האלה phi, הוא משתמש במנגנון alloca (זה דומה לעבודה עם משתנים מקומיים רגילים). לאחר מכן, בעת הפעלת כרטיס אופטימיזציה של LLVM נקרא mem2reg, הוראות alloca הומר לטופס SSA. עם זאת, TinyGo מקבלת קלט מ- Go SSA, שבאופן נוח, כבר הומר לצורת SSA.

חידוש נוסף של קטע קוד הביניים הנדון הוא שגישה לרכיבי פרוסה לפי אינדקס מיוצגת בצורה של פעולת חישוב הכתובת ופעולה של זיהוי המצביע המתקבל. כאן אתה יכול לראות את התוספת הישירה של קבועים לקוד ה-IR (לדוגמה - 1:int). בדוגמה עם הפונקציה myAdd זה לא היה בשימוש. כעת, לאחר שהורדנו את התכונות הללו, בואו נסתכל על מה שהקוד הזה הופך כאשר הומר לצורת LLVM IR:

define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
  br label %for.loop

for.loop:                                         ; preds = %for.body, %entry
  %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
  %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
  %2 = icmp slt i64 %1, %len
  br i1 %2, label %for.body, label %for.done

for.body:                                         ; preds = %for.loop
  %3 = getelementptr i64, i64* %ptr, i64 %1
  %4 = load i64, i64* %3
  %5 = add i64 %0, %4
  %6 = add i64 %1, 1
  br label %for.loop

for.done:                                         ; preds = %for.loop
  ret i64 %0
}

כאן, כמו בעבר, נוכל לראות את אותו מבנה, הכולל מבנים תחביריים נוספים. למשל בשיחות phi ערכים ותוויות הוחלפו. עם זאת, יש כאן משהו שכדאי לשים אליו לב במיוחד.

מלכתחילה, כאן אתה יכול לראות חתימת פונקציה שונה לחלוטין. LLVM אינו תומך בפרוסות, וכתוצאה מכך, כאופטימיזציה, מהדר TinyGo שיצר את קוד הביניים הזה פיצל את התיאור של מבנה הנתונים הזה לחלקים. זה יכול לייצג שלושה רכיבי פרוסה (ptr, len и cap) כמבנה (struct), אך ייצוגם כשלוש ישויות נפרדות מאפשר אופטימיזציות מסוימות. מהדרים אחרים עשויים לייצג את הפרוסה בדרכים אחרות, בהתאם למוסכמות הקריאה של פונקציות פלטפורמת היעד.

תכונה מעניינת נוספת של קוד זה היא השימוש בהוראה getelementptr (לעתים קרובות מקוצר GEP).

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

int* sliceptr(int *ptr, int index) {
    return &ptr[index];
}

או עם המקבילה הבאה לזה:

int* sliceptr(int *ptr, int index) {
    return ptr + index;
}

הדבר החשוב ביותר כאן הוא שההוראות getelementptr אינו מבצע פעולות הרחקה. זה רק מחשב מצביע חדש על סמך הקיים. אפשר לקחת את זה כהוראות mul и add ברמת החומרה. אתה יכול לקרוא עוד על הוראות GEP כאן.

תכונה מעניינת נוספת של קוד ביניים זה היא השימוש בהוראה icmp. זוהי הוראה כללית המשמשת ליישום השוואות מספרים שלמים. התוצאה של הוראה זו היא תמיד ערך מסוג i1 - ערך לוגי. במקרה זה, מתבצעת השוואה באמצעות מילת המפתח slt (חתום פחות מ), מכיוון שאנו משווים שני מספרים שיוצגו בעבר על ידי הטיפוס int. אם היינו משווים שני מספרים שלמים ללא סימנים, אז היינו משתמשים icmp, ומילת המפתח שבה נעשה שימוש בהשוואה תהיה ult. כדי להשוות מספרי נקודה צפה, נעשה שימוש בהוראה אחרת, fcmp, שעובד בצורה דומה.

תוצאות של

אני מאמין שבחומר זה כיסיתי את התכונות החשובות ביותר של LLVM IR. כמובן, יש כאן הרבה יותר. בפרט, ייצוג הביניים של הקוד עשוי להכיל הערות רבות המאפשרות מעברי אופטימיזציה לקחת בחשבון תכונות מסוימות של הקוד המוכרות לקומפיילר שאינן יכולות להתבטא אחרת ב-IR. לדוגמה, זהו דגל inbounds הוראות GEP, או דגלים nsw и nuw, שניתן להוסיף להוראות add. אותו דבר לגבי מילת המפתח private, המציין למיטוב שהפונקציה שהוא מסמן לא תופנה מחוץ ליחידת ההידור הנוכחית. זה מאפשר הרבה אופטימיזציות בין-פרוצדורליות מעניינות כמו ביטול טיעונים שאינם בשימוש.

אתה יכול לקרוא עוד על LLVM ב תיעוד, שאליו תתייחס לעתים קרובות בעת פיתוח מהדר משלך מבוסס LLVM. כאן מַנהִיגוּת, שמסתכל על פיתוח מהדר לשפה פשוטה מאוד. שני מקורות המידע הללו יהיו שימושיים עבורך בעת יצירת מהדר משלך.

קוראים יקרים! האם אתה משתמש ב-LLVM?

מקור: www.habr.com