Aliasing et pointeurs restreints

Depuis ses débuts, le langage C pose un problème assez gênant aux compilateurs désireux d’optimiser le code, dû à son utilisation massive des pointeurs : le risque d'aliasing (ou « risque de chevauchement »).

Les normes successives ont tenté de l’atténuer à l’aide de la règle de strict aliasing (C89) et des pointeurs restreints (C99) ; deux concepts qui vont retenir notre attention dans ce tutoriel.

• Une histoire d'aliasing
• La règle de strict aliasing
• Les pointeurs restreints

Une histoire d'aliasing

Dans un premier temps, nous allons découvrir cette notion d'aliasing et voir en quoi elle complique le travail du compilateur.

Rappels

La notion d’objet

Le terme d'objet, qui sera au centre de nos discussions futures, désigne simplement une zone mémoire pouvant contenir des données.

La notion de lvalue

Une lvalue est une expression qui désigne un objet (que ce soit pour un accès ou une modification).

int i;
int j;
int *p;
 
/*
 * `p' est une lvalue car elle modifie un objet.
 * `&i' n'est pas une lvalue.
 */
p = &i;
 
/* `i' est une lvalue car elle modifie un objet. */
i = 10;
 
/*
 * `j' est une lvalue car elle modifie un objet.
 * `i' est une lvalue car elle accède à un objet.
 */
j = i;
 
/* `*p' est une lvalue car elle modifie un objet. */
*p = 30;

Gardez bien ces deux notions à l’esprit, nous allons en avoir besoin.

Présentation de la notion d’aliasing

En programmation, un cas d'aliasing se produit lorsque plusieurs lvalues désignent le même objet ; celles-ci sont alors qualifiées d'alias.

Par exemple, dans le code source ci-dessous, *p est un alias de n, c’est-à-dire que toute modification de *p aura une répercussion sur la valeur de n et vice versa.

int n;
int *p = &n;

Cette définition peut paraître simple, mais elle comporte aussi sa part de subtilités.

int a[2][10];
 
int *p = a[0];
int *q = a[1];

On serait ici tenté de dire que les lvalues *p et *q accèdent au même objet (le tableau a), pourtant il n’en est rien. En effet, il ne faut pas perdre de vue que la notion d’objet est étrangère à celle de type. Dès lors, un même objet peut être subdivisé en deux autres, indépendants l’un de l’autre. *p et *q ne sont donc pas des alias.

De la même manière, dans le code ci-dessous, *p, *q, *r et *s ne le sont pas non plus.

char a[4];
 
char *p = a + 0;
char *q = a + 1;
char *r = a + 2;
char *s = a + 3;

Cette division fonctionne jusqu’au plus petit objet possible (à savoir un bit dans le cas des champs de bits). Ainsi, a.i n’est pas un alias de a.j.

struct s {
    unsigned int i : 1;
    unsigned int j : 1;
};
 
struct s a;

Problématique d’optimisation du compilateur

Si les relations d'aliasing qui existent entre les différentes lvalues du programme ne sont pas préoccupantes pour le programmeur, cela l’est plus pour le compilateur, qui peut être gêné dans son travail d’optimisation.

Problèmes causés par les alias au compilateur

Après avoir vérifié que le code source est syntaxiquement correct, le compilateur entre dans une seconde phase : celle de l'optimisation de code. Cette étape consiste simplement en la modification du code dans le but que l’exécution du programme se déroule le plus rapidement possible. Pour cela, il va prendre en compte certains éléments de l’implémentation, comme les différentes instructions dont dispose le processeur. Pour le moment, nous nous concentrerons uniquement sur une des optimisations les plus basiques : la réorganisation du code.

#include <stdio.h>
 
void
f(void)
{
    const int n = 5;

    printf("%d\n", n);
}

Ici, force est de constater que l’instruction de la ligne 6 est inutile, puisque la variable n n’est pas modifiée. Aussi le compilateur pourra-t-il, par exemple, remplacer le code d’appel de cette fonction par un simple printf("%d ", 5).

