تحلیل مستعار

تحلیل مستعار (به انگلیسی: Alias Analysis) مجموعه‌ای از روش‌هایی است که تعیین می‌کند که آیا دو اشاره گر به شیء یکسانی در حافظه اشاره می‌کنند یا نه. الگوریتم‌های مختلفی برای تحلیل مستعار و راه‌های زیادی برای دسته‌بندی آن‌ها وجود دارد که عبارت است از: الگوریتم غیرحساس به جریان، الگوریتم حساس به متن و الگوریتم غیر حساس به متن، الگوریتم حساس به میدان و الگوریتم غیر حساس به میدان، مبتنی بر متحدسازی و مبتنی بر زیرمجموعه و غیره. در صورتی که دو اشاره‌گر به یک مکان اشاره کنند به آن‌ها مستعار می‌گویند. در نتیجه هر دو متغیری که می‌توانند مقادیرشان را از دو مقدار رسمی مجزا بگیرند نیز مستعار خواهند بود. در ابتدا تحلیل‌گرهای مستعار به یک جستار با کلماتی مثل: must, may و no جواب می‌دادند که نشان می‌داد که دو اشاره‌گر همیشه به یک شیء یکسان اشاره می‌کنند یا نه. وجود متغیرهای مستعار عملیات بهینه‌سازی را سخت‌تر می‌کنند زیرا نمی‌توانیم تشخیص دهیم که این کدام متغیر تغییر کرده‌است.

بررسی اجمالی کلاس تحلیل مستعار

کلاس تحلیل مستعار یک رابط(interface) تعریف می‌کند که پیاده‌سازی های مختلفی از تحلیل مستعار باید آن را پشتیبانی کنند. این کلاس دو enum مهم به نام‌های AliasResult و ModRefResult دارد که به ترتیب نتیجهٔ یک جستار مستعار یا یک جستار mod/ref را نشان می‌دهند. رابط AliasAnalysis اطلاعات حافظه را به روش‌های مختلف نمایش می‌دهد. به خصوص شی‌های حافظه به عنوان آدرس شروع و اندازه، و فراخوانی توابع به صورت دستور یک فراخوانی واقعی که فراخوانی را انجام می‌دهند نشان داده می‌شوند. علاوه بر این رابط AliasAnalysis چند روش کمک‌کننده که به شما امکان گرفتن اطلاعات mod/ref را برای دستور دلخواه را می‌دهد. در در همهٔ رابط‌های AliasAnalysis باید در جستارهای شامل مقدارهای چندگانه، مقدارهایی که ثابت نیستند باید در همان تابع تعریف شوند. به‌طور کلی تحلیل مستعار تعیین می‌کند که آیا ارجاع به حافظه به قسمت یکسانی اشاره می‌کند یا نه. در نتیجه این اجازه به کامپایلر داده می‌شود که مشخص کند که متغیرهای برنامه توسط یک بخش از برنامه عوض می‌شوند یا خیر. برای مثال قطعه کد زیر را در نطر بگیرید:

*p.foo = ۱
*q.foo = ۲
*i = p.foo + 3

سه حالت مستعار برای این کد وجود دارد:

1. متغیرهای p و q مستعار نیستند که د این حالت به دو نقطهٔ یکسان اشاره نمی‌کنند.
2. متغیرهای p و q باید مستعار باشند که در این صورت همیشه به یک نقطهٔ یکسان اشاره می‌کنند.
3. به صورت قطعی در زمان کامپایل نمی‌توان گفت که p و q مستعار هستند یا نه.

در صورتی که مستعار نباشند آنگاه i برابر ۴ خواهد شد. اگر حالت دوم پیش بیاید i برابر ۵ می‌شود، چون p.foo + 3 = q.foo + 3. در هر دو حالت می‌توانیم بهینه‌سازی را روی آن‌ها اجرا کنیم. از طرفی، اگر نمی‌دانیم که این دو متغیر مستعار هستند یا نه نمی‌توان بهینه‌سازی را انجام داد و کل برنامه باید اجرا شود تا نتیجه به دست آید. در صورتی که وضعیت مستعار بودن دو ارجاع به حافظه نامشخص باشد می‌گوییم رابطهٔ may_alias دارند.

پیاده‌سازی یک AliasAnalysis جدید

