Question sur les pointeurs restreints

Le
Taurre
Bonjour à tous,

Je me suis récemment penché sur la notion de pointeurs restreints
introduite par la Norme C99 et il y a plusieurs questions auxquelles
je n'ai trouvé aucune réponse:

- la première porte sur ce code:

#include <stdlib.h>


void
test (int *a, int *b, int * restrict v)
{
*a = *v;
*b = *v;
}


int
main (void)
{
int a;
int b;
int v = 10;

test (&a, &b, &v);
return EXIT_SUCCESS;
}

si j'ai bien saisit la notion de pointeur restreint cela signifie,
dans le cas de la fonction "test", que l'objet sur lequel pointe la
variable "v" ne peut-être accéder que via cette dernière. Donc, en
toute logique, on peut supposer que l'objet pointé par la variable "v"
ne sera pas modifié lors de l'exécution de cette fonction. Or, si je
compile ce code, j'obtiens ces lignes en assembleur pour la fonction
"test":

movl (%rdx), %eax
movl %eax, (%rdi)
movl (%rdx), %eax
movl %eax, (%rsi)

la valeur de l'objet pointé par la variable "v" est chargé deux fois
dans le registre eax alors qu'elle ne devrait l'être qu'une seule
fois l'optimisation n'aura lieu que si un ou les deux autres
pointeurs sont également déclaré avec le qualificatif "restrict".
Quelqu'un pourrait-il m'expliquer pourquoi?

- la deuxième porte sur le même code, mais avec des variables de type
char. Dans cette hypothèse, même si les trois pointeurs sont déclar=
és
avec le qualificatif "restrict", aucune optimisation n'est effectuée
et j'obtiens donc:

movzbl (%rdx), %eax
movb %al, (%rdi)
movzbl (%rdx), %eax
movb %al, (%rsi)

Je précise que je compile avec GCC et l'option d'optimisation -O2
Merci d'avance pour vos réponses.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 4
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Marc
Le #23305951
Taurre wrote:

void
test (int *a, int *b, int * restrict v)
{
*a = *v;
*b = *v;
}


[...]
si j'ai bien saisit la notion de pointeur restreint cela signifie,
dans le cas de la fonction "test", que l'objet sur lequel pointe la
variable "v" ne peut-être accéder que via cette dernière. Donc, en
toute logique, on peut supposer que l'objet pointé par la variable "v"
ne sera pas modifié lors de l'exécution de cette fonction. Or, si je
compile ce code, j'obtiens ces lignes en assembleur pour la fonction
"test":

movl (%rdx), %eax
movl %eax, (%rdi)
movl (%rdx), %eax
movl %eax, (%rsi)

la valeur de l'objet pointé par la variable "v" est chargé deux fois
dans le registre eax alors qu'elle ne devrait l'être qu'une seule
fois... l'optimisation n'aura lieu que si un ou les deux autres
pointeurs sont également déclaré avec le qualificatif "restrict".
Quelqu'un pourrait-il m'expliquer pourquoi?



En fait ce sont "a" et "v" dont tu veux indiquer l'indépendance au
compilateur.

char c[42];
test(c,b,c+1);
--> l'écriture dans *a modifie la valeur *v.
(sur une archi où les int sont forcément alignés, ça ne serait pas
absurde de faire l'optimisation sans restrict j'ai l'impression, mais
je peux rater quelque chose)

- la deuxième porte sur le même code, mais avec des variables de type
char. Dans cette hypothèse, même si les trois pointeurs sont déclarés
avec le qualificatif "restrict", aucune optimisation n'est effectuée



Essaie un gcc plus récent alors.
Taurre
Le #23306231
On 24 avr, 00:06, Marc
Taurre  wrote:
> void
> test (int *a, int *b, int * restrict v)
> {
>         *a = *v;
>         *b = *v;
> }
[...]
> si j'ai bien saisit la notion de pointeur restreint cela signifie,
> dans le cas de la fonction "test", que l'objet sur lequel pointe la
> variable "v" ne peut-être accéder que via cette dernière. Donc, e n
> toute logique, on peut supposer que l'objet pointé par la variable "v "
> ne sera pas modifié lors de l'exécution de cette fonction. Or, si j e
> compile ce code, j'obtiens ces lignes en assembleur pour la fonction
> "test":

