OVH Cloud OVH Cloud

Decalages d'un nombre de bits pouvant etre >= a la taille du type

134 réponses
Avatar
Vincent Lefevre
J'ai besoin de faire un décalage vers la droite sur un type entier
(disons non signé) générique (i.e. défini par typedef) d'un certain
nombre constant de bits. Le problème est que ce nombre de bits peut
être supérieur ou égal à la taille du type en question. Une idée
sur la façon de faire ça efficacement sans obtenir de comportement
indéfini et sans passer par un outil du style "configure"?

--
Vincent Lefèvre <vincent@vinc17.org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA

10 réponses

Avatar
Vincent Lefevre
Dans l'article <ckjg87$37n$,
Antoine Leca écrit:

En 20041008171943$, Vincent Lefevre va escriure:
Par exemple, si on considère k || 1 / 0 (j'ai pris volontairement
quelque chose qui n'était pas constant devant le ||),


Soit [k] n'est pas constant, et on est hors du cadre.


Pourquoi hors du cadre?


Parce que s'il n'est pas constant (en réalité, constament nul ou non nul),
l'expression n'est pas une expression constante (!), et rien du 6.6 ne peut
s'appliquer.


Je ne suis pas du tout d'accord. Même si k n'est pas constant, dans
k || 1 / 0, l'expression 1 / 0 reste une expression constante (je
rappelle que j'avais appliqué le 6.6 à 1 / 0).

Une expression constante est un lexème non terminal: autrement dit, c'est
utile là où c'est attendu, mais c'est une notion inutile ailleurs. Par
exemple, on se moque royalement de savoir que 10 est constant dans
int i = mon_strtoi(input, NULL, 10);


Je ne vois pas bien ce que tu veux dire.

Pour reprendre un exemple avec un programme complet (ça sera peut-être
plus clair):

int main(int argc, char **argv)
{
return argc > 1 ? 0 : 1 / 0;
}

Le 1 / 0 est bien une expression constante, non?

L'implémentation peut donc appliquer le 6.6 dessus et évaluer le 1 / 0
pendant la phase de traduction, non?

Dans ce cas, on a bien un comportement indéfini pendant la phase de
traduction, non? ... auquel cas l'implémentation est libre de faire
ce qu'elle veut, et que si du code est généré, il peut faire n'importe
quoi.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA




Avatar
Vincent Lefevre
Dans l'article <ckjgid$4tn$,
Antoine Leca écrit:

En 20041008173027$, Vincent Lefevre va escriure:
Donc tu dis que dans le bout de programme suivant,


Les appels de fonction sont interdits dans l'évaluation des expressions
constantes, et je ne sais pas imaginer ce que cela devrait être s'ils le
fussent.


Dans mon exemple

int test(void)
{
return 1.1 + 2.0;
}

je ne fais pas d'appel de fonction dans l'expression constante
"1.1 + 2.0".

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA


Avatar
Gabriel Dos Reis
Vincent Lefevre <vincent+ writes:

| Je ne vois pas bien ce que tu veux dire.

Ce n'est pas grave.

-- Gaby
Avatar
Gabriel Dos Reis
Vincent Lefevre <vincent+ writes:

| Dans l'article ,
| Gabriel Dos Reis écrit:
|
| > Vincent Lefevre <vincent+ writes:
|
| > | Dans l'article ,
| > | Gabriel Dos Reis écrit:
| > |
| > | > Qu'appelles-tu optimisation lorsques tu fais abstraction de la
| > | > sémantique d'un programme ?
| > |
| > | Je ne fais pas abstraction de la sémantique d'un programme.
|
| > Groumph. Remets le contexte que tu as enlevé et tu verras.
|
| Je n'ai pas enlevé de contexte.

Compare le contexte de

Message-ID:

avec celui de

Message-ID: <20041009210559$

|
| > | Le mot
| > | "optimisation" a seulement le sens donné par le compilateur utilisé.
| > | Voici un exemple (vu dans la réalité).
| > |
| > | int main(void)
| > | {
| > | int i;
| > | return i;
| > | }
| > |
| > | Il y a bien comportement indéfini. D'accord?
|
| > Oui.
|
| > | On considère un certain compilateur. Compilé sans optimisation,
|
| > Qu'est-ce que tu appelles « optimisation » ?
|
| La réponse est au-dessus.

?

| > | le programme renvoie toujours 0, car i est initialisé à 0 par
| > | le compilo. Compilé avec optimisation, le programme renvoie une
| > | valeur différente de 0.
|
| > Tu tournes en rond. T'as pas le vertige ?
|
| Pourquoi dis-tu que je tourne en rond?

Parce que c'est le cas.

-- Gaby
Avatar
Antoine Leca
En 20041013215122$, Vincent Lefevre va escriure:
Pour reprendre un exemple avec un programme complet (ça sera peut-être
plus clair):

int main(int argc, char **argv)
{
return argc > 1 ? 0 : 1 / 0;
}

Le 1 / 0 est bien une expression constante, non?


Non. Parce que la grammaire n'attend pas d'expression constante ici, et rien
(du point de vue de la grammaire) ne différencie cette expression d'une
autre plus compliquée où on comparerait par rapport à 0.


L'implémentation peut donc appliquer le 6.6 dessus et évaluer le 1 / 0
pendant la phase de traduction, non?


Si l'implémentation évalue réellement 1 / 0 dans une expression constante
(attendue comme telle) pendant la phase de traduction, elle doit émettre un
diagnostic pour violation de contrainte (6.6p4, résultat hors domaine).

Autrement dit, l'implémentation doit _garantir_ que les expressions
constantes sont définies.

Maintenant, si tu écris un programme qui viole une contrainte, et qu'un
exécutable est généré, le comportement observé à l'exécution du dit
exécutable sort sérieusement du domaine intéressant de la norme, ÀMHA.


Antoine

Avatar
Vincent Lefevre
Dans l'article <ckld3l$c15$,
Antoine Leca écrit:

En 20041013215122$, Vincent Lefevre va escriure:
Pour reprendre un exemple avec un programme complet (ça sera peut-être
plus clair):

int main(int argc, char **argv)
{
return argc > 1 ? 0 : 1 / 0;
}

Le 1 / 0 est bien une expression constante, non?


Non. Parce que la grammaire n'attend pas d'expression constante ici,
et rien (du point de vue de la grammaire) ne différencie cette
expression d'une autre plus compliquée où on comparerait par rapport
à 0.


Mais c'est pareil pour le cas suivant, non?

static void tstall (void)
{
double x;
x = 1.1 + 16.0;
printf ("%.20gn", x);
}

J'ai toujours vu les compilateurs évaluer des choses constantes à
la compilation, même si la grammaire n'attend pas une expression
constante.

Le programme ci-dessous compilé avec gcc -stdcÉ9 -O2 -lm affiche
sur ma machine:

__STDC_IEC_559__ defined:
The implementation shall conform to the IEEE-754 standard.
FLT_EVAL_METHOD is 0 (see ISO/IEC 9899, 5.2.4.2.2#7).
Rounding to nearest
17.100000000000001421
Rounding toward 0
17.100000000000001421
Rounding to -oo
17.100000000000001421
Rounding to +oo
17.100000000000001421

Bug de gcc?

Si je remplace la fonction tstall par

static void tstall (void)
{
double x, y;
x = 1.1;
y = 16.0;
printf ("%.20gn", x + y);
}

j'obtiens:

__STDC_IEC_559__ defined:
The implementation shall conform to the IEEE-754 standard.
FLT_EVAL_METHOD is 0 (see ISO/IEC 9899, 5.2.4.2.2#7).
Rounding to nearest
17.100000000000001421
Rounding toward 0
17.099999999999997868
Rounding to -oo
17.099999999999997868
Rounding to +oo
17.100000000000001421

------------------------------------------------------------------

#include <stdio.h>
#include <float.h>
#include <math.h>
#include <fenv.h>

static void tstall (void)
{
double x;
x = 1.1 + 16.0;
printf ("%.20gn", x);
}

int main (void)
{
#if __STDC_VERSION__ >= 199901 && defined(__STDC_IEC_559__)
printf ("__STDC_IEC_559__ defined:n"
"The implementation shall conform to the IEEE-754 standard.n"
"FLT_EVAL_METHOD is %d (see ISO/IEC 9899, 5.2.4.2.2#7).n",
(int) FLT_EVAL_METHOD);
#endif

#ifdef FE_TONEAREST
printf ("Rounding to nearestn");
if (fesetround (FE_TONEAREST))
printf ("Errorn");
else
tstall ();
#endif

#ifdef FE_TOWARDZERO
printf ("Rounding toward 0n");
if (fesetround (FE_TOWARDZERO))
printf ("Errorn");
else
tstall ();
#endif

#ifdef FE_DOWNWARD
printf ("Rounding to -oon");
if (fesetround (FE_DOWNWARD))
printf ("Errorn");
else
tstall ();
#endif

#ifdef FE_UPWARD
printf ("Rounding to +oon");
if (fesetround (FE_UPWARD))
printf ("Errorn");
else
tstall ();
#endif

return 0;
}

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA


Avatar
Antoine Leca
En 20041015190901$, Vincent Lefevre va escriure:
J'ai toujours vu les compilateurs évaluer des choses constantes à
la compilation, même si la grammaire n'attend pas une expression
constante.


La raison à cela est que l'évaluation à la compilation des expressions
constantes est une optimisation (payante et sans grand risque, sauf cas
particuliers comme les compilateurs croisés) qui est peu difficile à
implanter puisque la grammaire oblige de toute manière le compilateur à
savoir réduire une expression constante, dans les cas où on attends une
constante (taille de tableau, initialisation, etc.)


Mais c'est pareil pour le cas suivant, non?

static void tstall (void)
{
double x;
x = 1.1 + 16.0;
printf ("%.20gn", x);
}

Le programme ci-dessous compilé avec gcc -stdcÉ9 -O2 -lm affiche
sur ma machine:

__STDC_IEC_559__ defined:
The implementation shall conform to the IEEE-754 standard.
FLT_EVAL_METHOD is 0 (see ISO/IEC 9899, 5.2.4.2.2#7).
Rounding to nearest
17.100000000000001421
Rounding toward 0
17.100000000000001421
Rounding to -oo
17.100000000000001421
Rounding to +oo
17.100000000000001421

Si je remplace la fonction tstall par
double x, y;
x = 1.1; y = 16.0;
printf ("%.20gn", x + y);

j'obtiens:
[couic]

Rounding to nearest
17.100000000000001421
Rounding toward 0
17.099999999999997868


[re-couic]

Bug de gcc?



ÀMHA on sort de la discussion précédente : de tous temps les flottants ont
été une bête à part.

En supposant que tu as utilisé FP_CONTRACT OFF...
Je dirais que oui. Je pense que c'est un sujet que tu devrais ouvrir sur la
liste de gcc, et attendre l'avis de Joseph Myers...

Pour moi, le fait que gcc ignore FP_CONTRACT OFF devrait l'obliger à ne
jamais faire de contraction (ce qu'il fait manifestement ici). Mais la norme
est assez floue sur le sujet, il y a bien une recommendation (F.6) qui va
dans ce sens, mais comme c'est une recommendation on peut également s'en
servir pour dire que le comportement inverse est conforme !

De plus, je ne serais pas surpris d'apprendre que la plupart des
compilateurs ont le même comportement que gcc...

Cependant, une lecture superficielle de la norme ne m'a pas permis de
trouver de licence pour faire une telle simplification à la compilation. Et
au contraire m'a enseigné les moyens de forcer un comportement prévisible
(cf. supra).


Antoine

Avatar
Vincent Lefevre
Dans l'article <ckvupk$8hp$,
Antoine Leca écrit:

En 20041015190901$, Vincent Lefevre va escriure:
J'ai toujours vu les compilateurs évaluer des choses constantes à
la compilation, même si la grammaire n'attend pas une expression
constante.


La raison à cela est que l'évaluation à la compilation des expressions
constantes est une optimisation (payante et sans grand risque, sauf cas
particuliers comme les compilateurs croisés) qui est peu difficile à
implanter puisque la grammaire oblige de toute manière le compilateur à
savoir réduire une expression constante, dans les cas où on attends une
constante (taille de tableau, initialisation, etc.)


Sauf qu'une optimisation ne devrait pas rendre quelque chose non
conforme à la norme. J'avais pris cette contraction comme une
application du 6.6. D'ailleurs on peut voir dans le K&R: "Une
/expression constante/ est une expression qui ne comporte que des
constantes." (sans faire référence à ce qu'attend la grammaire).
Je crois que ce bouquin est définitivement à jeter.

ÀMHA on sort de la discussion précédente : de tous temps les
flottants ont été une bête à part.

En supposant que tu as utilisé FP_CONTRACT OFF...


De toute façon, comme tu le dis plus loin, c'est ignoré:

tst.c:6: warning: ignoring #pragma STDC FP_CONTRACT

Je dirais que oui. Je pense que c'est un sujet que tu devrais ouvrir
sur la liste de gcc, et attendre l'avis de Joseph Myers...


... en espérant qu'ils veuillent bien corriger. J'avais vu dans
les archives une discussion à propos d'un autre bug de gcc et les
flottants (les résultats en précision étendue ne sont pas convertis
en double précision lorsqu'on fait un cast en double ou qu'on fait
une affectation), et ça m'a donné l'impression qu'ils ne voulaient
rien changer. :(

Pour moi, le fait que gcc ignore FP_CONTRACT OFF devrait l'obliger à
ne jamais faire de contraction (ce qu'il fait manifestement ici).
Mais la norme est assez floue sur le sujet, il y a bien une
recommendation (F.6) qui va dans ce sens, mais comme c'est une
recommendation on peut également s'en servir pour dire que le
comportement inverse est conforme !


Est-ce que la norme autorise les implémentations à ne pas reconnaître
les pragmas qu'elle définit? Si ce n'est pas autorisé, alors on n'a
même pas besoin de cette recommandation.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA


Avatar
Antoine Leca
En 20041019002004$, Vincent Lefevre va escriure:
Dans l'article <ckvupk$8hp$,
Antoine Leca écrit:

Sauf qu'une optimisation ne devrait pas rendre quelque chose non
conforme à la norme.


Tout-à-fait d'accord, c'est d'ailleurs la position de Gaby depuis le début!

En supposant que tu as utilisé FP_CONTRACT OFF...


De toute façon, comme tu le dis plus loin, c'est ignoré:


Je sais, c'est pour cela qu'il y a les points de suspension.
Cela étant, si ton programme n'a pas ce pragma, tu ne peux (selon la norme)
rien exiger, puisque l'implémentation a le droit de faire une contraction
dans ce cas-là (c'est-à-dire, sauf si tu imposes explicitement le respect
des contraintes d'arrondi en forçant à OFF).


Je dirais que oui. Je pense que c'est un sujet que tu devrais ouvrir
sur la liste de gcc, et attendre l'avis de Joseph Myers...


... en espérant qu'ils veuillent bien corriger.


Avant de corriger (qui nécessite certainement du boulot, et qui risque de
pénaliser les performances), il faut les convaincre que c'est non conforme.
En l'occurence, quand je lis

/Whether and how floating expressions are contracted when not
disallowed by the FP_CONTRACT pragma (C99 6.5)./

Expressions are currently only contracted if
-funsafe-math-optimizations or -ffast-math are used.
This is subject to change.

Je me dis (dernière phrase) que tout espoir n'est pas perdu, et que
peut-être ils ont besoin d'une impulsion! C'est sûr que ce qu'ils attendent
réellement, c'est une réalisation. Mais si un autre compilateur (Intel?)
implémente ce machin, et que certains programmes (de preuve, par exemple)
s'en servent, ils seront un peu obligé de faire un effort...

Le vrai problème, c'est qu'aujourd'hui ils font dans le facile (en se
mettant la tête dans le sable).

Si tu veux faire les choses vraiment bien, il faut un évaluateur
d'expressions flottantes constantes capable de reconnaître si l'arrondi (ou
autre chose) peut avoir un effet. Avec la condition que cet évaluateur soit
relativement indépendant de la plateforme (contrainte spécifique de GCC).
Inutile de dire que c'est beaucoup de travail, et que cela n'en vaut
peut-être pas la peine si on considère le potentiel disponible pour faire
des développements.

Mais si tu veux seulement être en accord avec la norme, une manière facile
c'est de ne jamais faire de contraction en mode OFF, même quand elles sont
inoffensives: par exemple, si tu écris 1.0 + 1.0 + 1.0 + 1.0, le compilo
devrait pouvoir toujours contracter, mais il est libre de ne pas le faire!
En faisant cela, les performances vont chuter (probablement pas de beaucoup,
mais l'impact psychologique sera important); cela pourrait amener la plupart
des programmeurs à éviter à tout prix de mettre FP_CONTRACT OFF (ce qui ÀMHA
est la position de base de ceux qui ont mis cela dans la norme). C'est
probablement un bon compromis à proposer aux gens de GCC.


J'avais vu dans les archives une discussion à propos d'un autre bug
de gcc et les flottants


Regarde bien le code d'aujourd'hui; je ne suis pas sûr (et je n'ai pas le
temps de fouiller), mais il me semble que pour un problème de ce genre
(peut-être le même), il y eu d'abord une discussion où le côté ne rien faire
l'a emporté, et un an plus tard un autre est venu, a tapé plus fort sur la
table ("ceci n'est pas conforme") et le compilo a évolué (au point
qu'aujourd'hui c'est difficile de choisir correctement les options de
compilation à utiliser)


Est-ce que la norme autorise les implémentations à ne pas reconnaître
les pragmas qu'elle définit?


Non (d'où l'avertissement, ÀMHA). Mais tu sais bien que GCC ne prétend pas
non plus être totalement conforme à C99, c'est seulement un objectif.

En plus, FP_CONTRACT fait partie formellement de <math.h>, donc d'une
implémentation hébergée; hors GCC est nominalement une implémentation
indépendante, et la bibliothèque mathématique est "ailleurs" (cela étant, si
tu te pointes avec ce rapport de bogue chez glibc, je vois d'ici le
résultat! ;-))) )


Antoine


Avatar
Vincent Lefevre
Dans l'article <cl2jai$mr6$,
Antoine Leca écrit:

Avant de corriger (qui nécessite certainement du boulot, et qui risque de
pénaliser les performances), il faut les convaincre que c'est non conforme.
En l'occurence, quand je lis

/Whether and how floating expressions are contracted when not
disallowed by the FP_CONTRACT pragma (C99 6.5)./

Expressions are currently only contracted if
-funsafe-math-optimizations or -ffast-math are used.
This is subject to change.


Cela voudrait donc dire que gcc 4.0 se comporte correctement par défaut?
(Le "only" est bizarrement placé, je ne suis pas sûr de bien comprendre.)

Mais si tu veux seulement être en accord avec la norme, une manière
facile c'est de ne jamais faire de contraction en mode OFF, même
quand elles sont inoffensives: par exemple, si tu écris 1.0 + 1.0 +
1.0 + 1.0, le compilo devrait pouvoir toujours contracter, mais il
est libre de ne pas le faire! En faisant cela, les performances vont
chuter (probablement pas de beaucoup, mais l'impact psychologique
sera important); cela pourrait amener la plupart des programmeurs à
éviter à tout prix de mettre FP_CONTRACT OFF (ce qui ÀMHA est la
position de base de ceux qui ont mis cela dans la norme). C'est
probablement un bon compromis à proposer aux gens de GCC.


Les programmeurs qui ont besoin d'un contrôle sur la contraction des
expressions flottantes doivent de toute façon savoir ce qu'ils font;
ils préfèrent certainement une baisse de performance (probablement
pas énorme) qu'un comportement incorrect. D'autre part, ils peuvent
toujours jouer le rôle de l'optimiseur en switchant entre ON et OFF
suivant les cas; ce n'est pas l'idéal, mais c'est déjà ça.

J'avais vu dans les archives une discussion à propos d'un autre
bug de gcc et les flottants


Regarde bien le code d'aujourd'hui; [...]


Ah oui, ça a été corrigé dans la version 3.4!

En plus, FP_CONTRACT fait partie formellement de <math.h>, donc
d'une implémentation hébergée; hors GCC est nominalement une
implémentation indépendante, et la bibliothèque mathématique est
"ailleurs" (cela étant, si tu te pointes avec ce rapport de bogue
chez glibc, je vois d'ici le résultat! ;-))) )


LOL! (Euh... je n'avais pas déjà fait quelque chose de ce genre? Ah,
c'était <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug!0598>,
un problème de dénormalisé sur Alpha, finalement un bug de GCC et
non pas de la glibc.)

De toute façon, même si les bibliothèques sont ailleurs, GCC a
des liens très forts avec tout ce qui concerne les implémentations
hébergées.

--
Vincent Lefèvre - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA