C++: W jaki sposób kompilator wie, ile pamięci należy przydzielić dla każdej ramki stosu?

Question

W pierwszej odpowiedzi here dodaje wspomniano o pamięci stosu w C++:

Gdy funkcja jest wywoływana, blok jest zarezerwowany na szczycie stosu dla zmiennych lokalnych i niektórych danych księgowych.

To ma sens na najwyższym poziomie, i czyni mnie ciekawi jak inteligentne kompilatory są przy przyznawaniu tej pamięci w sobie, biorąc pod uwagę kontekst this question: Ponieważ szelki sami nie są ramki stosu w C (Zakładam, że dotyczy to również C++), chcę sprawdzić, czy kompilatory optymalizują pamięć zarezerwowaną na podstawie zakresów zmiennych w ramach jednej funkcji.

Poniżej jestem przy założeniu, że stos wygląda tak przed wywołaniem funkcji:

-------- 
|main()| 
-------- <- stack pointer: space above it is used for current scope 
|  | 
|  | 
|  | 
|  | 
-------- 

A potem następującym po wywołaniu funkcji f():

-------- 
|main()| 
-------- <- old stack pointer (osp) 
| f() | 
-------- <- stack pointer, variables will now be placed between here and osp upon reaching their declarations 
|  | 
|  | 
|  | 
|  | 
-------- 

Na przykład, biorąc pod uwagę ta funkcja:

void f() { 
    int x = 0; 
    int y = 5; 
    int z = x + y; 
} 

Przypuszczalnie po prostu przydzieli 3*sizeof(int) + dodatkowe obciążenie dla księgowości.

Jednak to, co o tej funkcji:

void g() { 
    for (int i = 0; i < 100000; i++) { 
    int x = 0; 
    } 
    { 
    MyObject myObject[1000]; 
    } 
    { 
    MyObject myObject[1000]; 
    } 
} 

Ignorowanie optymalizacje kompilatora, który może Elide wiele rzeczy w wyżej ponieważ naprawdę nie robią nic, jestem ciekaw co następuje w drugim przykładzie:

• Dla pętli for: czy przestrzeń na stosie będzie wystarczająco duża, aby zmieściła się we wszystkich 100000 ints?
• Co więcej, czy przestrzeń na stosie zawiera 1000*sizeof(MyObject) lub 2000*sizeof(MyObject)?

Ogólnie: czy kompilator uwzględnia zakres zmienny przy określaniu wymaganej ilości pamięci dla nowej ramki stosu przed wywołaniem określonej funkcji? Jeśli jest to zależne od kompilatora, jak robią to niektóre dobrze znane kompilatory?

Answer 1

Kompilator przydzieli miejsce w razie potrzeby (zwykle dla wszystkich elementów na początku funkcji), ale nie dla każdej iteracji w pętli.

Na przykład, co Clang produkuje, jak LLVM-IR

define void @_Z1gv() #0 { 
    %i = alloca i32, align 4 
    %x = alloca i32, align 4 
    %myObject = alloca [1000 x %class.MyObject], align 16 
    %myObject1 = alloca [1000 x %class.MyObject], align 16 
    store i32 0, i32* %i, align 4 
    br label %1 

; <label>:1:          ; preds = %5, %0 
    %2 = load i32, i32* %i, align 4 
    %3 = icmp slt i32 %2, 100000 
    br i1 %3, label %4, label %8 

; <label>:4:          ; preds = %1 
    store i32 0, i32* %x, align 4 
    br label %5 

; <label>:5:          ; preds = %4 
    %6 = load i32, i32* %i, align 4 
    %7 = add nsw i32 %6, 1 
    store i32 %7, i32* %i, align 4 
    br label %1 

; <label>:8:          ; preds = %1 
    ret void 
} 

ta jest wynikiem:

class MyObject 
{ 
public: 
    int x, y; 
}; 

void g() { 
    for (int i = 0; i < 100000; i++) 
    { 
    int x = 0; 
    } 
    { 
    MyObject myObject[1000]; 
    } 
    { 
    MyObject myObject[1000]; 
    } 
} 

Więc, jak widać, x przeznaczono tylko raz, a nie 100000 czasy. Ponieważ tylko JEDNA z tych zmiennych będzie istnieć w dowolnym momencie.

(Kompilator mógł ponownie wykorzystać przestrzeń dla myObject[1000] dla x i drugi myObject[1000] - i prawdopodobnie będzie to zrobić dla zoptymalizowanej konstrukcji, ale w tym przypadku byłoby również całkowicie usunąć te zmienne, ponieważ nie są używane, więc byłoby miło bardzo dobrze pokazać)

Answer 2

W nowoczesnym kompilatorze funkcja jest najpierw przekształcana na wykres przepływu. W każdym łuku przepływu, kompilator wie, ile zmiennych jest aktywnych, tzn. Utrzymuje widoczną wartość. Niektóre z nich będą żyły w rejestrach, a dla innych kompilator będzie musiał zarezerwować miejsce na stosie.

Rzeczy stają się nieco bardziej skomplikowane, ponieważ optymalizator dodatkowo angażuje się, ponieważ może nie chcieć przenosić zmiennych stosu. To nie jest za darmo.

W dalszym ciągu kompilator ma wszystkie operacje montażu gotowe i może zliczyć ile unikalnych adresów stosu jest używanych.