موضوع مقاله: تحلیل متغیر زنده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تحلیل متغیر زنده | مقدمه: در کامپایلر تحلیل متغیر زنده (یا همان تحلیل زنده بودن) یک مسئله‌ی سنتی تحلیل جریان داده برای محاسبه متغیرهایی میباشد که در هر لحظه از برنامه زنده هستند. | ## بخش 1: تحلیل متغیر زنده | یک متغیر زمانی زنده است که دارای مقداری است که ممکن است در آینده به آن نیاز شود، یا به‌طور معادل مقدار آن قبل از اینکه مقدار بعدی در آن نوشته شود، خوانده خواهد شد. جرا که با توجه به تعداد محدود ثبات‌ها یک ثبات تنها زمانی میتواند برای دو متغیر استفاده شود که این دو متغیر هیچگاه همزمان زنده نباشند. مثال برنامه‌ی زیر را در نظر بگیرید: b = 3 c = 5 a = f(b * c) مجموعه‌ی متغیرهای زنده بین خط دو و سه {b, c} می‌باشد؛ زیرا هر دوی آنها برای ضرب در خط سوم استفاده می‌شوند. ولی مجموعه‌ی متغیرهای زنده در خط یک فقط {b} می‌باشد، چون متغیر c در ادامه در خط دو آپدیت می‌شود. در نظر داشته باشید که ممکن است خط سه، از آنجایی که از a بعداً استفاده نمی‌شود، پاک شود. ولی ما اطلاعات کافی برای پاک کردن خط سه نداریم؛ بنابراین ممکن است عوارض جانبی داشته باشد (به‌طور مثال ممکن است مقدار b * c بعداً چاپ شود) عبارت ریاضی مرتبط با معادله جریان داده تحلیل زنده بودن یک تحلیل «معکوس محتمل» می‌باشد. تحلیل به صورت معکوس انجام می‌شود و عملگر برخورد جریان داده عملگر اجتماع می‌باشد. | ## بخش 2: تحلیل متغیر زنده | به زبانی دیگر، هنگامی که تحلیل متغیر زنده برای یک تابع با تعدادی شاخه‌های عبارات منطقی در آن اعمال می‌شود، تحلیل از آخر تابع شروع به اعمال می‌شود تا به اول تابع برسد (پس معکوس است). و یک متغیر زنده محسوب می‌شود، اگر هر کدام از شاخه‌های عبارات منطقی که به داخل حرکت می‌کنند ممکن است به مقدار فعلی متغیر نیاز داشته باشند (پس محتمل است). این در تضاد با «معکوس حتمی» می‌باشد که در آن، این شرط برای شاخه‌هایی که به خارج حرکت می‌کنند اجرا می‌شود. معادلات جریان داده برای بلوک ساده s و بلوک خارج شونده f در تحلیل متغیرهای زنده به صورت زیر است: : مجموعه متغیرهایی که در s استفاده شده‌اند قبل از اینکه مقدار جدیدی به آنها داده شود. :مجموعه متغیرهایی که مقداری به آنها در s داده شده‌است (در بسیاری از کتاب‌ها مقدار KILL (s) همچنین به معنای مجموعه متغیرهایی که قبل از هیچ استفاده ای در s به آن‌ها مقداری داده شده‌است نیز تعریف شده‌است ، ولی این راه‌حل معادله جریان داده را تغییر نمی‌دهد) حالت داخلی بلوک مجموعه ای از متغیرها می‌باشد که در هنگام شروع بلوک زنده هستند. تابع انتقال یک حالت به صورت کشتن متغیرهایی که در آن نوشته می‌شود و زنده کردن متغیرهایی که خوانده می‌شوند، اجرا می‌شود. الگوریتم محاسبه متغیرهای زنده هیچ متغیری زنده نیست مگر در گراف بلوک‌های پایه مسیری پیدا شود که در طی این مسیر متغیر قبل از تعریف دوباره استفاده شود. | ## بخش 3: تحلیل متغیر زنده | بنابراین ما با این فرض که هیچ متغیری در خروج از هیچ بلوک پایه‌ای زنده نیست شروع میکنیم. روند به دلیل این که ما تنها متغیرها را به مجموعه اضافه میکنیم و تعداد متغیرها محدود میباشد متوقف میشود. تعریف متغیر c در b2 میتواند حذف شود، چرا که c بلافاصله پس از عبارت دیگر زنده نمیباشد. حل معادلات جریان داده بدینصورت شروع میشود که ابتدا همه حالات داخلی و خارجی را با مجموعه‌ی تهی مقداردهی اولیه میکنیم، سپس لیستی را تحت عنوان لیست کارها در نظر گرفته و نقطه‌ی خروج (b3) را به لیست اضافه میکنیم (حرکتی رایج برای جریان معکوس). مقداردهی اولیه با مجموعه‌ی تهی یک مقداردهی خوشبینانه میباشد(تمامی متغیرها از ابتدا به صورت مرده در نظر گرفته میشوند). دقت کنید که حالات خارجی از یک دور به دور بعدی نمیتوانند کاهش یابند، هرچند حالت خارجی میتواند کوچکتر از حالت داخلی باشند؛ چراکه پس از دور اول حالت خارجی تنها با تغییر حالت داخلی میتواند تغییر یابد. | ## جمع‌بندی | از آنجا که حالت داخلی با مجموعه‌ی تهی شروع میشود در ادامه تنها میتواند بزرگتر شود.