Comment les variables sont-elles stockées et extraites de la pile de programmes?

Toutes mes excuses par avance pour la naïveté de cette question. Je suis un artiste de 50 ans qui essaie de bien comprendre les ordinateurs pour la première fois. Alors voilà.

J'ai essayé de comprendre comment les types de données et les variables sont gérés par un compilateur (dans un sens très général, je sais que cela comporte beaucoup de choses). Il me manque quelque chose dans ma compréhension de la relation entre le stockage dans "la pile" et les types de valeur, et le stockage sur "le tas" et les types de référence (les guillemets sont censés signifier que je comprends que ces termes sont des abstractions et non être pris trop littéralement dans un contexte aussi simplifié que celui que j’adresse cette question). Quoi qu'il en soit, mon idée simpliste est que des types tels que des booléens et des entiers utilisent "la pile" parce qu'ils le peuvent, car ils sont des entités connues en termes d'espace de stockage et que leur portée est facilement contrôlée en conséquence.

Mais ce que je ne comprends pas, c'est comment une application lit ensuite les variables sur la pile. Si je déclare et attribue xun entier, disons x = 3, le stockage est réservé sur la pile, puis sa valeur 3est stockée là, puis dans la même fonction que je déclare et assigne en ytant que, dis 4, et ensuite que j'utilise ensuite xdans une autre expression, (dire z = 5 + x) comment le programme peut-il être lu xafin d'évaluer zs'il est en dessousysur la pile? Il me manque clairement quelque chose. Est-ce que l'emplacement sur la pile ne concerne que la durée de vie / la portée de la variable, et que toute la pile est effectivement accessible au programme tout le temps? Si tel est le cas, cela signifie-t-il qu'un autre index contient uniquement les adresses des variables de la pile afin de permettre l'extraction des valeurs? Mais ensuite, j'ai pensé que le but de la pile était que les valeurs étaient stockées au même endroit que l'adresse de la variable. Dans mon esprit chétif, il semble que s’il existe cet autre indice, on parle alors de quelque chose qui ressemble plus à un tas? Je suis clairement très confus et j'espère seulement qu'il y aura une réponse simple à ma question simpliste.

Merci d'avoir lu si loin.

Le stockage de variables locales sur une pile est un détail de la mise en œuvre, essentiellement une optimisation. Vous pouvez penser de cette façon. Lors de la saisie d'une fonction, l'espace pour toutes les variables locales est alloué quelque part. Vous pouvez ensuite accéder à toutes les variables, puisque vous connaissez leur emplacement (cela fait partie du processus d’allocation). Lorsque vous quittez une fonction, l’espace est libéré (libéré).

La pile est un moyen de mettre en œuvre ce processus. Vous pouvez la considérer comme une sorte de "tas rapide" de taille limitée, qui ne convient donc que pour de petites variables. En tant qu'optimisation supplémentaire, toutes les variables locales sont stockées dans un bloc. Étant donné que chaque variable locale a une taille connue, vous connaissez le décalage de chaque variable dans le bloc et vous y accédez. Cela contraste avec les variables allouées sur le tas, dont les adresses sont elles-mêmes stockées dans d'autres variables.

Vous pouvez considérer la pile comme très similaire à la structure de données de pile classique, avec une différence cruciale: vous êtes autorisé à accéder aux éléments situés en dessous du sommet de la pile. En effet, vous pouvez accéder au ème élément à partir du haut. Voici comment vous pouvez accéder à toutes vos variables locales avec pushing et popping. La seule poussée effectuée est lors de l’entrée dans la fonction, et la seule qui se produit lorsque vous quittez la fonction.$k$

