گراف کنترل جریان

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

یک گراف کنترل جریان (CFG) در علوم کامپیوتر، یک نمایش با استفاده از نشان گذاری گراف از تمام مسیرهای ممکن است که می تواند توسط یک برنامه در زمان اجرای آن پیمایش شود.

معرفی[ویرایش]

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

CFG برای بسیاری از ابزارهای بهینه سازی های کامپایلر و تحلیل ایستا ضروری است.

مثال[ویرایش]

مثال زیر را در نظر بگیرید

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

در بالا، ۴ بلوک پایه داریم: الف از ۰ به ۱، ب از ۲ به ۳، ج در ۴ و د در ۵. به صورت خاص در این حالت، الف "بلوک ورودی"، د "بلوک خروجی" و خطوط ۴ و ۵ اهداف برش هستند. یک گراف برای این قطعه دارای یال هایی از الف به ب، الف به ج، ب به د و ج به د است.