Le problème dans tout cela, c’est que l’aliasing complique cette réorganisation. En effet, dans le code ci-dessous, on peut se dire à première vue que le compilateur pourrait supprimer la ligne 8 et remplacer l’instruction de la ligne 10. Or, si les lvalues *p et n sont des alias, le résultat attendu est complètement différent (10 en l’occurrence). Par conséquent, compte tenu du risque d’aliasing, le compilateur est obligé de laisser ces instructions telles quelles (ce qui peut, à long terme, ralentir l’exécution du programme).

#include <stdio.h>
 
static int n;
 
void
f(int *p)
{
    n = 5;
    *p = 10;
    printf("%d\n", n);
}

Analyse d’alias par le compilateur

L'analyse d’alias, c’est-à-dire la recherche des situations d'aliasing dans un programme donné, est donc nécessaire pour le compilateur, afin de pouvoir déterminer quels cas peuvent permettre telle ou telle optimisation.

Peu importe le résultat de cette analyse (alias ou pas) : dans les deux cas, une optimisation pourra être effectuée. La seule situation problématique se produit lorsqu’on ne peut pas déterminer, lors de la compilation, les relations d'aliasing qui existent entre deux lvalues. Le compilateur est alors obligé de considérer le pire des cas : on parle d'aliasing pessimiste.

*p = 4;
*q = 6;
n = *p + *q;

Avec uniquement ces informations, le compilateur se retrouve face à trois cas distincts (en supposant que *p, *q et n sont de type int) :

• si *p et *q ne sont pas des alias, alors n = *p + *q pourra être remplacé par n = 10 ;
• si *p et *q sont des alias, alors n = *p + *q pourra être remplacé par n = 12 ;
• si il est impossible de déterminer les relations d'aliasing qui existent entre *p et *q, alors le code ne pourra pas être modifié.

Le compilateur se doit donc d’effectuer une analyse d’alias pertinente pour sélectionner une de ces affirmations (et, si possible, une des deux premières). Dans cette optique, beaucoup algorithmes ont été développés. Néanmoins, en pratique, la plupart sont trop lourds pour être intégrés aux compilateurs courants, si bien que ces derniers se contentent généralement d’une analyse superficielle (ce qui peut se révéler pénalisant pour les performances).

La règle de strict aliasing

Nous avons donc vu en quoi il était important pour le travail d’optimisation du compilateur de connaître les relations d'aliasing qui existent entre les lvalues du programme. Cette préoccupation a été au centre de beaucoup de critiques du langage C à ses débuts, qui lui reprochaient son imprécision dans l’analyse des pointeurs. Aussi la norme aide-t-elle l’analyse d’alias avec un premier concept : la règle de strict aliasing.

Normalisation de la règle de strict aliasing

Nous allons maintenant faire un petit tour d’horizon de la définition et de la normalisation de cette règle en suivant un ordre chronologique (de son inauguration dans la norme C89 à sa précision dans la norme C99).

La norme C89

C’est en 1989 que le comité de l’ANSI décida de l’instaurer, dans le but de réduire le nombre de cas d'aliasing pessimistes. Grâce à cela, le compilateur a pu affiner son analyse d’alias en présumant des lvalues comme n’étant pas des alias en fonction de leur type et de celui de l’objet qu’elles désignent.

Voyons maintenant l’énoncé de la règle.

Un objet ne peut être accédé que par une lvalue qui a un des types suivants :

• un type identique au type déclaré de l’objet ;
• une version qualifiée du type déclaré de l’objet ;
• un type qui est le type signé ou non signé correspondant au type déclaré de l’objet ;
• un type qui est le type signé ou non signé correspondant à une version qualifiée du type déclaré de l’objet ;
• un agrégat ou une union qui inclut un des types mentionnés ci-dessus parmi ses membres (incluant, de manière récursive, les sous-agrégats ou les sous-unions) ;
• un type caractère.

La norme se base sur le type déclaré de l’objet, qui lui est attribué lors de sa définition. Par exemple, dans le code ci-dessous, deux objets sont créés, ayant respectivement comme type déclaré le type int et le type double.

int n;
double x;

La norme C99