> movl       (%rdx), %eax
> movl       %eax, (%rdi)
> movl       (%rdx), %eax
> movl       %eax, (%rsi)

> la valeur de l'objet pointé par la variable "v" est chargé deux foi s
> dans le registre eax alors qu'elle ne devrait l'être qu'une seule
> fois... l'optimisation n'aura lieu que si un ou les deux autres
> pointeurs sont également déclaré avec le qualificatif "restrict".
> Quelqu'un pourrait-il m'expliquer pourquoi?

En fait ce sont "a" et "v" dont tu veux indiquer l'indépendance au
compilateur.

char c[42];
test(c,b,c+1);
--> l'écriture dans *a modifie la valeur *v.
(sur une archi où les int sont forcément alignés, ça ne serait pa s
absurde de faire l'optimisation sans restrict j'ai l'impression, mais
je peux rater quelque chose)

> - la deuxième porte sur le même code, mais avec des variables de ty pe
> char. Dans cette hypothèse, même si les trois pointeurs sont décl arés
> avec le qualificatif "restrict", aucune optimisation n'est effectuée

Essaie un gcc plus récent alors.



Tout d'abord, merci pour cette réponse :)

En fait ce sont "a" et "v" dont tu veux indiquer l'indépendance au
compilateur.

char c[42];
test(c,b,c+1);
--> l'écriture dans *a modifie la valeur *v.



Oui, mais n'est ce pas un comportement interdit? Normalement, en
qualifiant le pointeur "v" de restreint, on indique au compilateur que
l'objet sur lequel il pointe ne sera accéder que via lui-même ou un
pointeur dérivé de lui. Or, dans cet exemple ce n'est pas le cas, les
pointeurs "a" et "v" accèdent au même objet (enfin pas tout à fait,
mais une partie de l'objet pointé par "v" est accéder via "a" ce qui
constitue un comportement indéterminé il me semble).

Essaie un gcc plus récent alors.



C'est vrai que je suis sous Debian Squeeze et que ma version n'est pas
la plus récente (4-4), je vais essayer avec une autre, merci du
conseil ;)
Marc
Le #23306701
Taurre wrote:

En fait ce sont "a" et "v" dont tu veux indiquer l'indépendance au
compilateur.

char c[42];
test(c,b,c+1);
--> l'écriture dans *a modifie la valeur *v.



Oui, mais n'est ce pas un comportement interdit? Normalement, en
qualifiant le pointeur "v" de restreint, on indique au compilateur que
l'objet sur lequel il pointe ne sera accéder que via lui-même ou un
pointeur dérivé de lui. Or, dans cet exemple ce n'est pas le cas, les
pointeurs "a" et "v" accèdent au même objet (enfin pas tout à fait,
mais une partie de l'objet pointé par "v" est accéder via "a" ce qui
constitue un comportement indéterminé il me semble).



C'est aussi comme ça que j'avais compris restrict au début, mais
ensuite j'ai regardé ce que faisait gcc, et les exemples donnés par le
standard, et ça ne collait pas bien.

exemple 1:
int * restrict a;
int * restrict b;
extern int c[];

exemple 2:
void f(int n, int * restrict p, int * restrict q)
{
while (n-- > 0)
*p++ = *q++;
}

autre exemple:
void *memcpy(void *restrict s1, const void *restrict s2, size_t n);

À chaque fois (sauf pour la variable extern) restrict est mis en
double. Le texte n'a pas changé dans C1X, c'est toujours aussi peu
clair.

Il est possible aussi que gcc soit trop conservateur.

Essaie un gcc plus récent alors.



C'est vrai que je suis sous Debian Squeeze et que ma version n'est pas
la plus récente (4-4), je vais essayer avec une autre, merci du
conseil ;)



Je vais tuer le suspens, mais j'avais essayé avant de poster, et ça
fait la même optimisation que pour int.
Taurre
Le #23307011
On 24 avr, 14:31, Marc
Taurre  wrote:
>> En fait ce sont "a" et "v" dont tu veux indiquer l'indépendance au
>> compilateur.

>> char c[42];
>> test(c,b,c+1);
>> --> l'écriture dans *a modifie la valeur *v.

