بهینه سازی درون تابع

بهینه سازی درون تابع (Interprocedural optimization: IPO) مجموعه ای از تکنیک‌های کامپایلر است برای بهبود عملکرد در برنامه‌هایی که شامل توابعی پر استفاده با اندازه متوسط و کم هستند.

بهینه سازی درون تابعی با بقیه بهینه سازهای کامپایلر متفاوت است به این دلیل که در این بهینه سازی تمام برنامه تحلیل می‌شود ولی بقیه بهینه سازها تنها به یکی از توابع یا حتی به یک بلوک از کد نگاه می‌کنند.

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

همین‌طور بهینه سازی درون تابع ممکن است بهینه سازی‌های معمولی کامپایلر در سطح کل برنامه هم باشد. برای مثال می‌توان به حذف کدهای مرده (DCE) اشاره کرد که در در آن کدهایی که هرگز اجرا نمی‌شوند حذف می‌شوند. برای رسیدن به این هدف کامپایلر شاخه‌هایی از کد را که اجرا نمی‌شوند را آزمایش می‌کند و در صورت نیاز کدهای داخل آن شاخه را حذف می‌کند. بهینه سازی درون تابع همنیطور استفاده بهتر از ثوابت تعریف شده در کد را تضمین می‌کند.کامپایلرهای مدرن بهینه سازی درون تابع را به عنوان یک گزینه اختیاری در زمان کامپایل ارایه می‌دهند. پردازش و کار واقعی بهینه سازی درون تابع در هر قدم بین کد قابل خواندن برای انسان‌ها و تولید کد دودویی قابل اجرا برنامه اتفاق می‌افتد.

برای زبان‌هایی که فایل به فایل کامپایل را انجام می‌دهند، بهینه سازی درون تابع زمانی کارامدی خود را برای ترجمه‌های واحدها دارد که دارای دانش نقطه ورود برنامه باشند که بهینه سازی کل برنامه (Whole Program Optimization: WPO) قابل اجرا باشد. در بسیاری از موارد این بهینه سازی به صورت بهینه سازی زمان ارتباط (link-time optimization: LTO) پیاده سازی می‌شود به این دلیل که این برنامه برای قابل مشاهده است.

تحلیل

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

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

برای مثال تصور کنید که روالی وجود دارد که تابع F(x) را محاسبه می‌کند و برنامه در مکان‌های متفاوتی مقدار تابع F(6) را درخواست می‌دهد. محاسبه درخواست‌های دوم به بعد برای این مقدار در مکان‌های دیگر کاملاً غیر ضروریست. نتیجه می‌توانست با فرض اینکه تابع خالص باشد به جای آن ذخیره شود و در جاهای دیگر که تابع صدا زده شده بود به کار گرفته شود. این بهینه سازی ساده در صورتی که پیاده سازی تابع مورد نظر خالص نباشد درست نیست. برای مثال زمانی که تابع در اجرای خود ارجاعی به متغیرهایی به غیر از متغیر ورودی ۶ در مثال ما داشته باشد که در بین زمان صدا زدن تابع مقدار آن عوض شده باشد و اثرات حاشیه ای مثل چاپ کردن مقداری در لاگ، شمردن تعداد محاسبه‌ها، جمع کردن زمان گرفته شده از واحد کنترل مرکزی، آماده کردن جدول‌های داخلی برای ساده‌سازی، اجرای زیر دستورهایی برای متغیرهای مرتبط و …. از دست دادن این اثرهای حاشیه ای منجر به پذیرفتن مقدار خروجی برای دفعه‌های دیگر می‌شود.

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

بهینه سازی کل برنامه(WPO) و بیهینه سازی زمان ارتباط(LTO)