La norme C99 a peaufiné cette règle en la rapportant, non plus au type déclaré, mais au type effectif de l’objet, une nouvelle notion qui permet de mieux gérer le cas dans lequel l’objet ne dispose pas d’un type déclaré. Cela vise essentiellement les objets alloués dynamiquement, puisque ces derniers ne sont pas créés lors d’une définition, mais lors d’un appel à une fonction d’allocation.

The effective type of an object for an access to its stored value is the declared type of the object, if any. If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. If a value is copied into an object having no declared type using memcpy or memmove, or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access. Source : ISO/IEC 9899:TC3, doc. N1256, § 6.5, Expressions, al. 6, pp. 67–68.

Dans le cas où un objet n’a pas de type déclaré, son type effectif est :

• celui de la lvalue le désignant (accès ou modification) ;
• celui de l’objet dont le contenu y a été copié à l’aide de memcpy ou memmove.

#include <stdlib.h>
 
int *p = malloc(sizeof *p);
 
/*
 * Le type de l'objet désigné par la lvalue `*p' prend le type
 * `int'.
 */
*p = 10;
 
/*
 * Le type de l'objet désigné par la lvalue `*p' prend le type
 * `unsigned int'.
 */
*(unsigned int *)p = 20U;

Pour conclure, notons que la norme C11 n’a pas changé l’énoncé de la règle.

Illustrations de la règle de strict aliasing

Vous devriez maintenant être au point avec la définition et la normalisation de la règle de strict aliasing. Pour illustrer un peu nos propos, nous étudierons tout d’abord quelques exemples et contre-exemples, puis nous verrons quel intérêt le compilateur peut tirer de tout cela.

Exemples

La question sera de savoir, pour chacune des lignes de code ci-dessous, si l’utilisation de l’alias créé est autorisé.

unsigned int n;
 
/*
 * Correct, car la lvalue `*p' a un type qui est une version
 * qualifiée du type effectif de l'objet.
 */
const unsigned int *p = &n;
 
/*
 * Incorrect, car la lvalue `*q' a un type qui n'est ni une version
 * qualifiée du type déclaré de l'objet, ni le type signé ou non
 * signé correspondant, ni un type caractère.
 */
long int *q = (long int *)&n;
 
/*
 * Correct, car la lvalue `*r' a un type qui est le type signé
 * correspondant à une version qualifiée du type effectif de l'objet.
 */
const int *r = &n;
 
/* Correct, car la lvalue `*s' a un type caractère. */
signed char *s = (signed char *)&n;

Mentionnons que toutes ces règles s’appliquent uniquement lors du déférencement, ce qui autorise donc en soi l’affectation (bien que, naturellement, le champ d’action du pointeur soit par la suite réduit puisqu’il sera interdit de le déférencer).

int n;
 
/* Correct : `p' n'est pas déférencé. */
short int *p = (short int *)&n;
 
/* Incorrect : `p' est déférencé. */
*p = 10;

Bénéfices pour le compilateur

Pour le compilateur, le plus intéressant reste la conséquence de cette règle, c’est-à-dire qu’en dehors des accès autorisés mentionnés ci-dessus, deux lvalues ne désigneront jamais un même objet.

Dans l’exemple ci-dessus, la règle de strict aliasing est brisée car *p a un type qui n’est ni une version qualifiée du type déclaré de l’objet, ni le type signé ou non signé correspondant, ni un type caractère. Les lvalues *p et n ne seront donc pas considérées comme des alias lors de la phase d’optimisation (bien qu’en vérité elles le soient). Voilà qui facilite bien l’analyse d’alias !

Paramétrage du compilateur gcc

Avec le compilateur gcc, la règle de strict aliasing n’est activée par défaut que dans les niveaux d’optimisation. Toutefois, il est possible pour le programmeur de spécifier explicitement s’il veut que son code subisse les vérifications associées, à l’aide des options -fstrict-aliasing (respect strict de la règle) et -fno-strict-aliasing (tolérance de comportements non conformes à la règle).

Si l’utilisation pertinente de l’option -fno-strict-aliasing peut vous paraître dangereuse, puisque le code n’est alors plus conforme à la norme, l’histoire retient que de grands noms l’ont soutenu (le noyau Linux pour ne citer que lui).