نوشتن یک تحلیل مستعار برای LLVM کار نسبتاً ساده‌ای است. پیاده‌سازی‌های مختلفی وجو دارد که می‌توان از آن‌ها استفاده کرد. در اولین مرحله باید مشخص کنیم چه نوع LLVM pass ای برای استفاده در تحلیل مستعار نیاز داریم. همانند سایر تحلیل‌ها و تبدیل ها، پاسخ باید از نوع مسئله‌ای که می‌خواهیم حل کنیم واضح باشد:

1. اگر نیاز به تحلیل درون برنامه‌ای داریم باید Pass باشد.
2. اگر نیاز به تحلیل توابع محلی داریم باید FunctionPass باشد.
3. اگر کلا نیازی به نگاه کردن به برنامه نداریم باید ImmutablePass باشد.

انواع تحلیل مستعار

در تحلیل مستعار حافظهٔ برنامه را به کلاس‌های مستعار تقسیم می‌کنیم. کلاس‌های مستعار مجموعه‌های مجزایی از محل‌های حافظه هستند که نمی‌توانند مستعار هم دیگر باشند. در اینجا فرض می‌شود که بهینه‌سازی روی نمایش سطح پایین برنامه اتفاق می‌افتد. چون برنامه‌ای که کامپایل می‌شود اعمال دودویی، پرش‌ها، حرکت بین ثبات‌ها، حرکت بین ثبات‌ها و حافظه، انشعاب و فراخوانی و برگرداندن توابع را انجام می‌دهد.

تحلیل مستعار مبتنی بر نوع

اگر زبانی که کامپایل می‌شود از نظر نوع امن باشد، بررسی‌کننده نوع(type checker) درست کار می‌کند و برنامه قادر به ایجاد اشاره گرهای اشاره‌کننده به متغیرهای محلی نیست. حال بهینه‌سازی‌های مفیدی می‌توان انجام داد. حالت‌های مختلفی وجود دارد که می‌دانیم دو محل از حافظه باید در کلاس‌های مستعار مختلفی باشند:

1. دو متغیر از انواع مختلف نمی‌توانند در کلاس یکسانی باشند زیرا این خصوصیت زبان‌های strongly-typed و memory reference-free است که دو متغیر از نوع‌های مختلف نمی‌توانند به صورت هم‌زمان محل‌های یکسانی از حافظه را به اشتراک بگذارند.
2. تخصیص‌های محلی به یک پشته نمی‌توانند در کلاس مستعار یکسانی باشند زیرا در این حالت تخصیص حافظهٔ جدید باید از بقیهٔ تخصیص‌های حافظه مجزا باشد.
3. هر record field از هر record type کلاس مستعار خودش را دارد. زیرا همهٔ رکوردهای یک نوع به شکل یکسان در حافظه ذخیره می‌شوند و هر فیلد می‌تواند مستعار خودش باشد.

وقتی تحلیل مستعار برای برنامه اجرا می‌شود هر عمل بارگذاری و ذخیره در حافظه باید با کلاسش برچسب‌گذاری شود. آنگاه اگر محل‌های $A_{i}$ و $B_{i}$ از حافظه را با کلاس‌های $i$ و $j$ در نظر بگیریم اگر $i=j$ آنگاه $A_{i}$ و $B_{i}$ با هم may-alias خواهند بود و اگر $i\neq j$ مستعار یکدیگر نخواهند بود.

تحلیل مستعار مبتنی بر جریان

تحلیل مستعار مبتنی بر جریان را بر خلاف تحلیل مستعار مبتنی بر نوع می‌توان در برنامه‌های یک زبان با ارجاعات و تغییر نوع استفاده کرد. این نوع از تحلیل را می‌توان به جای تحلیل مبتنی بر نوع مکمل استفاده کرد. در این تحلیل کلاس‌های مستعار برای هر تخصیص از حافظه و برای هر متغیر محلی و سراسری که آدرس آن استفاده می‌شود، ایجاد می‌شود. ارجاعات به حافظه ممکن است به بیش از یک مقدار در طول زمان اشاره کنن و در نتیجه در بیش از یک کلاس مستعار باشند و این بدان معناست که هر تخصیص حافظه یک مجموعه از کلاس‌ها به جای یک کلاس مستعار دارد.

منابع

• Appel, Andrew W. (1998). ''Modern Compiler Implementation in ML'', Cambridge, UK: Cambridge University Press
• https://llvm.org/docs/AliasAnalysis.html
• Alfred Aho,(1986).Compilers, Principles, Techniques, and Tools