موضوع مقاله: تجزیه و تحلیل جریان داده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه و تحلیل جریان داده | مقدمه: تجزیه و تحلیل جریان داده یکی از روش‌هایی است که با استفاده از آن می‌توان اطلاعات مربوط به داده‌هایی که در نقاط مختلف یک برنامهٔ رایانه‌ای محاسبه می‌شوند را فراهم کرد. | ## بخش 1: تجزیه و تحلیل جریان داده | گراف روند کنترلی برای تعیین قسمت‌های برنامه که به تعریف یک متغیر یا مقداردهی یک متغیر منجر شده‌است، استفاده می‌شود. بلوک پایه مجموعه ای از دستورالعمل‌های متوالی است به طوری که هیچ دستور پرشی به این خطوط به جز خط اول وجود نداشته باشد و به جز خط آخر هیچ‌کدام ازین دستورها پرشی نباشند؛ در واقع این مجموعه دستورالعمل پشت سر هم و به ترتیب اجرا می‌شوند."Basic Blocks in Compiler Design" یک راه ساده برای پیاده‌سازی تجزیه و تحلیل جریان داده این است که معادله جریان داده را برای هر گره از گراف روند کنترلی تنظیم کنیم و سپس به صورت محلی خروجی هر گره را از ورودی‌های آن محاسبه کنیم و این کار را تا زمانی که سیستم به نقطه ثابتی برسد تکرار کنیم. اصول اساسی تجزیه و تحلیل جریان داده فرایند تولید اطلاعات دربارهٔ شیوه به کار رفتن متغیرهای تعریف شده در برنامه است و تلاش می‌کند اطلاعات خاصی را در هر نقطه از اجرا به دست بیاورد. معمولاً به دست آوردن این اطلاعات در محدودهٔ بلوک‌های پایه کفایت می‌کند؛ زیرا با استفاده از آن به راحتی می‌توان اطلاعات نقاط مختلف بلوک پایه را به دست آورد. در نتیجه مجموعه ای از معادلات جریان داده به دست می‌آید: برای هر بلاک b: در این‌جا تابع انتقال بلوک می‌باشد. این تابع روی حالت ورودی کار می‌کند و حالت خروجی را نتیجه می‌دهد و عملگر پیوند است که حالت‌های خروجی اجداد بلوک را ترکیب کرده و حالت ورودی را نتیجه می‌دهد. بعد از حل این مجموعه از معادلات، می‌توان از حالت‌های ورودی و خروجی بلوک‌ها برای استخراج ویژگی‌های برنامه در محدوده بلوک‌های پایه استفاده کرد. با اعمال کردن تابع انتقال هر عبارت به صورت جداگانه، می‌توان اطلاعات مطلوب را در هر نقطه از بلوک پایه به دست آورد. این تحلیل به جز تابع انتقال و عملگر پیوند تقریباً مشابه تحلیل رو به جلو می‌باشد؛ تابع انتقال در این تحلیل روی حالت خروجی بلوک اعمال می‌شود و حالت ورودی آن را نتیجه می‌دهد و عملگر پیوند روی حالت‌های ورودی بلوک‌های فرزند اعمال شده و حالت خروجی یک بلوک را نتیجه می‌دهد. می‌توانید شمایی ساده از گراف کنترل جربان داده را در تصویر زیر مشاهده کنید: حل مسائل تجزیه و تحلیل جریان داده رایج‌ترین روش برای حل مسائل تجزیه و تحلیل جریان داده، استفاده از الگوریتم‌های تکراری است. | ## بخش 2: تجزیه و تحلیل جریان داده | این الگوریتم، با یک تقریب از حالت ورودی هر بلوک شروع می‌کند و حالت خروجی را با اعمال کردن تابع انتقال هر بلوک بر روی حالت ورودی آن، به دست می‌آورد. حالت ورودی جدید برای هر بلوک با اعمال عملگر پیوند روی اجداد آن بلوک در گراف روند کنترلی به دست می‌آید. حال الگوریتم روی حالت‌های اولیه جدید تکرار خواهد شد و این تکرار تا زمانی ادامه پیدا می‌کند که سیستم به نقطه ثابتی برسد به این معنا که با تکرار فرایند الگوریتم، حالت ورودی و خروجی جدید برای هر بلوک با حالت ورودی و خروجی قبلی آن تفاوتی نکند. همگرایی همان‌طور که پیش تر گفته شد، در روش استفاده از الگوریتم‌های تکراری، تکرار الگوریتم تا زمانی ادامه پیدا می‌کند که به نقطه ثابتی برسد؛ پس برای اینکه در عمل بتوانیم از این روش استفاده کنیم، سیستم باید همگرا باشد. همگرایی سیستم با اعمال یک سری شرط روی دامنه مقادیر حالت‌ها، تابع انتقال و عملگر پیوند تضمین خواهد شد. ترکیب تابع انتقال و پیوند باید یک تابع یکنوا نسبت به ترتیب مقادیر در دامنه باشد. با وجود این دو شرط نتیجه یک تابع یکنوای کراندار است و یک تابع یکنوای کراندار حتماً همگرا است. مقداردهی اولیه همان‌طور که پیش تر گفته شد، الگوریتم با یک تقریب از حالت ورودی هر بلوک شروع می‌شود. این مقدار دهی اولیه باید به گونه ای باشد که نتیجه نهایی صحیح و دقیق باشد برای مثال چنانچه قرار است نتایج برای بهینه‌سازی کد در کامپایلرها مورد استفاده قرار بگیرد، نتیجه حاصل باید منطق برنامه را حفظ کند. اهمیت ترتیب پیمایش بلوک‌ها ترتیب پیمایش بلوک‌ها در فرایند اجرای الگوریتم روی کارایی الگوریتم و زمان اجرای آن، تأثیر مستقیم دارد. | ## بخش 3: تجزیه و تحلیل جریان داده | عامل مهم دیگری که در این بحث اهمیت دارد، رو به جلو یا رو به عقب بودن تحلیل در گراف روند کنترل می‌باشد. اگر تحلیل ما رو به جلو باشد، بهتر است اجداد هر گره در گراف، قبل از آن شده باشند؛ چرا که حالت هر بلوک وابسته به حالات اجداد آن در گراف خواهد بود و اگر قبل از دیدن هر گره اجداد آن دیده شده باشند، سرعت همگرایی الگوریتم بیشتر خواهد بود. اگر در گراف حلقه نداشته باشیم، می‌توان ترتیبی از بلوک‌ها را پیدا کرد که تنها با یک بار اجرای الگوریتم روی هر بلوک، مقدار نهایی و صحیح هر بلوک به دست آید. برخی از ترتیب‌های ممکن برای پیمایش گراف در اجرای الگوریتم عبارتند از: پیمایش تصادفی: در این روش بلوک‌ها به ترتیب تصادفی پیمایش می‌شوند و به رو به جلو یا رو به عقب بودن تحلیل توجهی نمی‌شود به همین دلیل عملکرد این مدل ترتیب پیمایش به نسبت پیمایش‌های دیگر ضعیف است. در این روش هر گره قبل از هر یک از فرزندانش دیده خواهد شد؛ مگر اینکه گره فرزند یک یال رو به عقب داشته باشد. (این روش با پیمایش پیشوندی متفاوت است) الگوریتم تکرار راند-رابین الگوریتم تکرار راند-رابین یکی از الگوریتم‌هایی است که برای حل مسائل تجزیه و تحلیل جریان داده از آن استفاده می‌شود. در این الگوریتم در هر نوبت تکرار الگوریتم، همه بلاک‌ها از نو پیمایش می‌شوند و تا رسیدن به نقطه ثابت تکرار ادامه خواهد داشت. در این الگوریتم پس از مقداردهی اولیه، یک لیست به نام لیست کار ایجاد می‌شود که در ابتدای الگوریتم همهٔ گره‌ها در این لیست قرار دارند. در هر مرحله، یک گره از لیست کار حذف می‌شود و اطلاعات مربوط به جریان دادهٔ آن، مشابه آنچه پیش تر توضیح داده شد، به روزرسانی می‌شود. | ## جمع‌بندی | اگر این به روزرسانی باعث تغییر در اطلاعات گره (حالت گره) شود، همهٔ گره‌هایی که این تغییر اطلاعات روی آنها تأثیر دارد به لیست کار اضافه می‌شوند و این فرایند تا خالی شدن لیست کار ادامه خواهد داشت.