تحلیل متغیر زنده کیست؟ توضیح بده.
در کامپایلر تحلیل متغیر زنده (یا همان تحلیل زنده بودن) یک مسئله‌ی سنتی تحلیل جریان داده برای محاسبه متغیرهایی میباشد که در هر لحظه از برنامه "زنده" هستند. یک متغیر زمانی "زنده" است که دارای مقداری است که ممکن است در آینده به آن نیاز شود، یا به‌طور معادل مقدار آن قبل از اینکه مقدار بعدی در آن نوشته شود، خوانده خواهد شد. بیشترین کاربرد این تحلیل در تخصیص ثبات میباشد. جرا که با توجه به تعداد محدود ثبات‌ها یک ثبات تنها زمانی میتواند برای دو متغیر استفاده شود که این دو متغیر هیچگاه همزمان زنده نباشند.مثال.برنامه‌ی زیر را در نظر بگیرید: b = 3 c = 5 a = f(b * c)مجموعه‌ی متغیرهای زنده بین خط دو و سه {codice_1, codice_2} می‌باشد؛ زیرا هر دوی آنها برای ضرب در خط سوم استفاده می‌شوند. ولی مجموعه‌ی متغیرهای زنده در خط یک فقط {codice_1} می‌باشد، چون متغیر codice_2 در ادامه در خط دو آپدیت می‌شود. مقدار متغیر codice_5 در این کد استفاده نشده‌است.در نظر داشته باشید که ممکن است خط سه، از آنجایی که از codice_5 بعداً استفاده نمی‌شود، پاک شود. ولی ما اطلاعات کافی برای پاک کردن خط سه نداریم؛ بنابراین ممکن است عوارض جانبی داشته باشد (به‌طور مثال ممکن است مقدار codice_7 بعداً چاپ شود)عبارت ریاضی مرتبط با معادله جریان داده.تحلیل زنده بودن یک تحلیل «معکوس محتمل» می‌باشد. تحلیل به صورت معکوس انجام می‌شود و عملگر برخورد جریان داده عملگر اجتماع می‌باشد. به زبانی دیگر، هنگامی که تحلیل متغیر زنده برای یک تابع با تعدادی شاخه‌های عبارات منطقی در آن اعمال می‌شود، تحلیل از آخر تابع شروع به اعمال می‌شود تا به اول تابع برسد (پس معکوس است). و یک متغیر زنده محسوب می‌شود، اگر هر کدام از شاخه‌های عبارات منطقی که به داخل حرکت می‌کنند ممکن است به مقدار فعلی متغیر نیاز داشته باشند (پس محتمل است). این در تضاد با «معکوس حتمی» می‌باشد که در آن، این شرط برای شاخه‌هایی که به خارج حرکت می‌کنند اجرا می‌شود.معادلات جریان داده برای بلوک ساده "s" و بلوک خارج شونده "f" در تحلیل متغیرهای زنده به صورت زیر است:حالت داخلی بلوک مجموعه ای از متغیرها می‌باشد که در هنگام شروع بلوک زنده هستند. حالت خارجی بلوک مجموعه متغیرهایی هستند که در هنگام خروج بلوک زنده هستند. حالت خارجی بلوک، اجتماع حالت‌های داخلی فرزندان بلوک می‌باشد. تابع انتقال یک حالت به صورت کشتن متغیرهایی که در آن نوشته می‌شود و زنده کردن متغیرهایی که خوانده می‌شوند، اجرا می‌شود.الگوریتم محاسبه متغیرهای زنده.هیچ متغیری زنده نیست مگر در گراف بلوک‌های پایه مسیری پیدا شود که در طی این مسیر متغیر قبل از تعریف دوباره استفاده شود. بنابراین ما با این فرض که هیچ متغیری در خروج از هیچ بلوک پایه‌ای زنده نیست شروع میکنیم. روند به دلیل این که ما تنها متغیرها را به مجموعه اضافه میکنیم و تعداد متغیرها محدود میباشد متوقف میشود. الگوریتم به صورت زیر پیاده سازی میشود:FOR all blocks B DO IN(B) = Gen(B)ENDFORWHILE there are changes DO FOR each block B DO Out(B) = In(S) S Succ(B) In(B) = (Out(B) - Kill(B)) Gen(B) ENDFORENDWHILEالگوریتم worklist.برنامه‌ی زیر را در نظر بگیرید:از آنجا که متغیر "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 variablesFor all nodes iin[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مراحل در جدول زیر خلاصه شده‌اند:دقت کنید که b1 زودتر از b2 به لیست اضافه شده که باعث شد b1 دو بار پردازش شود (b1 دوباره به عنوان جد b2 وارد لیست شده است). اضافه شدن b2 قبل از b1 باعث تمام شدن زودتر روند میشد.مقداردهی اولیه با مجموعه‌ی تهی یک مقداردهی خوشبینانه میباشد(تمامی متغیرها از ابتدا به صورت مرده در نظر گرفته میشوند). دقت کنید که حالات خارجی از یک دور به دور بعدی نمیتوانند کاهش یابند، هرچند حالت خارجی میتواند کوچکتر از حالت داخلی باشند؛ چراکه پس از دور اول حالت خارجی تنها با تغییر حالت داخلی میتواند تغییر یابد. از آنجا که حالت داخلی با مجموعه‌ی تهی شروع میشود در ادامه تنها میتواند بزرگتر شود.منابع.کامپایلر بهینه‌ساز