gcc dispose notamment d’un avertissement permettant de prévenir les situation non conformes à la règle de strict aliasing.

warning: dereferencing type-punned pointer will break strict-aliasing rules

L’option permettant de gérer de tels affichages est -Wstrict-aliasing[=n], avec n compris entre 1 et 3 (niveau 3 par défaut). Plus n est petit, moins gcc fera de vérifications (par exemple, avec n = 1 ou n = 2, l’avertissement peut se déclencher même si le pointeur n’est pas déférencé). De même, le pourcentage de faux positifs et de faux négatifs dépend du niveau utilisé.

Par exemple, avec gcc 4.9.2, l’avertissement ne se déclare qu’aux niveaux 1 et 2 pour ce code, au niveau de l’instruction d’affectation (ligne 5).

int
main(void)
{
    unsigned int n;
    long int *p = (long int *)&n;

    *p = 10L;
    return 0;
}

Si la règle de strict aliasing constitue une aide réelle à l’analyse d’alias des compilateurs, il reste encore le cas des alias de type identique (ou ne différant que par le signe et/ou par le qualificateur, ainsi que celui des types caractères). Il est évident qu’on ne peut pas interdire cette pratique, qui signifierait l’abolition des pointeurs ! Mais c’est à ce moment-là que le programmeur entre en scène avec l'aliasing spécifié, thème qui fera l’objet de notre prochaine sous-partie.

Les pointeurs restreints

Malgré cette règle, il reste donc encore quelques situations d'aliasing compromettantes. Comme la norme et les compilateurs ne peuvent plus faire d’hypothèses supplémentaires, c’est le programmeur lui-même qui est sollicité.

Introduction aux pointeurs restreints

L'aliasing spécifié par le développeur est implémenté dans la norme C99 sous la forme de la notion de pointeur restreint. L’idée est de permettre la mise en place d’un droit exclusif d’accès sur un objet référencé par un pointeur qualifié de restreint. Ce droit ne peut être transmis qu’à des lvalues dérivées de ce pointeur, c’est-à-dire qui ont obtenu l’adresse de l’objet via celui-ci.

Le qualificateur restrict

Pour déclarer un pointeur restreint, la norme C99 a mis à la disposition des programmeurs un nouveau qualificateur : restrict. Il est applicable uniquement aux pointeurs sur objet ; il doit donc être placé, lors de la déclaration, après le symbole *.

/* `p' est un pointeur restreint sur `int'. */
int * restrict p;
 
/* `q' est un pointeur sur pointeur restreint sur `int'. */
int * restrict *q:
 
/* `r' est un pointeur restreint sur pointeur sur `int'. */
int ** restrict r;

Définition

Le passage à propos de restrict dans la norme C99 peut paraître alambiqué et tordu ; nous vous ferons donc grâce des citations. L’essentiel du fonctionnement des pointeurs restreints peut se résumer dans les deux règles suivantes.

1. il ne peut y avoir qu’un seul pointeur restreint référençant un même objet dans un même bloc ;
2. une lvalue ne peut modifier un objet référencé par un pointeur restreint que si elle est dérivée de ce dernier.

Quelques exemples

À ce stade, la définition peut vous paraître encore un peu floue, c’est pourquoi nous vous proposons quelques petits exemples.

#include <stdlib.h>

static char * restrict r, * restrict s;

void
copy(void * restrict dst, void * restrict src, size_t n)
{
    /*
     * Valide car `p' et `q' ne sont pas des pointeurs
     * restreints.
     */
    char *p = dst;
    char *q = src;

    while (n-- != 0) {
        /*
         * Valide car les lvalues `*p' et `*q' sont
         * respectivement basées sur les pointeurs restreints
         * `dst' et `src'.
         */
        *p++ = *q++;
    }

    /*
     * Invalide car `r' et `s' sont des pointeurs restreints et
     * référencent, respectivement, les mêmes objets que `dst' et
     * `src' dans le bloc de la fonction `copy'.
     */
    *r = *s;
}