> Oui, mais n'est ce pas un comportement interdit? Normalement, en
> qualifiant le pointeur "v" de restreint, on indique au compilateur que
> l'objet sur lequel il pointe ne sera accéder que via lui-même ou un
> pointeur dérivé de lui. Or, dans cet exemple ce n'est pas le cas, l es
> pointeurs "a" et "v" accèdent au même objet (enfin pas tout à fai t,
> mais une partie de l'objet pointé par "v" est accéder via "a" ce qu i
> constitue un comportement indéterminé il me semble).

C'est aussi comme ça que j'avais compris restrict au début, mais
ensuite j'ai regardé ce que faisait gcc, et les exemples donnés par l e
standard, et ça ne collait pas bien.

exemple 1:
int * restrict a;
int * restrict b;
extern int c[];

exemple 2:
void f(int n, int * restrict p, int * restrict q)
{
      while (n-- > 0)
            *p++ = *q++;

}

autre exemple:
void *memcpy(void *restrict s1, const void *restrict s2, size_t n);

À chaque fois (sauf pour la variable extern) restrict est mis en
double. Le texte n'a pas changé dans C1X, c'est toujours aussi peu
clair.

Il est possible aussi que gcc soit trop conservateur.

>> Essaie un gcc plus récent alors.

> C'est vrai que je suis sous Debian Squeeze et que ma version n'est pas
> la plus récente (4-4), je vais essayer avec une autre, merci du
> conseil ;)

Je vais tuer le suspens, mais j'avais essayé avant de poster, et ça
fait la même optimisation que pour int.



Voilà qui répond parfaitement à mes interrogations!
Merci beaucoup :)
Antoine Leca
Le #23310151
Taurre écrivit :
si j'ai bien saisit la notion de pointeur restreint cela signifie,
dans le cas de la fonction "test", que l'objet sur lequel pointe la
variable "v" ne peut-être accéder que via cette dernière.



Dans ton exemple, v est à la fois une variable int de valeur 10, et un
pointeur restreint (vers la première.) Je ne suis pas sûr que cela
facilite la compréhension pour nous autres humains.


Donc, en toute logique, on peut supposer que l'objet pointé par la
variable "v" ne sera pas modifié lors de l'exécution de cette fonction.



Oui, puisque le code ne modifie pas le pointeur, et le propos de
restrict est d'affirmer que d'autres modifications n'ont pas lieu par
ailleurs.


la valeur de l'objet pointé par la variable "v" est chargé deux fois
dans le registre eax alors qu'elle ne devrait l'être qu'une seule
fois...



« devrait » : pas d'accord. La norme est limpide, restrict est une
opportunité d'optimisation, pas une obligation imposée au compilateur.


l'optimisation n'aura lieu que si un ou les deux autres
pointeurs sont également déclaré avec le qualificatif "restrict".
Quelqu'un pourrait-il m'expliquer pourquoi?



Il faudrait demander aux développeurs de GCC.


- la deuxième porte sur le même code, mais avec des variables de type
char. Dans cette hypothèse, même si les trois pointeurs sont déclarés
avec le qualificatif "restrict", aucune optimisation n'est effectuée



Là encore, c'est un sujet pour GCC. À mon sens, tu peux avoir le cas
théorique où les pointeurs pointent vers le même mot mémoire (un mot
pouvant être constitué de plusieurs bytes), et GCC veux peut-être éviter
les problèmes liés à des accès concurrents à un même mot.
Cela étant, ce peut être aussi un bête bogue dans le code de GCC...
Dans tous les cas, c'est totalement conforme à la norme, en vertu de ce
qui est rappelé ci-dessus: restrict n'est pas une obligation.


Antoine
Taurre
Le #23321961
On 26 avr, 10:45, Antoine Leca
Taurre écrivit :

> si j'ai bien saisit la notion de pointeur restreint cela signifie,
> dans le cas de la fonction "test", que l'objet sur lequel pointe la
> variable "v" ne peut-être accéder que via cette dernière.

Dans ton exemple, v est à la fois une variable int de valeur 10, et un
pointeur restreint (vers la première.) Je ne suis pas sûr que cela
facilite la compréhension pour nous autres humains.

