Поиск изолятора цикла в статическом анализе

Question

Как найти итератор цикла в статическом анализе? Какое другое условие для переменной является итератором?

В супер упрощенном цикле, таком как for(i = 0; i < n; i++);, можно предположить, что lhs выражения инициализации является итератором. Но как мы можем найти итератор в цикле while или более сложный цикл?

Я готов со следующими понятиями:

• достигающих определений
• Диапазон значений
• график

Answer 1

потока управления В общем случае нет итераторапетля. Например, может быть недостаточно одного итератора переменной (например, массив может быть перемещен с обоих концов одновременно), завершение цикла может зависеть от внешних данных (например, ввода пользователя) и есть полезные бесконечные циклы (где итераторы бесполезны).

Однако некоторые эвристики могут быть использованы для идентификации Итератор выражения. Для петель они часто выражали два свойства: прогресс и окончание. Прогресс часто связан с обновлением той же переменной со значением, которое зависит от этой переменной, например:

i++; // For indexed structures 
p = p -> next; // For linked structures 

Прекращение часто связано с сравнением выражения прогресса в некоторой постоянной (то есть «постоянная для петля "), например:

i <= n; // For scalar values 
p == null; // For pointers 

в целом может быть несколько прогресс выражений и, следовательно, несколько констант терминации, а также несколько переменного прогресса может быть использована в выражении завершения.

Таким образом, базовая стратегия будет:

1. Соберите все переменные из условия выхода из цикла.
2. Проверьте, какие из них модифицированы в корпусе контура с зависимостью от самих себя.

Но имейте в виду, что некоторые циклы не имеют выражений прогресса, некоторые из них не имеют условий завершения, переменные обновления могут быть косвенными, и существует сглаживание.