Analyse d'alias - Alias analysis

L'analyse d'alias est une technique de la théorie du compilateur , utilisée pour déterminer si un emplacement de stockage peut être accédé de plusieurs manières. On dit que deux pointeurs sont aliasés s'ils pointent vers le même emplacement.

Les techniques d'analyse d'alias sont généralement classées par sensibilité au flux et sensibilité au contexte. Ils peuvent déterminer les informations de may-alias ou must-alias. Le terme analyse d'alias est souvent utilisé de manière interchangeable avec l' analyse de points à , un cas particulier.

Les analyseurs d'alias ont l'intention de créer et de calculer des informations utiles pour comprendre l' aliasing dans les programmes.

Aperçu

En général, l'analyse d'alias détermine si des références de mémoire distinctes pointent vers la même zone de mémoire. Cela permet au compilateur de déterminer quelles variables du programme seront affectées par une instruction. Par exemple, considérez la section de code suivante qui accède aux membres des structures: 

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

Il existe trois cas d'alias possibles ici:

  1. Les variables p et q ne peuvent pas d'alias (c'est-à-dire qu'elles ne pointent jamais vers le même emplacement mémoire).
  2. Les variables p et q doivent être alias (c'est-à-dire qu'elles pointent toujours vers le même emplacement mémoire).
  3. Il ne peut pas être déterminé de manière concluante au moment de la compilation si p et q alias ou non.

Si p et q ne peuvent pas créer d'alias, alors i = p.foo + 3; peuvent être remplacés par i = 4 . Si p et q doivent être alias, alors i = p.foo + 3; peut être changé en i = 5 parce que p.foo + 3 = q.foo + 3 . Dans les deux cas, nous sommes en mesure d'effectuer des optimisations à partir de la connaissance des alias (en supposant qu'aucun autre thread mettant à jour les mêmes emplacements ne puisse s'entrelacer avec le thread actuel, ou que le modèle de mémoire de langage permet à ces mises à jour de ne pas être immédiatement visibles pour le thread actuel dans absence de constructions de synchronisation explicites ). Par contre, si on ne sait pas si p et q alias ou non, alors aucune optimisation ne peut être effectuée et l'ensemble du code doit être exécuté pour obtenir le résultat. On dit que deux références mémoire ont une relation may-alias si leur alias est inconnu.

Effectuer une analyse d'alias

Dans l'analyse des alias, nous divisons la mémoire du programme en classes d'alias . Les classes d'alias sont des ensembles d'emplacements disjoints qui ne peuvent pas s'aliaser les uns sur les autres. Pour la discussion ici, on suppose que les optimisations effectuées ici se produisent sur une représentation intermédiaire de bas niveau du programme. C'est-à-dire que le programme a été compilé en opérations binaires, saute, se déplace entre les registres, passe des registres à la mémoire, passe de la mémoire aux registres, branches et appels / retours de fonctions.

Analyse d'alias basée sur le type

Si le langage en cours de compilation est de type sécurisé , le vérificateur de type du compilateur est correct et le langage n'a pas la capacité de créer des pointeurs référençant des variables locales (telles que ML , Haskell ou Java ), alors des optimisations utiles peuvent être effectuées. Il existe de nombreux cas où nous savons que deux emplacements mémoire doivent être dans des classes d'alias différentes:

  1. Deux variables de types différents ne peuvent pas être dans la même classe d'alias car il s'agit d'une propriété de langages fortement typés et sans référence mémoire (c'est-à-dire que les références aux emplacements mémoire ne peuvent pas être modifiées directement) que deux variables de types différents ne peuvent pas partager le même emplacement mémoire simultanément.
  2. Les allocations locales au cadre de pile actuel ne peuvent pas être dans la même classe d'alias que toute allocation précédente provenant d'un autre cadre de pile. C'est le cas car les nouvelles allocations de mémoire doivent être disjointes de toutes les autres allocations de mémoire.
  3. Chaque champ d'enregistrement de chaque type d'enregistrement a sa propre classe d'alias, en général, car la discipline de saisie ne permet généralement que les enregistrements du même type en alias. Étant donné que tous les enregistrements d'un type seront stockés dans un format identique en mémoire, un champ ne peut s'alias que sur lui-même.
  4. De même, chaque tableau d'un type donné a sa propre classe d'alias.

Lors de l'analyse d'alias pour le code, chaque chargement et stockage en mémoire doit être étiqueté avec sa classe. Nous avons alors la propriété utile, étant donné les emplacements de mémoire et avec les classes d'alias, que si alors may-alias , et si alors les emplacements de mémoire ne seront pas alias.

Analyse d'alias basée sur le flux

L'analyse basée sur le flux peut être appliquée à des programmes dans un langage avec des références ou un casting de type. L'analyse basée sur le flux peut être utilisée à la place ou pour compléter l'analyse basée sur le type. Dans l'analyse basée sur le flux, de nouvelles classes d'alias sont créées pour chaque allocation de mémoire et pour chaque variable globale et locale dont l'adresse a été utilisée. Les références peuvent pointer vers plus d'une valeur au fil du temps et peuvent donc appartenir à plus d'une classe d'alias. Cela signifie que chaque emplacement mémoire a un ensemble de classes d'alias au lieu d'une seule classe d'alias.

Voir également

Références

  • Appel, Andrew W. (1998). Implémentation moderne du compilateur dans ML . Cambridge, Royaume-Uni: Cambridge University Press. ISBN   0-521-60764-7 .

Liens externes