تولید کد (Code Generation) در طراحی کامپایلر — راهنمای جامع

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

• می‌بایست حامل معنی دقیق کد منبع باشد
• می‌بایست از نظر مصرف CPU و مدیریت حافظه بهینه باشد.

اینک خواهیم دید که کد میانی به کد آبجکت مقصد که در این مورد اسمبلی است تبدیل می‌شود.

گراف بی‌دور جهت‌دار

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

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

کلیک کنید

• گره‌های برگ نشان‌دهنده شناسه‌ها، نام‌ها یا ثابت‌ها
• گره‌های درونی نشان‌دهنده عملگرها
• گره‌های درونی همچنین نشان‌دهنده نتایج عبارت‌ها یا شناسه‌ها/ نام‌ها هستند که مقادیرشان باید انتساب یافته یا ذخیره شوند.

مثال

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t0 = a   + b]

[t1 = t0 + c]

[d = t0 + t1]

بهینه‌سازی Peephole

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

حذف دستورالعمل‌های تکراری

در سطح کد منبع، موارد زیر از سوی کاربر قابل اجرا هستند:

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

• MOV x, R0
• MOV R0, R1

می‌توانیم دستور نخست را حذف کنیم و جمله را به صورت زیر بازنویسی کنیم:

MOV x, R1

کد غیر قابل دسترسی

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

مثال

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is%d”, x);
}

در این قطعه کد، عبارت printf هرگز اجزا نمی‌شود، زیرا کنترل برنامه پیش از اجرای آن باز می‌گردد و از این رو می‌توان printf را حذف کرد.

بهینه‌سازی گردش کنترل

مواردی در کد وجود دارند که کنترل برنامه بدون اجرای هیچ وظیفه خاصی بین متدهای مختلف دست به دست می‌شود. این پرش‌ها را می‌توان حذف کرد. برای مثال کد زیر را ملاحظه کنید:

...
MOV R1, R2
GOTO L1
...
L1: GOTO L2
L2: INC R1

در این کد برچسب L1 را می‌توان حذف کرد، چون کنترل را به L2 می‌سپارد. بنابراین به جای پرش به L1 و سپس L2 کنترل می‌تواند مانند کد زیر، به طور مستقیم به L2 برسد:

...
MOV R1, R2
GOTO L2
...
L2: INC R1

ساده‌سازی عبارت‌های جبری

مواردی در کد وجود دارند که عبارت‌های جبری را می‌توان ساده‌تر کرد. برای نمونه عبارت a = a + 0 را می‌توان با حذف a ساده‌تر کرد و عبارت a = a+1 را می‌توان با جایگزینی عملگر افزایشی به صورت a++ ساده‌تر نوشت.

کاهش مصرف منابع

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

برای نمونه x * 2 را می‌توان با x<<1 جایگزین کرد که تنها به یک جابجایی به چپ نیاز دارد. با این که خروجی a * a با a² یکسان است؛ اما a² پیاده‌سازی بسیار کارآمدتری دارد.

دسترسی به دستورالعمل‌های رایانه

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

تولیدکننده کد

از یک تولیدکننده کد انتظار می‌رود که درکی از محیط زمان اجرای (runtime environment) ماشین مقصد داشته باشد و مجموعه دستورالعمل‌های آن را بشناسد. تولیدکننده کد برای ایجاد کد باید ملاحظات زیر را در نظر بگیرد:

فیلم آموزش طراحی کامپایلر – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

• زبان مقصد – تولیدکننده کد از ماهیت زبان مقصدی که کد به آن تبدیل می‌شود باید آگاه باشد. این زبان برخی دستورالعمل‌های خاص رایانه را مورد استفاده قرار می‌دهد تا کامپایلر بتواند کد را به روشی راحت‌تر تولید کند. ماشین مقصد می‌تواند دارای معماری پردازنده CISC یا RISC باشد.
• نوع IR – بازنمایی میانی (IR) شکل‌های مختلفی دارد. این بازنمایی می‌تواند به شکل ساختمان درخت نحوی مجرد (AST)، نمادگذاری لهستانی معکوس یا کد 3 آدرسی باشد.
• انتخاب دستورالعمل – تولیدکننده کد بازنمایی میانی را به عنوان ورودی می‌گیرد و آن را به مجموعه دستورالعمل‌های ماشین مقصد تبدیل (نگاشت) می‌کند. یک بازنمایی می‌تواند روش (دستورالعمل) های مختلفی برای تبدیل شدن داشته باشد و از این رو معقول است که تولیدکننده بهترین دستورالعمل را به روشی هوشمندانه انتخاب نماید.
• تخصیص ثبّات – یک برنامه چند مقدار دارد که باید در طی اجرا حفظ شوند. معماری ماشین مقصد ممکن است اجازه ندهد که همه مقادیر در حافظه CPU یا ثبات‌ها حفظ شوند. تولیدکننده کد تصمیم می‌گیرد که کدام مقادیر باید در ثبات‌ها حفظ شوند. همچنین تصمیم می‌گیرد که کدام ثبات‌ها برای حفظ این مقادیر مورد استفاده قرار گیرند.
• ترتیب‌بندی دستورالعمل‌ها – در نهایت تولیدکننده کد تصمیم می‌گیرد که کدام ترتیب از دستورالعمل‌ها اجرا شود. تولیدکننده کد، ترتیب زمانی اجرای دستورالعمل‌ها را تعیین می‌کند.

