تحلیل متغیر زنده

در کامپایلر تحلیل متغیر زنده (یا همان تحلیل زنده بودن) یک مسئله‌ی سنتی تحلیل جریان داده برای محاسبه متغیرهایی میباشد که در هر لحظه از برنامه زنده هستند. یک متغیر زمانی زنده است که دارای مقداری است که ممکن است در آینده به آن نیاز شود، یا به‌طور معادل مقدار آن قبل از اینکه مقدار بعدی در آن نوشته شود، خوانده خواهد شد. بیشترین کاربرد این تحلیل در تخصیص ثبات میباشد. جرا که با توجه به تعداد محدود ثبات‌ها یک ثبات تنها زمانی میتواند برای دو متغیر استفاده شود که این دو متغیر هیچگاه همزمان زنده نباشند.

مثال

برنامه‌ی زیر را در نظر بگیرید:

b = 3
c = 5
a = f(b * c)

مجموعه‌ی متغیرهای زنده بین خط دو و سه {b, c} می‌باشد؛ زیرا هر دوی آنها برای ضرب در خط سوم استفاده می‌شوند. ولی مجموعه‌ی متغیرهای زنده در خط یک فقط {b} می‌باشد، چون متغیر c در ادامه در خط دو آپدیت می‌شود. مقدار متغیر a در این کد استفاده نشده‌است.

در نظر داشته باشید که ممکن است خط سه، از آنجایی که از a بعداً استفاده نمی‌شود، پاک شود. ولی ما اطلاعات کافی برای پاک کردن خط سه نداریم؛ بنابراین ممکن است عوارض جانبی داشته باشد (به‌طور مثال ممکن است مقدار b * c بعداً چاپ شود)

عبارت ریاضی مرتبط با معادله جریان داده

تحلیل زنده بودن یک تحلیل «معکوس محتمل» می‌باشد. تحلیل به صورت معکوس انجام می‌شود و عملگر برخورد جریان داده عملگر اجتماع می‌باشد. به زبانی دیگر، هنگامی که تحلیل متغیر زنده برای یک تابع با تعدادی شاخه‌های عبارات منطقی در آن اعمال می‌شود، تحلیل از آخر تابع شروع به اعمال می‌شود تا به اول تابع برسد (پس معکوس است). و یک متغیر زنده محسوب می‌شود، اگر هر کدام از شاخه‌های عبارات منطقی که به داخل حرکت می‌کنند ممکن است به مقدار فعلی متغیر نیاز داشته باشند (پس محتمل است). این در تضاد با «معکوس حتمی» می‌باشد که در آن، این شرط برای شاخه‌هایی که به خارج حرکت می‌کنند اجرا می‌شود.

معادلات جریان داده برای بلوک ساده s و بلوک خارج شونده f در تحلیل متغیرهای زنده به صورت زیر است:

${\displaystyle {\mbox{GEN}}[s]}$: مجموعه متغیرهایی که در s استفاده شده‌اند قبل از اینکه مقدار جدیدی به آنها داده شود.

${\displaystyle {\mbox{KILL}}[s]}$:مجموعه متغیرهایی که مقداری به آنها در s داده شده‌است (در بسیاری از کتاب‌ها^{[نیازمند شفاف‌سازی]} مقدار KILL (s) همچنین به معنای مجموعه متغیرهایی که قبل از هیچ استفاده ای در s به آن‌ها مقداری داده شده‌است نیز تعریف شده‌است ، ولی این راه‌حل معادله جریان داده را تغییر نمی‌دهد)

${\displaystyle {\mbox{LIVE}}_{in}[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{out}[s]-{\mbox{KILL}}[s])}$

${\displaystyle {\mbox{LIVE}}_{out}[final]={\emptyset }}$

${\displaystyle {\mbox{LIVE}}_{out}[s]=\bigcup _{p\in succ[s]}{\mbox{LIVE}}_{in}[p]}$

${\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}$

${\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}$

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

الگوریتم محاسبه متغیرهای زنده

هیچ متغیری زنده نیست مگر در گراف بلوک‌های پایه مسیری پیدا شود که در طی این مسیر متغیر قبل از تعریف دوباره استفاده شود. بنابراین ما با این فرض که هیچ متغیری در خروج از هیچ بلوک پایه‌ای زنده نیست شروع میکنیم. روند به دلیل این که ما تنها متغیرها را به مجموعه اضافه میکنیم و تعداد متغیرها محدود میباشد متوقف میشود. الگوریتم به صورت زیر پیاده سازی میشود:

FOR all blocks B DO
  IN(B) = Gen(B)
ENDFOR
WHILE there are changes DO
  FOR each block B DO
    Out(B) =  In(S)
        S  Succ(B)
    In(B) = (Out(B) - Kill(B))  Gen(B)
  ENDFOR
ENDWHILE

الگوریتم worklist

برنامه‌ی زیر را در نظر بگیرید:

// in: {} b1: a = 3; b = 5; d = 4; x = 100; //x is never being used later thus not in the out set {a,b,d} if a > b then // out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d} // in: {a,b} b2: c = a + b; d = 2; // out: {b,d} // in: {b,d} b3: endif c = 4; return b * d + c; // out:{}

از آنجا که متغیر c مقداردهی شده است، حالت داخلی b3 تنها شامل b و d میباشد. حالت خارجی b1 برابر با اجتماع حالت داخلی b2 و b3 میباشد. تعریف متغیر c در b2 میتواند حذف شود، چرا که c بلافاصله پس از عبارت دیگر زنده نمیباشد.

حل معادلات جریان داده بدینصورت شروع میشود که ابتدا همه حالات داخلی و خارجی را با مجموعه‌ی تهی مقداردهی اولیه میکنیم، سپس لیستی را تحت عنوان لیست کارها در نظر گرفته و نقطه‌ی خروج (b3) را به لیست اضافه میکنیم (حرکتی رایج برای جریان معکوس). حالت داخلی محاسبه شده برای آن با قبلی متفاوت است. سپس نقاط قبل از آن یعنی b1 و b2 اضافه شده و عملیات ادامه میابد. شبه کد الگوریتم به صورت زیر میباشد:

input: control flow graph CFG = (N, E, Entry, Exit)
// Initialize in[Exit] = //local variables
For all nodes i
in[i] = //can optimize by in[i]=use[i]
ChangedNodes = N
// iterate 
While ChangedNodes {
 Remove i from Changed Nodes
 out[i] = U (in[s]), for all successors s of i
 oldin = in[i] 
 in[i] = fi(out[i]) //in[i]=use[i]U(out[i]-def[i]) 
 if oldin in[i] { 
  for all predecessors p of i 
  add p to ChangedNodes
 }
}

مراحل در جدول زیر خلاصه شده‌اند:

در حال پردازش	حالت خارجی	حالت داخلی قدیمی	حالت داخلی جدید	لیست کارها
b3	{}	{}	{b,d}	(b1,b2)
b1	{b,d}	{}	{}	(b2)
b2	{b,d}	{}	{a,b}	(b1)
b1	{a,b,d}	{}	{}	()

دقت کنید که b1 زودتر از b2 به لیست اضافه شده که باعث شد b1 دو بار پردازش شود (b1 دوباره به عنوان جد b2 وارد لیست شده است). اضافه شدن b2 قبل از b1 باعث تمام شدن زودتر روند میشد.

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

منابع

کامپایلر بهینه‌ساز