تجزیه و تحلیل جریان داده
تجزیه و تحلیل جریان داده یکی از روش‌هایی است که با استفاده از آن می‌توان اطلاعات مربوط به داده‌هایی که در نقاط مختلف یک برنامهٔ رایانه‌ای محاسبه می‌شوند را فراهم کرد. گراف روند کنترلی برای تعیین قسمت‌های برنامه که به تعریف یک متغیر یا مقداردهی یک متغیر منجر شده‌است، استفاده می‌شود. تحلیل جریان داده اطلاعاتی را تولید می‌کند که معمولاً کامپایلرها از آن برای بهینه‌سازی برنامه استفاده می‌کنند.
در یک گراف کنترل جریان هر گره در گراف یک بلوک پایه را نشان می‌دهد. بلوک پایه مجموعه ای از دستورالعمل‌های متوالی است به طوری که هیچ دستور پرشی به این خطوط به جز خط اول وجود نداشته باشد و به جز خط آخر هیچ‌کدام ازین دستورها پرشی نباشند؛ در واقع این مجموعه دستورالعمل پشت سر هم و به ترتیب اجرا می‌شوند.
یک راه ساده برای پیاده‌سازی تجزیه و تحلیل جریان داده این است که معادله جریان داده را برای هر گره از گراف روند کنترلی تنظیم کنیم و سپس به صورت محلی خروجی هر گره را از ورودی‌های آن محاسبه کنیم و این کار را تا زمانی که سیستم به نقطه ثابتی برسد تکرار کنیم.
تجزیه و تحلیل جریان داده فرایند تولید اطلاعات دربارهٔ شیوه به کار رفتن متغیرهای تعریف شده در برنامه است و تلاش می‌کند اطلاعات خاصی را در هر نقطه از اجرا به دست بیاورد. معمولاً به دست آوردن این اطلاعات در محدودهٔ بلوک‌های پایه کفایت می‌کند؛ زیرا با استفاده از آن به راحتی می‌توان اطلاعات نقاط مختلف بلوک پایه را به دست آورد. در تحلیل جریان رو به جلو، حالت خروجی یک بلوک تابعی از حالت ورودی آن بلوک است. این تابع ترکیب اثرات عبارات موجود در بلوک می‌باشد. حالت ورودی یک بلوک تابعی از حالت‌های خروجی اجداد آن بلوک می‌باشد. در نتیجه مجموعه ای از معادلات جریان داده به دست می‌آید: برای هر بلاک b:
formula_1
formula_2
در این‌جا formula_3 تابع انتقال بلوک formula_4 می‌باشد. این تابع روی حالت ورودی formula_5 کار می‌کند و حالت خروجی formula_6 را نتیجه می‌دهد و formula_7 عملگر پیوند است که حالت‌های خروجی اجداد بلوک formula_4 را ترکیب کرده و حالت ورودی formula_4 را نتیجه می‌دهد.
بعد از حل این مجموعه از معادلات، می‌توان از حالت‌های ورودی و خروجی بلوک‌ها برای استخراج ویژگی‌های برنامه در محدوده بلوک‌های پایه استفاده کرد. با اعمال کردن تابع انتقال هر عبارت به صورت جداگانه، می‌توان اطلاعات مطلوب را در هر نقطه از بلوک پایه به دست آورد.
هر نوع خاصی از تحلیل جریان داده، تابع انتقال و عملگر پیوند خاص خود را دارد. برخی از مسئله‌های جریان داده، به تحلیل جریان رو به عقب نیاز دارند. این تحلیل به جز تابع انتقال و عملگر پیوند تقریباً مشابه تحلیل رو به جلو می‌باشد؛ تابع انتقال در این تحلیل روی حالت خروجی بلوک اعمال می‌شود و حالت ورودی آن را نتیجه می‌دهد و عملگر پیوند روی حالت‌های ورودی بلوک‌های فرزند اعمال شده و حالت خروجی یک بلوک را نتیجه می‌دهد.
می‌توانید شمایی ساده از گراف کنترل جربان داده را در تصویر زیر مشاهده کنید:
رایج‌ترین روش برای حل مسائل تجزیه و تحلیل جریان داده، استفاده از الگوریتم‌های تکراری است. محبوبیت این الگوریتم‌ها به خاطر سرعت، قدرت و سادگی پیاده‌سازی آن هاست. این الگوریتم، با یک تقریب از حالت ورودی هر بلوک شروع می‌کند و حالت خروجی را با اعمال کردن تابع انتقال هر بلوک بر روی حالت ورودی آن، به دست می‌آورد. حالت ورودی جدید برای هر بلوک با اعمال عملگر پیوند روی اجداد آن بلوک در گراف روند کنترلی به دست می‌آید. حال الگوریتم روی حالت‌های اولیه جدید تکرار خواهد شد و این تکرار تا زمانی ادامه پیدا می‌کند که سیستم به نقطه ثابتی برسد به این معنا که با تکرار فرایند الگوریتم، حالت ورودی و خروجی جدید برای هر بلوک با حالت ورودی و خروجی قبلی آن تفاوتی نکند.
همان‌طور که پیش تر گفته شد، در روش استفاده از الگوریتم‌های تکراری، تکرار الگوریتم تا زمانی ادامه پیدا می‌کند که به نقطه ثابتی برسد؛ پس برای اینکه در عمل بتوانیم از این روش استفاده کنیم، سیستم باید همگرا باشد. همگرایی سیستم با اعمال یک سری شرط روی دامنه مقادیر حالت‌ها، تابع انتقال و عملگر پیوند تضمین خواهد شد. این شروط عبارتند از: با وجود این دو شرط نتیجه یک تابع یکنوای کراندار است و یک تابع یکنوای کراندار حتماً همگرا است.
همان‌طور که پیش تر گفته شد، الگوریتم با یک تقریب از حالت ورودی هر بلوک شروع می‌شود. این مقدار دهی اولیه باید به گونه ای باشد که نتیجه نهایی صحیح و دقیق باشد برای مثال چنانچه قرار است نتایج برای بهینه‌سازی کد در کامپایلرها مورد استفاده قرار بگیرد، نتیجه حاصل باید منطق برنامه را حفظ کند.
ترتیب پیمایش بلوک‌ها در فرایند اجرای الگوریتم روی کارایی الگوریتم و زمان اجرای آن، تأثیر مستقیم دارد. عامل مهم دیگری که در این بحث اهمیت دارد، رو به جلو یا رو به عقب بودن تحلیل در گراف روند کنترل می‌باشد. اگر تحلیل ما رو به جلو باشد، بهتر است اجداد هر گره در گراف، قبل از آن شده باشند؛ چرا که حالت هر بلوک وابسته به حالات اجداد آن در گراف خواهد بود و اگر قبل از دیدن هر گره اجداد آن دیده شده باشند، سرعت همگرایی الگوریتم بیشتر خواهد بود. اگر در گراف حلقه نداشته باشیم، می‌توان ترتیبی از بلوک‌ها را پیدا کرد که تنها با یک بار اجرای الگوریتم روی هر بلوک، مقدار نهایی و صحیح هر بلوک به دست آید. برخی از ترتیب‌های ممکن برای پیمایش گراف در اجرای الگوریتم عبارتند از:
الگوریتم تکرار راند-رابین یکی از الگوریتم‌هایی است که برای حل مسائل تجزیه و تحلیل جریان داده از آن استفاده می‌شود. در این الگوریتم در هر نوبت تکرار الگوریتم، همه بلاک‌ها از نو پیمایش می‌شوند و تا رسیدن به نقطه ثابت تکرار ادامه خواهد داشت. شبه کد این الگوریتم مشابه شبه کد زیر است:
ترتیب پیمایش گره‌ها در این روش ثابت است.
این روش، مدل بهبود یافته‌ای از الگوریتم راند-رابین است. در این روش، تکرار تنها در بخشی از گراف که در حال تغییر است انجام می‌شود. در این الگوریتم پس از مقداردهی اولیه، یک لیست به نام لیست کار ایجاد می‌شود که در ابتدای الگوریتم همهٔ گره‌ها در این لیست قرار دارند. در هر مرحله، یک گره از لیست کار حذف می‌شود و اطلاعات مربوط به جریان دادهٔ آن، مشابه آنچه پیش تر توضیح داده شد، به روزرسانی می‌شود. اگر این به روزرسانی باعث تغییر در اطلاعات گره (حالت گره) شود، همهٔ گره‌هایی که این تغییر اطلاعات روی آنها تأثیر دارد به لیست کار اضافه می‌شوند و این فرایند تا خالی شدن لیست کار ادامه خواهد داشت. شبه کد این الگوریتم مشابه زیر است: