زنجیره استفاده-تعریف

زنجیره استفاده-تعریف (به انگلیسی: use-definition chain) یک ساختمان داده(به انگلیسی: data structure) است که متشکل از استفاده یک متغیر و همه‌ی تعریف‌هایی از آن متغیر است که می‌تواند به آن استفاده بدون مداخله تعریف دیگری برسد. به طور کلی زنجیره استفاده-تعریف به معنی انتساب چند مقدار به یک متغیر است. همتای زنجیره استفاده-تعریف (به انگلیسی: use-definition chain)، زنجیره‌ی تعریف-استفاده (به انگلیسی: definition-use chain) است که تشکیل شده‌است از یک تعریف یک متغیر و همه‌ی استفاده‌های آن که قابل دسترسی از آن استفاده بدون مداخله تعریف دیگری است. هر دوی زنجیره‌ی استفاده-تعریف و زنجیره‌ی تعریف-استفاده از یک فرم آنالیز ایستای برنامه (به انگلیسی: static code analysis) به نام آنالیز جریان داده (به انگلیسی: data-flow analysis) تشکیل شده‌اند. دانستن زنجیره‌های استفاده-تعریف و تعریف-استفاده برای یک برنامه یا زیربرنامه یک پیش‌نیاز برای چند بهینه‌سازی کامپایلر از جمله درهم کردن ثابت و حذف عبارت‌های مشترک است.

هدف

درست کردن زنجیره‌ی استفاده-تعریف یا تعریف-استفاده یک گام برای تحلیل متغیر زنده است، که باعث می‌شود نمایش منطقی همه‌ی متغیرها شناخته‌شود و در کد ردیابی شود. تکه کد زیر را در نظر بگیرید:

int x = 0;    /* A */
x = x + y;    /* B */
/* 1, some uses of x */
x = 35;       /* C */
/* 2, some more uses of x */

که همانطور که در کد مشخص است متغیر x سه بار مقداردهی شده‌است.(در نقاط A, B, C) با این که در نقطه‌ای که با "1" مشخص شده‌است زنجیره‌ی استفاده-تعریف برای x باید مشخص کند که مقدار حاضر این متغیر باید از خط B بیاید (و مقدار x در خط B باید از خط A بیاید) اما در نقطه‌ای که با "2" مشخص شده‌است زنجیره‌ی استفاده-تعریف برای x نشان می‌دهد که مقدار حال حاضر این متغیر از C آمده‌است. به دلیل این که مقدار متغیر x در بلاک 2 به هیچ تعریفی از بلاک 1(یا قبل‌تر از آن) بستگی ندارد x ممکن است در آن‌جا متغیری دیگر باشد. در عمل می‌توان گفت یک متغیر دیگر است که ما آن را x2 می‌نامیم.

int x = 0;    /* A */
x = x + y;    /* B */
/* 1, some uses of x */
int x2 = 35;  /* C */
/* 2, some uses of x2 */

فرایند تقسیم x به دو متغیر جدا را تقسیم دامنه‌ی زنده (به انگلیسی: live range splitting) می‌نامند. همچنین فرم تخصیص ایستای منفرد را نیز ببینید.

برپایی

لیست گزاره‌ها ترتیب مشخصی از گزاره‌ها ارائه می‌دهد.

• گزاره‌ها به این شکل برچسب می‌خورند: s(i) که i یک عدد صحیح در بازه ۱ تا n است؛ که n تعداد گزاره‌های موجود در بلوک پایه(به انگلیسی: basic block) است.
• متغیرها با حروف انگلیسی ایتالیک نشان داده می‌شوند. مثال: v,u
• فرض می‌شود هر متغیر دارای تعریفی در آن محدوده (به انگلیسی: scope or context) است.(در فرم تخصیص ایستای منفرد، زنجیره‌های استفاده-تعریف به دلیل این که هر زنجیره یک عضو دارد، صریح (به انگلیسی: explicit) هستند.)

برای یک متغیر مانند v تعریف اولیه آن با V شناخته می‌شود و برای اختصار تعریف اولیه به شکل s(0) معرفی می‌شود. و البته به طور کلی تعریف اولیه یک متغیر می‌تواند خارج از محدوده انجام شود.(مثال: متغیرهای گلوبال)

تعریف یک متغیر

وقتی متغیر v در سمت چپ گزاره، مانند s(j) قرار دارد. آن‌گاه s(j) تعریف v خواهد شد. هر متغیر v حداقل یک تعریف از تعریف اولیه V(یا شروع برنامه) دارد.

استفاده یک متغیر

