موضوع مقاله: زنجیره استفاده-تعریف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زنجیره استفاده-تعریف | مقدمه: زنجیره استفاده-تعریف یک ساختمان داده است که متشکل از استفاده یک متغیر و همه‌ی تعریف‌هایی از آن متغیر است که می‌تواند به آن استفاده بدون مداخله تعریف دیگری برسد. | ## بخش 1: زنجیره استفاده-تعریف | همتای زنجیره استفاده-تعریف ، زنجیره‌ی تعریف-استفاده است که تشکیل شده‌است از یک تعریف یک متغیر و همه‌ی استفاده‌های آن که قابل دسترسی از آن استفاده بدون مداخله تعریف دیگری است. هر دوی زنجیره‌ی استفاده-تعریف و زنجیره‌ی تعریف-استفاده از یک فرم آنالیز ایستای برنامه به نام آنالیز جریان داده تشکیل شده‌اند. دانستن زنجیره‌های استفاده-تعریف و تعریف-استفاده برای یک برنامه یا زیربرنامه یک پیش‌نیاز برای چند بهینه‌سازی کامپایلر از جمله درهم کردن ثابت و حذف عبارت‌های مشترک است. هدف درست کردن زنجیره‌ی استفاده-تعریف یا تعریف-استفاده یک گام برای تحلیل متغیر زنده است، که باعث می‌شود نمایش منطقی همه‌ی متغیرها شناخته‌شود و در کد ردیابی شود. به دلیل این که مقدار متغیر x در بلاک 2 به هیچ تعریفی از بلاک 1(یا قبل‌تر از آن) بستگی ندارد x ممکن است در آن‌جا متغیری دیگر باشد. گزاره‌ها به این شکل برچسب می‌خورند: s(i) که i یک عدد صحیح در بازه ۱ تا n است؛ که n تعداد گزاره‌های موجود در بلوک پایه است. مثال: v,u فرض می‌شود هر متغیر دارای تعریفی در آن محدوده است.(در فرم تخصیص ایستای منفرد، زنجیره‌های استفاده-تعریف به دلیل این که هر زنجیره یک عضو دارد، صریح هستند.) برای یک متغیر مانند v تعریف اولیه آن با V شناخته می‌شود و برای اختصار تعریف اولیه به شکل s(0) معرفی می‌شود. | ## بخش 2: زنجیره استفاده-تعریف | و البته به طور کلی تعریف اولیه یک متغیر می‌تواند خارج از محدوده انجام شود.(مثال: متغیرهای گلوبال) تعریف یک متغیر وقتی متغیر v در سمت چپ گزاره، مانند s(j) قرار دارد. اجرا فرض کنید لیست مرتب گزاره‌های برنامه را s(j) نام گذاری کنیم و اکنون در حال مشاهده گزاره j ام هستیم: اگر در گزاره s(i) ، i<j یک تعریف وجود داشته باشد در صورتی این تعریف را «زنده» در نظر میگیریم که یک «استفاده» از آن تعریف در گزاره s(k) با شرط k>=j وجود داشته باشد. مجموعه تمام تعریف های زنده در گزاره i را با A(i) و تعداد تعریف های زنده نیز با |A(i)| نشان می‌دهیم. مثالی از اجرای زنجیره تعریف-استفاده این مثال بر پایه کد زیر در زبان جاوا است که وظیفه آن پیدا کردن مقدار بزرگترین مقسوم علیه مشترک دو عدد است. در مثال ما خط هفتم "d=b" اولین گزاره‌ای که در آن از متغیر خوانده‌شده است را جستجو نمایید. در مثال ما خط نهم "return d" اطلاعات به‌دست آمده را به شکل قالب زیر بنویسید: [گزاره‌ای که در آن خواندن صورت گرفته است، گزاره‌ای که در آن نوشتن صورت گرفته‌است، نام متغیری که در حال ساخت زنجیره تعریف-استفاده آن هستیم] در مثال ما می‌شود: [d, d=b, return d] این مراحل را به این شکل تکرار کنید: هر گزاره که در آن خواندن صورت گرفته را با هر گزاره‌ای که در آن نوشتن صورت گرفته ترکیب کنید. برای مثال، از خط ۷ الی ۱۳ در برنامه نوشته شده، متغیر d دوباره تعریف نشده و مقدار آن نیز عوض نشده‌است. | ## بخش 3: زنجیره استفاده-تعریف | به همین دلیل شما باید این گزاره را با همه گزاره‌های خواندن از d که ممکن است پس از این گزاره اجرا شوند ترکیب کنید و به زنجیره اضافه کنید. در مثال ما، فقط خطوط ۱۰ به بعد امکان اجرا پس از خط ۱۴ را دارند و برای مثال خط ۷ هیچگاه دوباره اجرا نخواهد شد. برای هر i در بازه ۱ تا n: a) همه تعریف‌های زنده‌ای که در گزاره s(i) استفاده شده‌اند را پیدا کنید. با این الگوریتم دو چیز به دست می‌آیند: یک گراف DAG با استفاده‌ها و تعریف‌های متغیر ساخته می‌شود. این گراف نشان دهنده یک وابستگی بین داده‌ها در بین تعریف‌ها و استفاده‌های آنها است و این وابستگی یک ترتیب جزئی ایجاد می‌کند. | ## جمع‌بندی | (از همین رو موازی بودن میان گزاره‌ها را نیز مشخص می‌کند.) زمانی که به گزاره s(i) رسیده‌ایم، لیستی از مقداردهی‌های زنده متغیرها وجود دارد.