Определение максимальной глубины стека

Question

Представьте, что у меня есть игрушечный язык на основе стека, который поставляется с операциями Push, Pop, Jump и If.

У меня есть программа, и ее ввод - игрушечный язык.Например, я получаю последовательность

Push 1
Push 1
Pop
Pop

. В этом случае максимальный стек будет равен 2. Более сложный пример будет использовать ветви.

Push 1
Push true
If   .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:

В этом случае максимальный стек будет3. Однако получить максимальный стек невозможно, пройдя сверху вниз, как показано в этом случае, так как это фактически приведет к ошибке переполнения стека.

CFG в помощь, вы можете построить график ипройти все возможные пути из основных блоков, которые у вас есть.Однако, поскольку число путей может быстро расти для n вершин, вы получаете (n-1)!возможные пути.

Мой текущий подход состоит в том, чтобы максимально упростить график и иметь меньше возможных путей.Это работает, но я бы посчитал это уродливым.Есть ли лучший (читай: быстрее) способ решения этой проблемы?Я в порядке, если алгоритм выдает глубину стека, которая не является оптимальной.Если правильный размер стека равен m, то мое единственное ограничение - результат n равен n> = m.Возможно, есть жадный алгоритм, который даст хороший результат здесь?

Обновление: Я знаю о циклах и инварианте, что все слияния потока controlf имеют одинаковую глубину стека.Я решил написать простой игрушечный язык, чтобы проиллюстрировать проблему.По сути, у меня есть детерминированный язык на основе стека (байт-код JVM), поэтому у каждой операции есть известная дельта стека.

Обратите внимание, что у меня есть рабочее решение этой проблемы, которое дает хорошие результаты (упрощенный cfg)но я ищу лучший / более быстрый подход.

Answer 1

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

Что касается вашей аргументации пути: знайте, что прыжки допускают циклы, следовательно, без дальнейшего анализа цикл может подразумевать отсутствие завершения и переполнения стека (то есть размер стека увеличивается после каждого выполнения цикла). [n узлов по-прежнему означает бесконечное число путей, если есть цикл]

Вместо реального выполнения кода вы могли бы сделать некоторую форму абстрактной интерпретации .

Относительно комментария от IVlad: просто считать толчки неправильно из-за существования возможных циклов.

Я не уверен, какова семантика ваших операторов if, хотя это тоже может быть полезно: предположим, что метка оператора if может быть только меткой пересылки (т. Е. Вы никогда не сможете вернуться назад в своем коде) , В этом случае ваш аргумент подсчета пути возвращается к жизни. По сути, результирующий CFG будет деревом (или DAG, если вы не копируете код). В этом случае вы могли бы сделать приблизительный подсчет путем вычисления количества нажатий снизу вверх и последующего получения максимального количества нажатий для обеих ветвей в случае оператора if. Это все еще не оптимальный правильный результат, но дает лучшее приближение, чем простое число push-операторов.

Answer 2

Как правило, вы хотите, чтобы глубина стека была инвариантной по отношению к скачкам и циклам.

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

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

Еще одна вещь, которую вы должны рассмотреть, это сделать эффект стека всех опкодов детерминированным. Примером недетерминированного кода операции будет: POP IF TopOfStack == 0.

Edit:

Если у вас есть детерминированный набор кодов операций и инвариант глубины стека, нет необходимости посещать все возможные пути программы. Достаточно сделать DFS / BFS через CFG, чтобы определить максимальную глубину стека. Это можно сделать за линейное время (в зависимости от количества инструкций), но не быстрее.

Оценка, если базовые блоки, по которым исходные ребра вашей текущей базовой точки блока все еще должны быть оценены, не должны иметь отношения к производительности. Даже в худшем случае каждая инструкция представляет собой IF, для оценки потребуется только 2 * N ребер.