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 را تولید می کند پذیرفته می شود. این یکی از دلایل زیادی است که کد LLVM IR، همانطور که بسیاری فکر می‌کنند، مستقل از پلتفرم نیست. چنین کدی که برای یک پلتفرم ایجاد شده است، نمی تواند به سادگی برای پلتفرم دیگری گرفته و کامپایل شود (مگر اینکه برای حل این مشکل مناسب باشید. با دقت زیاد).

نکته جالب دیگری که شایان ذکر است این است که نوع i64 یک عدد صحیح علامت دار نیست: از نظر نشان دادن علامت عدد خنثی است. بسته به دستورالعمل، می تواند هر دو اعداد امضا شده و بدون علامت را نشان دهد. در مورد نمایش عمل جمع، این مهم نیست، بنابراین تفاوتی در کار با اعداد علامت دار یا بدون علامت وجود ندارد. در اینجا می‌خواهم توجه داشته باشم که در زبان C، سرریز کردن یک متغیر عدد صحیح علامت‌دار منجر به رفتار نامشخص می‌شود، بنابراین جلوی 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. دستورالعمل ها کاملاً غیرعادی هستند و ممکن است درک آن مدتی طول بکشد. به یاد بیاور S.S.A. مخفف 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 کار کند. از منظر انسانی، همه اینها درک کد را دشوار می کند، اما این واقعیت که هر مقدار فقط یک بار اختصاص داده می شود، بسیاری از بهینه سازی ها را بسیار آسان تر می کند.

توجه داشته باشید که اگر کامپایلر خود را بنویسید، معمولاً مجبور نخواهید بود با این نوع موارد سر و کار داشته باشید. حتی Clang همه این دستورالعمل ها را تولید نمی کند 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