“بهینه سازی کامل برنامه"(WPO) بهینه سازی کامپایلر یک برنامه با استفاده از اطلاعات مربوط به همه (ماژول (برنامه نویسی)|ماژول‌ها) در برنامه است. به طور معمول، بهینه سازی‌ها بر اساس [واحد ترجمه (برنامه نویسی) | در هر ماژول ، "کامپایل"] انجام می‌شوند. اما این رویکرد، در حالی که نوشتن و تست ساده‌تر و نیازمند تقاضای کمتری از منابع در حین کامپایل خود است، قطعیت در مورد ایمنی تعدادی از بهینه سازی‌ها مانند تهاجمی درگیری را فراهم نمی‌کند و بنابراین نمی‌تواند آنها را انجام دهد حتی اگر آنها در واقع به دست آوردن عملکرد تبدیل می‌شوند که سمنتیک کد شیء منتشر شده را تغییر نمی‌دهند.

«بهینه سازی زمان پیوند» '(LTO) نوعی بهینه سازی برنامه است که توسط یک کامپایلر به یک برنامه در زمان پیوند انجام می‌شود. بهینه سازی زمان لینک در زبان‌های برنامه‌نویسی مرتبط است که برنامه‌ها را به صورت فایل به فایل کامپایل می‌کنند، و سپس آن فایل‌ها را به هم پیوند می‌دهد (مانند C و فورترن)، به جای اینکه همه را با هم پیوند دهد. (مانند جاوا تفسیر آنی (JIT)).

هنگامی که همه فایل‌ها به‌طور جداگانه به فایل شی (آبجکت فایل) تفسیر شدند، به‌طور سنتی، کامپایلر فایل‌های شی را به یک فایل واحد، اجرایی پیوند می‌دهد. با این حال، در LTO همان‌طور که توسط مجموعه کامپایلرهای GNU (جی‌سی‌سی: GCC) یا ال‌ال‌وی‌ام پیاده سازی شده‌است، مفسر قادر است نمایش میانی (جی‌سی‌سی bytod کد یا بیت کد LLVM) خود را در دیسک قرار دهد به گونه ای که تمام واحدهای مختلف مفسر که برای ساختن یک فایل اجرایی واحد به کار می‌روند، می‌توانند به عنوان یک ماژول واحد هنگامی که در نهایت اتفاق می‌افتد بهینه سازی شوند. این دامنه بهینه سازی‌های درون تابع را در بر می‌گیرد تا کل برنامه را شامل شود (یا به عبارت دیگر، هر آنچه در زمان پیوند قابل مشاهده است). با بهینه سازی زمان پیوند، کامپایلر می‌تواند اشکال مختلف بهینه سازی درون تابع را برای کل برنامه اعمال کند، و این امکان را برای تجزیه و تحلیل عمیق‌تر، بهینه سازی بیشتر و در نهایت عملکرد بهتر برنامه فراهم می‌کند.

در عمل، LTO همیشه کل برنامه را بهینه نمی‌کند - [کتابخانه (محاسبات) | توابع کتابخانه]، به ویژه پیوند پویا اشیاء مشترک، به‌طور عمد برای جلوگیری از تکرار بیش از حد و قابلیت تغییر در زمان نگه داشته می‌شوند. پیوند استاتیک به‌طور طبیعی به مفهوم LTO امانت داده می‌شود، اما فقط با بایگانی کتابخانه کار می‌کند که حاوی اشیاء IR است بر خلاف فایل‌های ماشین که فقط با فایل‌های شیء کار می‌کنند. با توجه به نگرانی‌های مربوط به عملکرد، حتی از کل واحد همواره به‌طور مستقیم استفاده نمی‌شود - یک برنامه می‌تواند به سبک تقسیم و تسخیر LTO مانند WHOPR GCC تقسیم شود.

و البته وقتی برنامه ای که ساخته می‌شود، خود یک کتابخانه است، بهینه‌سازی هر نمادی را که در دسترس خارجی (صادر شده) قرار دارد، نگه می‌دارد، بدون آنکه تلاش زیادی در از بین بردن آنها به عنوان بخشی از DCE داشته باشید.

شکل بسیار محدود تری از WPO هنوز هم بدون LTO امکان‌پذیر نیست، همان‌طور که توسط سوئیچ C | کد | -بعد برنامه-} GCC توضیح داده شده‌است. این حالت باعث می‌شود که GCC فرض کند که ماژول در حال تدوین شامل نقطه ورود (معمولاً main ()) کل برنامه است، به گونه ای که هر تابع دیگری در آن از بیرون استفاده نمی‌شود و می‌توان با خیال راحت ازبهینه شود. از آنجا که فقط به یک ماژول مربوط می‌شود، نمی‌تواند کل برنامه را در بر بگیرد. (می توان آن را با LTO به معنای یک ماژول بزرگ ترکیب کرد، وقتی پیوند دهنده در حال ارتباط برقرار کردن با GCC در مورد آنچه که از نقاط ورودی یا نمادها که از خارج استفاده می‌شوند)

Example

Program example;

integer b;              {یک متغیر سراسری برای تابع silly.}

Procedure Silly(a,x)

if x < 0 then a:=x + b else a:=-6;

End Silly;              {ارجاع به b, نه یک پارامتر،  در حالت کلی silly  را ناخالص می‌کند.}

integer a,x;            {در صورت متغیر بودن این پارامترها در دسترس silly قرار دارند.}

x:=7; b:=5;

Silly(a,x); write(x);

Silly(x,a); write(x);

Silly(b,b); write(b);

End example;

اگر پارامترها به "Silly" گذر به مقدار # فراخوانی با مقدار باشند، اقدامات رویه هیچ تأثیری روی متغیرهای اصلی ندارند و از آنجا که "Silly" هیچ کاری با محیط آن ندارد (خواندن از فایل، نوشتن روی یک فایل، تغییر متغیرهای جهانی مانند b و غیره) کد آن به علاوه همه فراخوانی‌ها ممکن است به‌طور کامل بهینه شده و مقدار "a" راتعریف نشده رها کند (که مهم نیست) که فقط کد "print” می‌ماند و مقادیر ثابت.

اگر در عوض پارامترها استراتژی ارزشیابی # فراخوانی توسط مرجع، پس اقدام بر روی آنها در "Silly" در واقع بر اصل متغیرها تأثیر می‌گذارد. این کار معمولاً با انتقال آدرس ماشین پارامترها به رویه انجام می‌شود تا تغییرات رویه در قسمت اصلی ذخیره سازی انجام شود.

بنابراین در صورت فراخوانی با مرجع، رویه "Silly" اثر دارد. فرض کنید که فراخوانی‌های آن در جای خود گسترش یافته‌است و با پارامترهای مشخص شده توسط آدرس:

x:=7; b:=5;

if x < 0 then a:=x + b else a:=-6; write(x);   {تغییر متغیر  a.}

if a < 0 then x:=a + b else x:=-6; write(x);   {برایی اینکه پارامترها جابجا شده‌اند.}

if b < 0 then b:=b + b else b:=-6; write(b);

{دو ورژن مختلف از متغیر b در “Silly” به علاوه یک متغیر جهانی}

سپس کامپایلر می‌تواند در این مثال نسبتاً کوچک از ثابت‌ها پیروی کند و دریابد که گزاره‌های if-عبارت‌ها ثابت هستند و بنابراین …

x:=7; b:=5;

a:=-6; write(7);            {b یک مرجع نیست پس استفاده خالص می‌ماند.}

x:=-1; write(-1);           {متغیر b یک اشاره گر است.}

b:=-6; write(-6);           {b از طریق پارامترهای آن اصلاح می‌شود.}

و از آنجا که مقداردهی‌های "a","b"و"x" هیچ چیز را به جهان خارج نمی‌رسانند - آنها در خروجی ظاهر نمی‌شوند، و نه به عنوان ورودی به محاسبات بعدی (که نتیجه آنها به در"do " منجر به خروجی شود، در غیر این صورت آنها نیز بی‌نیاز هستند) - هیچ نکته ای در این کد وجود ندارد، و نتیجه این است که

write(7);

write(-1);

write(-6);

یک روش متغیر برای عبور پارامترهایی که "توسط مرجع" به نظر می‌رسد استراتژی ارزیابی # فراخوانی با کپی-بازیابی است که در آن روی یک کپی محلی از پارامترهایی کار می‌کند که مقادیر آنها در هنگام خروج از رویه کپی می‌شوند. اگر این رویه به یک پارامتر یکسان دسترسی داشته باشد، اما به روشهای مختلف مانند فراخوانی مانند "Silly (a، a)" یا "Silly (a، b)"، اختلافات ایجاد می‌شود؛ بنابراین، اگر پارامترها با استفاده از کپی کردن منتقل شوند، به ترتیب از چپ به راست "Silly (b،b) "گسترش می‌یابد به

p1:=b; p2:=b;                               {کپی به داخل. متغیرهای محلی p1 و p2 برابر هستند.}

if p2 < 0 then p1:=p2 + b else p1:=-6;      {بنابر این ممکن است متغیر p1 دیگر با p2 برابر نباشد.}

b:=p1; b:=p2;                               {کپی بیرون. از چپ به راست متغیر p1 رو نویسی می‌شود.}

و در این حالت کپی کردن مقدار "p1” (که تغییر یافته‌است) در"b” بی‌معنی است، زیرا بلافاصله با مقدار "p2" بازنویسی می‌شود، که این مقدار اصلاح نشده‌است. در این رویه از مقدار اصلی "b" استفاده می‌شود، بنابراین جمله سوم می‌شود

write(5);          {−۶ نیست.}

چنین اختلافاتی در رفتار احتمالاً باعث ایجاد پازل خواهد شد، و این سؤالات راجع به ترتیب کپی پارامترها تشدید می‌شود: آیا در هنگام خروج مانند ورود نیز چپ به راست می‌شود؟ احتمالاً این جزئیات در کتابچه راهنمای کامپایلر توضیح داده نشده‌است، و اگر وجود داشته باشد، احتمالاً به دلیل نامربوط بودن به وظیفه منتقل می‌شوند و تا زمانی که یک مشکل پیش می‌آید فراموش می‌شوند. اگر (به احتمال زیاد) مقادیر موقتی از طریق یک برنامه ذخیره سازی پشته ارائه می‌شود، احتمالاً روند کپی به عقب (copy-back) به ترتیب معکوس برای کپی به داخل (copy-in) خواهد بود، که در این مثال به این معنی است که"p1” در عوض آخرین مقدار برگشتی به "b" خواهد بود.

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

به عبارت دیگر، یک برنامه آزمایشی کتبی با دقت نوشته شده می‌تواند در مورد اینکه پارامترها براساس مقدار یا مرجع منتقل می‌شوند، گزارش دهند، و در صورت استفاده، از چه نوع طرح کپی به داخل و کپی به خارجی استفاده می‌کنند. با این حال، تنوع بی پایان است: پارامترهای ساده ممکن است با فراخوانی با کپی منتقل شوند در حالی که ساختارهای بزرگ مانند آرایه ممکن است توسط مرجع منتقل شود. ثابتهای ساده مانند صفر ممکن است توسط کدهای ویژه ماشین (مانند پاک کردن یا LoadZ) ایجاد شود در حالی که ثابت‌ترین پیچیدگی‌ها ممکن است در حافظه ذخیره شده و با استفاده از هر تلاشی برای اصلاح آن منجر به خاتمه برنامه فوری و غیره شوند.

به‌طور کلی

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

برخی از زبانهای رایانه اعلان‌های مربوط به استفاده از پارامترها را فعال می‌کنند (یا حتی به آن احتیاج دارند)، و ممکن است فرصتی را فراهم کنند تا اعلام کنند متغیرها مقادیر خود را برای برخی از مجموعه‌ها محدود می‌کنند (به عنوان مثال ،۶<x)تا خرد کردن برای فرایند بهینه سازی و همچنین فراهم کردن بررسی‌های ارزشمند در انسجام کد منبع برای شناسایی اشتباهات آسان شود. اما این هرگز کافی نیست - فقط به بعضی از متغیرها محدودیت‌های ساده ای داده می‌شود، در حالی که برخی دیگر به مشخصات پیچیده‌ای نیاز دارند: چگونه می‌توان مشخص کرد که متغیر "P" یک عدد اول باشد و اگر چنین باشد، یک عضو عدد اول هست یا نیست. پیچیدگی‌ها فوری هستند: با توجه به اینکه "M" یک ماه است، محدوده‌های معتبر برای "D" روزهای یک ماه چیست؟ و آیا همه تخلفات ارزش توقف فوری برنامه را دارند؟ حتی اگر همه این موارد قابل کنترل باشد، چه فایده ای دارد؟ و با چه هزینه ای؟ مشخصات کامل و کنترل با جزییات منجر به بیان و تعریف مجدد توابع برنامه به شکل دیگر می‌شود و جدا از زمانی که کامپایلر در ترجمه آنها مصرف می‌کند، در معرض اشکالات و باگ خواهند بود. در عوض، فقط جزییات ساده با بررسی دامنه در زمان اجرا ارائه می‌شود.

در مواردی که برنامه ای ورودی را نمی‌خواند (مانند مثال)، می‌توان تصور کرد که تحلیل‌های کامپایلر در حال انجام است به طوری که نتیجه بیشتر از یک سری خط‌های چاپ شده نخواهد بود، یا احتمالاً برخی از حلقه‌ها به‌طور مصلحتانه چنین مقادیری را تولید می‌کنند. آیا آنگاه برنامه ای را برای تولید عددهای اول و تبدیل به بهترین روش شناخته شده برای انجام این کار، یا در عوض مراجعه به کتابخانه ارائه می‌دهد؟ بعید است! به‌طور کلی، ملاحظات خودسرانه پیچیده (Entscheidungsproblem)برای جلوگیری از این امر بوجود می‌آید، و چاره ای جز اجرای کد تنها با اصلاحات محدود وجود ندارد.

تاریخچه

برای زبانهای رویه ای یا الگول، تجزیه و تحلیل بینابینی و بهینه سازی به نظر می‌رسد که اوایل دهه ۱۹۷۰ وارد عمل تجاری شده‌اند.

بهینه سازی کامپایلر IBM PL / I از تحلیل‌های بین رویه ای به منظور درک عوارض جانبی فراخونی رویه و استثنائات (به اصطلاح PL / I به عنوان "در شرایط") استفاده کرد.

کار روی کامپایل کردن زبان‌های برنامه‌نویسی، لازمه بهینه سازی درون برنامه است.

تکنیک‌های تحلیل بین رویه ای و بهینه سازی موضوع تحقیقات دانشگاهی در دهه‌های ۱۹۸۰ و ۱۹۹۰ بود.

در اوایل دهه ۱۹۹۰ با کامپایلرهایی از محدب ("کامپایلر برنامه" برای محدب C4 و از اردنت کامپایلر برای [Ardent Titan]) وارد دنیای کامپایلر تجاری شد و دوباره ظهور کردند. این کامپایلرها نشان داده‌اند که فناوری‌ها می‌توانند به اندازه کافی سریع ساخته شوند تا به عنوان یک کامپایلر تجاری قابل قبول باشند. متعاقباً تکنیکهای بین رویه ای در تعدادی از سیستمهای تجاری و غیرتجاری دیده می‌شوند.

نشانه‌ها و پیاده سازی

 کامپایلرهای Intel C / C ++ اجازه بهینه سازی درون تابعی تمام برنامه را می‌دهند. نشانه برای فعال کردن بهینه سازی‌های بین رویه ای برای یک فایل واحد ،ip است، نشانه برای فعال سازی بهینه سازی بین رویه ای در تمام پرونده‌های این برنامه -ipo است.

جی‌سی‌سی دارای توابع داخلی است، که به‌طور پیش فرض در -O3 روشن می‌شود و می‌توان با دادن سوئیچ (-finline-functions) در زمان کامپایل به صورت دستی روشن کرد.

همچنین GCC گزینه ای برای IPO دارد: -fwhole-program --combine.

کامپایلر C ماکروسافت، ادغام شده با ویژوال استودیو (Visual Studio,) همچنین از بهینه سازی درون تابع پشتیبانی می‌کند.

کامپایلرهای GNU(Gnu's Not Unix) GCC و Clang هر دو بهینه سازی درون تابعی (IPO) را در سطح بهینه سازی پشتیبانی می‌کنند.

منابع مرتبط

• بهینه سازی پروفایل (قطعه) محور(PGO:Profile-guided optimization)
• واحد کامپایل تکی(Single Compilation Unit)

پیوند به بیرون

• How to trick C/C++ compilers into generating terrible code?