int
main(void)
{
    /*
     * Valide car `r' et `s' référencent deux objets différents
     * dans le bloc de la fonction main.
     */
    r = malloc(10);
    s = malloc(10);

    /*
     * Valide car `dst' et `src' référencent deux objets
     * différents dans le bloc de la fonction `copy'.
     */
    copy(r, s, 10);

    /*
     * Invalide car `dst' et `src' référencent le même objet dans
     * le bloc de la fonction `copy'.
     */
    copy(r, r, 10);

    /*
     * Invalide car `r' et `s' référencent alors le même objet
     * dans le bloc de la fonction main.
     */
    r = s;
    return 0;      
}

Bien qu’il soit techniquement possible d’assigner des pointeurs restreints à des pointeurs non restreints, c’est une pratique déconseillée car cela peut compliquer le travail d’optimisation du compilateur.

Bénéfice des pointeurs restreints

À l’instar de la règle de strict aliasing, les pointeurs restreints permettent aux compilateurs d’effectuer des présomptions quant aux relations d'aliasing qui existent entre les pointeurs d’un même bloc. En effet, deux pointeurs restreints sont garantis de ne pas être des alias. Ainsi, c’est toute la phase d’optimisation de code qui en profite, et notamment la réorganisation du code.

La vectorisation

De plus, étant donné que le mot-clé restrict vise des pointeurs de même type, cela laisse également place à une optimisation plus poussée faisant intervenir les tableaux : la vectorisation. Cette dernière pratique consiste à effectuer des opérations sur des petits tableaux de taille fixe plutôt que sur un seul élément à la fois. Cela est possible sur la plupart des processeurs modernes, qui disposent d’instructions spécialisées travaillant sur plusieurs éléments à la fois : les instructions vectorielles.

Dans les exemples suivants, nous considérerons un processeur disposant d’instructions vectorielles capables de travailler sur 128 bits, c’est-à-dire ici de 16 char ou de 4 int. Elles seront illustrées par les trois fonctions suivantes :

• vect_cpy16 : copie un tableau de 16 char ;
• vect_cpy4 : copie un tableau de 4 int ;
• vect_add4 : additionne deux tableaux de 4 int et stocke le résultat dans le premier.

Exemple (1)

void
memcpy(void * restrict dst, void * restrict src, size_t n)
{
    char *p = dst;
    char *q = src;

    while (n-- != 0)
        *p++ = *q++;
}

Dans le code ci-dessus, la règle de strict aliasing est inutile car les lvalues *p et *q sont toutes deux de type char. En revanche, elles sont basées sur un pointeur restreint et sont donc garanties de ne pas être des alias. Le compilateur pourrait donc vectoriser cette boucle, en copiant des tableaux de taille fixe plutôt que des char un par un.

void
memcpy(void * restrict dst, void * restrict src, size_t n)
{
    char *p = dst;
    char *q = src;
    size_t i;

    for (i = 0; n - i >= 16; i += 16)
        vect_cpy16(p + i, q + i);

    for (; i < n; ++i)
        p[i] = q[i];
}

Exemple (2)

void
vect_add(int * restrict res, int * restrict a, int * restrict b, size_t n)
{
    for (size_t i = 0; i < n; ++i)
        res[i] = a[i] + b[i];
}

De la même manière, le code ci-dessus opère sur des lvalues basées sur des pointeurs restreints. Ainsi, le compilateur pourrait utiliser des instructions vectorielles afin d’optimiser le code comme suit.

void
vect_add(int * restrict res, int * restrict a, int * restrict b, size_t n)
{
    size_t i;

    for (i = 0; n - i >= 4; i += 4) {
        vect_cpy4(res + i, a + i);
        vect_add4(res + i, b + i);
    }

    for (; i < n; ++i)
        res[i] = a[i] + b[i];
}

Dangers des pointeurs restreints

Malgré tout, il est important de prendre des précautions lors de l’utilisation des pointeurs restreints ; ils ne doivent en effet pas être utilisés à tout-va.

Confusion entre appelant et appelé

Si deux pointeurs sont indiqués comme étant restreints mais, qu’en réalité, ils se chevauchent, le résultat est indéterminé et le code produit a de fortes chances d’être incorrect.

