C++: come fa il compilatore a sapere quanta memoria allocare per ogni frame dello stack?

Question

Nella prima risposta here, la seguente è stato accennato sulla memoria dello stack in C++:

Quando viene chiamata una funzione, un blocco è riservato in cima alla pila per le variabili locali e alcuni dati contabili.

Questo rende perfettamente senso sul livello superiore, e mi fa curioso di come compilatori intelligente sono nell'assegnazione questa memoria di per sé, dato il contesto di this question: Poiché bretelle stessi non sono uno stack frame in C (Presumo che ciò valga anche per C++), voglio verificare se i compilatori ottimizzano la memoria riservata in base agli ambiti variabili all'interno di una singola funzione.

Di seguito Sto assumendo che la pila assomiglia a questo prima di una chiamata di funzione:

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

E allora la seguente dopo aver richiamato una funzione f():

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

Ad esempio, dato questa funzione

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

Presumibilmente, questo alloca solo 3*sizeof(int) + un po 'di spese generali extra per la contabilità.

Tuttavia, che dire di questa funzione:

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

Ignorando le ottimizzazioni del compilatore che può elidere un sacco di roba in precedenza poiché in realtà non fanno nulla, io sono curioso di sapere quanto segue nel secondo esempio:

• Per il ciclo for: lo spazio dello stack sarà abbastanza grande da contenere tutti i 100000 pollici?
• Inoltre, lo spazio di stack contiene 1000*sizeof(MyObject) o 2000*sizeof(MyObject)?

In generale: il compilatore considera l'ambito variabile quando si determina la quantità di memoria necessaria per il nuovo stack frame, prima di richiamare una determinata funzione? Se questo è specifico del compilatore, come fanno alcuni noti compilatori a farlo?

Answer 1

Il compilatore alloca lo spazio in base alle esigenze (in genere per tutti gli elementi all'inizio della funzione), ma non per ogni iterazione nel ciclo.

Per esempio, ciò che produce Clang, come 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 
} 

Questo è il risultato di:

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

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

Quindi, come si può vedere, x è assegnato solo una volta, non 100000 volte. Perché solo UNA di quelle variabili esiste in un dato momento.

(Il compilatore potrebbe riutilizzare lo spazio per myObject[1000] per x e la seconda myObject[1000] - e, probabilmente, avrebbe fatto così per una build ottimizzata, ma in quel caso sarebbe anche rimuovere completamente queste variabili in quanto non vengono utilizzati, in modo che wouldn mostra molto bene)

Answer 2

In un compilatore moderno, la funzione viene prima trasformata in un diagramma di flusso. In ogni arco del flusso, il compilatore sa quante variabili sono live - vale a dire mantenendo un valore visibile. Alcuni di questi vivranno nei registri, mentre per gli altri il compilatore dovrà riservare lo spazio in pila.

Le cose diventano un po 'più complicate poiché l'ottimizzatore viene ulteriormente coinvolto, perché potrebbe preferire non spostare le variabili dello stack in giro. Questo non è gratuito.

Ancora, il compilatore ha tutte le operazioni di assemblaggio pronte e può contare solo quanti indirizzi di stack univoci vengono utilizzati.