как найти максимальное число переменных в стеке

Question

Во время выполнения следующей программы, что является максимальным числом переменных, которые связаны в то время, в стеке:

int x, y, z; 

int g(int a, int b) { 
    int c = 5 * a + b; 
    return c; 
} 

int f(int a, int b) { 
    a = g(a, 5); 
    return g(b, a); 
} 

int main() { 
    int a, b, c; 
    x = y = z = 0; 
    a = 5; b = 6; 
    c = f(a, b); 
    printf("%d", c); 
} 

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

Другой пример:

int x,y; 

int f(int a){ 
    if (a!=5) 
    return f(--a); 
    else 
    return a; 
} 

int main(){ 
    int a,b; 
    a=8;b=6; 
    x=f(a); 
    y=f(b); 
    printf("%d", x+y); 

    return 0; 
} 

Это выше ответ 6? Потому что первый возврат возвращает переменную 3 раза .., а второй возврат возвращает один раз число, и у нас есть две переменные в главном, так что 6?

Answer 1

Это зависит от настроек компилятора и оптимизации. Хороший алгоритм оптимизации генерирует что-то вроде этого:

int main() { 
    printf("%d", 155); 
} 

Другие алгоритмы будут генерировать что-то еще. Итак, попробуйте использовать дизассемблер для скомпилированного результата.

Answer 2

Вы можете запускать свою программу шаг за шагом в голове (или в отладчике) и можете считать все активные переменные в каждом кадре call stack (затем получить максимальную сумму из них).

В вашем конкретном примере, не предполагая оптимизации, самый глубокий стек вызовов происходит в return c; заявления в g наречен f наречено main. Таким образом, у нас есть 3 стек вызовов кадров с 3 переменными для g (a, b, c;! Я предполагаю, что формали, как локальные переменные, это не всегда верно на практике), 2 переменных для f (a, b), и 3 переменные для main.

Ваш учитель, вероятно, ожидает, что вы нарисуете стек вызовов в его самом глубоком состоянии. Я оставляю это вам.

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

Однако, как Ilya answered, хороший компилятор преобразит вашу программу для optimization purposes, так что на практике ответ может быть другим.

При использовании GCC, вы можете попытаться посмотреть на сгенерированный код на ассемблере (с использованием gcc -fverbose-asm -S), и вы увидите, что результат и количество используемых переменных зависит от флагов оптимизации (т.е. -O1, -O2, и т.д .. или их отсутствие). Вы также можете использовать флаг -fstack-usage GCC. Вы даже можете попробовать флаг -fdump-tree-all в gcc, который дает сотни файлов дампов, подробно объясняющих различные промежуточные представления (Gimple, SSA, ...) вашей программы внутри компилятора.

Читайте также wikipages на continuations (также, возможно, call/cc), tail call, recursion и inline expansion.

BTW, наличие стека вызовов не является строго обусловленным стандартом C99 (но я не знаю, как реализация C не использует стеки вызовов). Если вам интересно, вы должны прочитать старую статью A.Appel garbage collection can be faster than stack allocation (в которой объясняется реализация SML, не использующая какой-либо стек вызовов, поскольку он выделяет каждый кадр «call frame», a.k.a. «frame продолжения», в кучу мусора).

Я также предлагаю, чтобы скомпилировать примеры (с gcc -Wall -g), а затем запустить их шаг за шагом в gdb отладчика. Используйте часто display, step, backtrace, framecommandsgdb.