НОУ ІНТУІТ, Лекція, Аналіз потоків даних
Аналіз потоків даних
Під аналізом потоків даних розуміють сукупність завдань, націлених на з'ясування деяких глобальних властивостей програми, тобто отримання інформації про поведінку тих чи інших конструкцій у певному контексті. Така постановка завдання можлива з тієї причини, що мова програмування та обчислювальне середовище визначають деяку загальну, "безпечну" семантику конструкцій, яка підходить "на всі випадки життя". Облік контекстних умов дозволяє робити більш конкретні, приватні висновки про поведінку тієї чи іншої конструкції; при цьому такі висновки, власне кажучи, перестають бути вірними в іншому контексті. Наприклад, загальна семантика присвоювання полягає у обчисленні виразу, що стоїть у правій частині, і присвоєння отриманого значення змінну, що стоїть у лівій частині. Однак у випадку, коли вираз у правій частині не має побічних ефектів, а змінна в лівій частині більше ніде не використовується, цей оператор стає еквівалентним порожньому.
Для того щоб описати поняття контексту, знову звернемося до графа потоку управління (див. "Оптимізація" та "Аналіз потоку управління"). Зрозуміло, що на сенс кожної конструкції може впливати будь-яка конструкція, з якої в цьому графі досяжна дана. Звідси випливає, що для правильного обліку контексту необхідно врахувати вплив усіх шляхів до цієї вершини, спочатку визначивши вплив кожного шляху, а потім виділивши загальну частину. Завдання ускладнюється тим, що за наявності контурів багато всіх шляхів у графі управління стає нескінченним.
Далі в цій лекції буде розглянуто загальноприйнятий ітеративний підхід, який дозволяє отримати наближене рішення задач аналізу потоків даних, а за певних умов це рішеннястає точним.
Для демонстрації суті завдань аналізу потоків даних розглянемо кілька прикладів.
На ілюстрації наведено фрагмент програми. Входження одного й того ж виразу (v+i)-b, обведені суцільною лінією, є еквівалентними. У той самий час входження тієї самої висловлювання, позначене пунктирної лінією, не еквівалентно першим двом, оскільки else -частина умовного оператора містить руйнівне присвоювання .
Зрозуміло, що для з'ясування еквівалентності даних виразів необхідно перебрати всі шляхи і переконатися, що в жодному значення змінних, що входять у вирази, не змінюються.