فرم تخصیص ایستای منفرد
در طراحی کامپایلر، فرم تخصیص ایستای منفرد (به انگلیسی: Static single assignment form) یا همان SSA، یک ویژگی نمایش میانی است، که نیاز دارد هر متغیر قبل از استفاده، تعریف و تنها یکبار اختصاص داده شود. متغیرهای موجود در IR اصلی به چند دسته تقسیم میشوند؛ متغیرهای جدید که معمولاً با نام اصلی با یک زیرنویس در کتابها ذکر میشوند، بهطوری که هر تعریف، در دسته خاص خود میگنجد. در روش SSA، زنجیرههای استفاده از تعریف واضح و روشن است و هر یک از آنها یک عنصر یکتا دارد. هر متغیری در متن برنامه دقیقاً یک مقدار را اخذ میکند. (اما این به این معنا نیست که نمیتوانیم در برنامه حلقه داشته باشیم)
SSA در سال ۱۹۸۸ توسط Barry K.Rosen ,Mark N.Wegman و F.Kenneth Zadeck ارائه شد. ران سیترون، ژان فرانتت و سه محقق قبلی IBM الگوریتمی را ایجاد کردند که میتواند فرم SSA را بهطور کارآمد محاسبه کند.
میتوان انتظار داشت که SSA را در یک کامپایلر برای Fortran یا C پیدا کنیم، در حالی که در کامپایلرهای زبانهای تابعی، مانند نمونههایی برای Scheme, ML و Haskell، از شیوه ادامهدادن (CPS) بهطور عمومی استفاده میشود. SSA رسماً با یک زیر مجموعه خوشرفتار از CPS (به استثنای روند کنترل غیر محلی)، معادل است که وقتی CPS به عنوان نمایندهٔ میانجی استفاده میشود، رخ نمیدهد؛ بنابراین بهینهسازیها و دگرگونیهای صورت گرفته در قالب یکی، بلافاصله روی دیگری اعمال میشوند.
مزایا
مزیت اصلی SSA این است که همزمان، نتایج انواع کامپایلر بهینهساز را بوسیله سادهسازی متغیرها ساده کرده و بهبود میبخشد. به عنوان مثال، این قطعه کد را در نظر بگیرید:
y := 1
y := 2
x := y
همانطور که قابل مشاهده است، تخصیص اوّل ضروری نیست و مقدار y در سطر سوم، از تخصیص دوم y بدست میآید. یک برنامه برای تشخیص این موضوع باید تجزیه و تحلیل دسترسی تعریف را انجام دهد. اما اگر این برنامه به شکل SSA باشد، هر دو مورد آنی و بیدرنگ هستند:
y1 := 1
y2 := 2
x1 := y2
برخی از بهینهسازی کامپایلرها در فرم SSA بهتر عمل میکند؛ انتشار شرطی مقدار ثابت(Conditional constant propagation) و عددگذاری سراسری متغیر (global value numbering) در فرمهای SSA سریعتر و کارآمدتر هستند.
الگوریتمهای بهینهسازی کامپایلر که با استفاده از SSA فعال شده یا قویاً بهبود داده شدهاند، عبارتند از:
- درهم کردن ثابت
- انتشار دامنه مقدار
- تکثیر ثابت شرطی پراکنده
- حذف کد مرده
- شماره گذاری جهانی مقدار
- حذف افزونگی جزئی
- کاهش قدرت
- تخصیص ثبات
تبدیل کردن به SSA
تبدیل کد معمولی به فرم SSA، در وهلهٔ اوّل جایگزین کردن هدف هر دستور با یک متغیر جدید و هر استفاده از متغیر با ورژنی از متغیر که به آن نقطه میرسد. برای مثال، گراف روند کنترلی زیر را در نظر بگیرید:
تغییر نام سمت چپ دستور " x ← x - 3 "و تغییر دستورها بعد از آن به x، برنامه را تغییر نمیدهد. این کار در SSA با ایجاد دو متغیر جدید x1 و x2 صورت میگیرد که هر یک فقط یکبار مقداردهی میشوند. به همین ترتیب، با اختصاص زیروندهای متمایز به سایر متغیرها چنین نتیجهای منجر میشود:
واضح است که هر کدام از موارد استفاده به کدام تعریف رجوع میکند؛ به جز متغیر y استفادهشده در بلوک پایینی که میتواند به هر کدام از y1 یا y2 اشاره کند؛ چرا که بستگی دارد کدام مسیر در روند کنترل طی کردهباشد. برای حل این مشکل، یک تابع ویژه به نام (Φ(Phi در آخرین بلوک درج میشود. این تابع، یک تعریف جدید از y تولید میکند که y3 نام دارد و بسته به آن که کدام مسیر قبلاً طی شده، مقدار y3 را برابر y1 یا y2 قرار میدهد.
اکنون، آخرین بلوک به سادگی میتواند از y3 استفاده کند و مقدار صحیح از هر مسیر، بدست میآید. استفاده از تابع Φ برای x لازم نیست؛ زیرا فقط یک نسخه از x، یعنی x2 به بلوک انتهایی میرسد. به عبارت دیگر، Φ(x2، x2) = x2. با داشتن یک گراف روند کنترل دلخواه، تشخیص این که کجا و برای کدام متغیرها از تابع Φ استفاده کنیم، میتواند بسیار دشوار باشد. اما این سؤال، یک راه حل کارآمد دارد که میتواند با استفاده از مفهومی به نام مرزهای تسلط محاسبه شود. در اکثر دستگاهها توابع Φ به عنوان دستور ماشین پیادهسازی نشدهاست. یک کامپایلر میتواند تابع Φ را برای هر عملیاتی که ورودی این تابع را تولید میکند، پیادهسازی کند. این کار به سادگی و با استفاده از همان مکان در حافظه به عنوان مقصد (یا همان ثبّات) انجام میشود. با این حال این رویکرد در شرایطی که چند عملیات به صورت همزمان ورودیهایی را برای یک تابع Φ تولید میکنند، کار نمیکند؛ همانطور که میتواند در ماشینهای wide-issue اتفاق بیفتد. معمولاً یک ماشین wide-issue یک دستور برای انتخاب دارد که توسط کامپایلر برای اجرای تابع Φ استفاده میشود. با توجه به Kenny Zadeck، زمانی که SSA که در تحقیقات IBM در دهه ۱۹۸۰ در حال توسعه بود، توابع Φ به عنوان توابع ساختگی شناخته شدهبودند. نام رسمی تابع Φ زمانی پذیرفتهشد که برای اولین بار در یک مقاله دانشگاهی انتشار یافت.
در واقع در فرم SSA گراف روند کنترل هیچ تفاوتی با حالت قبل ندارد. تنها از عملگر Φ برای تشخیص مقدار صحیح در محلهای به هم پیوستن در گراف استفاده میشود. دقت شود که لزوماً در تمامی محلهای اتصال نیازی به Φ نیست؛ اگر تعریف مشترکی از متغیر به گره برسد، نیازی به استفاده از آن نیست. ترجمه از فرم SSA به زبان ماشین، با مقادیر تکراری تعاریف همراه است که ممکن است باعث کاهش بازده شود. پس از ترجمه به فرم SSA، ۳ شرط زیر باید برای هر متغیر V در برنامه اصلی برقرار باشد:
- اگر دو مسیر ناتُهی از گره X و Y که (هر کدام تعریفی از V دارند) به مقصد مشترک P وجود داشته باشد، آن گاه P یک تابع بدیهی به شکل (v = φ(v, v, … , v دارد که تعداد آرگومانهای آن برابر با درجهٔ ورودی راس P است.
- هر مشاهدهٔ P در برنامهٔ اصلی یا یک تابع Φ در برنامهٔ جدید، باید با یک متغیر جدید Vi جایگزین شود تا به فرم SSA تبدیل شود.
- هر استفاده از V در هر کدام از مسیرهای کنترلی در برنامهٔ اصلی یا هر استفاده از Vi در برنامهٔ جدید، باید به مقدار مشابهی از V و Vi برسد.
محاسبه حداقل SSA با استفاده از مرزهای تسلط
در ابتدا به بررسی مفهوم سلطهگر (dominator) میپردازیم: در گراف روند کنترل گره A اکیداً بر گره متمایز B تسلط دارد اگر رسیدن به B بدون عبور از A امکانپذیر نباشد. این مفهوم بسیار پرکاربرد است؛ زیرا هر زمان به B رسیدیم، اطمینان داریم که تمامی کدهای بخش A اجرا شدهاست. در نتیجه A بر B تسلط دارد (B تحت سلطه A است) اگر A اکیداً بر B تسلط داشتهباشد یا A = B باشد.
حالا میتوانیم مرز تسلط را تعریف کنیم: گره B در مرز تسلط گره A است اگر A اکیداً بر B تسلط نداشتهباشد، اما بر پدر B تسلط داشته باشد. (ممکن است گره A، پدر B باشد. با توجه آن که هر گره بر خودش مسلط است و A نیز بر خودش مسلط است، گره B در مرز تسلط گره A خواهد بود) از دیدگاه A، این گرهها، در مسیرهای کنترلی دیگر (که از A نمیگذرند) زودتر از سایر گرههای آن ظاهر میشوند.
مرزهای تسلط مکانهای دقیقی را که در توابع Φ به آنها نیاز داریم، مییابند؛ اگر گره A یک متغیر خاص تعریف میکند، آن تعریف یا تعریف مجدد آن متغیر، به هر گرهی که A تسلط دارد، دسترسی مییابد. هنگامی که این گرهها را ترک کرده و وارد مرز تسلط میشویم، باید جریانهای دیگری که بر اساس تعاریف دیگری از همان متغیر ارائه میشود، در نظر بگیریم. علاوه بر این، در نمودار روند کنترل، تابع Φ دیگری برای سر و کار داشتن با تعاریف A مورد نیاز نیست و نمیتوان با کمتر از این تعداد تابع Φ، کار را انجام داد. کد زیر، یک الگوریتم برای محاسبه مجموعه مرزی تسلط است:
for each node b
dominance_frontier(b) := {}
for each node b
if the number of immediate predecessors of b ≥ 2
for each p in immediate predecessors of b
runner := p
while runner ≠ idom(b)
dominance_frontier(runner) := dominance_frontier(runner) ∪ { b }
runner := idom(runner)
توجه: در کد بالا، پدر گره n هر گره ای است که کنترل از آن به گره n داده میشود، و (idom(b گره ای است که بلافاصله بر گره b (یک مجموعه منفرد) تسلط مییابد.
الگوریتم کارآمد دیگری برای یافتن مرزهای تسلط بر هر گره وجود دارد. این الگوریتم در ابتدا در Cytron شرح دادهشد.
تغییراتی که موجب کاهش تعداد توابع Φ میشود
SSA کمینه، حداقل تعداد توابع Φ مورد نیاز را اضافه میکند تا از اختصاص دقیقاً یکبار هر اسم به یک مقدار اطمینان حاصل کند. همچنین هر ارجاع به یک اسم در برنامه اصلی میتواند به یک اسم یکتا ارجاع داشته باشد. این شرط به این علت است که کامپایلر بتواند برای هر عملوند درون یک دستور، یک اسم قرار دهد.
با این حال، برخی از این توابع ممکن است بلا استفاده یا به اصطلاح کد مرده باشند؛ به همین دلیل SSA کمینه، لزوماً کمترین تعداد Φ لازم برای یک تابع خاص را، ایجاد نمیکند. برای برخی از تجزیه و تحلیلها، این توابع اضافی هستند و در نتیجه کارایی را کاهش میدهند.
SSA هرسشده
SSA هرسشده بر اساس ملاحظات سادهای است؛ توابع Φ تنها برای متغیرهایی که بعد از اجرای Φ، مورد استفاده قرار گرفتهاند، لازم هستند. در اصطلاح به این متغیرها، «متغیرهای زنده» گفته میشود. اگر یک متغیر زنده نباشد، نتیجه تابع Φ مورد استفاده قرار نمیگیرد و مقداردهی هر متغیر بوسیله این تابع، مردهاست.
ساختار SSA هرسشده از تحلیل متغیر زنده برای تصمیمگیری درج یا حذف تابع Φ استفاده میکند. اگر نام متغیر اصلی در هنگام درج تابع Φ زنده نباشد، تابع Φ مورد استفاده قرار نمیگیرد و در نتیجه هرس میشود.
روش دیگر برای هرسکردن، حل مسئله به عنوان یک مسئله از بین بردن کد مردهاست. در نتیجه، یک تابع Φ زنده است اگر در یک برنامه بازنویسی شده باشد یا به عنوان ورودی به تابع Φ دیگری استفاده شود. هنگام وارد کردن فرم SSA، هر کاربرد آن به نزدیکترین تعریفی که بر آن اختصاص دارد، بازنویسی میشود. سپس، هر تابع Φ زنده منظور میشود اگر در نزدیکترین تعریفی که به آن اختصاص دارد، حداقل یکبار استفاده شده باشد یا حداقل یکبار به عنوان ورودی به تابع Φ دیگری استفاده شود.
SSA نیمه هرسشده
SSA نیمه هرسشده تلاش میکند تا تعداد توابع Φ را بدون متحملشدن هزینه بالا برای محاسبه اطلاعات متغیر زنده، کاهش دهد. این روش مبتنی بر ملاحظه زیر است:
اگر یک متغیر هیچگاه هنگام ورود به یک بلوک پایه زنده نباشد، هرگز به تابع Φ نیاز ندارد. در طول ساخت SSA، توابع Φ برای هر متغیر محلی در سطح یک بلوک، حذف میشود.
محاسبه مجموعه متغیرهای محلی در سطح یک بلوک، یک روش سادهتر و سریعتر از آنالیز کامل متغیرهای زنده است. این باعث میشود فرم SSA نیمه هرسشده از فرم SSA هرسشده کارآمدتر باشد. از طرف دیگر، فرم SSA نیمه هرسشده تعداد توابع Φ بیشتری دارد.
تبدیل فرم SSA
فرم SSA معمولاً برای اجرای مستقیم استفاده نمیشود و اغلب بالای IRهای دیگر که در ارتباط مستقیم باقی میماند، استفاده میشود. این امر با ساخت SSA، به عنوان مجموعه ای از توابع نگاشت قسمتهای IR موجود (اعم از بلوکهای پایه، دستورالعملها، عملوندها و …) به نقطه مقابل این قسمتها در SSA، کامل میشود. هنگامیکه دیگر به فرم SSA نیازی نباشد، این توابع نگاشت از بین رفته و فقط IR بهینه شده باقی میماند. انجام بهینهسازی روی فرم SSA معمولاً منجر به درهم آمیختگی SSA-Webs میشود؛ به این معنی که دستورالعملهایی در Φ وجود دارد که عملوندهای آن، ریشه یکسان ندارند. در چنین مواردی برای رسیدن به نتیجه مطلوب بوسیله SSA از الگوریتمهای رنگی استفاده میشود. الگوریتمهای پایه، برای هر مسیر، یک کپی تولید میکنند که باعث میشود سورس ریشه مختلف عملوند، به جای مقصد Φ در خود Φ قرار گیرد. الگوریتمهای دیگری حل مشکل درهم آمیختگی SSA با کپیهای کمتری نیز وجود دارد که بیشتر آنها از نمودارهای تداخل یا مقادیر تقریبی آنها استفاده میکنند.
کامپایلرهایی که از فرم SSA استفاده میکنند
فرم SSA یک توسعهٔ نسبتاً جدید در موضوع کامپایلر است. به همین دلیل، بسیاری از کامپایلرهای قدیمی فقط برای بخشی از فرایند کامپایل یا بهینهسازی از فرم SSA استفاده میکنند، اما اکثر آنها بر پایهٔ آن نیستند. نمونههایی از کامپایلرهایی که به فرم SSA بسیار متکی هستند عبارتند از:
- کامپایلر ETH Oberon-2 یکی از اولین پروژههای عمومی بود که از "GSA" استفاده کرد. (نوع دیگر از SSA)
- زیرساخت کامپایلر LLVM از فرم SSA برای کلیه مقادیر عددی ثبّاتها برای ارائه کد اصلی خود استفاده میکند. فرم SSA فقط هنگام تخصیص ثبّات حذف میشود.
- کامپایلر Open64 از فرم SSA در بهینهسازی مقیاس جهانی استفاده میکند؛ اگرچه کد، ابتدا به فرم SSA داده میشود و در آخر از فرم SSA خارج میشود. Open64 از افزونههای فرم SSA برای نشان دادن حافظه در فرم SSA مانند مقادیر عددی استفاده میکند.
- طبق نسخه ۴ (منتشر شده در آوریل 2005) GCC، مجموعه کامپایلر GNU، از SSA استفاده گستردهای میکند. frontends کد "GENERIC" را بوسیله gimplifier تولید میکند که در نهایت به کد "GIMPLE" تبدیل میشود. سپس بهینهسازیهای سطح بالا، روی فرم SSA کد GIMPLE اعمال میشوند. کد بدست آمده از بهینهسازی به RTL ترجمه میشود و در آن بهینهسازیهای سطح پایین انجام میشوند. معماری خاص Backend در نهایت RTL را به زبان اسمبلی برمیگرداند.
- منابع قابل دسترس IBM، از آرایهٔ توسعهیافته SSA استفاده میکنند که امکاناتی از قبیل تجزیه و تحلیل مقادیر، آرایهها و اشیا در یک چارچوب تعریف نشده را فراهم میسازد. تجزیه و تحلیل آرایهٔ توسعه یافتهٔ SSA تنها در بالاترین سطح بهینهسازی انجام میشود و روی قسمتهایی از کد که بیشتر اجرا میشود، اعمال میگردد.
- در سال ۲۰۰۲، محققان JikesRVM را برای اجرای استاندارد بایت کدهای جاوا و نوع امن SSA یا همان SafeTSA اصلاح کردند. این اصلاح، مزایای قابل توجهی در هنگتم استفاده از بایت کد SSA نشان داد.
- ماشین مجازی HotSpot Java Virtual Machine در کامپایلر JIT از یک زبان واسط مبتنی بر SSA استفاده میکند.
- زیرساخت کامپایلر ++Microsoft Visual C موجود در Microsoft Visual Studio 2015 Update 3 از SSA استفاده میکند.
- مونو در کامپایلر JIT خود، از SSA تحت عنوان Mini استفاده میکند.
- jackcc یک کامپایلر متن باز برای مجموعه دستورالعملهای دانشگاهی Jackal 3.0 است که برای نمایش میانی خود، از دستورها سادهٔ ۳ عملوندی SSA استفاده میکند. به عنوان یک گونهٔ جالب، توابع Φ را با یک دستورالعمل به یک دستور مشابه جایگزین میکند، که به تخصیصدهنده ثبّات دستور میدهد دامنه دو ثبّات فیزیکی مشابه یکسان قرار دهد.
- جدا کنندهٔ Boomerangاگرچه کامپایلر نیست، اما در نمای داخلی خود از فرم SSA استفاده میکند. SSA برای سادهسازی انتشار عبارات، شناسایی پارامترها، بازگشتها و… استفاده میشود.
- Portable.NET از SSA در کامپایلر JIT خود استفاده میکند.
- libFirm، یک نمایش میانی برای کامپایلرها و یک SSA کاملاً مبتنی بر گراف است. libFirm از فرم SSA برای تمام مقادیر عددی ثبّاتها استفاده میکند.
- کامپایلر Illinois Concert در سال ۱۹۹۴، از یک نوع SSA به نام SSU یا Static Single Use استفاده کرد. در این کامپایلر، هر متغیر هنگام تخصیص به یک مقدار تغییر نام میدهد.
- کامپایلر COINS از بهینهسازی فرم SSA استفاده میکند.
- موتور جاوا اسکریپت Mozilla Firefox SpiderMonkey از IR مبتنی بر SSA استفاده میکند.
- همانطور که در دسامبر ۲۰۱۰ اعلام شد، موتور Chromium V8 JavaScript در زیرساخت کامپایلر Crankshaft خود SSA را اجرا میکند.
- PyPy در کامپایلر JIT خود، از یک نمایشگر خطی SSA برای traceها استفاده میکند.
- ماشین مجازی اندرویدی Dalvik در کامپایلر JIT خود، از SSA استفاده میکند.
- کامپایلر بهینهساز جدید اندروید برای زمان اجرا، در IR آن از SSA استفاده میکند.
- کامپایلر MLton در یکی از زبانهای میانی خود از SSA استفاده میکند.
- LuaJIT از بهینهسازیهای مبتنی بر SSA استفاده میکند.
- کامپایلر PHP و Hack HHVM در IR خود، از SSA استفاده میکنند.
- کامپایلر R-Stream آزمایشگاه Reservoir از فرمهای غیر SSA ,SSA و SSI پشتیبانی میکند.
- Go ورژن ۱٫۷ فقط برای معماری x86-64 و ۱٫۸ برای کلیه معماریهای پشتیبانی شدهاست.
- WebKit در کامپایلرهای JIT خود از SSA استفاده میکند.
- Swift فرم SSA خود را بر پایه LLVM IR تحت عنوان SIL تعریف میکند.
- ارلانگ کامپایلر خود را در OTP 22.0 بازنویسی کرد تا از نمایش میانی مبتنی بر SSA استفاده کند.
منابع
- ↑ "Barry Rosen; Mark N. Wegman; F. Kenneth Zadeck (1988). "https://www.cse.wustl.edu/~cytron/cs531/Resources/Papers/valnum.pdf
- ↑ (Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K. ; Wegman, Mark N. & Zadeck, F. Kenneth (1991) ,http://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf
- ↑ https://iith.ac.in/~ramakrishna/fc5264/ssa-intro-construct.pdf
- ↑ http://llvm.org/devmtg/2007-05/05-Lewycky-Predsimplify.pdf
- ↑ F. Kenneth, "The Origin of Ф-Functions and the Name" of Zadeck
- ↑ https://iith.ac.in/~ramakrishna/fc5264/ssa-intro-construct.pdf page8
- ↑ ,Briggs, Preston; Cooper, Keith D. ; Harvey, Timothy J. ; Simpson, L. Taylor(1998). https://web.archive.org/web/20100607003509/http://www.cs.rice.edu/~harv/my_papers/ssa.pdf
- ↑ Boissinot, Benoit; Darte, Alain; Rastello, Fabrice; Dinechin, Benoît Dupont de; Guillon, Christophe (2008). , https://hal.inria.fr/inria-00349925
- ↑ "The Java HotSpot Performance Engine Architecture". Oracle Corporation.
- ↑ "Introducing a new, advanced Visual C++ code optimizer".
- ↑ "Illinois Concert Project". Archived from the original on 13 March 2014. Retrieved 30 January 2020.
- ↑ http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/
- ↑ "IonMonkey Overview".,
- ↑ "Bytecode Optimizations". the LuaJIT project.
- ↑ "HipHop Intermediate Representation (HHIR)".
- ↑ Ananian, C. Scott; Rinard, Martin (1999). "Static Single Information Form". CiteSeerX 10.1.1.1.9976.
- ↑ "Swift Intermediate Language".
- ↑ "Swift's High-Level IR: A Case Study of Complementing LLVM IR with Language-Specific Optimization, LLVM Developers Meetup 10/2015".
- ↑ "OTP 22.0 Release Notes".