فرم تخصیص ایستای منفرد

در طراحی کامپایلر ، فرم تخصیص ایستای منفرد یا همان SSA، یک ویژگی نمایش واسط (IR) است، که نیاز دارد که هر متغیر دقیقا یک بار assign شود، و هر متغیر قبل از استفاده تعریف می شود. متغیرهای موجود در 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 فعال شده یا قویاً بهبود داده شده‌اند، عبارتند از:

• انتشار ثابت‌ها
• انتشار دامنه مقدار
• تکثیر ثابت شرطی پراکنده
• حذف کد مرده
• شماره گذاری جهانی مقدار
• حذف افزونگی جزئی
• کاهش قدرت
• تخصیص ثبّات

تبدیل کردن به SSA

تبدیل کد معمولی به فرم SSA، در وهله‌ی اوّل یک مورد ساده‌ی جایگزینی هدف هر تخصیص با یک متغیر جدید، و جایگزین کردن هر استفاده از متغیر با "ورژن" متغیری که به آن نقطه می‌رسد. برای مثال، گراف روند کنترل زیر را در نظر بگیرید:

تغییر نام در سمت چپ "x $\leftarrow$ x - 3 "و تغییر استفاده‌های بعد از آن از x به آن نام جدید، برنامه را بدون تغییر می‌گذارد. این می‌تواند در SSA با ایجاد دو متغیر جدید مورد استفاده قرار گیرد: x ₁ و x ₂، که هر یک فقط یک بار مقداردهی می‌شود. به همین ترتیب، دادن زیروندهای متمایز به سایر متغیرها به چنین نتیجه‌ای می‌رسد:

واضح است که هر کدام از موارد استفاده به کدام تعریف رجوع می‌کند؛ به جز یک مورد: هر دو مورد استفاده از y در بلوک پایینی، می‌تواند به هر کدام از y ₁ یا y ₂ اشاره کند و بستگی دارد کدام مسیر را در روند کنترل طی کرده باشد. برای حل این مشکل، یک عبارت ویژه در آخرین بلوک درج شده است که تابع (Φ (Phi نامیده می‌شود. این عبارت یک تعریف جدید از y تولید می‌کند که y₃ نام دارد و بسته به این که کدام مسیر قبلا در جریان طی شده، مقدار y ₁ یا y ₂ را انتخاب می‌کند.

اکنون ، آخرین بلوک به سادگی می تواند از y ₃ استفاده کند، و مقدار صحیح از هر مسیری به دست می آید. استفاده از یک تابع Φ برای x لازم نیست؛ زیرا فقط یک نسخه از x، یعنی x ₂ به بلوک انتهایی می‌رسد، بنابراین مشکلی وجود ندارد. (به عبارت دیگر، Φ ( x ₂ ، x ₂ ) = x ₂ )

با داشتن یک گراف روند کنترل دلخواه، تشخیص این که کجا و برای کدام متغیرها از تابع Φ استفاده کنیم، می‌تواند بسیار دشوار باشد. اما این سوال کلی، یک راه حل کارآمد دارد که می‌تواند با استفاده از مفهومی به نام مرزهای تسلط محاسبه شود. (در زیر توضیح داده شده است.)

توابع Φ به عنوان عملیات ماشین در اکثر دستگاه‌ها پیاده نشده است. یک کامپایلر می تواند یک تابع Φ را به سادگی و با استفاده از همان مکان در حافظه (یا همان ثبّات) به عنوان مقصد برای هر عملیاتی که ورودی به تابع Φ ایجاد می کند‌، پیاده‌سازی کند. با این حال، این رویکرد زمانی که چند عملیات همزمان ورودی‌هایی را برای یک تابع Φ تولید کنند، کار نمیکند؛ همانطور که می تواند در ماشین های wide-issue اتفاق بیفتد. معمولا یک ماشین wide-issue دارای یک دستورالعمل انتخاب است که در چنین شرایطی توسط کامپایلر برای اجرای تابع Φ استفاده می‌شود.

با توجه به Kenny Zadeck، زمانی که SSA که در تحقیقات IBM در دهه 1980 در حال توسعه بود، توابع Φ در اصل به عنوان توابع ساختگی شناخته شده بودند. نام رسمی یک تابع Φ تنها زمانی پذیرفته شد که این کار برای اولین بار در یک مقاله دانشگاهی منتشر شد.

محاسبه حداقل SSA با استفاده از مرزهای تسلط

ابتدا، به مفهوم <i id="mwhg">سلطه گر (</i>dominator) نیاز داریم: می گوییم که گره A اکیداً بر گره متمایز B در گراف روند کنترل تسلط دارد، اگر رسیدن به B بدون عبور از A غیرممکن باشد. این پرکاربرد است، زیرا هر زمان به B رسیدیم، می‌دانیم که هر کد که در A است، اجرا شده است. ما می گوییم که A بر B تسلط دارد (B تحت سلطه A است) اگر A اکیداً بر B تسلط داشته باشد یا A = B باشد.

حالا ما می توانیم <i id="mwjA">مرز تسلط</i> را تعریف کنیم: گره B در مرز تسلط گره A است اگر A اکیدا بر B تسلط نداشته باشد، اما بر گره بلافاصله کنار B تسلط داشته باشد. (احتمالا گره A، گره بلافاصله کنار B باشد؛ سپس، به دلیل این که هر گره بر خودش مسلط می‌شود و گره A بر خودش مسلط می شود، گره B در مرز تسلط گره A خواهد بود.) از دیدگاه A ، این‌ها گره‌هایی هستند که در مسیرهای کنترل دیگر (که از A نمی گذرند) زودتر از سایر گره‌های آن ظاهر می‌شوند.

مرزهای تسلط مکان‌های دقیقی را که در آن به توابع Φ نیاز داریم می‌یابند: اگر گره A یک متغیر خاص را تعریف می‌کند، آن تعریف و آن تعریف به تنهایی (یا تعریف مجدد) به هر گرهی که A تسلط دارد، می‌رسد. فقط هنگامی که این گره ها را رها می کنیم و وارد مرز تسلط می شویم، باید جریان‌های دیگری را که تعاریف دیگری از همان متغیر به گره ارائه می دهند، در نظر بگیریم. علاوه بر این، هیچ تابع Φ دیگری در نمودار روند کنترل برای سر و کار داشتن با تعاریف A مورد نیاز نیست؛ و ما نمی توانیم با کمتر از این، کار را انجام دهیم.

کد زیر، یک الگوریتم برای محاسبه مجموعه مرزی تسلط است:

یک الگوریتم کارآمد برای یافتن مرزهای هر گره وجود دارد. این الگوریتم در ابتدا در 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 یک توسعه‌ی نسبتاً جدید در موضوع کامپایلر است. به همین دلیل، بسیاری از کامپایلرهای قدیمی فقط برای بخشی از فرآیند کامپایل یا بهینه سازی از فرم SSA استفاده می کنند، اما اکثر آن‌ها بر پایه‌ی آن نیستند. نمونه‌هایی از کامپایلرهایی که به فرم SSA بسیار متکی هستند عبارتند از:

• کامپایلر ETH Oberon-2 یکی از اولین پروژه‌های عمومی بود که از "GSA" استفاده کرد. (نوع دیگر از SSA)
• زیرساخت کامپایلر LLVM از فرم SSA برای کلیه مقادیر عددی ثبّات‌ها در ارائه کد اصلی خود استفاده می‌کند. (همه چیز به جز حافظه) فرم SSA فقط هنگام وقوع تخصیص ثبّات، در مراحل آخر کامپایل (اغلب در زمان پیوند) حذف می‌شود.
• کامپایلر Open64 از فرم SSA در بهینه‌ساز مقیاس جهانی استفاده می کند، اگرچه کد ابتدا به فرم SSA وارد شده و پس از آن از فرم SSA خارج می شود. Open64 از افزونه های فرم SSA برای نشان دادن حافظه در فرم SSA مانند مقادیر عددی استفاده می کند.
• طبق نسخه 4 (منتشر شده در آوریل 2005) GCC ، مجموعه کامپایلر GNU ، از SSA استفاده گسترده‌ای می‌کند. frontends تولید کد " GENERIC " است که توسط "gimplifier" به کد " GIMPLE " تبدیل می شود. بهینه‌سازی‌های سطح بالا سپس روی فرم SSA "GIMPLE" اعمال می‌شوند. کد واسطه بهینه‌سازی شده‌ی بدست آمده سپس به RTL ترجمه می شود، که در آن بهینه‌سازی‌های سطح پایین اعمال می شود. معماری خاص (Backend) در نهایت RTL را به زبان اسمبلی بر می‌گردانند.
• ماشین مجازی جاوای متن‌باز قابل تطبیق IBM یا همان Jikes RVM ، از آرایه‌ی توسعه یافته‌ی SSA استفاده می‌کند که تجزیه و تحلیل مقیاس‌ها، آرایه ها و فیلدهای شی را در یک چارچوب تعریف نشده امکان پذیر می‌کند. تجزیه و تحلیل آرایه‌ی توسعه یافته‌ی SSA فقط در بیشترین سطح بهینه‌سازی فعال می‌شود، که در قسمت‌های بیشتر اجرا شده از کد اعمال می شود.
• در سال 2002، محققان اصلاح JikesRVM آی بی ام (به نام هالاپینیو در آن زمان) برای اجرای هر دو استاندارد فایل‌های کلاس جاوا بایت کد و نوع امن SSA (همان SafeTSA)، و مزایای قابل توجه عملکرد استفاده از بایت کد SSA را نشان داد.
• ماشین مجازی HotSpot Java Virtual Machine در کامپایلر JIT از یک زبان واسط مبتنی بر SSA استفاده می کند.
• زیرساخت کامپایلر Microsoft Visual C ++ موجود در Microsoft Visual Studio 2015 Update 3 از SSA استفاده می کند
• مونو از SSA در کامپایلر JIT خود به نام Mini استفاده می‌کند.
• jackcc یک کامپایلر متن باز برای مجموعه دستورالعمل‌های دانشگاهی Jackal 3.0 است. ب از یک کد ساده‌ی ۳ عملوندی با SSA برای نمایش میانی خود استفاده می‌کند. به عنوان یک گونه‌ی جالب، توابع Φ را با یک دستورالعمل به اصطلاح SAME جایگزین می‌کند، که به توزیع‌کننده‌ی ثبّات دستور می‌دهد دو دامنه زنده را در ثبّات فیزیکی مشابهی قرار دهد.
• اگرچه کامپایلر نیست، اما جدا کننده‌ی بومرنگ از فرم SSA در نمای داخلی خود استفاده می‌کند. SSA برای ساده‌سازی انتشار عبارات، شناسایی پارامترها و بازگشت‌ها، آنالیز نگهداری و سایر موارد استفاده می‌شود.
• Portable.NET از SSA در کامپایلر JIT خود استفاده می‌کند.
• libFirm، یک SSA کامل مبتنی بر گراف است که یک نمایش میانی برای کامپایلرهاست. libFirm از فرم SSA برای تمام مقادیر عددی ثبّات‌ها استفاده می‌کند؛ تا زمانی که کد به وسیله‌ی یک تخصیص‌دهنده‌ی ثبّات آگاه از SSA تولید بشود.
• کامپایلر Illinois Concert در حدود ۱۹۹۴ از یک نوع SSA به نام SSU یا Static Single Use استفاده کرد که هر متغیر را هنگام تخصیص یک مقدار، تغییر نام می‌دهد و هم چنین در هر متن شرطی که از آن متغیر استفاده می‌شود؛ اساس static single information form در بالا ذکر شد. فرم SSU در پایان نامه دکتری جان پلویواک ثبت شده است.
• کامپایلر COINS از بهینه سازی فرم SSA همان‌طور که در لینک زیر توضیح داده شده، استفاده می کند: http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/
• موتور جاوا اسکریپت Mozilla Firefox SpiderMonkey از IR مبتنی بر SSA استفاده می‌کند.
• موتور Chromium V8 JavaScript در زیرساخت کامپایلر Crankshaft خود SSA را اجرا می‌کند، همان‌طور که در دسامبر ۲۰۱۰ اعلام شد.
• PyPy از یک نمایشگر خطی SSA برای trace ها در کامپایلر JIT خود استفاده می‌کند.
• ماشین مجازی اندرویدی Dalvik در کامپایلر JIT خود از SSA استفاده می‌کند.
• اندروید را کامپایلر بهینه‌سازی جدید برای زمان اجرا اندروید با استفاده از SSA برای IR آن است.
• کامپایلر ML استاندارد MLton از SSA در یکی از زبان‌های میانی خود استفاده می‌کند.
• LuaJIT از بهینه‌سازی‌های مبتنی بر SSA استفاده‌ سنگین می‌کند.
• کامپایلر PHP و Hack HHVM از SSA در IR خود استفاده می‌کند.
• کامپایلر R-Stream آزمایشگاه Reservoir از فرم‌های غیر SSA (لیست چهار)، SSA و SSI (همان Static Single Information ) پشتیبانی می کند.
• گو (1.7: فقط برای معماری x86-64؛ 1.8: برای کلیه معماری های پشتیبانی شده).
• SPIR-V ، استاندارد زبان سایه‌زنی برای API گرافیکی Vulkan و زبان هسته برای API محاسبه OpenCL ، یک نمایش SSA است.
• درایورهای مختلف Mesa از طریق NIR ، نمایندگی SSA برای زبانهای سایه دار.
• WebKit از SSA در کامپایلرهای JIT استفاده می کند.
• Swift فرم SSA خود را بر پایه LLVM IR به نام SIL تعریف می کند. (Swift Intermediate Language).
• ارلانگ کامپایلر خود را در OTP 22.0 بازنویسی کرد تا "از نمای داخلی واسطه ای مبتنی بر استاتیک تک انتهایی (SSA) استفاده کند." با برنامه ریزی برای بهینه سازی بیشتر ساخته شده در پایه SSA در نسخه های بعد.

منابع

منابع عمومی

• Appel, Andrew W. (1999). Modern Compiler Implementation in ML. Cambridge University Press. ISBN 978-0-521-58274-2. Also available in Java (شابک ‎۰−۵۲۱−۸۲۰۶۰-X, 2002) and C (شابک ‎۰−۵۲۱−۶۰۷۶۵−۵, 1998) versions.
• Cooper, Keith D.; Torczon, Linda (2003). Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2. {{cite book}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.
• Kelsey, Richard A. (March 1995). "A Correspondence between Continuation Passing Style and Static Single Assignment Form". ACM SIGPLAN Notices. 30 (3): 13–22. doi:10.1145/202530.202532.
• Appel, Andrew W. (April 1998). "SSA is Functional Programming". ACM SIGPLAN Notices. 33 (4): 17–20. doi:10.1145/278283.278285.
• Pop, Sebastian (2006). "The SSA Representation Framework: Semantics, Analyses and GCC Implementation" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
• Matthias Braun; Sebastian Buchwald; Sebastian Hack; Roland Leißa; Christoph Mallon; Andreas Zwinkau (2013), "Simple and Efficient Construction of Static Single Assignment Form", Compiler Construction, Lecture Notes in Computer Science, vol. 7791, Springer Berlin Heidelberg, pp. 102–122, doi:10.1007/978-3-642-37051-9_6, ISBN 978-3-642-37050-2, retrieved 24 March 2013

لینک‌های خارجی

• Bosscher, Steven; and Novillo, Diego. GCC gets a new Optimizer Framework. An article about GCC's use of SSA and how it improves over older IRs.
• The SSA Bibliography. Extensive catalogue of SSA research papers.
• Zadeck, F. Kenneth. "The Development of Static Single Assignment Form", December 2007 talk on the origins of SSA.
• VV.AA. "SSA-based Compiler Design" (2014)