کامپایلر بهینه‌ساز

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

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

انواع بهینه سازیویرایش

تکنیک های مورد استفاده در بهینه سازی می تواند در زمینه های مختلف به کار برود که می تواند هر چیزی را از یک جمله واحد به کل برنامه تحت تأثیر قرار دهد. به طور کلی ، تکنیکهای محلی مورد استفاده در مقایسه با روشهای جهانی آسانتر هستند اما منجر به دستاوردهای کوچکتر می شوند. برخی از نمونه های دامنه شامل موارد زیر است:

بهینه‌سازی Peepholeویرایش

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

بهینه سازی های محلیویرایش

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

بهینه سازی های جهانیویرایش

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

بهینه سازی حلقهویرایش

اینها در مورد جمله هایی که یک حلقه را تشکیل می دهند ، مانند حلقه for (مانند حرکت کد حلقه بدون تغییر ) عمل می کنند. بهینه سازی حلقه می تواند تأثیر بسزایی داشته باشد زیرا بسیاری از برنامه ها درصد زیادی از زمان خود را در حلقه ها می گذرانند.

بهینه سازی درون برنامه ای ، کل برنامه یا لینک زمانویرایش

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

بهینه سازی کد دستگاه و بهینه ساز Object codeویرایش

برخی از تکنیک هایی که می توانند در محدوده محدودتری اعمال شوند ، مانند فشرده سازی کلان (که با از بین بردن توالی های متداول از دستورالعمل ها موجب صرفه جویی در فضا می شود) وقتی کل تصویر وظیفه اجرایی برای تجزیه و تحلیل در دسترس باشد ، مؤثرتر هستند.[۲]

عوامل مؤثر بر بهینه‌سازیویرایش

خود دستگاهویرایش

بسیاری از گزینه هایی که در مورد آنها بهینه سازی ها می توانند و باید انجام شوند به ویژگی های دستگاه هدف بستگی دارد. پارامتر کردن بعضی از این عوامل وابسته به ماشین گاهی اوقات امکان پذیر است ، به گونه ای که می توان تنها با تغییر پارامترهای توصیف دستگاه ، از یک قطعه کد کامپایلر برای بهینه سازی ماشینهای مختلف استفاده کرد. GCC کامپایلری است که نمونه این رویکرد را نشان می دهد.

معماری CPU هدفویرایش

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

  • RISC vs CISC : مجموعه های دستورالعمل CISC معمولاً دارای طول دستورالعمل متغیر هستند ، معمولاً تعداد بیشتری دستورالعمل ممکن را دارند که می توانند استفاده شوند و هر دستورالعمل می تواند زمانهای مختلفی را ببرد. مجموعه های دستورالعمل RISC سعی در محدود کردن تغییرپذیری در هر یک از این موارد دارند: مجموعه دستورالعمل ها معمولاً دارای طول ثابت هستند ، با استثنائات اندک ، معمولاً تعداد کمتری از ثبت ها و عملیات حافظه ، و میزان انتشار دستورالعمل ها (تعداد دستورالعمل های انجام شده در هر دوره زمانی ، کمتر) وجود دارد. معمولاً یک عدد صحیح از چرخه ساعت) معمولاً در مواردی که تأخیر حافظه عاملی نباشد ، ثابت است. ممکن است روش های مختلفی برای انجام یک کار خاص وجود داشته باشد ، که CISC معمولاً گزینه های بیشتری نسبت به RISC ارائه می دهد. کامپایلرها باید در بین دستورالعمل های مختلف هزینه های نسبی را بدانند و بهترین دنباله دستورالعمل را انتخاب کنند (به انتخاب دستورالعمل مراجعه کنید).
  • خطوط لوله : در واقع یک خط لوله CPU است که به یک خط مونتاژ شکسته می شود. این کار با استفاده از بخش هایی از CPU برای دستورالعمل های مختلف با شکستن اجرای دستورالعمل ها در مراحل مختلف امکان پذیر است: رمزگشایی دستورالعمل ، رمزگشایی آدرس ، انتقال حافظه ، ثبت نام fetch ، محاسبه ، ثبت فروشگاه و غیره. یک دستورالعمل می تواند در مرحله ثبت نام باشد ، در حالی که دیگری می تواند در مرحله ثبت نام باشد. درگیری خط لوله زمانی اتفاق می افتد که یک دستورالعمل در یک مرحله از خط لوله به نتیجه یک دستورالعمل دیگر در پیش روی آن در خط لوله بستگی دارد اما هنوز کامل نشده است. درگیری های خط لوله می تواند به غرفه های خط لوله منجر شود: جایی که CPU چرخه ها را در انتظار حل و فصل یک درگیری می کند.

معماری دستگاهویرایش

  • نرخ انتقال حافظه پنهان / حافظه: اینها نشانگر جریمه برای خطاهای حافظه پنهان است. این مورد عمدتاً در کاربردهای تخصصی مورد استفاده قرار می گیرد.

استفاده در نظر گرفته شده از کد تولید شدهویرایش

اشکال زداییویرایش

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

استفاده عمومیویرایش

انتظار می رود نرم‌افزار Prepackaged در ماشین آلات و CPU های مختلفی اجرا شود که ممکن است یک مجموعه دستورالعمل یکسان را به اشتراک بگذارند ، اما دارای ویژگی های مختلف زمان بندی ، حافظه پنهان یا حافظه هستند. بنابراین ، ممکن است کد به هیچ CPU خاصی تنظیم نشده باشد ، یا ممکن است تنظیم شود تا در محبوب ترین CPU بهترین کار را داشته باشد و در عین حال هنوز هم در سایر پردازنده ها به خوبی قابل قبول کار کند.

استفاده خاصویرایش

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

سیستم های جاسازی شدهویرایش

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

مضامین متداولویرایش

تا حدود زیادی ، تکنیک های بهینه سازی کامپایلر دارای مضامین زیر هستند که گاهی اوقات با هم در تضاد اند.

مورد مشترک را بهینه کنیدویرایش

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

از حشو اجتناب کنیدویرایش

به جای محاسبه مجدد نتایج ، از نتایج محاسبه شده دوباره استفاده کرده و آنها را برای استفاده های بعدی ذخیره کنید.

کمتر کد نویسی کنیدویرایش

محاسبات غیرضروری و مقادیر میانی را حذف کنید. کار کمتر برای پردازنده ، حافظه پنهان و حافظه معمولاً منجر به اجرای سریعتر می شود. متناوباً ، در سیستم های تعبیه شده ، کد کمتر محصول کم هزینه تری را به همراه دارد.

با استفاده از کد خط مستقیم که به آن کد بدون شاخه نیز گفته می شود ، پرش های کمتری انجام می شودویرایش

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

موقعیتویرایش

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

از سلسله مراتب حافظه بهره برداری کنیدویرایش

دسترسی به حافظه برای هر سطح از سلسله مراتب حافظه به طور فزاینده ای گران تر است ، بنابراین قبل از رفتن به دیسک ، بیشترین موارد مورد استفاده را ابتدا در ثبات ها ، سپس حافظه پنهان ، سپس حافظه اصلی قرار دهید.

موازی سازی کنیدویرایش

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

اطلاعات دقیق تر بهتر استویرایش

هرچه اطلاعات کامپایلر دقیق تر باشد ، بهتر می تواند از تکنیک های بهینه سازی یا همه اینها استفاده کند.

ماتریس های زمان اجرا می تواند کمک کندویرایش

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

کاهش قدرتویرایش

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

تکنیک های خاصویرایش

بهینه سازی های حلقهویرایش

مقاله اصلی: بهینه سازی حلقه

برخی از تکنیک های بهینه سازی که اساساً برای کار با حلقه ها طراحی شده اند ، عبارتند از:

تجزیه و تحلیل متغیر القاییویرایش

تقریباً ، اگر یک متغیر در یک حلقه یک تابع خطی ساده از متغیر شاخص باشد ، مانند j: = 4 * i + 1 ، هر زمان که متغیر حلقه تغییر می کند ، می تواند به طور مناسب به روز رسانی شود. این یک کاهش قدرت است ، و همچنین ممکن است اجازه دهد که تعاریف متغیر شاخص به کد مرده تبدیل شوند. این اطلاعات همچنین برای حذف بر اساس بررسی مرزها و تجزیه و تحلیل وابستگی ، از جمله موارد دیگر ، مفید است.

شکاف حلقه یا توزیع حلقهویرایش

شکاف حلقه تلاش می کند تا یک حلقه را به چندین حلقه در یک محدوده شاخص تبدیل کند ، اما هر یک فقط بخشی از بدن حلقه را می گیرد.

همجوشی حلقه یا حلقه ترکیبی یا حلقه رامینگ یا گرفتگی حلقه

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

وارونگی حلقهویرایش

این تکنیک یک حلقه while استاندارد را به حلقه do / while تبدیل می کند (همچنین به عنوان تکرار / تا شناخته می شود) که در یک شرط مشروط قرار گرفته و برای مواردی که حلقه اجرا می شود، تعداد پرش ها را دو تا کاهش می دهد. انجام این کار بررسی وضعیت را کپی می کند (اندازه کد را افزایش می دهد) ، اما کارآمدتر است زیرا پرش ها معمولاً باعث توقف خط لوله می شوند. بعلاوه ، اگر شرط اولیه در زمان کامپایل شناخته شده باشد و بدون عوارض باشد ، می توان از نگهبان if صرف نظر کرد.

تبادل حلقهویرایش

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

حرکت کد حلقه ثابتویرایش

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

بهینه سازی لانه حلقهویرایش

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

  1. ۱٫۰ ۱٫۱ Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. pp. 404, 407. ISBN 978-1-55860-698-2.
  2. Clinton F. Goss (August 2013) [First published June 1986]. "Machine Code Optimization - Improving Executable Object Code" (PDF) (Ph.D. dissertation). Computer Science Department Technical Report #246. Courant Institute, New York University. arXiv:1308.4815. Bibcode:2013arXiv1308.4815G. Retrieved 22 Aug 2013. Lay summary.