> Donc, en toute logique, on peut supposer que l'objet pointé par la
> variable "v" ne sera pas modifié lors de l'exécution de cette fonct ion.

Oui, puisque le code ne modifie pas le pointeur, et le propos de
restrict est d'affirmer que d'autres modifications n'ont pas lieu par
ailleurs.

> la valeur de l'objet pointé par la variable "v" est chargé deux foi s
> dans le registre eax alors qu'elle ne devrait l'être qu'une seule
> fois...

« devrait » : pas d'accord. La norme est limpide, restrict est une
opportunité d'optimisation, pas une obligation imposée au compilateur .

> l'optimisation n'aura lieu que si un ou les deux autres
> pointeurs sont également déclaré avec le qualificatif "restrict".
> Quelqu'un pourrait-il m'expliquer pourquoi?

Il faudrait demander aux développeurs de GCC.

> - la deuxième porte sur le même code, mais avec des variables de ty pe
> char. Dans cette hypothèse, même si les trois pointeurs sont décl arés
> avec le qualificatif "restrict", aucune optimisation n'est effectuée

Là encore, c'est un sujet pour GCC. À mon sens, tu peux avoir le cas
théorique où les pointeurs pointent vers le même mot mémoire (un mot
pouvant être constitué de plusieurs bytes), et GCC veux peut-être éviter
les problèmes liés à des accès concurrents à un même mot.
Cela étant, ce peut être aussi un bête bogue dans le code de GCC...
Dans tous les cas, c'est totalement conforme à la norme, en vertu de ce
qui est rappelé ci-dessus: restrict n'est pas une obligation.

Antoine

« devrait » : pas d'accord. La norme est limpide, restrict est une
opportunité d'optimisation, pas une obligation imposée au compilateur .



Oui, je me suis mal exprimé, ce que je voulais dire c'est que suivant
cette logique on peut supposé avoir un résultat en spécifiant
seulement "v" comme pointeur restreint et non en devant spécifier deux
ou tous les pointeurs comme restreint.

Il faudrait demander aux développeurs de GCC.



Merci du conseil :)
Taurre
Le #23322221
Je pense que je viens de trouver la réponse à mes questions en
relisant la Norme C99 :)
En effet, si je prends ce paragraphe de la Norme C99 (6.7.3.1 §4 p
110):

During each execution of B, let L be any lvalue that has &L based on
P. If L is used to
access the value of the object X that it designates, and X is also
modified (by any means),
then the following requirements apply: T shall not be const-qualified.
Every other lvalue
used to access the value of X shall also have its address based on P.
Every access that
modifies X shall be considered also to modify P, for the purposes of
this subclause. If P
is assigned the value of a pointer expression E that is based on
another restricted pointer
object P2, associated with block B2, then either the execution of B2
shall begin before
the execution of B, or the execution of B2 shall end prior to the
assignment. If these
requirements are not met, then the behavior is undefined.

et plus précisément cette phrase:

Every other lvalue used to access the value of X shall also have its
address based on P

elle suppose donc que n'importe qu'elle lvalue utilisée pour accéder à
l'objet pointé par le pointeur restreint soit dérivé de ce dernier.
Oui, mais si on l'a prend a contrario cela signifie aussi qu'un objet
pointé par un pointeur non restreint ne doit pas forcément être acc édé
via des lvalues dérivées de ce dernier. Autrement dit, il est possible
qu'un pointeur restreint accède à un objet pointé par un pointeur non
restreint et qu'il y aie donc de l'aliasing. Aussi, pour reprendre mon
code, les pointeurs "a", "b" et "v" doivent tous être qualifiés de
restreints pour que tout risque d'aliasing soit écarté.

Maintenant, à la question pourquoi cela fonctionne si seulement "a" et
"v" sont déclarés comme étant des pointeurs restreints? Et bien parce
que l'ordre d'assignation le permet. En effet, l'expression *a = *v
garantit que l'objet pointé par "v" n'est pas modifié puisque "a" et
"v" sont des pointeurs restreints. La valeur de l'objet n'a donc pas
besoin d'être rechargée pour l'affectation suivante :)
Antoine Leca
Le #23330431
Taurre écrivit :

En supposant (axiome):
elle suppose donc que n'importe qu'elle lvalue utilisée pour accéder à
l'objet pointé par le pointeur restreint soit dérivé de ce dernier.



