فرم تخصیص ایستای منفرد
در طراحی کامپایلر، فرم تخصیص ایستای منفرد یا همان 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، در وهلهٔ اوّل جایگزین کردن هدف هر دستور با یک متغیر جدید و هر استفاده از متغیر با ورژنی از متغیر که به آن نقطه می‌رسد. برای مثال، گراف روند کنترلی زیر را در نظر بگیرید:
تغییر نام سمت چپ دستور " x ← x - 3 "و تغییر دستورها بعد از آن به x، برنامه را تغییر نمی‌دهد. این کار در SSA با ایجاد دو متغیر جدید x و x صورت می‌گیرد که هر یک فقط یک‌بار مقداردهی می‌شوند. به همین ترتیب، با اختصاص زیروندهای متمایز به سایر متغیرها چنین نتیجه‌ای منجر می‌شود:
واضح است که هر کدام از موارد استفاده به کدام تعریف رجوع می‌کند؛ به جز متغیر y استفاده‌شده در بلوک پایینی که می‌تواند به هر کدام از y یا y اشاره کند؛ چرا که بستگی دارد کدام مسیر در روند کنترل طی کرده‌باشد. برای حل این مشکل، یک تابع ویژه به نام (Φ(Phi در آخرین بلوک درج می‌شود. این تابع، یک تعریف جدید از y تولید می‌کند که y نام دارد و بسته به آن که کدام مسیر قبلاً طی شده، مقدار y را برابر y یا y قرار می‌دهد.
اکنون، آخرین بلوک به سادگی می‌تواند از y استفاده کند و مقدار صحیح از هر مسیر، بدست می‌آید. استفاده از تابع Φ برای x لازم نیست؛ زیرا فقط یک نسخه از x، یعنی x به بلوک انتهایی می‌رسد. به عبارت دیگر، Φ(x، x) = x. با داشتن یک گراف روند کنترل دلخواه، تشخیص این که کجا و برای کدام متغیرها از تابع Φ استفاده کنیم، می‌تواند بسیار دشوار باشد. اما این سؤال، یک راه حل کارآمد دارد که می‌تواند با استفاده از مفهومی به نام مرزهای تسلط محاسبه شود. در اکثر دستگاه‌ها توابع Φ به عنوان دستور ماشین پیاده‌سازی نشده‌است. یک کامپایلر می‌تواند تابع Φ را برای هر عملیاتی که ورودی این تابع را تولید می‌کند، پیاده‌سازی کند. این کار به سادگی و با استفاده از همان مکان در حافظه به عنوان مقصد (یا همان ثبّات) انجام می‌شود. با این حال این رویکرد در شرایطی که چند عملیات به صورت همزمان ورودی‌هایی را برای یک تابع Φ تولید می‌کنند، کار نمی‌کند؛ همان‌طور که می‌تواند در ماشین‌های wide-issue اتفاق بیفتد. معمولاً یک ماشین wide-issue یک دستور برای انتخاب دارد که توسط کامپایلر برای اجرای تابع Φ استفاده می‌شود. با توجه به Kenny Zadeck، زمانی که SSA که در تحقیقات IBM در دهه ۱۹۸۰ در حال توسعه بود، توابع Φ به عنوان توابع ساختگی شناخته شده‌بودند. نام رسمی تابع Φ زمانی پذیرفته‌شد که برای اولین بار در یک مقاله دانشگاهی انتشار یافت.
در واقع در فرم SSA گراف روند کنترل هیچ تفاوتی با حالت قبل ندارد. تنها از عملگر Φ برای تشخیص مقدار صحیح در محل‌های به هم پیوستن در گراف استفاده می‌شود. دقت شود که لزوماً در تمامی محل‌های اتصال نیازی به Φ نیست؛ اگر تعریف مشترکی از متغیر به گره برسد، نیازی به استفاده از آن نیست. ترجمه از فرم SSA به زبان ماشین، با مقادیر تکراری تعاریف همراه است که ممکن است باعث کاهش بازده شود. پس از ترجمه به فرم SSA، ۳ شرط زیر باید برای هر متغیر V در برنامه اصلی برقرار باشد:
در ابتدا به بررسی مفهوم سلطه‌گر (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 مورد نیاز نیست و نمی‌توان با کمتر از این تعداد تابع Φ، کار را انجام داد. کد زیر، یک الگوریتم برای محاسبه مجموعه مرزی تسلط است: توجه: در کد بالا، پدر گره n هر گره ای است که کنترل از آن به گره n داده می‌شود، و (idom(b گره ای است که بلافاصله بر گره b (یک مجموعه منفرد) تسلط می‌یابد.
الگوریتم کارآمد دیگری برای یافتن مرزهای تسلط بر هر گره وجود دارد. این الگوریتم در ابتدا در Cytron شرح داده‌شد.
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 بسیار متکی هستند عبارتند از: