حذف عبارت‌های مشترک

حذف عبارت‌های مشترک (به انگلیسی: Common subexpression elimination) در نظریه کامپایلر، حذف عبارت‌های مشترک یک بهینه‌سازی کامپایلر است که نمونه‌هایی از عبارت‌های یکسان را جستجو می‌کند و تجزیه و تحلیل می‌کند که آیا جایگزین کردن عبارت‌ها با یک متغیر نگهدارنده مقدار آن ارزش دارد یا نه.

نمونه

در کد زیر:

;a = b * c + g
;d = b * c * e

ممکن است ارزش داشته باشد که اینطور تغییر دهیم:

؛tmp = b * c
;a = tmp + g
;d = tmp * e

اگر هزینه‌های ذخیره‌سازی و بازیابی "tmp" کمتر از هزینه محاسبه "b * c" باشد.

اصل

امکان انجام CSE بر اساس تجزیه و تحلیل عبارت در دسترس است. در یک برنامه عبارت b*c در نقطه p در دسترس است اگر:

• هر مسیر از شروع برنامه تا نقطه p, ارزیابی b*c قبل از رسیدن به p انجام دهد.
• مقادیر b یا c پس از آخرین ارزیابی b*c نباید تغییر کند.

تجریه و تحلیل هزینه/سود انجام شده توسط یک بهینه‌ساز بیان می‌کند که آیا هزینه ذخیره‌سازی در tmp کمتر از هزینه ضرب است یا نه؛ در عمل عوامل دیگر مانند اینکه مقادیر در چه ریجسترهایی نگه‌داری می‌شوند نیز قابل توجه است.

نویسندگان کامپایلر بین دو نوع CSE تمایز قایل‌اند:

• حذف عبارت‌های مشترک محلی در یک بلوک پایه انجام می‌شود.
• حذف عبارت‌های مشترک سراسری در کل رویه انجام می‌شود.

در هر دو نوع، بر تجزیه و تحلیل جریان داده‌ها تکیه می‌شود که کدام عبارات در کدام نقاط یک برنامه در دسترس هستند.

مثال‌های حذف عبارت‌های مشترک محلی و سراسری

کد سی‌پلاس‌پلاس زیر را در نظر بگیرید:

int main() {
    int x;
    int y;
    int z;

    y = 137;
    if (x == 0)
        z = y;
    else
        x = y;
}

برنامه بالا را به کد ماشین تبدیل می‌کنیم:

main:
   _t0 = 137;
     y = _t0;
   IfZ x Goto _L0;
_L1:
   _t2 = y;
     x = _t2;
   Goto end;
_L0:
   _t1 = y;
     z = _t1;
end:
   endFunc;

با حذف عبارت‌های مشترک محلی داریم:

main:
   y = 137;
   IfZ x Goto _L0;
_L1:
   x = x;
   Goto end;
_L0:
   z = y;
end:
   endFunc;

همچنین با حذف عبارت‌های مشترک سراسری داریم:

main:
   y = 137;
   IfZ x Goto _L0;
_L1:
   x = 137;
   Goto end;
_L0:
   z = 137;
end:
   endFunc;

منابع

• Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378–396
• John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
• Briggs, Preston, Cooper, Keith D. , and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.