Analyse du pointeur - Pointer analysis

En informatique , l' analyse de pointeurs , ou analyse de points à , est une technique d' analyse de code statique qui établit quels pointeurs , ou références de tas, peuvent pointer vers quelles variables ou emplacements de stockage. C'est souvent une composante d'analyses plus complexes telles que l' analyse des évasions . Une technique étroitement liée est l' analyse de forme .

(Il s'agit de l'utilisation familière la plus courante du terme. Une utilisation secondaire est que l' analyse de pointeur est le nom collectif de l'analyse des points à , définie comme ci-dessus, et de l' analyse des alias . Les analyses des points à et des alias sont étroitement liées mais pas toujours équivalentes. problèmes.)

Exemple

Pour l'exemple de programme suivant, une analyse points-à calculerait que l'ensemble de points-à de p est { x , y }. 

int x;
int y;
int* p = unknown() ? &x : &y;

introduction

En tant que forme d'analyse statique, une analyse de pointeur parfaitement précise peut s'avérer indécidable . La plupart des approches sont solides , mais varient largement en performances et en précision. Pour les grands programmes, certains compromis peuvent être nécessaires pour que l'analyse se termine dans un délai et un espace raisonnables. Deux exemples de ces compromis sont:

  • Traiter toutes les références d'un objet structuré comme provenant de l'objet dans son ensemble. Ceci est connu sous le nom d' insensibilité de champ ou d' insensibilité de structure .
  • Ignorer le flux de contrôle lors de l'analyse des objets affectés aux pointeurs. Ceci est connu sous le nom d' analyse de pointeur insensible au contexte (lorsque vous ignorez le contexte dans lequel les appels de fonction sont effectués) ou d' analyse de pointeur insensible au flux (lorsque vous ignorez le flux de contrôle dans une procédure).

L'inconvénient de ces simplifications est que l'ensemble calculé d'objets pointés peut devenir moins précis.

Algorithmes insensibles au contexte et insensibles au flux

Les algorithmes d'analyse de pointeur sont utilisés pour convertir les utilisations de pointeur brutes collectées (affectations d'un pointeur à un autre ou attribution d'un pointeur pour en pointer vers un autre) en un graphique utile de ce que chaque pointeur peut pointer.

L'algorithme de Steensgaard et l'algorithme d'Andersen sont communs insensible au contexte, les algorithmes de flux insensibles à la casse pour l' analyse de pointeur. Ils sont souvent utilisés dans les compilateurs et ont des implémentations dans la base de code LLVM .

Approches insensibles au débit

De nombreuses approches d'analyse de pointeurs insensibles au flux peuvent être comprises comme des formes d' interprétation abstraite , où les allocations de tas sont abstraites par leur site d'allocation (c'est-à-dire, un emplacement de programme).

De nombreux algorithmes insensibles au flux sont spécifiés dans Datalog , y compris ceux du framework d'analyse Soot pour Java.

Les algorithmes contextuels et insensibles au flux atteignent une plus grande précision, généralement au prix de certaines performances, en analysant chaque procédure plusieurs fois, une fois par contexte . La plupart des analyses utilisent une approche de "chaîne de contexte", où les contextes consistent en une liste d'entrées (les choix courants d'entrées de contexte incluent les sites d'appels, les sites d'allocation et les types). Pour assurer la terminaison (et plus généralement l'évolutivité), ces analyses utilisent généralement une approche de limitation k , où le contexte a une taille maximale fixe, et les éléments les moins récemment ajoutés sont supprimés si nécessaire. Trois variantes courantes d'analyse contextuelle et insensible au flux sont:

  • Sensibilité du site d'appel
  • Sensibilité aux objets
  • Sensibilité de type

Sensibilité du site d'appel

Dans la sensibilité des sites d'appels, l'ensemble des points vers de chaque variable (l'ensemble des allocations de tas abstraites vers lesquelles chaque variable pourrait pointer) est davantage qualifié par un contexte consistant en une liste de sites d'appel dans le programme. Ces contextes font abstraction du flux de contrôle du programme.

Le programme suivant montre comment la sensibilité du site d'appel peut atteindre une précision plus élevée qu'une analyse insensible au flux et insensible au contexte. 

int *id(int* x) {
  return x;
}
int main() {
  int y;
  int z;
  int *y2 = id(&y); // call-site 1
  int *z2 = id(&z); // call-site 2
  return 0;
}

Pour ce programme, une analyse insensible au contexte conclurait (de manière solide mais imprécise) que x peut pointer vers l'allocation contenant y ou celle de z , donc y2 et z2 peuvent s'aliaser, et les deux pourraient pointer vers l'une ou l'autre des allocations. Une analyse sensible au site d'appel analyserait l' identifiant deux fois, une fois pour le site d'appel 1 et une fois pour le site d'appel 2, et les faits de point-vers pour x seraient qualifiés par le site d'appel, permettant à l'analyse de déduire que lorsque le principal retourne , y2 ne peut pointer que sur le holding d'allocation y et z2 ne peut pointer que sur le holding d'allocation z .

Sensibilité aux objets

Dans une analyse sensible aux objets, l'ensemble de points à de chaque variable est qualifié par l'allocation abstraite de tas de l'objet récepteur de l'appel de méthode. Contrairement à la sensibilité du site d'appel, la sensibilité aux objets est non syntaxique ou non locale : les entrées de contexte sont dérivées au cours de l'analyse des points vers elle-même.

Sensibilité de type

La sensibilité de type est une variante de la sensibilité d'objet où le site d'allocation de l'objet récepteur est remplacé par la classe / type contenant la méthode contenant le site d'allocation de l'objet récepteur. Cela entraîne strictement moins de contextes que ceux qui seraient utilisés dans une analyse sensible aux objets, ce qui signifie généralement de meilleures performances.

Les références

Bibliographie