تجزیه و تحلیل وابستگی

در تئوری کامپایلر، تجزیه و تحلیل وابستگی برای اجرا جمله‌ها/دستور‌ها، محدودیت‌های ترتیبی ایجاد می‌کند. به طور کلی، اگر S1 باید قبل از S2 اجرا شود، دستور S2 به S1 بستگی دارد. به طور گسترده دو دسته از وابستگی ها وجود دارد : وابستگی های کنترلی و وابستگی های داده ای .

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

کنترل وابستگی ها

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

عبارت S2 کنترل وابسته به S1 است (نوشته می‌شود: $S1\ \delta ^{c}\ S2$ ) اگر و فقط اگر اجرای S2 به طور مشروط توسط S1 حفظ شود. در مثال زیر نمونه‌ای از این نوع وابستگی کنترلی دیده می‌شود:

S1 اگر x > 2 باید L1 باشد
S2 y := 3  
S3 L1: z := y + 1

اینجا، S2 تنها در صورت غلط بودن گزاره S1 اجرا می شود.

برای توضیحات بیشتر به وابستگی داده ها مراجعه کنید.

وابستگی داده ها

یک وابستگی داده‌ای از دو عبارت‌هایی که به یک منبع دسترسی مشترک دارند و یا آن را تغییر می دهند، به وجود می‌آید.

وابستگی جریان (واقعی).

یک عبارت S2 به جریان وابسته به S1 است (نوشته شده است $S1\ \delta ^{f}\ S2$ ) اگر و فقط اگر S1 منبعی را تغییر دهد که S2 بخواند و S1 قبل از S2 در اجرا باشد. در زیر نمونه ای از وابستگی به جریان (RAW: Read After Write) آمده است:

S1 x := 10
S2 y := x + c

ضد وابستگی

یک عبارت S2 ضد وابسته به S1 است (نوشته می‌شود $S1\ \delta ^{a}\ S2$ ) اگر و فقط اگر S2 منبعی را تغییر بدهد که S1 را بخواند و S1 قبل از S2 اجرا شود. نمونه زیر نمونه ای از یک ضد وابستگی است:

S1 x := y + c
S2 y := 10

در اینجا، S2 مجموعه ارزش y اما S1 برای خواندن مقدارهای قبلی y .

وابستگی به خروجی

یک عبارت S2 خروجی وابسته به S1 است (نوشته شده $S1\ \delta ^{o}\ S2$ ) اگر و فقط اگر S1 و S2 همان منبع را تغییر دهند و S1 قبل از S2 در اجرا باشد. نمونه زیر نمونه ای از وابستگی خروجی است (WAW: Write After Write):

S1 x := 10
S2 x := 20

در اینجا، S2 و S1 هر دو متغیر x تنظیم می کنند.

وابستگی ورودی

یک عبارت S2 ورودی وابسته به S1 است (نوشته شده $S1\ \delta ^{i}\ S2$ ) اگر و فقط اگر 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.