اگر متغیر v در سمت راست گزاره s(j) باشد. آنگاه یک گزاره s(i) با i<j و min(i-j) وجود دارد که تعریف v است و در s(j) استفاده دارد.(یا به اختصار، وقتی متغیر v در سمت راست گزاره s(j) قرار دارد آنگاه v در گزاره s(j) استفاده دارد.

اجرا

فرض کنید لیست مرتب گزاره‌های برنامه را s(j) نام گذاری کنیم و اکنون در حال مشاهده گزاره j ام هستیم:

• اگر در گزاره s(i) ، i<j یک تعریف وجود داشته باشد در صورتی این تعریف را «زنده» (به انگلیسی: alive) در نظر میگیریم که یک «استفاده» (به انگلیسی: use) از آن تعریف در گزاره s(k) با شرط k>=j وجود داشته باشد. مجموعه تمام تعریف های زنده در گزاره i را با A(i) و تعداد تعریف های زنده نیز با |A(i)| نشان می‌دهیم. (A(i) مفهمومی ساده و قدرتمند است. نتایج نظری و عملی در space complexity theory، access complexity، Register allocation، cache locality exploitation همه بر پایه A(i) به‌دست آمده‌اند.)
• اگر تعریفی در گزاره s(i) وجود داشته باشد، این تعریف تمام تعریف‌های قبلی همان متغیر مانند s(k) به شرط k<i را می‌کشد (به انگلیسی: kill).

مثالی از اجرای زنجیره تعریف-استفاده

این مثال بر پایه کد زیر در زبان جاوا است که وظیفه آن پیدا کردن مقدار بزرگترین مقسوم علیه مشترک دو عدد است. (نیازی به فهمیدن نحوه عملکرد تابع نیست.)

/**

* @param(a, b) The values used to calculate the divisor.
* @return The greatest common divisor of a and b.
*/

int gcd(int a, int b) {

   int c = a;
   int d = b; 
   if (c == 0)
       return d;
   while (d != 0) { 
       if (c> d)
           c = c - d;
       else
           d = d - c;
   } 
   return c; 

}

برای یافتن تمام زنجیره‌های تعریف-استفاده مربوط به متغیر d، مراحل زیر انجام دهید:

1. اولین گزاره‌ای که در آن این متغیر تعریف شده و مقدار به آن تخصیص داده شده‌است را جستجو نمایید. در مثال ما خط هفتم "d=b"
2. اولین گزاره‌ای که در آن از متغیر خوانده‌شده است را جستجو نمایید. در مثال ما خط نهم "return d"
3. اطلاعات به‌دست آمده را به شکل قالب زیر بنویسید: [گزاره‌ای که در آن خواندن صورت گرفته است، گزاره‌ای که در آن نوشتن صورت گرفته‌است، نام متغیری که در حال ساخت زنجیره تعریف-استفاده آن هستیم] در مثال ما می‌شود: [d, d=b, return d]

این مراحل را به این شکل تکرار کنید: هر گزاره که در آن خواندن صورت گرفته را با هر گزاره‌ای که در آن نوشتن صورت گرفته ترکیب کنید. (با در نظر گرفتن تغییر مقدار متغیر) نتیجه باید به شکل مقابل باشد:

[d, d=b, return d] 
[d, d=b, while(d!=0)] 
[d, d=b, if(c>d)] 
[d, d=b, c=c-d] 
[d, d=b, d=d-c]
[d, d=d-c, while(d!=0)] 
[d, d=d-c, if(c>d)] 
[d, d=d-c, c=c-d] 
[d, d=d-c, d=d-c]

باید در صورت تغییر مقدار متغیر، اقدام‌های لازم را انجام دهید. برای مثال، از خط ۷ الی ۱۳ در برنامه نوشته شده، متغیر d دوباره تعریف نشده و مقدار آن نیز عوض نشده‌است. در خط ۱۴، این متغیر دوباره مقداردهی شده‌است و ممکن است مقدار جدیدی پیدا بکند. به همین دلیل شما باید این گزاره را با همه گزاره‌های خواندن از d که ممکن است پس از این گزاره اجرا شوند ترکیب کنید و به زنجیره اضافه کنید. در مثال ما، فقط خطوط ۱۰ به بعد امکان اجرا پس از خط ۱۴ را دارند و برای مثال خط ۷ هیچگاه دوباره اجرا نخواهد شد. برای فهم بهتر می‌توانید دو متغیر متفاوت به نام‌های d1 , d2 را تصور کنید و زنجیره آن‌ها را به این شکل محاسبه کنید:

[d1, d1=b, return d1] 
[d1, d1=b, while(d1!=0)] 
[d1, d1=b, if(c>d1)] 
[d1, d1=b, c=c-d1] 
[d1, d1=b, d1=d1-c]
[d2, d2=d2-c, while(d2!=0)] 
[d2, d2=d2-c, if(c>d2)] 
[d2, d2=d2-c, c=c-d2] 
[d2, d2=d2-c, d2=d2-c]

در نتیجه می‌توانید چیزی شبیه برنامه زیر داشته باشید. متغیر d1 می‌تواند با متغیر b جابجا شود.

/**

* @param(a, b) The values used to calculate the divisor.
* @return The greatest common divisor of a and b.
**/

int gcd(int a, int b) {

   int c = a;
   int d; 
   if (c == 0)
       return b;
   if (b != 0) {
       if (c> b) {
           c = c - b;
           d = b;
       }
       else
           d = b - c;
       while (d != 0) { 
           if (c> d)
               c = c - d;
           else
               d = d - c;
       }
   } 
   return c; 

}

روش به دست آوردن زنجیره استفاده-تعریف

1. تعریف ها را در گزاره s(0) قرار دهید.
2. برای هر i در بازه ۱ تا n:

a) همه تعریف‌های زنده‌ای که در گزاره s(i) استفاده شده‌اند را پیدا کنید.

b) ارتباطات بین استفاده ها و تعریف ها را ایجاد کنید.

c) گزاره s(i) را به عنوان گزاره تعریف قرار دهید.

d) همه تعاریف قبلی را بکشید.

با این الگوریتم دو چیز به دست می‌آیند:

1. یک گراف DAG با استفاده‌ها و تعریف‌های متغیر ساخته می‌شود. این گراف نشان دهنده یک وابستگی بین داده‌ها در بین تعریف‌ها و استفاده‌های آنها است و این وابستگی یک ترتیب جزئی ایجاد می‌کند. (از همین رو موازی بودن میان گزاره‌ها را نیز مشخص می‌کند.)
2. زمانی که به گزاره s(i) رسیده‌ایم، لیستی از مقداردهی‌های زنده متغیرها وجود دارد. برای مثال اگر تنها یک مقداردهی زنده وجود داشته باشد می‌توانیم از روش constant propagation استفاده کنیم.