تجزیه و تحلیل وابستگی
در تئوری کامپایلر، تجزیه و تحلیل وابستگی برای اجرا جملهها/دستورها، محدودیتهای ترتیبی ایجاد میکند. به طور کلی، اگر S1 باید قبل از S2 اجرا شود، دستور S2 به S1 بستگی دارد. به طور گسترده دو دسته از وابستگی ها وجود دارد : وابستگی های کنترلی و وابستگی های داده ای .
تجزیه و تحلیل وابستگی مشخص میکند که آیا مرتب کردن دوباره یا موازی کردن عبارات بی خطر است یا خیر.
کنترل وابستگی ها
ویرایشکنترل وابستگی موقعیتی است که در آن یک دستورالعمل برنامه اجرا می شود به شرط آنکه دستورالعمل قبلی به گونهای ارزیابی شده باشد تا امکان اجرای آن را فراهم شده باشد.
عبارت S2 کنترل وابسته به S1 است (نوشته میشود: ) اگر و فقط اگر اجرای S2 به طور مشروط توسط S1 حفظ شود. در مثال زیر نمونهای از این نوع وابستگی کنترلی دیده میشود:
S1 اگر x > 2 باید L1 باشد S2 y := 3 S3 L1: z := y + 1
اینجا، S2 تنها در صورت غلط بودن گزاره S1 اجرا می شود.
برای توضیحات بیشتر به وابستگی داده ها مراجعه کنید.
وابستگی داده ها
ویرایشیک وابستگی دادهای از دو عبارتهایی که به یک منبع دسترسی مشترک دارند و یا آن را تغییر می دهند، به وجود میآید.
وابستگی جریان (واقعی).
ویرایشیک عبارت S2 به جریان وابسته به S1 است (نوشته شده است ) اگر و فقط اگر S1 منبعی را تغییر دهد که S2 بخواند و S1 قبل از S2 در اجرا باشد. در زیر نمونه ای از وابستگی به جریان (RAW: Read After Write) آمده است:
S1 x := 10 S2 y := x + c
ضد وابستگی
ویرایشیک عبارت S2 ضد وابسته به S1 است (نوشته میشود ) اگر و فقط اگر S2 منبعی را تغییر بدهد که S1 را بخواند و S1 قبل از S2 اجرا شود. نمونه زیر نمونه ای از یک ضد وابستگی است:
S1 x := y + c S2 y := 10
در اینجا، S2 مجموعه ارزش y
اما S1 برای خواندن مقدارهای قبلی y
.
وابستگی به خروجی
ویرایشیک عبارت S2 خروجی وابسته به S1 است (نوشته شده ) اگر و فقط اگر S1 و S2 همان منبع را تغییر دهند و S1 قبل از S2 در اجرا باشد. نمونه زیر نمونه ای از وابستگی خروجی است (WAW: Write After Write):
S1 x := 10 S2 x := 20
در اینجا، S2 و S1 هر دو متغیر x
تنظیم می کنند.
وابستگی ورودی
ویرایشیک عبارت S2 ورودی وابسته به S1 است (نوشته شده ) اگر و فقط اگر S1 و S2 یک منبع را بخوانند و S1 قبل از S2 در اجرا باشد. مثال زیر نمونه ای از وابستگی ورودی (RAR: Read-After-Read) است:
S1 y := x + 3 S2 z := x + 5
در اینجا، S2 و S1 هر دو به متغیر x
دسترسی دارند. این وابستگی سفارش مجدد را ممنوع نمی کند.
وابستگی های حلقه
ویرایشمشکل محاسبه وابستگی ها در حلقه ها، که یک مشکل مهم و غیر پیش پا افتاده است، با تجزیه و تحلیل وابستگی حلقه، که چارچوب وابستگی ارائه شده در اینجا را گسترش می دهد، حل می شود.
همچنین ببینید
ویرایش- تجزیه و تحلیل برنامه (علوم کامپیوتر)
- موازی سازی خودکار
- بردارسازی خودکار
- تحلیل وابستگی حلقه
- چارچوب هایی که از مدل چند وجهی پشتیبانی می کنند
- خطر (معماری کامپیوتر)
- برش برنامه
- حذف کد مرده
خواندن بیش
ویرایش- Kennedy, Ken; Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
- Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4.
- Cooper, Keith D.; Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X.