Enfin, permettez-moi de mentionner que, dans la pratique, certaines des variables locales sont stockées dans des registres. En effet, l'accès aux registres est plus rapide que l'accès à la pile. C'est une autre façon d'implémenter un espace pour les variables locales. Une fois encore, nous savons exactement où une variable est stockée (cette fois-ci pas via offset, mais via le nom d'un registre), et ce type de stockage n'est approprié que pour de petites données.

Avoir ysur la pile n'empêche physiquement pas l' xaccès, ce qui, comme vous l'avez fait remarquer, différencie les piles d'ordinateurs des autres piles.

Lorsqu'un programme est compilé, les positions des variables dans la pile sont également prédéterminées (dans le contexte d'une fonction). Dans votre exemple, si la pile contient un xavec un y"dessus", le programme sait à l'avance qu'il y xaura 1 élément sous le haut de la pile pendant qu'il se trouve dans la fonction. Étant donné que le matériel informatique peut demander explicitement un élément sous le sommet de la pile, l'ordinateur peut être utilisé xmême s'il yexiste.

Est-ce que l'emplacement sur la pile ne concerne que la durée de vie / la portée de la variable, et que toute la pile est effectivement accessible au programme tout le temps?

Oui. Lorsque vous quittez une fonction, le pointeur de la pile revient à sa position précédente, ce qui efface efficacement xet y, mais techniquement, il sera toujours présent jusqu'à ce que la mémoire soit utilisée pour autre chose. De plus, si votre fonction appelle une autre fonction xet ysera toujours là et peut être consultée en allant intentionnellement trop loin dans la pile.

Pour fournir un exemple concret de la manière dont un compilateur gère la pile et comment accéder aux valeurs de la pile, nous pouvons examiner les représentations visuelles, ainsi que le code généré par GCCdans un environnement Linux avec i386 comme architecture cible.

1. empiler des cadres

Comme vous le savez, la pile est un emplacement de l’espace adresse d’un processus en cours utilisé par des fonctions ou procédures , en ce sens que l’espace est alloué sur la pile pour les variables déclarées localement, ainsi que les arguments passés à la fonction ( l'espace pour les variables déclarées en dehors de toute fonction (c'est-à-dire les variables globales) est alloué dans une région différente de la mémoire virtuelle). L'espace alloué pour toutes les données d'une fonction est appelé un cadre de pile . Voici une représentation visuelle de plusieurs cadres de pile (de Computer Systems: Perspective du programmeur ):

2. Gestion des cadres de pile et emplacement variable

Pour que les valeurs écrites dans la pile dans un cadre de pile particulier soient gérées par le compilateur et lues par le programme, il doit exister une méthode permettant de calculer les positions de ces valeurs et d'extraire leur adresse de mémoire. Les registres de la CPU dénommés le pointeur de pile et le pointeur de base facilitent cette tâche.

Le pointeur de base, ebppar convention, contient l'adresse de la mémoire du bas, ou base, de la pile. Les positions de toutes les valeurs dans le cadre de pile peuvent être calculées en utilisant l'adresse du pointeur de base comme référence. Ceci est illustré dans l'image ci-dessus: %ebp + 4est l'adresse de la mémoire stockée dans le pointeur de base plus 4, par exemple.

3. Code généré par le compilateur

Mais ce que je ne comprends pas, c'est comment une application lit ensuite les variables sur la pile. Si je déclare et assigne x sous forme d’entier, disons x = 3, le stockage est réservé sur la pile et sa valeur 3 est stockée. là, puis dans la même fonction, je déclare et assigne y comme, disons 4, et ensuite que j'utilise ensuite x dans une autre expression, (disons z = 5 + x) comment le programme peut-il lire x afin d'évaluer z quand il est en dessous de y sur la pile?

Utilisons un exemple de programme écrit en C pour voir comment cela fonctionne:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Examinons le texte d'assemblage produit par GCC pour ce texte source C (je l'ai un peu nettoyé pour des raisons de clarté):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

Nous observons que les variables x, y et z sont situées aux adresses %ebp - 12, %ebp -8et %ebp - 4respectivement. En d'autres termes, les emplacements des variables dans le cadre de pile main()sont calculés en utilisant l'adresse de mémoire enregistrée dans le registre de la CPU %ebp.

4. Les données en mémoire au-delà du pointeur de pile sont hors de portée

