موضوع مقاله: فرم تخصیص ایستای منفرد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فرم تخصیص ایستای منفرد | مقدمه: در طراحی کامپایلر، فرم تخصیص ایستای منفرد یا همان SSA، یک ویژگی نمایش میانی است، که نیاز دارد هر متغیر قبل از استفاده، تعریف و تنها یک‌بار اختصاص داده شود. | ## بخش 1: فرم تخصیص ایستای منفرد | متغیرهای موجود در IR اصلی به چند دسته تقسیم می‌شوند؛ متغیرهای جدید که معمولاً با نام اصلی با یک زیرنویس در کتاب‌ها ذکر می‌شوند، به‌طوری که هر تعریف، در دسته خاص خود می‌گنجد. در روش SSA، زنجیره‌های استفاده از تعریف واضح و روشن است و هر یک از آنها یک عنصر یکتا دارد. Kenneth (1991) , می‌توان انتظار داشت که SSA را در یک کامپایلر برای فورتران یا سی پیدا کنیم، در حالی که در کامپایلرهای زبان‌های تابعی، مانند نمونه‌هایی برای اسکیم، ام ال و هسکل، از شیوه ادامه‌دادن (CPS) به‌طور عمومی استفاده می‌شود. SSA رسماً با یک زیر مجموعه خوش‌رفتار از CPS (به استثنای روند کنترل غیر محلی)، معادل است که وقتی CPS به عنوان نمایندهٔ میانجی استفاده می‌شود، رخ نمی‌دهد؛ بنابراین بهینه‌سازی‌ها و دگرگونی‌های صورت گرفته در قالب یکی، بلافاصله روی دیگری اعمال می‌شوند. __TOC__ مزایا مزیت اصلی SSA این است که همزمان، نتایج انواع کامپایلر بهینه‌ساز را بوسیله ساده‌سازی متغیرها ساده کرده و بهبود می‌بخشد. به عنوان مثال، این قطعه کد را در نظر بگیرید: y := 1 y := 2 x := y همان‌طور که قابل مشاهده است، تخصیص اوّل ضروری نیست و مقدار y در سطر سوم، از تخصیص دوم y بدست می‌آید. الگوریتم‌های بهینه‌سازی کامپایلر که با استفاده از SSA فعال شده یا قویاً بهبود داده شده‌اند، عبارتند از: درهم کردن ثابت انتشار دامنه مقدار تکثیر ثابت شرطی پراکنده حذف کد مرده شماره گذاری جهانی مقدار حذف افزونگی جزئی کاهش قدرت تخصیص ثبات تبدیل کردن به SSA تبدیل کد معمولی به فرم SSA، در وهلهٔ اول جایگزین کردن هدف هر دستور با یک متغیر جدید و هر استفاده از متغیر با ورژنی از متغیر که به آن نقطه می‌رسد. برای مثال، گراف روند کنترلی زیر را در نظر بگیرید: | تغییر نام سمت چپ دستور " x ← x - 3 "و تغییر دستورها بعد از آن به x، برنامه را تغییر نمی‌دهد. این کار در SSA با ایجاد دو متغیر جدید x1 و x2 صورت می‌گیرد که هر یک فقط یک‌بار مقداردهی می‌شوند. به همین ترتیب، با اختصاص زیروندهای متمایز به سایر متغیرها چنین نتیجه‌ای منجر می‌شود: | واضح است که هر کدام از موارد استفاده به کدام تعریف رجوع می‌کند؛ به جز متغیر y استفاده‌شده در بلوک پایینی که می‌تواند به هر کدام از y1 یا y2 اشاره کند؛ چرا که بستگی دارد کدام مسیر در روند کنترل طی کرده‌باشد. این تابع، یک تعریف جدید از y تولید می‌کند که y3 نام دارد و بسته به آن که کدام مسیر قبلاً طی شده، مقدار y3 را برابر y1 یا y2 قرار می‌دهد. | اکنون، آخرین بلوک به سادگی می‌تواند از y3 استفاده کند و مقدار صحیح از هر مسیر، بدست می‌آید. استفاده از تابع Φ برای x لازم نیست؛ زیرا فقط یک نسخه از x، یعنی x2 به بلوک انتهایی می‌رسد. با داشتن یک گراف روند کنترل دلخواه، تشخیص این که کجا و برای کدام متغیرها از تابع Φ استفاده کنیم، می‌تواند بسیار دشوار باشد. اما این سؤال، یک راه حل کارآمد دارد که می‌تواند با استفاده از مفهومی به نام مرزهای تسلط محاسبه شود. یک کامپایلر می‌تواند تابع Φ را برای هر عملیاتی که ورودی این تابع را تولید می‌کند، پیاده‌سازی کند. این کار به سادگی و با استفاده از همان مکان در حافظه به عنوان مقصد (یا همان ثبّات) انجام می‌شود. با این حال این رویکرد در شرایطی که چند عملیات به صورت همزمان ورودی‌هایی را برای یک تابع Φ تولید می‌کنند، کار نمی‌کند؛ همان‌طور که می‌تواند در ماشین‌های wide-issue اتفاق بیفتد. نام رسمی تابع Φ زمانی پذیرفته‌شد که برای اولین بار در یک مقاله دانشگاهی انتشار یافت.F. تنها از عملگر Φ برای تشخیص مقدار صحیح در محل‌های به هم پیوستن در گراف استفاده می‌شود. | ## بخش 2: فرم تخصیص ایستای منفرد | دقت شود که لزوماً در تمامی محل‌های اتصال نیازی به Φ نیست؛ اگر تعریف مشترکی از متغیر به گره برسد، نیازی به استفاده از آن نیست. ترجمه از فرم SSA به زبان ماشین، با مقادیر تکراری تعاریف همراه است که ممکن است باعث کاهش بازده شود. پس از ترجمه به فرم SSA، ۳ شرط زیر باید برای هر متغیر V در برنامه اصلی برقرار باشد: اگر دو مسیر ناتُهی از گره X و Y که (هر کدام تعریفی از V دارند) به مقصد مشترک P وجود داشته باشد، آن گاه P یک تابع بدیهی به شکل (v = φ(v, v, … , v دارد که تعداد آرگومان‌های آن برابر با درجهٔ ورودی راس P است. هر مشاهدهٔ P در برنامهٔ اصلی یا یک تابع Φ در برنامهٔ جدید، باید با یک متغیر جدید Vi جایگزین شود تا به فرم SSA تبدیل شود. هر استفاده از V در هر کدام از مسیرهای کنترلی در برنامهٔ اصلی یا هر استفاده از Vi در برنامهٔ جدید، باید به مقدار مشابهی از V و Vi برسد. این مفهوم بسیار پرکاربرد است؛ زیرا هر زمان به B رسیدیم، اطمینان داریم که تمامی کدهای بخش A اجرا شده‌است. حالا می‌توانیم مرز تسلط را تعریف کنیم: گره B در مرز تسلط گره A است اگر A اکیداً بر B تسلط نداشته‌باشد، اما بر پدر B تسلط داشته باشد. با توجه آن که هر گره بر خودش مسلط است و A نیز بر خودش مسلط است، گره B در مرز تسلط گره A خواهد بود) از دیدگاه A، این گره‌ها، در مسیرهای کنترلی دیگر (که از A نمی‌گذرند) زودتر از سایر گره‌های آن ظاهر می‌شوند. مرزهای تسلط مکان‌های دقیقی را که در توابع Φ به آن‌ها نیاز داریم، می‌یابند؛ اگر گره A یک متغیر خاص تعریف می‌کند، آن تعریف یا تعریف مجدد آن متغیر، به هر گرهی که A تسلط دارد، دسترسی می‌یابد. هنگامی که این گره‌ها را ترک کرده و وارد مرز تسلط می‌شویم، باید جریان‌های دیگری که بر اساس تعاریف دیگری از همان متغیر ارائه می‌شود، در نظر بگیریم. علاوه بر این، در نمودار روند کنترل، تابع Φ دیگری برای سر و کار داشتن با تعاریف A مورد نیاز نیست و نمی‌توان با کمتر از این تعداد تابع Φ، کار را انجام داد. تغییراتی که موجب کاهش تعداد توابع Φ می‌شود SSA کمینه، حداقل تعداد توابع Φ مورد نیاز را اضافه می‌کند تا از اختصاص دقیقاً یکبار هر اسم به یک مقدار اطمینان حاصل کند. همچنین هر ارجاع به یک اسم در برنامه اصلی می‌تواند به یک اسم یکتا ارجاع داشته باشد. این شرط به این علت است که کامپایلر بتواند برای هر عملوند درون یک دستور، یک اسم قرار دهد. با این حال، برخی از این توابع ممکن است بلا استفاده یا به اصطلاح کد مرده باشند؛ به همین دلیل SSA کمینه، لزوماً کمترین تعداد Φ لازم برای یک تابع خاص را، ایجاد نمی‌کند. برای برخی از تجزیه و تحلیل‌ها، این توابع اضافی هستند و در نتیجه کارایی را کاهش می‌دهند. SSA هرس‌شده SSA هرس‌شده بر اساس ملاحظات ساده‌ای است؛ توابع Φ تنها برای متغیرهایی که بعد از اجرای Φ، مورد استفاده قرار گرفته‌اند، لازم هستند. اگر یک متغیر زنده نباشد، نتیجه تابع Φ مورد استفاده قرار نمی‌گیرد و مقداردهی هر متغیر بوسیله این تابع، مرده‌است. ساختار SSA هرس‌شده از تحلیل متغیر زنده برای تصمیم‌گیری درج یا حذف تابع Φ استفاده می‌کند. اگر نام متغیر اصلی در هنگام درج تابع Φ زنده نباشد، تابع Φ مورد استفاده قرار نمی‌گیرد و در نتیجه هرس می‌شود. | ## بخش 3: فرم تخصیص ایستای منفرد | در نتیجه، یک تابع Φ زنده است اگر در یک برنامه بازنویسی شده باشد یا به عنوان ورودی به تابع Φ دیگری استفاده شود. هنگام وارد کردن فرم SSA، هر کاربرد آن به نزدیکترین تعریفی که بر آن اختصاص دارد، بازنویسی می‌شود. سپس، هر تابع Φ زنده منظور می‌شود اگر در نزدیکترین تعریفی که به آن اختصاص دارد، حداقل یک‌بار استفاده شده باشد یا حداقل یک‌بار به عنوان ورودی به تابع Φ دیگری استفاده شود. تلاش می‌کند تا تعداد توابع Φ را بدون متحمل‌شدن هزینه بالا برای محاسبه اطلاعات متغیر زنده، کاهش دهد. این روش مبتنی بر ملاحظه زیر است: اگر یک متغیر هیچ‌گاه هنگام ورود به یک بلوک پایه زنده نباشد، هرگز به تابع Φ نیاز ندارد. محاسبه مجموعه متغیرهای محلی در سطح یک بلوک، یک روش ساده‌تر و سریع‌تر از آنالیز کامل متغیرهای زنده است. تبدیل فرم SSA فرم SSA معمولاً برای اجرای مستقیم استفاده نمی‌شود و اغلب بالای IRهای دیگر که در ارتباط مستقیم باقی می‌ماند، استفاده می‌شود. این امر با ساخت SSA، به عنوان مجموعه ای از توابع نگاشت قسمت‌های IR موجود (اعم از بلوک‌های پایه، دستورالعمل‌ها، عملوندها و …) به نقطه مقابل این قسمت‌ها در SSA، کامل می‌شود. هنگامی‌که دیگر به فرم SSA نیازی نباشد، این توابع نگاشت از بین رفته و فقط IR بهینه شده باقی می‌ماند. انجام بهینه‌سازی روی فرم SSA معمولاً منجر به درهم آمیختگی SSA-Webs می‌شود؛ به این معنی که دستورالعمل‌هایی در Φ وجود دارد که عملوندهای آن، ریشه یکسان ندارند. در چنین مواردی برای رسیدن به نتیجه مطلوب بوسیله SSA از الگوریتم‌های رنگی استفاده می‌شود. الگوریتم‌های پایه، برای هر مسیر، یک کپی تولید می‌کنند که باعث می‌شود سورس ریشه مختلف عملوند، به جای مقصد Φ در خود Φ قرار گیرد. , کامپایلرهایی که از فرم SSA استفاده می‌کنند فرم SSA یک توسعهٔ نسبتاً جدید در موضوع کامپایلر است. به همین دلیل، بسیاری از کامپایلرهای قدیمی فقط برای بخشی از فرایند کامپایل یا بهینه‌سازی از فرم SSA استفاده می‌کنند، اما اکثر آن‌ها بر پایهٔ آن نیستند. کد بدست آمده از بهینه‌سازی به RTL ترجمه می‌شود و در آن بهینه‌سازی‌های سطح پایین انجام می‌شوند. تجزیه و تحلیل آرایهٔ توسعه یافتهٔ SSA تنها در بالاترین سطح بهینه‌سازی انجام می‌شود و روی قسمت‌هایی از کد که بیشتر اجرا می‌شود، اعمال می‌گردد. به عنوان یک گونهٔ جالب، توابع Φ را با یک دستورالعمل به یک دستور مشابه جایگزین می‌کند، که به تخصیص‌دهنده ثبّات دستور می‌دهد دامنه دو ثبّات فیزیکی مشابه یکسان قرار دهد. SSA برای ساده‌سازی انتشار عبارات، شناسایی پارامترها، بازگشت‌ها و… استفاده می‌شود. | ## جمع‌بندی | ارلانگ کامپایلر خود را در OTP 22.0 بازنویسی کرد تا از نمایش میانی مبتنی بر SSA استفاده کند.