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

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

بهینه‌سازی حلقه‌ها

حلقه‌ها بهترین کاندیداها برای بهینه‌سازی هستند چراکه بیشتر وقت برنامه در حلقه‌ها صرف می‌شود. تحلیل متغیرهای استقرایی: در هر حلقه اگر متغیری باشد که به صورت حاصل عملیات ریاضی بیان شده باشد، شاید بتوان آن را هربار بدون محاسبه (index variable) بر روی متغیر اندیس دوباره، با یک تغییر کوچک بروز کرد. این کار همچنین می‌تواند متغیر اندیس را به سمت بی‌مصرف شدن و در نهیت حذف پیش ببرد. مساوی داشته باشند و با داده (iteration) تلفیق حلقه‌ها: اگر دو حلقه مجاور تعداد تکرار های یکدیگر کار نکنند، می‌توان آن‌ها را تلفیق کرده و به یک حلقه واحد تبدیل کرد تا بدینگونه جلوگیری شود. (توجه داشته باشید که برای loop overhead از پرداخت هزینه اضافی بررسی تساوی تعداد تکرار دو حلقه، نیازی نداریم تعداد دقیق تکرار را بدانیم). هر چند گاهی عکس این عمل نیز (تبدیل یک حلقه به چند حلقه جدا از هم) می‌تواند باعث بهینه شدن کد شود که این مورد بیشتر در مورد پردازنده‌های چند هسته‌ای بکار می‌رود است while بهتر از حلقه‌های do/while واژگون کردن حلقه: اغلب استفاده از حلقه‌های چرا که چک کردن شرط حلقه در آخر حلقه باعث استفاده کمتر از پرش می‌شود. (به یاد را می‌گیرند. pipelining داشته باشید در اغلب پردازنده‌ها دستورها پرش جلوی استفاده از جابجایی کد مستقل از حلقه: اگر مقدار یک عبارتی که باید محاسبه شود در تمام تکرارهای حلقه ثابت باشد، با جابجا کردن کد مربوط به محاسبه حاصل عبارت به بیرون حلقه می توانیم سرعت برنامه را افزایش دهیم. بازکردن حلقه: اگر تعداد تکرار یک حلقه در زمان کامپایل مشخص باشد، می‌توان کد بدنه حلقه را به آن تعداد کپی کرد تا از چک کردن شرط حلقه و همچنین دستورها پرش جلوگیری می‌شود و ممکن cache شود. هرچند این کار باعث افزایش طول کد و استفاده کمتر از است حتی برنامه را کندتر هم بکند. در واقع این تکنیک چیزی نیست که بتوان همیشه روی آن حساب کرد. اگر در داخل بدنه یک حلقه، انشعابی داشته باشیم که شرط آن: Loop unswitching مستقل از حلقه است، می‌توانیم آن را به بیرون حلقه آورده و حلقه را در هر یک از شاخه های انشعاب کپی کنیم. این کار، اگر چه باعث افزایش حجم کد می‌شود، اما به پردازنده درون حلقه‌ها را دارند کمک می‌کند (parallelization)های جدید که قابلیت هم‌زمان سازی کد را سریعتر اجرا کنند. اگر دستورها درون یک حلقه مجبور باشند پشت سر هم اجرا شوند (نتوان آنها: Pipelining کرد) ولی اجرای آن‌ها در تکرارهای مختلف حلقه مستقل از هم باشد، می‌توان pipeline را pipeline کد چند بار اجرای آن (برای تکرارهای بعد) را در بدنه حلقه گذاشت تا با این کار به کردن سخت‌افزاری کمک کنیم.

بهینه‌سازی‌های مبتنی بر جریان داده

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

بهینه‌سازی‌های مربوط به تولید کد

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

دیگر بهینه‌سازی‌ها

اگر فراخوانی بازگشتی یک تابع در انتهای آن صورت: (Tail Recursion) حذف بازگشتی از ته گرفته باشد، می‌توان آن به یک تابع غیربازگشتی تبدیل کرد تا ار هزینه فراخوانی چندباره تابع جلوگیری شود. خذف بررسی کرانه‌ها: برای زبان‌های برنامه‌نویسی که قبل از دسترسی به یک آرایه از طریق اندیس، مقدار اندیس را بررسی می‌کنند که در محدوده آرایه باشد، حذف این بررسی در مواقعی که مقدار اندیس در زمان کامپایل معلوم است می‌تواند کمک بزرگی به سرعت اجرای برنامه بکند. حذف کد مرده: کامپایلر می‌تواند با تشخیص اینکه حاصل یک قطعه کد در هیچ جای دیگری استفاده نشده‌است، آن را حذف کند. این عملیات باید یکی از آخرین عملیاتهای بهینه‌سازی باشد چرا که بسیاری از بهینه‌سازی‌های دیگر حجم کد مرده را بیشتر می‌کنند. کردن توابع: این کار می‌تواند از هزینه فراخوانی توابع جلوگیری کند و بخصوص در Inline کاربرد دارد. هر چند، به علت (functional) بهینه‌سازی زبان‌های شئ گرا و زبان‌های روال گرا ها که مقدار حافظه محدودی دارند با embedded system افزایش زیاد حجم کد، باید در مورد هوشیاری بکار گرفته شود

منابع

دانشنامه آزاد ویکی‌پدیای انگلیسی