Il me manque clairement quelque chose. Est-ce que l'emplacement sur la pile ne concerne que la durée de vie / la portée de la variable, et que toute la pile est effectivement accessible au programme tout le temps? Si tel est le cas, cela signifie-t-il qu'un autre index contient uniquement les adresses des variables de la pile afin de permettre l'extraction des valeurs? Mais ensuite, j'ai pensé que le but de la pile était que les valeurs étaient stockées au même endroit que l'adresse de la variable.

La pile est une région de la mémoire virtuelle, dont l'utilisation est gérée par le compilateur. Le compilateur génère du code de sorte que les valeurs situées au-delà du pointeur de la pile (les valeurs situées au-dessus du sommet de la pile) ne soient jamais référencées. Lorsqu'une fonction est appelée, la position du pointeur de la pile change pour créer un espace sur la pile réputé ne pas être "hors limites", pour ainsi dire.

Lorsque les fonctions sont appelées et retournées, le pointeur de pile est décrémenté et incrémenté. Les données écrites dans la pile ne disparaissent pas une fois hors de portée, mais le compilateur ne génère pas d'instructions référençant ces données car il ne dispose d'aucun moyen pour calculer les adresses de ces données à l'aide de %ebpou %esp.

5. Résumé

Le code pouvant être exécuté directement par la CPU est généré par le compilateur. Le compilateur gère la pile, les cadres de pile pour les fonctions et les registres de la CPU. Une stratégie utilisée par GCC pour suivre les emplacements des variables dans des cadres de pile dans du code destiné à être exécuté sur une architecture i386 consiste à utiliser l'adresse mémoire dans le pointeur de base du cadre de pile %ebp, comme référence et à écrire les valeurs des variables dans les emplacements des cadres de pile. à des décalages à l'adresse en %ebp.

Il existe deux registres spéciaux: ESP (pointeur de pile) et EBP (pointeur de base). Quand une procédure est appelée, les deux premières opérations sont généralement

push        ebp  
mov         ebp,esp 

La première opération enregistre la valeur de l'EBP sur la pile et la deuxième opération charge la valeur du pointeur de pile dans le pointeur de base (pour accéder aux variables locales). EBP pointe donc au même endroit que l’ESP.

Assembler traduit les noms de variables en décalages EBP. Par exemple, si vous avez deux variables locales x,yet que vous avez quelque chose comme

  x = 1;
  y = 2;
  return x + y;

alors il peut être traduit en quelque chose comme

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Les valeurs de décalage 6 et 14 sont calculées au moment de la compilation.

C'est à peu près comment cela fonctionne. Reportez-vous à un livre de compilation pour plus de détails.

Vous êtes confus, car la règle d'accès de la pile ne permet pas d'accéder aux variables locales stockées dans la pile: premier entré dernier sorti ou simplement FILO .

Le fait est que la règle FILO s’applique aux séquences d’appel de fonction et aux cadres de pile , plutôt qu’aux variables locales.

Qu'est-ce qu'un cadre de pile?

Lorsque vous entrez dans une fonction, une certaine quantité de mémoire, appelée frame de pile, lui est attribuée. Les variables locales de la fonction sont stockées dans le cadre de la pile. Vous pouvez imaginer que la taille du cadre de pile varie d'une fonction à l'autre puisque chaque fonction a des nombres et des tailles différentes de variables locales.

La manière dont les variables locales sont stockées dans le cadre de la pile n'a rien à voir avec FILO. (Même l'ordre d'apparition de vos variables locales dans votre code source ne garantit pas que les variables locales seront stockées dans cet ordre.) Comme vous l'avez correctement déduit dans votre question, "il existe un autre index qui ne contient que les adresses des variables sur la pile pour permettre la récupération des valeurs ". Les adresses des variables locales sont généralement calculées avec une adresse de base , telle que l'adresse limite du cadre de pile, et des valeurs de décalage spécifiques à chaque variable locale.

Alors, quand ce comportement de FILO apparaît-il?

Maintenant, qu'advient-il si vous appelez une autre fonction? La fonction appelée doit avoir son propre cadre de pile, et c'est ce cadre de pile qui est inséré dans la pile . C'est-à-dire que le cadre de pile de la fonction appelée est placé au-dessus du cadre de pile de la fonction appelant. Et si cette fonction appelée appelle une autre fonction, son cadre de pile sera de nouveau placé en haut de la pile.

Que se passe-t-il si une fonction revient? Au retour de la fonction à la fonction callee de l' appelant, le cadre de pile de fonction est callee sauté hors de la pile, libérant de l' espace pour une utilisation future.

Donc de votre question:

Est-ce que l'emplacement sur la pile ne concerne que la durée de vie / la portée de la variable, et que toute la pile est effectivement accessible au programme tout le temps?

vous avez tout à fait raison ici car les valeurs des variables locales sur le cadre de la pile ne sont pas vraiment effacées au retour de la fonction. La valeur y reste, bien que l'emplacement de la mémoire où elle est stockée n'appartienne à aucune image de pile. La valeur est effacée lorsqu'une autre fonction obtient son cadre de pile qui inclut l'emplacement et écrit sur une autre valeur dans cet emplacement de mémoire.

Alors qu'est-ce qui différencie pile de tas?

Stack et heap sont identiques en ce sens qu'ils sont tous deux des noms qui font référence à de l'espace sur la mémoire. Puisque nous pouvons accéder à n’importe quel emplacement en mémoire avec son adresse, vous pouvez accéder à n’importe quel emplacement en pile ou en tas.

La différence vient de la promesse du système informatique quant à la manière dont il va les utiliser. Comme vous l'avez dit, heap est pour le type de référence. Comme les valeurs de tas n'ont aucune relation avec un cadre de pile spécifique, la portée de la valeur n'est liée à aucune fonction. Cependant, une variable locale est définie dans une fonction. Bien que vous puissiez accéder à toute valeur de variable locale située en dehors du cadre de pile de la fonction actuelle, le système essaiera de s’assurer que ce type de comportement ne se produit pas. empiler des cadres. Cela nous donne une sorte d'illusion que la variable locale est étendue à une fonction spécifique.

Il existe de nombreuses façons d'implémenter des variables locales par un système d'exécution de langue. L'utilisation d'une pile est une solution efficace commune, utilisée dans de nombreux cas pratiques.

Intuitivement, un pointeur de pile spest conservé au moment de l'exécution (dans une adresse fixe ou dans un registre - cela compte vraiment). Supposons que chaque "push" incrémente le pointeur de pile.

Au moment de la compilation, le compilateur détermine l'adresse de chaque variable, sp - Koù Kest une constante qui ne dépend que de la portée de la variable (peut donc être calculée au moment de la compilation).

Notez que nous utilisons le mot "pile" ici dans un sens vague. Cette pile n’est pas accessible uniquement par le biais d’opérations Push / Pop / Top, elle est également accessible via sp - K.

Par exemple, considérons ce pseudocode:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Lorsque la procédure est appelée, des arguments x,ypeuvent être transmis sur la pile. Pour plus de simplicité, supposons que la convention est la suivante: l’appelant appuie en xpremier y.

Ensuite, le compilateur au point (1) peut trouver xà sp - 2et yà sp - 1.

Au point (2), une nouvelle variable entre en portée. Le compilateur génère un code qui fait la somme x+y, c.-à-d. Ce qui est indiqué par sp - 2et sp - 1, et applique le résultat de la somme sur la pile.

Au point (3), zest imprimé. Le compilateur sait que c'est la dernière variable dans la portée, alors c'est indiqué par sp - 1. Ce n'est plus y, depuis spchangé. Néanmoins, pour imprimer yle compilateur, il sait qu’il peut le trouver, dans cette portée, à sp - 2. De même, xse trouve maintenant à sp - 3.

Au point (4), nous sortons du scope. zest sauté, et yest à nouveau trouvé à l'adresse sp - 1, et xest à sp - 2.

À notre retour, fl’appelant ou l’appelant sort x,yde la pile.

Ainsi, l’informatique Kpour le compilateur consiste à compter approximativement le nombre de variables dans la portée. Dans le monde réel, cela est en réalité plus complexe puisque toutes les variables n’ont pas la même taille, le calcul de Kest donc légèrement plus complexe. Parfois, la pile contient également l'adresse de retour pour f, vous Kdevez donc "ignorer" celle-ci également. Mais ce sont des détails techniques.

Notez que, dans certains langages de programmation, les choses peuvent devenir encore plus complexes si des fonctionnalités plus complexes doivent être gérées. Par exemple, les procédures imbriquées nécessitent une analyse très minutieuse, car elles Kdoivent désormais "ignorer" de nombreuses adresses de retour, en particulier si la procédure imbriquée est récursive. Les fonctions Closures / lambdas / anonymous nécessitent également quelques précautions pour gérer les variables "capturées". Néanmoins, l'exemple ci-dessus devrait illustrer l'idée de base.

L'idée la plus simple est de considérer les variables comme des noms de correctifs pour les adresses en mémoire. En effet, certains assembleurs affichent le code machine de cette façon ("stocke la valeur 5 dans adresse i", où iest un nom de variable).

Certaines de ces adresses sont "absolues", comme les variables globales, d'autres "relatives", comme les variables locales. Les variables (c'est-à-dire les adresses) dans les fonctions sont relatives à un endroit de la "pile" différent pour chaque appel de fonction; De cette manière, le même nom peut faire référence à différents objets réels et les appels circulaires à la même fonction sont des appels indépendants travaillant en mémoire indépendante.

Les éléments de données pouvant aller sur la pile sont placés sur la pile - Oui! C'est un espace premium. En outre, une fois que nous avons poussé xdans la pile, puis ydans la pile, idéalement, nous ne pouvons pas accéder xtant yqu’il n’y en a pas. Nous devons faire un pop ypour y accéder x. Vous les avez correctes.

La pile n'est pas de variables, mais de frames

La mauvaise solution concerne la pile elle-même. Sur la pile, ce ne sont pas les éléments de données qui sont directement poussés. Plutôt, sur la pile, quelque chose appelé stack-frameest poussé. Ce cadre de pile contient les éléments de données. Bien que vous ne puissiez pas accéder aux cadres au plus profond de la pile, vous pouvez accéder au cadre supérieur et à tous les éléments de données qu’il contient.

Disons que nos éléments de données sont regroupés dans deux cadres de pile frame-xet frame-y. Nous les avons poussés l'un après l'autre. Maintenant, tant que vous êtes frame-yassis au-dessus de frame-x, vous ne pouvez pas accéder de manière idéale à un élément de données à l'intérieur frame-x. Seulement frame-yest visible. MAIS si cela frame-yest visible, vous pouvez accéder à tous les éléments de données qu’il contient. L'ensemble du cadre est visible, exposant tous les éléments de données qu'il contient.

Fin de réponse Plus (déclamer) sur ces cadres

Pendant la compilation, une liste de toutes les fonctions du programme est faite. Ensuite, pour chaque fonction, une liste d' éléments de données empilables est établie. Ensuite, pour chaque fonction, a stack-frame-templateest créé. Ce modèle est une structure de données qui contient toutes les variables choisies, l'espace pour les données d'entrée de la fonction, les données de sortie, etc. Maintenant, pendant l'exécution, chaque fois qu'une fonction est appelée, une copie de celle-ci templateest placée sur la pile - avec toutes les variables d'entrée et intermédiaires. . Lorsque cette fonction appelle une autre fonction, une nouvelle copie de cette fonction stack-frameest placée dans la pile. Tant que cette fonction est en cours d'exécution, les éléments de données de cette fonction sont préservés. Une fois que cette fonction est terminée, son cadre de pile est sorti. À présentce frame de pile est actif et cette fonction peut accéder à toutes ses variables.

Notez que la structure et la composition d'un cadre de pile varient d'un langage de programmation à un autre. Même au sein d'une langue, il peut exister des différences subtiles dans différentes implémentations.

Merci d'avoir envisagé CS. Je suis un programmeur maintenant quelques jours à prendre des leçons de piano :)