On a
Oui, mais si on l'a prend a contrario cela signifie aussi qu'un objet
pointé par un pointeur non restreint ne doit pas forcément être accédé
via des lvalues dérivées de ce dernier.



Mais j'y lis aussi
: cela signifie aussi qu'un objet
: pointé par un pointeur non restreint ne peut pas jamais être accédé
: via des lvalues dérivées d'un pointeur restreint.

(Les deux ne sont pas incompatibles.)

En fait je le vois comme une partition de l'espace des objets en n+1
ensembles, où n est le nombre de pointeurs restreints. Dans la dernière
partie, les objets peuvent être atteints par différents pointeurs
(alias), mais ne peuvent être atteints par l'un quelconque des n
pointeurs restreints ou une de leurs dérivations.


Autrement dit, il est possible
qu'un pointeur restreint accède à un objet pointé par un pointeur non
restreint et qu'il y aie donc de l'aliasing.



Non. Ce serait une violation de la règle comme quoi les objets pointés
par les pointeurs restreints ne peuvent être modifiés par ailleurs, et
cela invaliderait complètement la possibilité d'optimisation. Le
raisonnement est donc incorrect (ce qui peut provenir d'une mauvaise
rédaction de la norme C99).


Antoine
Taurre
Le #23332831
On 3 mai, 10:18, Antoine Leca
Taurre écrivit :

En supposant (axiome):

> elle suppose donc que n'importe qu'elle lvalue utilisée pour accéde r à
> l'objet pointé par le pointeur restreint soit dérivé de ce dernie r.

On a

> Oui, mais si on l'a prend a contrario cela signifie aussi qu'un objet
> pointé par un pointeur non restreint ne doit pas forcément être a ccédé
> via des lvalues dérivées de ce dernier.

Mais j'y lis aussi
:                                       cela signifie aussi qu'un objet
: pointé par un pointeur non restreint ne peut pas jamais être accé dé
: via des lvalues dérivées d'un pointeur restreint.

(Les deux ne sont pas incompatibles.)

En fait je le vois comme une partition de l'espace des objets en n+1
ensembles, où n est le nombre de pointeurs restreints. Dans la derniè re
partie, les objets peuvent être atteints par différents pointeurs
(alias), mais ne peuvent être atteints par l'un quelconque des n
pointeurs restreints ou une de leurs dérivations.

> Autrement dit, il est possible
> qu'un pointeur restreint accède à un objet pointé par un pointeur non
> restreint et qu'il y aie donc de l'aliasing.

Non. Ce serait une violation de la règle comme quoi les objets pointé s
par les pointeurs restreints ne peuvent être modifiés par ailleurs, e t
cela invaliderait complètement la possibilité d'optimisation. Le
raisonnement est donc incorrect (ce qui peut provenir d'une mauvaise
rédaction de la norme C99).

Antoine



Je me rends en effet compte que mon raisonnement ne tient pas la route
et se contredit tout seul :-°

En fait je le vois comme une partition de l'espace des objets en n+1
ensembles, où n est le nombre de pointeurs restreints. Dans la derniè re
partie, les objets peuvent être atteints par différents pointeurs
(alias), mais ne peuvent être atteints par l'un quelconque des n
pointeurs restreints ou une de leurs dérivations.



