Как оптимизирующий компилятор C ++ повторно использует стековые слоты функции?

Question

Как оптимизирующий компилятор c ++ определяет, когда слот стека функции (часть стекового фрейма функции) больше не нужен этой функции, поэтому он может повторно использовать свою память? .
Под слотом стека я подразумеваю часть стекового фрейма функции, а не обязательно целый стековый фрейм функции, и пример, проясняющий ситуацию: предположим, у нас есть функция, в которой в ее области определены шесть целочисленных переменных, когда пришло время чтобы использовать шестую переменную в функции, пятая переменная становится бесполезной, поэтому компилятор может использовать один и тот же блок памяти для пятой и шестой переменных.
любая информация на эту тему приветствуется.

Answer 1

РЕДАКТИРОВАТЬ: я интерпретировал вопрос, чтобы означать, "как компилятор повторно использовать определенное слово памяти в стеке?" Большинство следующих ответов отвечают на этот вопрос, а примечание в конце отвечает на вопрос: «Как компилятор повторно использует все пространство стека, необходимое для функции?».

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

(Есть некоторые сложности с этой идеей, которые возникают, когда несколько назначений могут получить доступ через разные пути управления; это решается с помощью умного расширения этой идеи под названием статическое одиночное назначение , которое обсуждать не собираюсь здесь).

В любой точке кода существует множество допустимых значений времени жизни переменных; когда вы выбираете разные кодовые точки, у вас есть разные допустимые времена жизни переменных. Фактическая проблема компилятора состоит в том, чтобы назначать разные регистры или слоты стека для каждого времени жизни. Можно думать об этом как о проблеме раскраски графа: каждое время жизни является узлом, и если в точке кода могут перекрываться два времени жизни, существует дуга «помехи» от этого узла другому узлу, представляющему другое время жизни. Вы можете раскрасить график (или эквивалентно использовать числа вместо цветов) так, чтобы никакие два узла, связанные дугой помехи, не имели одинаковый цвет (число); вам, возможно, придется использовать произвольно большие числа, чтобы сделать это, но для большинства функций числа не должны быть очень большими. Если вы сделаете это, цвета (числа) сообщат вам о безопасном слоте стека, который нужно использовать для назначенного значения времени жизни конкретной переменной. (Эта идея обычно используется примерно в два этапа: один раз для выделения регистров и один раз для выделения слотов стека для тех времен жизни, которые не вписываются в регистры).

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

Есть много сложностей: разные значения занимают разное количество места и т. Д., Но основная идея здесь. Не все компиляторы используют технику раскраски графа, но почти все они выясняют, как назначать стековые слоты и регистры таким образом, чтобы избежать подразумеваемых помех. И, таким образом, они знают номера слотов стека и размер фрейма стека.

РЕДАКТИРОВАТЬ ... во время ввода кажется, что вопрос был интерпретирован как "когда стековый фрейм для функции исчезает"? Ответ: при выходе из функции. Компилятор уже знает, насколько он велик. Нет необходимости вставлять или вставлять в стек во время выполнения функции; он знает, куда поместить все, основываясь на нумерации слотов стека, определяемой раскраской графа.

Answer 2

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

Теоретически, компилятор может выполнить анализ потока для функции, выяснить, какие блоки памяти используются в какое время и, возможно, даже переупорядочить распределение стеков на основе порядка, в котором переменные становятся доступными. Затем, если новые автоматические переменные будут введены где-то посередине функции или другой области видимости, вложенной в функцию (а не в ее начало), эти недавно освобожденные слоты можно будет использовать повторно.

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

Answer 3

Если я правильно понимаю вопрос, это касается цепочки вызовов, то есть вызова функции из функции без выделения нового кадра стека.

Это возможно, когда вызов может быть преобразован в хвостовой вызов - последний оператор перед возвратом. Таким образом, все локальные переменные (стек) уже находятся вне области видимости, поэтому пространство можно использовать повторно. Затем компилятор генерирует инструкцию <b>jump</b> вместо <b>call</b>. Исходный адрес возврата по-прежнему находится в нужном месте в стеке.

Я, наверное, здесь замалчиваю многие детали, но это идея.