بلوک پایه
در کامپایلرسازی، به رشته‌ای از کدها که هیچ انشعاب وارد شونده ای به غیر از ورودی و هیچ انشعاب خارج شونده‌ای به غیر از محل خارج شدن از آن رشته کد نداشته باشد، بلوک پایه می‌گویند. این محدود بودنْ قابلیت آنالیز شدن را به بلوک پایه می‌دهد. کامپایلرها معمولاً در قدم اول، برنامه‌ها را به بلوک‌های پایه تجزیه می‌کنند. توسط بلوک‌های پایه میان راس‌ها و یال‌های گراف روند کنترلی را مشخص کرد.
تعریف
در ابتدا تعریف شهودی از یک بلوک پایه را ارائه می‌کنیم و در ادامه تعریف رسمی آن را بیان می‌کنیم. تعریف شهودی بلوک پایه به این صورت است:
کدهایی که در بلوک پایه قرار میگیرند دو ویژگی زیر را دارند:
- هر بلوک پایه فقط یک نقطه ورود دارد، یعنی کدهایی که داخل یک بلوک پایه هستند نمیتوانند مقصد دستورها پرش دیگر در هر کجای برنامه باشند.
- هر بلوک پایه فقط یک نقطه خروج دارد، یعنی فقط آخرین دستور در بلوک پایه میتواند یک دستور پرشی یا شرطی باشد و جریان اجرای برنامه را تغییر دهد.
تحت این شرایط، هر زمانی که اولین دستور در بلوک پایه اجرا شود، تمام دستورها دیگر بلوک پایه نیز باید به اجبار به ترتیب اجرا شوند.
منظور از "کد" در اینجا انواع مختلف کد است یعنی میتواند کد منبع، کد اسمبلی و یا هر ترتیب دیگری از دستورها باشد.
حال تعریف رسمی را بیان می‌کنیم که به این صورت است:
تربیت از دستورها تشکیل یک بلوک پایه را می دهند اگر:
- هر دستوری درجایگاهش بر دستورها در جاگاه‌های بعدی تسلط دارد، به عبارت دیگر هر دستوری باید قبل از دستورها بعدی‌اش اجرا شود.
- هیچ دستور دیگری بین دو دستور متوالی اجرا نشود.
این تعریف رسمی از تعریف شهودی عمومی‌تر است. برای مثال بر اساس این تعریف، امکان اینکه پرش‌های غیرشرطی مقصدهایی داشته باشند که انواع دیگر پرش به آن مقصدها پرش نمی‌کنند را فراهم می‌کند. تعریف رسمی ویژگی‌هایی را برای بلوک پایه‌ها ایجاد می‌کند که کار کردن با آنها را در زمان اجرای الگوریتم‌ها آسان می‌کند.
به بلوک‌های که از آنها وارد یک بلوک پایه می‌شویم، اجداد آن بلوک پایه می‌گویند. همچنین به بلوک‌هایی که وقتی از یک بلوک پایه خارج می‌شویم، به آنها وارد می‌شویم، جانشینان آن بلوک پایه می‌گویند.
شناسایی بلوک های پایه
برای پیدا کردن بلوک های پایه یک الگوریتم ساده وجود دارد. ابتدا این الگوریتم را به صورت کلی توصیف کرده و در ادامه آن را به طور کامل تشریح می‌کنیم. توصیف کلی الگوریتم: اجرا کننده‌ی الگوریتم در ابتدا باید یک دور کد را خوانده و مرزهای بلوک پایه را شناسایی کند (مرزهای بلوک پایه دستورها شروع و پایان بلوک می باشند) و آنها را نشانه‌گذاری می‌کند. دستور شروع بلوک پایه میتواند مقصد یک دستور پرشی و دستور پایان بلوک می تواند یک دستور پرشی باشد. حال کد را در این نقاط "برش" می‌دهیم؛ بلوک‌های پایه تکه کدهایی هستند که باقی می‌مانند.
توجه داشته باشید که این روش همیشه بلوک پایه ماکسیمال را شناسایی نمی‌کند، ولی بنابر تعریف رسمی، بلوک های پایه پیدا شده دارای شرایط کافی می باشند ( بلوک پایه ماکسیمال بلوکی است که نمی‌توان آن را بدون نقض کردن تعریف بلوک پایه، توسط بلوک های مجاورش گسترش داد).
حال این الگوریتم را به صورت کامل شرح می‌دهیم: ورودی: یک ترتیب از دستورها ( که معمولاً کدهای سه آدرسی هستند). خروجی: یک لیست از بلوک های پایه به صورتی که هر دستور سه آدرسی در یک بلوک پایه قرار گیرد. مرحله اول: ابتدا هدرها را در کد مشخص کنید. هدرها دستورهایی هستند که در یکی از شرایط زیر صدق می کنند:
- اولین دستور یک هدر است.
- مقصد یک دستور پرش ( چه شرطی و چه غیرشرطی) یک هدر است.
- دستوری که بلافاصله پس از یک دستور پرش ظاهر شود یک هدر است.
مرحله دوم: با شروع از یک هدر، تمام دستورها بعد از آن تا هدر بعدی در بلوک پایه مربوط به هدر اولیه قرار می گیرد. بنابراین هر بلوک پایه یک هدر دارد. دستورهایی که در پایان یک بلوک پایه ظاهر می شوند یکی از موارد زیر می باشند:
- دستورها پرشی، چه دستورها شرطی و چه دستورها غیر شرطی
- دستور برگشت به تابع صدا زننده
- دستورهایی که ممکن است در آنها یک خطا رخ دهد
- توابعی که نیازی به بازگشت به برنامه ای که آن را صدا زده است نداشته باشد می تواند در پایان یک بلوک پایه ظاهر شوند، مانند توابع exit و longjmp در زبان برنامه نویسی C
- دستورهایی که مربوط به بازگشت می باشند.
دستورهایی که در ابتدا یک بلوک پایه ظاهر می شوند یکی از موارد زیر می باشند:
- دستور ورودی یک تابع
- مقصد دستورها پرشی
- دستورهایی که بلافاصله پس از دستوارتی که خطا تولید می کنند، ظاهر شده باشند.
- دستورهایی که بلافاصله پس از دستورها انشعاب ظاهر شده اند.
- کنترل کننده های خطا
مثال
قطعه کد زیر را برای ضرب داخلی دو بردار a و b که طول هر یک برابر 10 می باشد، در نظر بگیرید.
begin
prod :=0;
i:=1;
do begin
prod :=prod+ a[i] * b[i];
i :=i+1;
end
while i <= 10
end
کد سه آدرسی برای کد منبع فوق به شکل زیر است:
B1 (1) prod := 0 (2) i := 1 B2 (3) t1 := 4* i (4) t2 := a[t1] (5) t3 := 4* i (6) t4 := b[t3] (7) t5 := t2*t4 (8) t6 := prod+t5 (9) prod := t6 (10) t7 := i+1 (11) i := t7 (12) if i<=10 goto (3)
بلوک پایه B1 شامل دستورها (1) تا (2) و بلوک پایه B2 شامل دستورها (3) تا (12) است. توجه کنید طبق قواعد گفته شده دستور (1) دستور شروع برنامه می باشد بنابراین یک هدر است. همچنین دستور (3) مقصد دستوری پرشی در (12) می باشد بنابراین این دستور نیز یک هدر است.
جستارهای وابسته
منابع
- ↑ Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.
- ↑ Daniel), Cooper, Keith D. (Keith (2012). Engineering a compiler. Torczon, Linda. (2nd ed.). Amsterdam: Elsevier/Morgan Kaufmann. p. 231. ISBN 978-0120884780. OCLC 714113472.
- ↑ "Control Flow Analysis" by Frances E. Allen
- ↑ Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. pp. 201–205. doi:10.1109/ICCKE.2015.7365827.
- ↑ "Global Common Subexpression Elimination" by John Cocke
- ↑ Modern Compiler Design by Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen p320
- ↑ Compiler Principles, Techniques and Tools, Aho Sethi Ullman