توصیفگرها (Descriptors)

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

• توصیفگر ثبّات - توصیفگر ثبات برای اطلاع‌رسانی موجود بودن ثبات‌ها به تولیدکننده کد استفاده می‌شود. توصیفگر ثبات، رد مقادیر ذخیره شده در هر ثبات را نگهداری می‌کند و هر زمان که در طی فرایند تولید کد، یک ثبات جدید مورد نیاز بود، موجود بودن ثبات از این توصیفگر سؤال می‌شود.
• توصیفگر آدرس – مقادیر نام‌ها (شناسه‌ها) که در برنامه استفاده می‌شوند ممکن است در موقعیت‌های مختلفی در زمان اجرا ذخیره شوند. از توصیفگرهای آدرس برای پیگیری رد موقعیت‌های حافظه که برای ذخیره مقادیر شناسه‌ها استفاده شده بهره می‌گیریم. این موقعیت‌ها ممکن است شامل ثبات‌های CPU، هیپ‌ها، پشته‌ها یا ترکیبی از موقعیت‌های فوق باشند.

تولید کنند کد هر زمان هر دو توصیفگر را به‌روزرسانی می‌کند. برای یک عبارت Load، LD، R1، تولیدکننده کد:

• توصیفگر ثبات، R1 را که مقدار x دارد به‌روزرسانی می‌کند.
• توصیفگر آدرس (x) را برای نمایش یک وهله از x در R1 به‌روزرسانی می‌کند.

تولید کد

بلوک‌های ابتدایی یک توالی از دستورالعمل‌های سه آدرسی تشکیل می‌دهند و تولیدکننده کد از این توالی دستورالعمل‌ها به عنوان ورودی استفاده می‌کند.

فیلم آموزش طراحی کامپایلر مرور و حل تست های کنکور کارشناسی ارشد در فرادرس

کلیک کنید

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

getRag: تولیدکننده کد از تابع getRag برای تعیین وضعیت استفاده می‌کند:

• اگر متغیر y قبلاً در ثبات R باشد، از این رجیستر استفاده می‌کند.
• در غیر این صورت اگر ثبات R موجود باشد از این ثبات استفاده می‌کند.
• در غیر این صورت هر دو گزینه فوق ناممکن هستند و ثباتی انتخاب می‌شود که نیازمند کمترین تعداد دستورالعمل‌های بارگذاری و ذخیره‌سازی باشد.

نمونه تولید کد

برای دستورالعمل x = y OP z، تولید کنند کد می‌تواند اعمال زیر را اجرا کند. فرض کنید که L موقعیت (ترجیحاً رجیستر) باشد که خروجی y OP z باید در آن ذخیره شود:

• تابع getRag فراخوانی می‌شود تا در مورد موقعیت L تصمیم‌گیری شود.
• موقعیت کنونی (ثبات یا حافظه) برای y با مشاوره توصیفگر آدرس y انتخاب می‌شود. اگر y اکنون در ثبات L ذخیره نشده باشد، در این صورت دستورالعمل‌های زیر برای کپی مقدار y به L تولید می‌شود:
  MOV y’, L
  که y’ مدار کپی شده y را نشان می‌دهد.
• موقعیت کنونی z با استفاده از همان روش مورد استفاده در گام 2 برای y تعیین شده و دستورالعمل زیر تولید می‌شود:
  OP z’, L
  که z’ نشان‌دهنده مقدار کپی شده مقدار z است.
• اینک L شامل مقدار y OP z است که به منظور انتساب به x استفاده می‌شود. بنابراین اگر L یک ثبات باشد، توصیفگر آن برای نشان دادن این که شامل مقدار x است به‌روزرسانی می‌شود. توصیفگر x برای نمایش این که این مقدار در موقعیت L ذخیره شده است به‌روزرسانی می‌شود.
• اگر y و z کاربرد دیگری داشته باشند، در این صورت می‌توانند به سیستم بازگشت داده شوند.

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

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

• آموزش طراحی کامپایلر
• مجموعه آموزش‌های برنامه‌نویسی
• مجموعه آموزش‌های مهندسی نرم افزار
• تجزیه پایین به بالا — طراحی کامپایلر
• کامپایلر، طراحی و معماری آن — به زبان ساده
• آموزش تجزیه انتقال (کاهش) در طراحی کامپایلر
• آموزش طراحی کامپایلر (مرور و حل تست های کنکور کارشناسی ارشد)

==