C'est aussi l'image que j'ai en tête, mais le problème c'est que les
exemples donné par la Norme ne semble pas tout à fait la suivre. En
effet, si je reprends mon exemple du début où seul le pointeur "v" est
qualifié de restreint, dans ce cas on se retrouve avec deux
partitions: une pour les objets accédés par "v" et une pour les autres
(si j'ai bien saisit?). En suivant cette logique, on pourrait donc
supposer que l'optimisation aura lieu, cependant elle ne se produira
que si tous les pointeurs sont qualifiés de restreint... La même
analyse peut être appliquée au prototype des fonctions standard:
pourquoi qualifié les deux pointeurs utilisé par la fonction memcpy de
restreint alors que logiquement un seul suffit?

Je trouve la définition de la Norme franchement floue, c'est limite si
elle ne se contredit pas dans son exemple numero deux (6.7.3.1 § 8 p
111) quand elle dit:

EXAMPLE 2 The function parameter declarations in the following example


void f(int n, int * restrict p, int * restrict q)
{
while (n-- > 0)
*p++ = *q++;
}

assert that, during each execution of the function, if an object is acces sed through
one of the pointer parameters, then it is not also accessed through the o ther.



alors qu'elle dit plus haut (6.7.3 § 7 p 109):

An object that is accessed through a restrict-qualified pointer has a spe cial association
with that pointer. This association, defined in 6.7.3.1 below, requires t hat all accesses to
that object use, directly or indirectly, the value of that particular poi nter.



Franchement, je commence à me demander si les concepteurs de GCC ne se
sont pas simplement dit que la définition était tellement alambiquée
qu'ils allaient appliquer l'optimisation seulement si tous les
pointeurs sont qualifiés de restreints, histoire d'être sûr --'

Enfin, si quelqu'un pouvait m'éclairer dans ce texte obscure :)
Antoine Leca
Le #23333661
Taurre écrivit :
En fait je le vois comme une partition de l'espace des objets en n+1
ensembles, où n est le nombre de pointeurs restreints. Dans la dernière
partie, les objets peuvent être atteints par différents pointeurs
(alias), mais ne peuvent être atteints par l'un quelconque des n
pointeurs restreints ou une de leurs dérivations.



C'est aussi l'image que j'ai en tête, mais le problème c'est que les
exemples donné par la Norme ne semble pas tout à fait la suivre. En
effet, si je reprends mon exemple du début où seul le pointeur "v" est
qualifié de restreint, dans ce cas on se retrouve avec deux
partitions: une pour les objets accédés par "v" et une pour les autres
(si j'ai bien saisit?).



Oui.

En suivant cette logique, on pourrait donc
supposer que l'optimisation aura lieu,



Non. C'est tout l'onjet de mon premier message : le fait est que l'on
ait une opportunité d'optimisation ne signifie pas obligatoirement que
le compilateur va effectivement réaliser la dite optimisation.

cependant elle ne se produira que si tous les pointeurs sont
qualifiés de restreint...



Euh, là c'est ton analyse du comportement de GCC. GCC est un gros
programme, je n'ai pas les possibilités intellectuelles pour déterminer
son comportement (qui par ailleurs varie avec les versions).


La même
analyse peut être appliquée au prototype des fonctions standard:
pourquoi qualifié les deux pointeurs utilisé par la fonction memcpy de
restreint alors que logiquement un seul suffit?



Parce que l'implémentation des fonctions de la bibliothèque standard
peut utiliser à sa guise d'autres objets (qui seront donc dans la
dernière partie). Si un seul des deux pointeurs était restreint, l'autre
serait dans la dernière partie aussi, et cela empêcherait des
opportunités d'optimisation ; la norme ne peut pas arbitrairement faire
ce genre de choses, surtout quand il est si simple de faire bien.

De plus, la norme est une sorte d'exemple à suivre dans la manière de
déclarer les interfaces, et là aussi il est plus logique et plus clair
de déclarer tous les pointeurs comme restreints.

Par ailleurs, je soupçonne que le fait de déclarer des paramètres comme
restreint doive permettre à des analyseurs de détecter des cas de
confusion de variables, ou au moins de soulever des questions sur des
constructions litigieuses, qui auraient avantage à être réécrites de
manière plus claire.


Je trouve la définition de la Norme franchement floue,



Disons que le style de cette partie tranche assez nettement avec le
reste ; c'est dû en partie au fait que les rédacteurs ne sont pas les mêmes.


c'est limite si elle ne se contredit pas dans son exemple numero deux
(6.7.3.1 § 8 p 111) quand elle dit:

EXAMPLE 2 The function parameter declarations in the following example


void f(int n, int * restrict p, int * restrict q)


<snip>
assert that, during each execution of the function, if an object is accessed through
one of the pointer parameters, then it is not also accessed through the other.



alors qu'elle dit plus haut (6.7.3 § 7 p 109):

An object that is accessed through a restrict-qualified pointer has a special association
with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to
that object use, directly or indirectly, the value of that particular pointer.





Désolé, je ne vois aucune contradiction.


Antoine
Publicité
Poster une réponse
Anonyme