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

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

حلقه‌ها بهترین کاندیداها برای بهینه‌سازی هستند چراکه بیشتر وقت برنامه در حلقه‌ها
صرف می‌شود.
تحلیل متغیرهای استقرایی: در هر حلقه اگر متغیری باشد که به صورت حاصل عملیات ریاضی
بیان شده باشد، شاید بتوان آن را هربار بدون محاسبه (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 افزایش زیاد حجم کد، باید در مورد
هوشیاری بکار گرفته شود