۰
subtitle
ارسال: #۱
انواع بهینه سازی در کامیایلرها
کامپایلرهای جدید قادر به انجام تغییرات زیادی بر روی کد ورودی به منظور افزایش کارایی آن میباشند. برای یک برنامه نویس سودمند خواهد بود که بداند یک کامپایلر چه بهینه سازی هایی را میتواند انجام دهد و کدام را نمیتواند. در این بخش به معرفی تعدادی از بهینه سازی هایی که یک کامپایلر میتواند انجام دهد میپردازیم.
۱- Function inlining
کامپایلر میتواند فراخوانی یک تابع را با بدنه آن جایگزین نماید. به مثال زیر دقت نمایید:
کامپایلر میتواند دستور فراخوانی تابع square را با بدنه آن جایگزین نماید. به صورت زیر:
مزایای این بهینه سازی عبارتند از:
۱- بالاسری ناشی از فراخوانی و بازگشت و انتقال پارامتر به تابع حذف میشود.
۲- درصد محلی بودن ارجاعات در کد بیشتر و درنتیجه ضریب برخورد در حافظه نهان بیشتر میشود.
۳- اگر فقط یک فراخوانی روی تابع inline شده وجود داشته باشد کد کوچکتر میشود.
۴- inline نمودن یک تابع فرصتی را برای اعمال سایر بهینه سازی‌ها روی کد بوجود می آورد که ذیلا توضیح داده خواهد شد.
عیب inline آنمودن یک تابع این است که اگر درصد فراخوانی تابع در کد زیاد بوده باشد و به خصوص این که تابع بزرگ باشد باعث افزایش طول کد برنامه میشود. به هر حال اکر تابع کوچک باشد و اگر تعداد فراخوانی های آن کم باشد کامپایلر آن تابع را inline میکند.
۲- constant folding and constant propagation
در بهینه سازی constant folding یک عبارت یا زیرعبارت که فقط شامل ثوابت باشد با نتیجه آن عبارت جایگزین میشود. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
به این نکته دقت نمایید که در عبارتی مثل b * 2.0 / 3.0 بهینه سازی constant folding انجام نمیشود چراکه کامپایلر در ابتدا عمل b * 2.0 را انجام میدهد. پس بهتر است این عبارت توسط خود برنامه نویس به صورت b * (2.0 / 3.0) نوشته شود.
در بهینه سازی constant propagation یک ثابت در صورت امکان در بین یک سری از عبارات منتشر میشود. به مثال زیر توجه نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
البته اگر در عبارت تابعی باشد که نتواند inline شود یا نتواند در زمان کامپایل محاسبه گردد نمیتوان از بهینه سازی های constant folding و constant propagation استفاده کرد. به مثال زیر توجه نمایید:
تابع sin در یک کتابخانه جدا تعریف شده و نمیتوان از کامپایلر انتظار داشت که بتواند این تابع را inline نماید و آن را در زمان کامپایل محاسبه نماید.
۳- Pointer elimination
اگر در زمان کامپایل معلوم باشد که یک اشاره گر به چه خانه ای از حافظه اشاره میکند میتوان آن اشاره گر را حذف نمود. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
اگر در یک عبارت چندین بار یک زیر عبارت تکرار شده باشد آنگاه کامپایلر فقط یکبار آن زیرعبارت را محاسبه مینماید. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
۵- Register variables
در این بهینه سازی کامپایلر سعی میکند که متغیرهایی را که بیشتر از همه مورد استفاده قرار میگیرند در ثبات های cpu ذخیره کند. از جمله این متغیرها میتوان به شمارنده های حلقه ها، اشاره گرها، پارامترهای توابع و … اشاره کرد.
دقت کنید که اگر در کد یک برنامه با آدرس یک متغیر کار میکنیم آن متغیر نمیتواند در یک ثبات قرار گیرد چراکه ثبات آدرس ندارد.
۶- Join identical branches
در این بهینه سازی قسمت های مشترک کد مربوط به دو پرش if-then-else به منظور صرفه جویی در کد یکی میشوند. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
۷- Eliminate jumps
با کپی کردن کدی که به آن پرش میشود میتوان از انجام پرش جلوگیری کرد. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
همچنین اگر درست یا غلط بودن نتیجه یک عبارت شرطی مربوط به یک دستور شرطی در زمان کامپایل مشخص باشد میتوان پرش را حذف نمود. به مثال زیر دقت نمایید:
// Example 10a
کامپایلر این کد را با کد زیر جایگزین مینماید:
همچنین اگر دو دستور شرطی با عبارات شرطی یکسان به طور متوالی آمده باشند و برای کامپایلر واضح باشد که نتیجه این دو عبارت شرطی یکسان است در این صورت دستور شرطی دوم میتواند حذف شود و دستورات موجود در بدنه آن به بدنه دستور شرطی اول اضافه شود. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
۸- Loop unrolling
بعضی از کامپایلرها حلقه را باز میکنند. معمولا این کار زمانی انجام میشود که بدنه حلقه خیلی کوچک باشد و باز کردن آن راه را برای انجام بهینه سازی های بیشتر باز کند. از طرف دیگر حلقه هایی نیز که تعداد تکرار آنها خیلی کوچک است به منظور حذف نمودن بالاسری حلقه سازی باز میشوند. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
در این بهینه سازی، کامپایلر عبارت یا دستوری را که بود یا نبود آن در حلقه، هیچ فرقی نداشته باشد از حلقه خارج میکند. به مثال زیر دقت نمایید:
کامپایلر این کد را با کد زیر جایگزین مینماید:
۱- Function inlining
کامپایلر میتواند فراخوانی یک تابع را با بدنه آن جایگزین نماید. به مثال زیر دقت نمایید:
کد:
// Example 1a
float square (float a) {
return a * a;}
float parabola (float x) {
return square(x) + 1.0f;}کامپایلر میتواند دستور فراخوانی تابع square را با بدنه آن جایگزین نماید. به صورت زیر:
کد:
// Example 1b
float parabola (float x) {
return x * x + 1.0f;}مزایای این بهینه سازی عبارتند از:
۱- بالاسری ناشی از فراخوانی و بازگشت و انتقال پارامتر به تابع حذف میشود.
۲- درصد محلی بودن ارجاعات در کد بیشتر و درنتیجه ضریب برخورد در حافظه نهان بیشتر میشود.
۳- اگر فقط یک فراخوانی روی تابع inline شده وجود داشته باشد کد کوچکتر میشود.
۴- inline نمودن یک تابع فرصتی را برای اعمال سایر بهینه سازی‌ها روی کد بوجود می آورد که ذیلا توضیح داده خواهد شد.
عیب inline آنمودن یک تابع این است که اگر درصد فراخوانی تابع در کد زیاد بوده باشد و به خصوص این که تابع بزرگ باشد باعث افزایش طول کد برنامه میشود. به هر حال اکر تابع کوچک باشد و اگر تعداد فراخوانی های آن کم باشد کامپایلر آن تابع را inline میکند.
۲- constant folding and constant propagation
در بهینه سازی constant folding یک عبارت یا زیرعبارت که فقط شامل ثوابت باشد با نتیجه آن عبارت جایگزین میشود. به مثال زیر دقت نمایید:
کد:
// Example 2a
double a, b;
a = b + 2.0 / 3.0;کد:
// Example 2b
a = b + 0.666666666666666666667;در بهینه سازی constant propagation یک ثابت در صورت امکان در بین یک سری از عبارات منتشر میشود. به مثال زیر توجه نمایید:
کد:
// Example 3a
float parabola (float x) {
return x * x + 1.0f;}
float a, b;
a = parabola (2.0f);
b = a + 1.0f;کامپایلر این کد را با کد زیر جایگزین مینماید:
کد:
// Example 3b
a = 5.0f;
b = 6.0f;کد:
// Example 4
double a = sin(0.8);تابع sin در یک کتابخانه جدا تعریف شده و نمیتوان از کامپایلر انتظار داشت که بتواند این تابع را inline نماید و آن را در زمان کامپایل محاسبه نماید.
۳- Pointer elimination
اگر در زمان کامپایل معلوم باشد که یک اشاره گر به چه خانه ای از حافظه اشاره میکند میتوان آن اشاره گر را حذف نمود. به مثال زیر دقت نمایید:
کد:
// Example 5a
void Plus2 (int *p) {
*p = *p + 2;}
int a;
Plus2 (&a);کد:
// Example 5b
a += 2;
۴- Common subexpression eliminationاگر در یک عبارت چندین بار یک زیر عبارت تکرار شده باشد آنگاه کامپایلر فقط یکبار آن زیرعبارت را محاسبه مینماید. به مثال زیر دقت نمایید:
کد:
// Example 6a
int a, b, c;
b = (a+1) * (a+1);
c = (a+1) / 4;کامپایلر این کد را با کد زیر جایگزین مینماید:
کد:
// Example 6b
int a, b, c, temp;
temp = a+1;
b = temp * temp;
c = temp / 4;در این بهینه سازی کامپایلر سعی میکند که متغیرهایی را که بیشتر از همه مورد استفاده قرار میگیرند در ثبات های cpu ذخیره کند. از جمله این متغیرها میتوان به شمارنده های حلقه ها، اشاره گرها، پارامترهای توابع و … اشاره کرد.
دقت کنید که اگر در کد یک برنامه با آدرس یک متغیر کار میکنیم آن متغیر نمیتواند در یک ثبات قرار گیرد چراکه ثبات آدرس ندارد.
۶- Join identical branches
در این بهینه سازی قسمت های مشترک کد مربوط به دو پرش if-then-else به منظور صرفه جویی در کد یکی میشوند. به مثال زیر دقت نمایید:
کد:
// Example 8a
double x, y, z; bool b;
if (b) {
y = sin(x);
z = y + 1.;
}
else {
y = cos(x);
z = y + 1.;
}کامپایلر این کد را با کد زیر جایگزین مینماید:
کد:
// Example 8b
double x, y; bool b;
if (b) {
y = sin(x);
}
else {
y = cos(x);
}
z = y + 1.;با کپی کردن کدی که به آن پرش میشود میتوان از انجام پرش جلوگیری کرد. به مثال زیر دقت نمایید:
کد:
// Example 9a
int SomeFunction (int a, bool b) {
if (b) {
a = a * 2;
}
else {
a = a * 3;
}
return a + 1;
}کد:
// Example 9b
int SomeFunction (int a, bool b) {
if (b) {
a = a * 2;
return a + 1;
}
else {
a = a * 3;
return a + 1;
}
}همچنین اگر درست یا غلط بودن نتیجه یک عبارت شرطی مربوط به یک دستور شرطی در زمان کامپایل مشخص باشد میتوان پرش را حذف نمود. به مثال زیر دقت نمایید:
// Example 10a
کد:
if (true) {
a = b;
}
else {
a = c;
}کامپایلر این کد را با کد زیر جایگزین مینماید:
کد:
// Example 10b
a = b;همچنین اگر دو دستور شرطی با عبارات شرطی یکسان به طور متوالی آمده باشند و برای کامپایلر واضح باشد که نتیجه این دو عبارت شرطی یکسان است در این صورت دستور شرطی دوم میتواند حذف شود و دستورات موجود در بدنه آن به بدنه دستور شرطی اول اضافه شود. به مثال زیر دقت نمایید:
کد:
// Example 11a
int SomeFunction (int a, bool b) {
if (b) {
a = a * 2;
}
else {
a = a * 3;
}
if (b) {
return a + 1;
}
else {
return a - 1;
}کامپایلر این کد را با کد زیر جایگزین مینماید:
کد:
// Example 11b
int SomeFunction (int a, bool
if (b) {
a = a * 2;
return a + 1;
}
else {
a = a * 3;
return a - 1;
}
}۸- Loop unrolling
بعضی از کامپایلرها حلقه را باز میکنند. معمولا این کار زمانی انجام میشود که بدنه حلقه خیلی کوچک باشد و باز کردن آن راه را برای انجام بهینه سازی های بیشتر باز کند. از طرف دیگر حلقه هایی نیز که تعداد تکرار آنها خیلی کوچک است به منظور حذف نمودن بالاسری حلقه سازی باز میشوند. به مثال زیر دقت نمایید:
کد:
// Example 12a
int i, a[2];
for (i = 0; i < 2; i++) a[i] = i+1;کد:
// Example 12b
int a[2];
a[0] = 1; a[1] = 2;
۹- Loop invariant code motionدر این بهینه سازی، کامپایلر عبارت یا دستوری را که بود یا نبود آن در حلقه، هیچ فرقی نداشته باشد از حلقه خارج میکند. به مثال زیر دقت نمایید:
کد:
// Example 13a
int i, a[100], b;
for (i = 0; i < 100; i++) {
a[i] = b * b + 1;
}کد:
// Example 13b
int i, a[100], b, temp;
temp = b * b + 1;
for (i = 0; i < 100; i++) {
a[i] = temp;
}
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close