#include <string.h>

void
f(void)
{
    int a[8] = { 0, 0, 45, 42, 12, 89, 2, 36 };

    /*
     * Les deux arguments restreints de `memcpy' se chevauchent,
     * c'est une situation de comportement indéterminé.
     */
    memcpy(a, a + 2, 6);
}

Or, nous pouvons remarquer que c’est à la fonction appelée de préciser si les arguments doivent être restreints, mais seule la fonction appelante peut contrôler si ces arguments sont conformes (le compilateur ne peut pas faire cette vérification par lui-même).

Précautions d’utilisation

On distingue deux grands cas dans lesquels on peut utiliser les pointeurs restreints.

1. Si l’algorithme de la fonction ne fonctionne pas ou n’a aucun sens dans le cas où les paramètres se chevauchent, alors le résultat avec les pointeurs restreints sera toujours incorrect, mais pourra avoir changé. Par exemple, le chevauchement des deux paramètres dans la fonction fopen serait complètement absurde.
2. Si le principe de la fonction a un sens dans le cas où les arguments se chevauchent mais que cela est pénalisant pour les optimisations, alors il est préférable de créer deux versions de la fonction (une avec restrict et une sans), à la manière des fonctions memcpy et memmove.

Au final, on peut représenter tout cela par une sorte de contrat passé entre les deux fonctions. Si il n’est pas respecté par la fonction appelante, alors la fonction appelée se réserve le droit de produire un code incorrect.

Une optimisation vraiment valable ?

Il ne faut pas oublier que restrict est une simple indication et pas une obligation pour le compilateur. Aussi les détracteurs du mot-clé ont-ils souvent souligné le fait que le gain de temps octroyé par l’utilisation des pointeurs restreints n’est pas toujours très important (par exemple, les processeurs qui ne disposent pas d’instructions vectorielles ne jouiront pas de cette optimisation).

Nous pouvons donc légitimement nous demander si l’utilisation des pointeurs restreints est réellement rentable par rapport à l’effort de réflexion associé (qui est loin d’être négligeable). Plusieurs travaux ont conclu que ce n’était pas le cas, et déconseillent donc l'aliasing spécifié.

À vous de vous forger votre propre avis ; n’hésitez pas, dans cette optique, à construire vos propres étalonnages suivant votre utilisation du langage. En tout cas, si vous êtes prêts à fournir un effort supplémentaire pour un bénéfice, si minimal qu’il soit, vous voilà informés !

Ainsi, ce tutoriel touche à sa fin. Nous espérons vous avoir éclairé sur ce difficile sujet d’aliasing et de pointeurs restreints. La norme du langage C est, aujourd’hui encore, une des seules normes de langage de programmation qui prône l’optimisation des compilateurs, le C cherche donc toujours à prouver ses qualités en performances pures.

Liens externes

Alias et optimisation

• (en) Optimisation de code par le compilateur sur Wikipédia.
• (en) Optimisation de boucles sur Wikipédia.
• (fr) Pipeline des instructions sur Wikipédia.
• (en) Les processeurs vectoriels sur Wikipédia.
• (en) Guide de programmation pour la vectorisation des compilateurs C/C++.

Analyse d’alias

• (en) Analyse d’alias sur Wikipédia.
• (en) Exemple d’algorithme effectuant une analyse d’alias performante.
• (en) L’analyse d’alias de gcc.

Règle de strict aliasing

• (en) Comprendre le strict aliasing.
• (en) Type-punning et strict aliasing.
• (en) Comprendre le strict aliasing en C/C++.

Paramétrage du compilateur

• (en) Voir les raisons de l’utilisation de -fno-strict-aliasing dans le noyau Linux.
• (en) Page de manuel de gcc (recherchez « -fstrict-aliasing »).

Les pointeurs restreints

• (fr) Le C et ses raisons : les pointeurs restreints.
• (en) Les pointeurs restreints en C.
• (en) Defect Report #294.
• (en) Démystification du mot-clé restrict.
• (en) Pourquoi l'aliasing spécifié est une mauvaise idée.