Comportements indéfinis ?

Bonjour,

Dans le cadre de l'étude du code de programmes de SPEC (www.spec.org) [1],
j'étudie le benchmark lié au programme gzip. Le programme est modifié pour
ne pas réellement donner un fichier compressé en sortie, mais juste le
faire directement en mémoire (compression/décompression). La fonction que
j'étudie est une recherche dans un dictionnaire (avec une sorte de table
de hachage/liste chaînée bizarre dont peut parcourir les éléments
d'après un certain masque).

Le code étant en GPL, je me permets de le recopier ici, en enlevant les
parties dont on ne se sert pas :

int longest_match(cur_match)
IPos cur_match; /* current match */
{
unsigned chain_length = max_chain_length; /* max hash chain length
*/
register uch *scan = window + strstart; /* current string */
register uch *match; /* matched string */
register int len; /* length of current match
*/
int best_len = prev_length; /* best match length so
far */
IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST :
NIL;
/* Stop when cur_match becomes <= limit. To simplify the code,
* we prevent matches with the string of window index 0.
*/
register uch *strend = window + strstart + MAX_MATCH;
register uch scan_end1 = scan[best_len-1];
register uch scan_end = scan[best_len];
/* Do not waste too much time if we already have a good match: */
if (prev_length >= good_match) {
chain_length >>= 2;
}
do {
Assert(cur_match < strstart, "no future");
match = window + cur_match;

/* Skip to next match if the match length cannot increase
* or if the match length is less than 2:
*/

if (match[best_len] != scan_end ||
match[best_len-1] != scan_end1 ||
*match != *scan ||
*++match != scan[1]) continue;

/* The check at best_len-1 can be removed because it will be made
* again later. (This heuristic is not always a win.)
* It is not necessary to compare scan[2] and match[2] since they
* are always equal when the other bytes match, given that
* the hash keys are equal and that HASH_BITS >= 8.
*/
scan += 2, match++;

/* We check for insufficient lookahead only every 8th comparison;
* the 256th check will be made at strstart+258.
*/

do {
} while (*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
scan < strend);

len = MAX_MATCH - (int)(strend - scan);
scan = strend - MAX_MATCH;

if (len > best_len) {
match_start = cur_match;
best_len = len;
if (len >= nice_match) break;
scan_end1 = scan[best_len-1];
scan_end = scan[best_len];
}
} while ((cur_match = prev[cur_match & WMASK]) > limit
&& --chain_length != 0);

return best_len;
}

Ce qui me pose problème dans ce code :

J'ai effectué quelques modifications pour observer la différence de
génération de code (j'utilise icc). Ainsi, le do{} while(...) interne
devient :

do {
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
++scan; ++match; if (*scan != *match) break;
} while (scan < strend);

Donc même sémantique, mais code différent.

Jusqu'ici, tout va bien.

Là où ça va beaucoup moins bien, c'est lorsque je veux extraire le code de
la condition du while extérieur :

cur_match = prev[cur_match & WMASK];
} while (cur_match > limit && --chain_length != 0);

Là, le programme me donne une sortie différente. Je ne parle même pas du
cas où j'avais modifié le code comme suit :

cur_match = prev[cur_match & WMASK];
if (cur_match <= limit) break;
--chain_length;
} while (chain_length !!= 0);

Dans ce cas, le programme se bloque, tout simplement.

Mis à part un code plutôt laid à lire, je ne vois pas vraiment ce qui
provoque ces changements de comportement du programme. Y aurait-il des cas
de comportements indéfinis que je n'aurais pas vus ?

Merci de m'avoir lu jusqu'au bout. :-)

[1] Les SPEC sont une série de programmes destinés à mesurer les
performances au niveau CPU et mémoire cache d'une marchine donnée.
Evidemment, les fabricants de compilateurs s'en servent pour pouvoir dire
"mon compilo a une plus grosse optimisation que le tien".

--
"Je deteste les ordinateurs : ils font toujours ce que je dis, jamais ce
que je veux !"
"The obvious mathematical breakthrough would be development of an easy
way to factor large prime numbers." (Bill Gates, The Road Ahead)