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

[Y@SiN]

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

[Y@SiN]

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